CSC 148 H1, Winter 2013

Lab 2 (Jan. 22/23)

This document contains the instructions for lab number 2 in CSC 148 H1. 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 the results of your work.

General rules

We will use the same general rules as for the first lab (including pair programming). See the instructions at the beginning of Lab 1 to refresh your memory.


Using Stacks

Getting started

(Student s1 drives and s2 navigates.)

  1. Save the file stack.py from last week's lectures (available on the Lectures & Labs page) in a new folder called "lab2".
  2. Start Wing and open stack.py.
  3. Create a new file called driver.py, and add code to it so that it:
    1. creates a new Stack;
    2. puts the string 'Hello' in the stack;
    3. removes the string from the stack and prints it.
    All of the above should be under the  if __name__ == '__main__':  statement.

Using a stack

(Switch roles: now, s2 drives and s1 navigates.)

  1. 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 input("Type a string: ").
  2. Add code at the end of driver.py to remove and print the lines you stored in the stack. When the stack becomes empty, end the program.

Show your work to your TA before moving on to the next section.


Queues

A queue is another ADT that stores a sequence of items. Unlike a stack, items are added at the "back" and removed from the "front", in first-in, first-out order (like a lineup at a grocery store). Here are the operations supported by the queue ADT:

Implementation

(Switch roles again: s1 drives and s2 navigates.)

  1. Write a Queue class in a file named queue.py to implements the queue ADT.
  2. Download the file testqueue.py from the Lectures & Labs page, open it in Wing, and run it to test your Queue class.

Using a queue

(Switch roles again: s2 drives and s1 navigates.)

  1. Modify driver.py so that it uses a queue instead of a stack, and expects input lines to contain integers (except for the "end" line).
  2. Now make your program print the product of all the numbers that were in the queue. (Do this by removing the items in the queue one by one.)

Show your work to your TA before moving on to the next section.


Efficiency

(Switch roles one last time: s1 drives and s2 navigates.)

  1. Download the file timestack.py from the Lectures & Labs page, open it in Wing, and run it to get information about the efficiency of the Stack class.
    How does the running time grow as a function of the number of items on the stack?
  2. Download the file timequeue.py from the Lectures & Labs page, open it in Wing, and run it to get information about the efficiency of your Queue class.
    How does the running time grow as a function of the number of items in the queue?
  3. Get out a piece of paper and spend some time with your partner trying to figure out why your Queue class behaves this way. Also brainstorm possible solutions to this O(n) efficiency (where n is the number of items that are in the queue).
    Hint: Draw a list, and think about keeping track of "front" and "back" indices, and ignoring some parts of your list. Don't worry if you can't come up with a solution, but do spend some time discussing!