CS 21: Algorithmic Problem Solving

 

HW #13: Optional Warmups

Due 11:59pm TUESDAY, May 15

This 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

Binary-Decimal-Binary Conversion
In this exercise, you will write two functions, binToDec(bin) and decToBin(dec).

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

  
Linked Lists
For the exercise in this section, you should begin with the code in cs21/homework/13/linked.py which is a complete implementation of linked lists.

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:

Binary Search Trees
For the two exercises in this section, you should begin with the code in cs21/homework/13/bst.py which is a complete implementation of binary search trees. Both questions deal with the depth of the tree. The depth of the tree is defined to be the maximum number of nodes along the path from the root of the tree to any leaf. Any tree with only one node has depth 1. Here are some other examples (in beautiful text art):
A.    5        B.    5        C.    5
       \            / \            / 
        7          3   8          3   
         \        / \   \             
          9      2   4   9             
                /              
               1              

  depth = 3     depth = 4       depth = 2