CS 21: Algorithmic Problem Solving
HW #13: Optional Warmups
Due 11:59pm TUESDAY, May 15This assignment is completely optional. Your grade on this assignment will supplant your lowest grade for any quiz or homework. (I will automatically drop the one that helps you the most.)
The program handin21 will only submit files in the cs21/homework/13 directory.
Your programs are graded on both correctness and style. Please review the comments regarding programming style on the main page
The binToDec function takes a string representing a binary number and converts it into an int representing the decimal equivalent of that number. The constructor for the int class allows the same conversion: int('1001', 2) returns an integer equivalent of the base 2 (binary) string (which, in this case, is the integer 9). You cannot use this constructor in your solution, but you can use it to test your solution.
The decToBin function takes an int representing a decimal number and converts it into a string representing the binary equivalent of that number. Although there is no built-in way to do this in Python, you can still test the functionality of your program: Assuming that binToDec works properly, you can assert decToBin(binToDec(s)) == s. The following pseudocode is a sketch of how to do the conversion. Other ways are also possible.
Converting decimal to binary pseudocode:
given decimal as an integer
initialize the result to be empty
repeat until the decimal is 0:
compute the remainder of decimal divided by 2
result = remainder concatenated with result
decimal = decimal / 2
return result
We have dealt exclusively with what are called singly-linked lists. They are called singly-linked because there is only one link that connects each node to another node in the list. We have called this link next because it points to the next item in the list.
In this exercise, you will write an implementation of doubly-linked list. A doubly-linked list maintains two links to other nodes in the list: a link called next which points to the next node in the list (and functions identically to the next pointer we have seen so far), and a link called prev which points to the previous node in the list. The prev allows you to walk back and forth through the list. For example, to find the second to last item in a doubly-linked list, you can start at the tail and follow one prev to get to the second to last node.
You will need to do the following:
- i. Modify LinkedNode so that it has a prev link, add support getPrev and setPrev, and update the __str__ method.
- ii. Modify LinkedList so that it properly maintains the prev links. You will need to update insertAtHead, insertAtTail, removeFromHead, and removeFromTail.
- iii. Add functionality to support a method called find(self, key) which returns the LinkedNode containing the first instance of the key in the LinkedList (starting from the head of the list).
- iv. Add functionality to support a method called remove(self, key) which removes the LinkedNode containing the first instance of the key in the LinkedList (starting from the head of the list). You will probably want to use the find method you wrote in part iii as part of this solution.
A. 5 B. 5 C. 5
\ / \ /
7 3 8 3
\ / \ \
9 2 4 9
/
1
depth = 3 depth = 4 depth = 2
- i. One way to know the depth of a tree is to modify the code for binary search trees so that the BinaryTree class maintains the depth of the tree in a variable (for example self.depth). When a new node is inserted, you must determine whether or not that node increased the depth of the tree. (Notice that the depth either doesn't increase, or it increases by 1.) Implement this solution.
- ii. Another way to know the depth of a tree is to compute it when the depth is queried. Write a method called getDepth(self) which computes and returns the depth of the tree without using the solution from the previous question. It is probably more intuitive to write this function recursively (using a helper function), but you may also implement it iteratively. (Or both if you have so much time you don't know what to do with it.)