This web page consists of a series of content units linked to interactive learning games formed from java applets. Our approach to interactive learning is described in the section on Active Learning Philosophy. The games are accessed from the "Available Tools:" list in the lower frame. Documentation for the games and their associated interactive learning units may be accessed by browsing of the following HTML pages.
The MyLayout Applet says:
For example, there is Logic Minimization game, in which the user tries to discover a minimum sum of products representation of a Boolean function. This is a theoretically difficult problem, and is technologically significant in a Logic Synthesis Context. Thus, it is closely related to the problem of designing a microchip to have minimum size. In its present form, the K-map game is played in a 6-dimensional boolean space, projected onto the plane. To play the game, click on K-map game.
Serious educational use of Java requires professional programming skills that few faculty have. N-ABLE will therefore aim to include a suite of CAD (Computer-Aided Design) tools that enable faculty to create new N-ABLE components with little or no programming. This will enable undergraduates throughout the State to get individual tutoring at extremely low cost from software that is tireless, responsive to their needs, and available whenever and wherever the Web is accessible. N-ABLE thus leverages existing hardware to enhance undergraduate education. Our work has 2 major goals.
Goal 1: To develop a prototype system that 1) enables undergraduates to have game-like interaction with animated concepts in myriad subject areas, 2) monitors these interactions, and 3) offers instruction to while students "play the games."
Goal 2: To develop CAD tools that enable faculty to rapidly develop new uses of N-ABLE with little or no programming--including tools that partially automate creation of animated concepts, agents and multimedia information from sources such as books and course notes. Goal 2 makes Goal 1 generically applicable.
The proposed work extends our current summer pilot study, funded with the help of Mark Dubin and Tim Neese by the Instructional Technology Resource Center at CU. In its first 6 weeks this study has already resulted in 6 working Java applets of animated concepts and a very preliminary form of the N-ABLE interface Boulder (visit http://dufay.colorado.edu/~mooni/N_ABLE/N_ABLE.html, which is this file).
Ideally, a noted Zen Koan should apply: "when the student is ready, the teacher will appear." Unfortunately, most undergraduates reach the teachable moment not in the classroom, but in the PC lab or at home, at 3am, the night before the homework is due--when the only available help comes from a cold and unresponsive textbook. No teacher is there to look over their shoulders, identify and diagnose the difficulties they are experiencing, then present and explain the principles for overcoming them.
We derive our notions of action-based learning both from our experiences as teachers and from Schoen's theory of reflection-in-action (Donald A. Schoen, The Reflective Practitioner: How Professionals Think in Action, Basic Books, New York, 1983). This theory describes effective problem-solving as a continual alternation between action and reflection. Action proceeds intuitively until it produces unexpected/undesired results. This breakdown of expectations leads to reflection aimed at "repairing" the breakdown. This can also be viewed in terms of Hegel's dialectic synthesis, in which new knowledge (synthesis) evolves only when thesis (that is the problem solver's expectation) meets antithesis (the breakdown in expectation).
Instruction works best when it detects breakdowns and provides information (lessons/principles) for overcoming (repairing) these breakdowns. This way students are provided instruction precisely at the moment when it solves a pressing problem in accomplishing the task at hand. This makes them motivated to learn, makes the material more clearly relevant, and increases the likelihood that the lessons will be remembered. This principle of action-based learning is most important in educating undergraduates, for whom the perceived relevance of knowledge and motivation to learn are typically crucial determinants of educational success.
Executable content is made possible by such programming languages as Java, Perl-Tk, and Tcl-Tk. While all of these languages are powerful, Java has a decisive advantage: anyone with Netscape Navigator or one of its major competitors, such as Microsoft Explorer, will automatically be able to run Java applets (programs) with no extra effort or cost, regardless of what type of hardware or operating system they have. This means that anyone who can run a word processor on a PC will find it easy to run the applets. However, we have also developed tools in Perl and Tcl-Tk, for example DDCALC, which ultimately will, along with other Perl scripts, become part of N-ABLE.
We plan for N-ABLE to have a robust and extensible software architecture designed for applicability to a wide range of educational content areas. N-ABLE will be tailorable to particular instructional tasks. Its components will be re-usable in a variety of ways and for a variety of purposes. Its architecture will be open in the sense that new components can be added to it both by ourselves and by other programmers as time goes on.
Writing serious, robust educational software in Java is orders of magnitude more difficult than writing simple applets. Realistically, only a small fraction of faculty will have the programming skill or the time to create serious Java software. The development of VLSI CAD tools relieves the hardware designer of the task of learning the algorithmic details of logic synthesis and chip layout and wiring, as well as the physical details of chip fabrication. According to the aforementioned analogy, faculty who wish to exploit modern web technology should not have to become experts in object oriented programming and visualization technology-N-ABLE will supply the CAD tools that are needed to facilitate the task of creating animated concept applets.
N-ABLE will therefore reduce or eliminate the need for Java programming skills by offering faculty a variety of tools to aid them to rapidly and easily createnew Web-based, interactive tutors. Some of these tools will automate portions of the process of creating a tutor, such as translating non-hypermedia data into hypermedia form and producing different graphical representations of given data--including animations of temporal data. A different type of tool will enable users to create and to edit data of various types. The latter type of tool will enable users to create tutors from scratch; they will also enable users to edit the representations produced automatically by tools of the former type.
When the "activated" object is in HTML format and placed on a web server PC, it is automatically available to any user of a client PC on the World Wide Web. Client-server interactions may be useful and in some cases essential. Authorization control over such interactions would provide a means of prioritizing Colorado student and industrial users in accessing web-based active learning resources. N-ABLE will also include specialized tools for semi-automating the "activation" of algorithms and procedures which are specified textually. The algorithms will be written in the usual "pseudo-code" format (see for example, Introduction to Algorithms, by Cormen, Leiserson, and Rivest, McGraw-Hill, a widely used textbook in Computer Science).
Both of these tools will utilize the services of the web-ready PHIDIAS database (phidias.colorado.edu).
A 6-dimensional Boolean cube is given, which is mapped onto 4 4x4 matrices in the plane (Karnaugh Map). A 6-variable Boolean function has been mapped onto this cube, as indicated by colored dots. Each dot represents a primitive boolean function called a minterm, for which the function evaluates to 1. A Boolean function F is completely characterized by such a set of minterms.
Minterms are in the class of Boolean function called Boolean cubes. If the 6 logic variables are a,b,c,d,e,f, the possible minterms are a'b'c'd'e'f',a'b'c'd'e'f,...,abcdef, where the prime denotes complement. The literals (logic symbols) a and a' are shorthands for a=1 and a=0. Thus minterms are conjunctions of any 6 literals and cubes are either single literals or conjunctions of k literals, where 1< k< 7. In an n-dimensional space, a k-literal cube contains 2**(n-k) minterms.
An implicant of F is a k-cube, k< n, for which F evaluates to 1 on all 2**k of its minterms. A set of S of implicants is said to cover the set of minterms where F=1 if and only if each dot is contained in one of the implicants of S. The object of the game is to find the smallest set of cubes which has the property that every minterm is contained in at least one of the cubes. To do this, the player tries expand the cubes where possible, trying to make some of the cubes redundant. Redundant cubes are to be deleted. The cost of the covering set decreases with the number of its cubes, and decreases with the size of each cube (fewer literals means larger cubes)
To avoid local minima, it is sometimes necessary to reduce cubes instead of expanding them. This is an "uphill move", which temporarily increases the cost of the solution, but ultimately can lead past a global minimum.
Here the variables of the 6-variable logic function $F$ are $t,u,v,w,x,y$. The
Boolean 6-cube is projected onto 4 4-variable K-maps. The map on the upper left
corresponds to $u=0, t=0$, and so on. Initially the cubes of $F$ are all minterms,
represented by the dots.
A cube with more than 1 minterm is "selected" by clicking one of its minterms
and dragging in one of the 6 coordinate directions. Direction is
defined by :drag and drop" mouse movements as follows.
Left/Right: +/- in $x$ or $y$, depending on position;
Up/Down: +/- in $v$ or $w$, depending on position;
Shift-Up/Down: +/- in $u$, depending on position;
Each of the 4 4-dimensional K-maps has a periphery of "virtual" cells, so that
a mouse movement to the left (up) from a left-edge cell indicates a "wrap-around"
movement to the corresponding cell on the right (bottom) of the K-map. For example,
if the (t=0,u=0,v=0,w=0,x=0,y=0) vertex is selected a rightward mouse drag adds
the (t=0,u=0,v=0,w=0,x=0,y=1) to the selection, whereas a downward movement would
add (t=0,u=0,v=0,w=1,x=0,y=0). A leftward movement, however, would add
(t=0,u=0,v=0,w=0,x=1,y=0) and an upward movement would add (t=0,u=0,v=1,w=0,x=0,y=0).
Finally, a shift-left movement would add (t=1,u=0,v=0,w=0,x=0,y=0) and a
shift-down movement would add (t=0,u=1,v=0,w=0,x=0,y=0).
Each cube is surrounded by an oval on the K-map. has an associated
integer index. If there are not too many cubes, all the indices are
shown. In all cases, the index of the selected cube is shown.
Solving the Optimization Problem is equivalent to finding the "smallest" (in the sense defined below) logic circuit which represents the specified logic function.
A Boolean n-cube is a unit n-dimensional equilateral parallelopiped with exactly 2**n vertices. The n-cube may be considered to be a non-planar graph with 2**n vertices and (n/2)2**n edges. Each vertex is connected to exactly n other vertices by a path of length 1 (a path of 1 edge).
n-cubes may be effectively visualized by isometric projection for n=0,1,2,3,4 (although drawing a 4-cube without line overlap is somewhat difficult). The 4-variable function represented by F=a'c'+b'c'+ac+bc is illustrated by the following figure. Here a=0 on the inner cube and a=1 on the outer cube. The upper right hand vertex has coordinates (1,1,1,1), and corresponds to the minterm abcd. F has 12 minterms, and the function evaluates to 1 for all minterms except those at vertices (1,1,0,0), (1,1,0,1), (0,0,1,0), and (0,0,1,1).
Note that the function F is independent of variable d, so that each minterm has a matching minterm with the opposite value of d.
Unfortunately the optimization problem tends to be trivial in 4 or fewer dimensions. This is because local minima, which are the rule in problems of practical importance (typically n> 32 in real logic circuits). This makes learning effective optimization strategies difficult to learn visually. This difficulty has led to widespread use of Karnaugh Maps or K-maps for short, which yields effective visualization for n=5 or n=6. In a K-map of size 4, the 16 vertices of the 4-cube are projected onto the plane as the elements, or "cells" of a 4x4 matrix.
Each edge has length 1, and each coordinate of any vertex is either 0> or 1. Along each edge, exactly one coordinate variable changes its logic value value from 0 to 1 or conversely.
Examples:
Consider a Boolean function F^k, which has exactly 2**k minterms. F^k may be viewed as a subgraph of G_k with 2**k vertices. Then F_k is a k-cube if and only if each of its vertices are connected to exactly k other vertices in the subgraph by a path of length 1. Under these conditions we similarly say that G_k is a k-cube
Thus the graph of the 1-cube has 2 distinct subgraphs which are 0-cubes, the 2-cube has 4 distinct subgraphs which are 1-cubes, and the 3-cube has 6 distinct subgraphs which are 2-cubes. In general, the n-cube has 2n distinct subgraphs which are (n-1)-cubes.
Let v_i be the ith of the 2^k vertices of a k-cube C. Exactly k of the n coordinates of v_i have the same value in all the other vertices v_j, i!=j. Thus a k-cube C can be denoted as the conjunction
The state of this applet window is controlled by the selection highlighted in the tools list (lower left). "Get Started" instructions for the selected tool appear in the message window (upper right). For the selected tool, lists of pertinent data items appear in the drop down choice list (middle left). The degree of learning interactivity is entered under the name field. Depending on the tools selection, additional text boxes may appear in the drawing window (lower right). Depending on the tool selection, "special action" buttons appear on the bottom of the window. selected contains 2 input text fields at the bottom, the upper being for specifying the SOP, and the lower for specifying a cube for display. The applet window shall also contain an output field at the top in which the cost function for the specified SOP will be displayed. The specified cube and SOP are painted onto the applet screen.
The applet window whall also have 5 "state toggle control" buttons, EXPAND, REDUCE, REDUNDANT CUBE, REMOVE REDUNDANT, and ESSENTIAL PRIMES. These buttons are stacked vertically on the right of the screen, in the indicated order.
In addition to typing a cube in the text window, Cube selection is done by the usual mouse manipulation. The selected cube is displayed by formula in the ouput text window. Selected cubes may be expanded, or reduced by similar mouse manipulation.
When the mouse is down, an orange highlight is put on the closest (Euclidian distance on the applet screen) minterm. The orange remains when the mouse goes up. At this point a minterm cube is "quasi-permanently" selected.
When a function is already displayed, only minterms of the given SOP may be thus selected
Once a cube has been quasi-permanently selected, a larger cube can be thus selected by similarly clicking on adjacent minterms. Minterms which are both in the cover and adjacent to one of minterms of the already quasi-permanently selected cube will be highlighted by mouse proximity (and ONLY such minterms). Not just the newly selected minterm, but all minterms of the cube or subcube of the given SOP which contains the new minterm as well as the already temporarily selected cube are thus highlighted. This new cube stays temporarily selected while the mouse is down. This selection may be changed by moving the mouse back to a minterm of the previously selected cube and then to a different minterm.
When the mouse goes up on a new minterm, the highlighted, larger cube, which has twice as many minterms as the previously selected cube, is now quasi-permanently selected. However, pressing the BACKSPACE key returns the quasi-permanent selection to its previous state.
For a non-trivial n-variable Boolean function, this process can be repeated up to n-1 times. Thus for n<7, at most 5 clicks are possible. Typically, however, on or two clicks should be sufficient.
Ultimately, a cube of the existing SOP will thus be selected. Then, the user should press the ENTER key, and the cube becomes permanently selected. If ENTER is depressed prior to full selection of an existing SOP cube, the message "Select another minterm" will be displayed.
This selection mechanism is restricted to cubes of the existing SOP.
The applet screen will contain EXPAND, REDUCE, and IRREDUNDANT toggle
buttons. Cube expansion is accomplished by the
above cube selection mechanism in concert with the
EXPAND button. When the EXPAND button is in its ON state, this
selection mechanism will be automatically extended to select any cube
which has the property that each of its minterms are in
If a temporarily selected minterm corresponds to an illegal selection, an alarm will sound, and the OFF-set minterm preventing expansion will be highlighted with a large red dot.
A legally expanded cube will be highlighted in black until the ENTER key is pressed. After this keyboard event, the highlight changes to orange, signifying that the permanently selected cube has been added to the existing cover.
When the EXPAND button is toggled to its ON state, the REDUCE and IRREDUNDANT buttons are toggled to their OFF state (only one of the three buttons may be in the ON state at any given time).
When the REDUCE button is in its ON state, the cube selection mechanism works in a manner opposite to that for expansion. A cube of the existing SOP is selected as described in section on cube selection. That is, when the mouse comes up and the ENTER key depressed, a cube of the existing cover is highlighted orange. Internally, the ifSelected switch is set to true.
In this state, any pair (m1,m2) of minterms of the selected cube may be selected by drag and drop (in the indicated order) for reduction. Minterms m1 and m2 will be highlighted in black.
The selected cube will be reduced "from m1 to m2". This means that if the mouse is lifted, the selected cube will be reduced to the unique subcube of the previously selected cube which contains m2 but not m1. Note this reduced cube will contain exactly half the number of minterms of the originally selected cube. Thus for non-trivial original cubes, at most (n-1) reductions are possible.
This process may be repeated as in expansion until the ENTER key is pressed. At this point the originally selected cube will be replaced in the current SOP by the reduced cube, and all highlighting will be removed. Thus the original cube is replaced by the chosen reduced cube.
A special case arises when a cube has been reduced to a single minterm In this case two minterms can not be selected, so the ENTER key may be depressed with just this one minterm highlighted in black. If this minterm is contained in any cube of the SOP except the currently selected one (orange highlight), then no minterms will be highlighted in black.
Thus it is possible for the reduced cube to be empty. That is, if the cube selected for reduction has no minterms which are not contained in some other cube of the cover, the ENTER keyboard event deletes it. In this case, the selected cube is replaced by the empty cube
Suppose a cube of the existing SOP is selected as described in section on cube selection. That is, when the mouse comes up and the ENTER key depressed, a cube of the existing cover is highlighted orange. If the IRREDUNDANT button is clicked ON in this state, the highlight will change to red if the cube is redundant, and if the ENTER key is then presses, the selected cube is removed from the cover.
If the REMOVE REDUNDANT button is pressed in any state, the redundant cubes will be removed from the current SOP, and the cost function updated in the output window. See Redundant Cube Removal.
If the ESSENTIAL PRIMES button is pressed in any state, the Essential Primes will be highlighted with pink centers as follows. First, the least (in ascending lexicographical order) is highlighted. Hitting the PAGEUP key selects the next largest lexicographically for highlighting. Similarly, PAGEDOWN selects the next largest lexicographically for highlighting. Wraparound is used for continuous scrolling of the essential primes, if any.