CSC 148 H1, Winter 2013

Lab 4 (Feb. 5/6)

This document contains the instructions for lab number 4 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.

Overview

In this lab, you will practice writing recursive functions, and also write some simple linked list code.


Practice recursion

(Student s1 drives and student s2 navigates.)

Writing recursive functions can be tricky, so make sure you take time to think about the following issues before you start typing!

It's easy to get stuck when you're working on recursion. Once you've come up with some test cases and have ideas for what the base case should be, ask for help if you're not confident about how to implement the rest of your solution.

Binary notation

In the base 2 number system there are only two possible digits: 0 and 1. These are often called bits. Each bit is an increasing power of 2 (that is, each bit counts for twice as much as the bit to the right), so the binary number 101 represents the value 1 × 4 + 0 × 2 + 1 × 1 = 1 × (22) + 0 × (21) + 1 × (20) = 5.

Here is a table of the first 8 non-negative numbers in both binary and decimal.

Decimal Binary
0 0
1 1
2 10
3 11
4 100
5 101
6 110
7 111
8 1000

Your task

Before you start solving the problem below, write an  if __name__ == '__main__':  block that calls binary_rep on some examples (like the ones listed above) and prints the results.

We really mean it! Take the time to do this (it's going to be fairly quick) so that you can test your code as you are developing it. It's an excellent habit to get into!

To convert from a base-10 integer numeral to its base-2 (binary) equivalent, the number is divided by two, and the remainder (either 0 or 1) is the least-significant bit (the last one on the right). The (integer) result is again divided by two, its remainder is the next least significant bit (the second-last one on the right). This process repeats until the quotient becomes zero.

Intuitively, we know that if a decimal number is even (remainder 0), its last digit in binary should also be 0. Similarly, if it's odd (remainder 1), its last digit should be 1. Then, we need to process the rest of the number, which we've shifted one bit to the right (dropping the last bit on the right and moving all the other bits one position over), which is equivalent to dividing the number by 2.

In a file named binary.py, write a recursive function binary_rep that takes a non-negative integer as a parameter and that returns the binary representation of that number (as a string of 0's and 1's).

Hint: You can figure out the remainder of a division by using the remainder operator: number % 2 (for example, 19 % 2 = 1). You could use integer division to get rid of the last digit (for example, 19 // 2 = 9), but you can also use the "right shift" operator as follows: number >> 1 (for example, 19 >> 1 = 9).

Once you are done and confident that your code works, show your work to your TA and switch roles.


Work with linked lists

(Student s2 drives and student s1 navigates.)

Working with linked lists can also be tricky, in a different way. Here is how you should approach this task.

In a file named linked_queue.py, write code for a Node class (take a look at the lecture materials from last week to see how we did this in class, in case you don't remember).

Next, write a class Queue that implements the Queue ADT with a linked list (see last week's lab for the definition of the ADT and of the methods you should implement). Do not use any list or dictionary or other standard container! Remember: the point of this exercise is to practice linked lists.

Use the file testqueue.py from last week's lab to test that your implementation seems to work correctly. Once you have done so, use the file timequeue.py from last week's lab to check the efficiency of your implementation. If you have done it correctly, timequeue.py should show that the time is the same no matter how many elements are in the queue.

Hint 1: Instances of your Queue class should store two attributes: a reference to the first Node in the linked list storing the Queue elements, and a separate reference to the last Node in the linked list.

Hint 2: Think carefully about which end of the list you want to use as the "back" of the Queue (where you will add new elements) and which end of the list you want to use as the "front" of the Queue (where you will remove elements). The reason why you have to be careful is that it is easy to remove elements from one end of a linked list, but difficult to do so from the other end (adding new elements is easy to do at either end).

Hint 3: You need to be careful to update your attributes correctly when the queue starts out (or ends up) empty.

Once you are done and confident that your code works, show your work to your TA.