# 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!

• Think about how the function you are writing will be called, and write down a few examples. Writing down those examples is particularly important: this helps to ensure you have a very clear sense of the exact purpose of the function.
• What parameter values would make your life the easiest, when you know the answer right away? What input means that there's nothing left to do? These help identify your base case(s).
• If you have a parameter value that is more complicated, is there a smaller version of that value that you can recurse on? For example, if you are given a list `L`, you might try recursing on `L[1:]` and then figuring out what to do with `L[0]` and the result of the recursive computation on `L[1:]`. You could also recurse on `L[:-1]` and then combine the result with `L[-1]`.

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

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.

• Draw lots of pictures to get a very clear idea of exactly what the linked structure should look like before, during, and after each operation you are trying to implement. This is important: if you skip this, you are likely to have only a vague idea of what it is your code should do, and you are much more likely to make mistakes!
• Think carefully about what variables and attributes each part of your picture represents. If you understand this, then you will be able to tell exactly what changes you need to make in order to carry out the task you want to carry out.

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.