• Nondeterministic Finite Automata
• Equivalence Relations and Partitions
• Operations on Linked Lists
• The Relational Model
• Operations on Binary Search Trees
• Stacks and Queues
• Quicksort Algorithm
• Nested Exception Handling

1) Take a simple NFA.
2) Select some students to be the states of the machine (if there is a large space in the room, the states could represented on the floor by duct tape).
3)  Choose a string.
4)  Have a person start at the start state.
5)  Fielding the class, ask where the student should go.
6)  If there is a branch in the NFA, get a new student to join in the simulation.

Note:  The instructor must keep this organized, especially when multiple branches are active.

1) Explain what a partition is. (Each subgroup member R each other)
2) Call up three groups of students.
        Tell one group to partition by the relation "older than"
        Tell one group to partition by the relation "partners on some project with"
        Tell one group to partition by the relation "comes from same hometown as"
3)  All other students in the class predict the outcome and have to "make a bet" on which group(s) will be able to create a partition.
4)  Discuss which group(s) succeeded and failed.
5)  Iteratively "fix" the first two groups:
        "older than" -> "at least as old as"
        "at least as old as" -> "same age as"
        "partners on some project" -> "partners on current project"
6)  Tie results into discussion of the properties of relations:  reflexive, symmetric, transitive.

In this activity, the students' names will act as pointers and the height of the student will be the data.

The TA (or instructor) will act as the head pointer.

1)  Everyone points to one student (NULL).
2)  The TA calls on a student (Nick)
3)  TA calls on another student (Steve) and points to the first student (Nick).

For example,  Tammy points to Nick and Nick points to Steve.

4)  Continue in this way until the list is created.
5)  Each student in the list only needs to remember one name -- the person at which they point.

Searching:
1)  Search for students having the same height as the TA by following the pointers.

Insertion:
1)  Call on a student not already in the list
2)  Insert this student in the list after a student that the person does not know.

Deletion:
1)  Delete someone with height > 5.5 ft (all the tall students leave).

1)  Divide the class into 2 groups.
        The first group gets 3 boxes labeled "Student Info", "Course Info", and "Schedule".
        The second group gets 1 box labeled "Student Course Data".

Students in the first group fill out slips of paper with the following fields:
        In the "Student Info" box:  slip of paper says "SID" and "Name"
        In the "Course Info" box:  slip of paper says "Course Number" and "Professor"
        In the "Schedule" box:  slip of paper says "SID" and "Course Number"

Students in the second group fill out slips of paper with the following fields:  "SID", "Name", "Course Number", and "Professor".

2)  Have each group fill out the slips of paper according to their class schedules and put these pieces of paper in their box(es).

3)  Give queries such as the following and time the students to find the answers:
"Who's in course X?"
"What classes is Y taking?"
"Who has a class in Kane?"
"What is Y taking from Professor Z?"

4)  The timing results should motivate the reason for building a relational database.

1)  Pick a student to act as the root of the tree.  This student stands in front of the class.
2)  Another student asks the root his/her name.  Depending on the alphabetical ordering of the names, the second student stands to the right or the left of the root.
3)  Continue step 2 with more students.
4)  Choose a name to delete from the tree.  Send another student to find that student node and remove it.

Try to limit examples to be no more than 3 levels deep, or lower levels will be too crowded.
Deleting the root might be a good example.

1)  Select a group of 10 students to stand at the front of the room.  Have them stand in a line in random order.
2)  The instructor selects a student to the be the pivot, partitions according to student first name.
3)  Now that the students are partitioned into two groups, we have the groups partition themselves.

After the demonstration, we can show the worse case scenario, similarly.

1)  Give examples of stacks and queues in real life:
        Stack is similar to the plates stacked up in the cafeteria.
        Queue is similar to a line waiting to get into the cafeteria.

2)  The professor (TA) says they will give candy away to students simulating a queue.  The first in line (in the queue) is the first to get a piece of candy.

3)  The professor (TA) says they will give candy away to students simulating a stack.  Hopefully, the students will realize that the first person pushed to the stack will be the last one popped from the stack.

Discussion of LIFO and FIFO:  Ask students where they would choose to be in a queue and a stack.

(This activity was seen by Sam in 143 Java during Autumn Quarter 2001).

1)  Let several students stand in a line -- this line represents the calling stack.
2)  Each student represents a method that calls the student next to him/her and the one at the end takes a balloon.  The balloon is the "exception" with its type written on it.  The student holding the balloon is the method generating the exception.  The student may either:
        1)  throw the exception to his caller (the student next to him/her)
        2)  handle the exception (pop the balloon)
In the second case, the student has the option of blowing up a new balloon representing a new type of exception which he/she then can pass up along the calling stack.
 

 <back to 590IT page>