Example Solution:
Linked Lists As a Queue - Pong ; Helpdesk Assignment
(Console version)
- Which version of C#/ Visual Studio is required for this assignment?
-
The provided files are (obviously) C#, and (less obviously:) ) they were built using
the Visual Studio 2005 product. If you have an older version of Visual Studio (or
are using Mono), you probaby won't be able to open the Solution (.SLN) file. If
this is the case, in order to build this, you'll need to add all the .CS files to
a new project, and then everything should compile & run just fine.
- Other than the System.Console classes, this program uses no other
classes, so this *should* be good to go on VS 2003, and Mono ; it hasn't been tested
on those systems, though.
- Console Application / Test Harness
- Feel free to omit these, and make the students do more of the
assignment, if you want to.
- Major Themes in Student Solutions
-
After you've read the assignment, it should make sense that there are (at least) two major
styles of solution to this assignment.
- The first major theme (which, of course, has many variations :) ) is to create
a class to represent a Queue, implemented using a LinkedList. One then creates a Helpdesk class
which has two Queue objects within in - one for the high priority items, and one for the low
priority items.
Thus, the Helpdesk class basically dispatches "Add Ticket" requests to the
correct queue, and making sure that PrintAll / PrintFirstItem types of methods do the right
thing. Personally, I think this tends to be the easier approach, especially for weaker
students. This solution is demonstrated in the Helpdesk_MultipleQueues class (and the
QueueOfTickets class)
-
The second major theme (again with variations) is to create a single class, and within it,
to keep all the tickets in a single linked list. The best way to do this is to have the
'first/head' pointer be the next thing to remove, and then keep a pointer to the last thing
in the 'high priority ticket' region of the list, and another pointer to the last thing
in the 'Low priority ticket' region of the list. By putting high priority tickets in front
of the Low priority tickets, add/remove are each O(1) operations.
This approach, demonstrated in the Helpdesk_SingleQueue class, tends to be more difficult.
Also, be aware that students can do bizzare things with this one - one student
added new items at the front of the list (without sorting), and 'timestamped' each node
as it was added, then (when printing), would run through the list N times (making the print
operation an O(N^2) operation!).
The second source of variation is how to model priority. Since the assignment only
specifies "High" and "Low" priorities, a bool(ean) is a natural and reasonable choice.
In my class, students have seen enums, and so I push them to use those, instead. Once in a
while a student will use an int to model priority, so that an arbitrary number of
priorities can be modeled.
The example solution uses enums, just because that's what I want my students to see.
Another possible source of differences amongst student solutions
is whether to have the Helpdesk/helper Queue classes store
references to Ticket objects, or whether to have the linked list's node class incorporate
the ticket description (and priority) directly. In the assignments
as they care currently written, the students are required to have
each linked list node contain a reference to a Ticket object. I tend to encourage them to have the
Helpdesk application interface with the rest of the program by description (strings) rather
than objects. Internally, they can either incorporate this into each linked list node, or have
each linked list node have a reference to a book object (their choice).