CSC148H/A48H lab -- week 2

This document contains the instructions for the week 2 CSC148H/A48H lab. To earn your lab mark, you must actively participate in the lab. We mark you in order to ensure a serious attempt at learning, not to make careful critical judgments on your work.

Here are the activities for this lab:

Icebreaker
Using the lab computers.
Setting up email forwarding.
Using Wing, playing with Stacks.
Compiling and running programs from the keyboard.

Icebreaker

You'll be spending lots of hours with your TA and fellow inmates, so you'll start by getting to know them. Your TA will get you going on this.

Using the lab computers

Sit down with your partner. The rest of these instructions call you two s1 and s2. Pick which one is which.

Repeat the following set of instructions twice, once for s1 and once for s2.

Enter your user ID and password. Wait while the computer starts up.
Start your browser, go to the CSC148H/A48H web site, and select the "Labs" link. Find the Week 2 entry and open it. This will allow you to click on links and download files for the lab.
On StG, we will sometimes email information to everyone's CSC148H account. Unless this will be your primary email account, you must set up email forwarding. Do this now.

Later, at home, check to see that you set up forwarding properly, by sending mail to yourself and seeing if it appears at the right destination account. Too often, we send messages such as assignment marks to students, only to find their addresses are wrong -- and we can't fix them. Please check your forwarding!

Brief instructions, in case the web reference isn't enough: Create a file called ".forward" -- don't forget the period at the beginning of the name -- in your home directory, and put your forwarding address in the file. You can edit your .forward file in Wing. If you see someone having trouble, please help them. Some of the class are new to the computer labs -- please make them feel welcome!
Log out.

Using Wing, playing with `Stack`s

In this lab, you'll be working in the pair programming model. Obviously, two programmers are involved, and we call these two people the driver and the navigator. Here are the definitions of the two roles:

driver: The person typing at the keyboard.
navigator: The person watching for mistakes, and thinking ahead.

And here is the most important rule for this lab:

The navigator must not touch the keyboard. If the navigator does any typing, the navigator will get a zero for this lab.

Getting started with Wing

Throughout the lab, you'll be switching back and forth between the driver and navigator roles. s1 will be the first driver, so s1 should now log in again.

Save stack.py to your hard drive. Make a new folder called "w2lab", and put that file in it. You may need to right-click on the link to get a menu giving you the option of saving the file.
Start Wing by double-clicking its icon, and open stack.py.
Create a new file called driver.py, and add code to it so that it:
1. makes a new Stack;
2. puts the string 'Hello' in the stack;
3. removes the string from the stack and prints it.

Run your program. When you're done, show your TA.

Filling a `Stack`

Switch roles: now, s2 drives and s1 navigates.

Change driver.py to read in a list of lines from standard input, until the string "end" is typed, and put each line into a Stack. Remember that a "read and process loop" looks like this:
```
            Read a line
            while not done:
              Process the line that was read
              Read the next line
```
You can read a line with raw_input("Type a string: ").

Run your program. When you're done, show your TA.

Emptying a `Stack`

Switch roles again: s1 drives and s2 navigates.

Add code at the end of driver.py to print the lines you stored in the stack.
- When the stack becomes empty, end the program.

Run your program. When you're done, show your TA.

Queues

A queue is another ADT much like a stack, except that items are added at the rear and removed from the front. (Like a lineup at a bank.) Here are the standard operations:

enqueue(o) Add a new item to the rear of the queue.
dequeue() Remove and return the front item.
front() Return the front item.
isEmpty() Test whether the queue is empty.
size() Return the number of items in the queue.

Implementation

Switch roles again: s2 drives and s1 navigates.

Save the file queue.py, which implements the Queue ADT. Modify the implementation so that it also supports the following method:

remove(o) Remove the first occurrence of object o from the queue if it exists

Here is a test_queue.py file containing nose unit tests; modify it so that it tests the new method that you implemented. When you have done this and all the tests pass, show your TA.

Timing

In lecture, we found that using index 0 as the top of a stack was inefficient. The same problem happens with our queue implementation: every time we dequeue we must shift everything over. You can see some numbers by running time_queue.py, where we put a bunch of items into a queue and then enqueue and dequeue 20000 items. Get out a piece of paper and spend some time with your partner brainstorming possible solutions to this problem. Draw a list, and think about keeping front and rear indices. Don't worry if you can't come up with a solution, but do spend some time arguing.

Using a PriorityQueue

Switch roles again: s1 drives and s2 navigates.

A priority queue is another ADT that is slightly different from a regular queue ADT. Instead of removing items in the order in which they were added to the queue, items are removed in order of their priority. Here are the operations:

insert(o) Add a new item to the queue
extractMin() Remove and return the item with highest priority
min() Return the item with highest priority
isEmpty() Test whether the queue is empty
size() Return the number of items in the queue

Save the file pqueue.py. It contains an implementation of the PriorityQueue ADT using a heap. Heaps are a topic that we will cover later in the course. At this point, you do not need to actually understand the details of how the PriorityQueue in pqueue.py works, but you do need to be able to use it.

Also save the file event.py. This file contains an Event class that has an associated timestamp. The timestamp is simply an integer that represents the number of units of time that have elapsed from some arbitrary starting point. Whenever you create a new instance of an Event, you pass it a timestamp in the constructor.

Here is what you should do:

Modify driver.py so that there are two instances of a priority queue and no stack. Also modify driver.py so that it expects input lines to contain integers (except for the "end" line):
- You can convert an input line to an integer by doing
```
          i = int(line)
```
For each integer input, insert the integer into the first instance of the priority queue. Also create a new Event with that integer as the timestamp, and insert the event into the second instance of the priority queue.
Make your program extract all elements from the first instance of the priority queue and print the items in the order they were extracted. Do the same for the second instance of the priority queue.

When you run your program, try inputting integers in a random order. What do you notice about the order in which items are extracted from the first priority queue compared to the second? Does this mean the priority queue is busted?

Show your program to your TA.

The problem has to do with the fact that there is no ordering defined for instances of the Event class the way there is for integers. In order to fix this, add the following method to the


Event

class:

def __cmp__(self, other):

    if self.timestamp < other.timestamp:

        return -1

    elif self.timestamp > other.timestamp:

        return 1

    else:

        return 0

Now try running your program again. You should see the events being printed in ascending order.

The following is why this fixed the problem. The priority queue compares entries using '<' and '>' operators in order to determine which entry has higher priority. When comparing integers, it is easy for Python to determine the truth or falsity of the comparison (e.g., "5<6" is True but "6<5" is False). However, Python needs additional information to determine the truth or falsity of comparisons that involve classes defined by the programmer (like the Event class). This information is provided by the __cmp__ method of the class. Suppose e1 and e2 are instances of the Event class. Whenever an expression of the form "

e1
< e2

" or "e1 > e2" appears, Python makes the call e1.__cmp__(e2) to help determine the expression's truth or falsity. (If the expression were "e2 < e1" or "e2 > e1", the call would be e2.__cmp__(e1) instead. Python behaves analagously for the other comparison operators.) The return value from __cmp__ tells Python the relative ordering of the two objects. In particular, if __cmp__ returns a negative number, then the self object is less than the other object, and if return value is positive, then the self object is greater than the other object. As you can see in our above implementation of __cmp__, whenever the self object has a smaller timestamp than the other object, a negative number is returned, indicating that self is less than other.

Modify __cmp__ so that 1 is returned in the first case, and -1 in the second case, and try running your program again. What has happened? Can you explain why such a small change has made such a dramatic difference?

CSC148H/A48H lab -- week 2

Icebreaker

Using the lab computers

Using Wing, playing with Stacks

Getting started with Wing

Filling a Stack

Emptying a Stack

Queues

Implementation

Timing

Using a PriorityQueue

Using Wing, playing with `Stack`s

Filling a `Stack`

Emptying a `Stack`