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.
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.
In this lab, you will practice writing recursive functions, and also write some simple linked list code.
(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!
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.
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 × (2^{2}) + 0 × (2^{1}) + 1 × (2^{0}) = 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.
(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.