Juha Hyvönen
Helsinki University of Technology
email: juha.hyvonen@hut.fi
1. Introduction
1.1 General
TRAKLA is an electronic mail (email) based system for teaching basic
computer science
data structures and algorithms. It distributes homework exercises and
evaluates the
students' answers automatically. The exercises are individually tailored
for each
student so that copying the answers from others is not possible. The
student receives
exercises by email, solves the problems using an interactive editor, and
sends the
answers back using email. TRAKLA is used at Helsinki University of
Technology (HUT)
in the basic course of data structures and algorithms (CS7).
1.2 Trakla Server
The TRAKLA Server consists of three main components (Figure 1):
database
mail server
checker/tailor
Figure 1. TRAKLA Server Components
First the student sends a registration request to the mail server. The mail
server
has a simple command language all messages sent to the server must follow.
A registration
message looks like the following:
#id
12345s
#name
Brian Kottarainen
#register
1.3 Trakla Editor
The TRAKLA Editor is a program that eliminates the errors involved in the
server command
language and the internal format of the exercises. It is a graphical editor
that
takes the exercise text as input, presents it graphically if necessary,
offers interactive tools to solve the problem, records the intermediate
steps the student does
to solve it, and finally generates the answer using the required textual
format.
The student does not need to know anything about the server command
language or the
textual format of either the exercise or the answer
The editor is an add-on component to the TRAKLA server as it reads and
generates the
format the server understands. The editor consists of three main components
(Figure
2)
parser/visualiser
editor tools
recorder/generator
Figure 2. TRAKLA Editor Structure
The parser reads the tailored exercises that the TRAKLA server has sent and
the visualiser
presents them in graphical form. The user solves the exercises using editor
tools
that form the user interface. All (necessary) actions are recorded and when
the student is done, the answer is generated in textual form to be sent
back to TRAKLA server.
2. General User Interface
2.1 Menus
The menu bar of TraklaEdit consists of the (Apple) menu, five application
menus,
and a version number of the application.
About TraklaEdit displays an alert window (see first page).
Help gives general help about the application.
Close closes the frontmost window.
Import TRAKLA questions opens a standard open dialog box for selecting a
exercise text file sent by the TRAKLA
Server.
Export TRAKLA answers opens a standard save dialog box for saving answers
in a text file. The file is of
type 'TEXT' and can be viewed and edited with any word processor.
Edit menu is not used by TraklaEdit application.
The Exercise is used to select the exercises. Some items may be dimmed
indicating that the editor
has not been implemented.
History menu provides a mechanism to multiple undos and redos. It is not
available
in all editors.
Forward redoes the latest undone event.
Backward undoes one (latest) event.
Play replays all events that have been undone.
Play reverse undoes all events.
2.2 Standard Buttons
There are three standard buttons in (almost) every editor window:
Reset restores the original exercise setup.
Export tells the application that the user has completed this exercise and
it can be saved
(when exporting the answers).
? gives context-sensitive information for current exercise.
Text shows the exercise in textual form.
3. Exercise Interfaces
The numbering of the exercises is the same as in spring 1994 course.
3.1 Round #1: Fundamental Data Structures
Exercise 1.3: Contents of a queue
Drag letters from input stream into the queue table and from the queue into
the output
stream.
You cannot drag the "get" items (marked "*").
Exercise 1.4: Contents of a deque
Drag letters from input stream into the deque and from the deque into the
output stream.
You cannot drag the "get" items (marked "<" and ">").
3.2 Round #2: Searching methods
Exercise 2.3: Binary Search Tree
The editor presents an empty binary tree "mask" at the bottom of the
window. The user
drags the circled letters from the top row one by one into the binary tree.
If a letter is placed on a reserved node its contens are replaced with the
new letter.
The previous letter which is zoomed back to its initial position in the top
row.
Any letter in the binary tree can be moved to an empty node in the tree. If
the node
is reserved the letters are swapped (in the tree).
If option key is pressed while clicking on a letter (in the tree) its
initial place
on the top row is highlighted.
Exercise 2.5: Hashing; Separate Chaining
The user drags boxed letters from the top row to a hash array below. The
editor automatically
chains the letters that are put into the same position.
The numbers under
the top row represent the numeral value of the letters.
The numbers above
the bottom row are hash array indexes.
Drags are only allowed onto the empty dotted-line boxes in the hash array.
Swapping is not allowed between nodes in the hash array chains.
The History menu is disabled for this exercise.
Exercise 2.6: Hashing; Linear Probing
The user drags boxed letters from the top row to a hash array below.
The numbers under
the top row represent the numeral value of the letters.
The numbers above
the bottom row are hash array indexes.
Exercise 2.7: Hashing; Double Hashing
The user drags boxed letters from the top row to a hash array below.
The numbers under
the top row represent the numeral value of the letters.
The numbers above
the bottom row are hash array indexes.
3.3 Round #3: Sorting
Exercise 3.1: Digital Search Tree
The editor presents an empty tree "mask" at the bottom of the window. The
user drags
the circled letters from the row of letters one by one into the tree.
If a letter is placed on a reserved node its contens are replaced with the
new letter.
The previous letter which is zoomed back to its initial position in the row.
Exercise 3.2: Shellsort
The exercise and the editor are divided in two parts. First, the user must
determine
which increment sequence to use. Second, the user must continue sorting one
h-sort
pass.
The first two arrays (white background) can be used to determine which
sequence is
used. The user drags the letters from the top array to the bottom array and
tries
to figure out the sequence.
The other two arrays (gray background) must be used to sort the next h-sort
pass.
Exercise 3.3: Finding the Median (or Quicksort Partitioning)
The arrays in the white backgroud are used to determine how the first pass
was done.
The result of the first pass is under the empty array.
The arrays in the gray background to continue partitioning the second pass.
Only the
letters that are used in the second pass should be moved down to the last
array.
Exercise 3.4: Heap Manipulation
- A row of circled letters form an array representation of a heap
at the top of the
window. The letters are to be dragged to the tree representation "skeleton"
of a
heap at the bottom.
- Then some letters are added into the heap "skeleton" (by
dragging) and restoring
the heap condition. You cannot add the letters before all the letters in
part 1)
are put into the heap.
- When you are done inserting, the top element is replaced by yet
another letter. This
is done by dragging the letter onto the top of the heap which causes the
original
element zoom back to its initial place in the array at the top of the
window.
- After that, some elements are removed by dragging from the heap
into the empty circles
(and restoring the heap condition).
Exercise 3.5: Bottom-up Heap Construction
The letters are to be dragged from the array into the heap. The letters can
be moved
from one heap node to another. If the node is not empty, the two nodes are
swapped.
(If you drag a letter from the array onto a node that is not empty, the
original
letter is replaced and zoomed back to its initial place in the array.)
Exercise 3.6: Multiway Merging; Replacement Selection
Letters are dragged from input tape to memory, "processed" there, and
dragged to output
tapes.
Exercise 3.7: Polyphase Merging
Drag letters between the tapes (and memory). If you drop a letter onto
another, the
letters are swapped.
Block separators can be left in there current places (in tapes #1 and #2).
3.4 Round #4: Graph Algorithms
Exercise 4.1: Linked list representation of a graph
The letter pairs at the top of the window represent the edges (with end
nodes) of
an undirected graph.
The dotted-line boxes represent an array (of linked lists).
The nodes (letters) are dragged onto the array elements to form a
linked-list representation
of the graph. The editor automatically chains (links) the letters in the
same array
position.
The letters can only be dropped on the dotted-line squares or back to their
initial
position. It is possible to move a letter from a linked list to another
list by dragging
the letter onto a dotted-line square.
Exercise 4.2: Depth-first traversal
The lists at the top are a linked-list representation of an undirected
graph. At the
bottom of the window is a stack.
Letters (graph nodes) are dragged to the stack on the dotted-line square.
When the
top element of the stack is popped (by pushin the Pop -> button), its
contents are copied to a new stack.
The History menu is not available, but you can "unpop" the stack by pushing
the <- Back button.
Exercise 4.3: Recursive depth-first traversal
When you click on an edge, the edge is highlighted and the nodes that are
connected
to it are also highlighted.
If you make a mistake just click the edge again to deselect it.
Exercise 4.4: Breadth-first traversal
The lists at the top are a linked-list representation of an undirected
graph. At the
bottom of the window is a queue.
Letters (graph nodes) are dragged to the queue on the dotted-line square.
When the
first (bottom) element of the queue is visited (by pushin the Get ->
button), its contents are copied to a new queue beside the old.
The History menu is not available, but you can "unget" the queue by pushing
the <- Back button.
Exercise 4.5: Breadth-first traversal
When you click on an edge, the edge is highlighted to indicate that it has
been used.
If you make a mistake just click the edge again to deselect it.
Exercise 4.8: Topological Sort
The lists at the top are a linked-list representation of a
directed
graph. At the bottom of the window is a queue.
The aim is to sort the nodes topologically.
Drag items from the middle row to the empty row below.
Move (or swap) items in the row to sort the nodes.