15-110 Summer 2015

Programming Assignment 6

Overview

Data structures are powerful tools for computer scientists and programmers. They help manage complexity, promote organization, and allow for the implementation of clever algorithms. In this assignment, you'll be playing around with a few basic data structures to solve programming problems. By the end of the assignment, you'll have familiarity with associatove arrays (implemented as dictionaries in Python), and binary search trees.

For this assignment, you will create Python source files containing functions implementing each of the problems described below. If you find it useful for any of the problems in this assignment, you may define additional helper functions that your primary function for that problem calls to solve a sub-problem. Definitions for these helper functions should be included in the same Python source file as the primary function they help. You should store a source file for each problem in a folder named pa6.

Note: You are responsible for protecting your solutions to these problems from being seen by other students either physically (e.g., by looking over your shoulder) or electronically. Before submitting your code, you should also download this file: test_pa6.py and do the following:

>>> from test_pa6 import *                (OR > python3 -i test_pa6.py)
>>> test_all()

These tests will automatically check that your function returns the correct value. If you don't see the message "All tests completed", then there is something that needs to be fixed for you to get full credit. You can isolate the problem as follows:

>>> test_duplicates()
Finished testing duplicates!
...

and so forth. There is a test function for each of the functions you are to write. Please note: Passing the tests does not guarantee you full credit. There may be cases not covered in the tests we give you, and there are other requirements for your code that are stated in this assignment but not checked by the test file. It is your responsibility to think about whether your function definitions satisfy the requirements.

Problems

[2 pts] A dictionary is an unordered mutable collection of key/value pairs. It associates a key (for example a word) with a value (for example a definition for that word). Any particular key can appear at most once in a dictionary and keys must be immutable. While the keys in a dictionary are guaranteed to be unique, the associated values are not. In the file triplets.py, define a function triplets(d) that takes a dictionary d as input and returns the number of unique values that appear exactly 3 times. Hint: For any dictionary d, list(d.values()) returns a list consisting of all the values in d. You may also find it convenient to use the count method for lists: lst.count(x) returns the number of occurrences of x in lst.
Example usage:
```
     >>> letters = {1: "a", 2: "a", 3:"a"}
     >>> triplets(letters)
     1                              # because "a" appears thrice 
     >>> letters = {1: "a", 2: "b", 3:"a"}
     >>> triplets(letters)
     0                              # because there is no value (i.e. letter) that appears exactly three times
     >>> letters = {1: "z", 2: "z", 3: "z", 4: "z"}
     0                              # because "z" appears 4, not 3, times.
     >>> letters[4] = "a"           # add new values to the dictionary
     >>> letters[5] = "a"
     >>> letters[6] = "a"
     >>> triplets(letters)        
     2                              # "z" and "a" each appears exactly thrice
     
```
[4 pts] Recall that, one way to represent the nodes of a full binary tree is with a list, where the first element contains the root, the next two elements contain the next level of the tree (the children of the root), the next four elements contain the next level of the tree (two containing the children of the root's left child and two containing the children of the root's right child), the next eight elements contain the next level (the two children of each of the nodes at the previous level), and so on, depending on how many levels the tree has.

The binary tree above with nodes labeled with strings "alpha", "bravo", ... would be represented by the Python list:
```
 
   ["alpha", "bravo", "charlie", "delta", "echo", "foxtrot", "golf", "hotel", "india", "juliet", "kilo", "lima", "mike", "nova", "oscar"]   
     0          1       2         3          4       5         6        7        8        9        10       11     12      13      14     
   
```
Let us look at the indices of left children:
- The node at 0 has its left child at 1 (alpha's left child is bravo)
- The node at 1 has its left child at 3 (bravo's left child is delta)
- The node at 2 has its left child at 5 (charlie's left child is foxtrot)
- The node at 3 has its left child at 7 (delta's left child is hotel)
- The node at 4 has its left child at 9 (echo's left child is juliet)
Do you see a pattern? There are simple formulas that can be used to calculate the indices of a node's left child, right child, and parent from that node's index.
1. Define a function left_index(i) (in left_index.py) that, when passed the index i of a node, will return the index of that node's left child. (You do not need to worry about whether the node has a left child; when the node does not actually have a left child, the function should still return where its left child would be if it had one. You may assume that i is a non-negative integer.)
2. Define a function right_index(i) (in right_index.py) that, when passed the index of a node, will return the index of that node's right child. (You do not need to worry about whether the node has a right child; when the node does not actually have a right child, the function should still return where its right child would be if it had one. You may assume that i is a non-negative integer.)
3. Define a function parent_index(i) (in parent_index.py) that, when passed the index of a node, will return the index of that node's parent. (You may assume that i is a positive integer.) Hint: Think about how this part relates to the previous parts.
4. Define a function is_leaf(tree, i) (in leaf.py) that, when passed the list representation tree of a full binary tree and the index of a node i, will return True if the node has no children and False otherwise (a node with no children is called a leaf). You may assume that i is a non-negative index less than the length of tree. You may want to use some of the functions you defined in the previous parts.
  Example usage:
```
     >>> a = ["alpha", "bravo", "charlie", "delta", "echo", "foxtrot", "golf", "hotel", "india", "juliett", "kilo", "lima", "mike", "nova", "oscar"]
     ["alpha", "bravo", "charlie", "delta", "echo", "foxtrot", "golf", "hotel", "india", "juliett", "kilo", "lima", "mike", "nova", "oscar"]
     >>> is_leaf(a,0)
     False
     >>> is_leaf(a,13) 
     True
     
```
[2pts] The list representation for binary trees can be extended to non-full trees by using None to represent the "missing" nodes that would need to be added to make a full tree.

For example, the binary tree above can be represented by the Python list
```
   ["alpha", "bravo", "charlie", "delta", "echo", "foxtrot",  None , "hotel", "india", "juliett",  None , "lima", "mike",  None ,  None ]   
     0          1       2         3          4       5        6       7        8         9        10     11      12      13    14     
   
```
Note that since missing children can always be represented by None, the tree ["alpha"] is the same as the tree ["alpha", None, None].
In file missing_child.py write a recursive function missing_child(tree,i) that searches the subtree beginning at node i and returns a list of the labels of the nodes that have only one child. Leaves of the tree should not be included in this list. In defining missing_child(tree,i) you may want to make use of some of the functions you defined in Question 1. You may assume that the tree will always be non-empty.
Example usage:
```
     >>> a = ["alpha", "bravo", "charlie", "delta", "echo", "foxtrot", None, "hotel", "india", "juliet", None, "lima", "mike", None, None]
     ["alpha", "bravo", "charlie", "delta", "echo", "foxtrot", None, "hotel", "india", "juliett", None, "lima", "mike", None, None]

     >>> missing_child(a, 0)
     ["echo", "charlie"]

     >>> missing_child(a, 1)
     ["echo"]

     >>> missing_child(a, 2)
     ["charlie"]

     >>> b = ["apple", "banana", "cherry", None, "date", None, None]
     ["apple", "banana", "cherry", None, "date", None, None]

     >>> missing_child(b, 0)     # draw the tree b to check the answer
     ["banana"]

     >>> c = ["aardvark", "bear", None, "cat", "dog", None, None, "eel", None]
     ["aardvark", "bear", None, "cat", "dog", None, None "eel", None]

     >>> missing_child(c, 0)     # draw the tree c to check the answer
     ["aardvark", "cat"]
     
```
You should solve this problem in stages:
- What is the base case? What value should be returned in that case? Write code that handles this base case.
- Test your program on the tree ["aardvark"] with initial index 0; the result should be [].
- What is the recursive case? How should you combine the results of the recursive calls? Add code to handle this case.
- You should get the same result for the tree ["aardvark", None, None] as for the tree ["aardvark"]. Do you see why?
- Test your program on the tree ["aardvark", "bear", None]. The result shold be ["aardvark"].
- Test your program on the tree ["aardvark", "bear", "cat"]. The result should be []. Draw this tree.
- Test your program on the tree ["aardvark", "bear", None, "cat", None, None, None]. The result should be ["aardvark", "bear"].
- Test your program on the tree ["aardvark", "bear", "cat", None, "dog", None, None]. The result should be ["bear"].
- If your program fails one of these tests, figure out how to change the code to fix the problem, and re-run all the preceding tests to make sure they still work.
- It might help to put the statements print(i, " "); print(tree) at the beginning of your function so you can trace the recursive calls.
- Continue adding tests until you are confident your program is correct.
[2 points] In a Binary Search Tree, each node stores a value that is greater than that of all of the nodes reachable through its left child and that is less than that of all of the nodes reachable through its right child. The examples below is a binary search tree. (We will assume that the tree does not hold two nodes with the same value.)

A Binary Search Tree can be stored using a list just as we did in the previous problems.

The following is an algorithm for searching a list tree encoding a binary search tree to determine whether it contains a node with the value key.
1. Set curr_index to the index of the root node of the tree.
2. While curr_index is less than the length of tree and tree[curr_index] is not None, do the following:
  1. Set curr_value to the value of the node at curr_index in tree.
  2. Return True if curr_value is equal to key.
  3. Set curr_index to the index of the left child of the node at curr_index if key is less than curr_value.
  4. Set curr_index to the index of the right child of the node at curr_index if key is greater than curr_value.
3. Return False.
Define a function bst_search(tree,key) (in bst_search.py) that uses this algorithm to determine whether the value key occurs in tree, the array representing a binary search tree. Call the functions left_index and right_index that you defined in problem 1 to set curr_index in substeps C and D above. Again, you may assume that the function will always be called with a non-empty list.

Example usage:
```
         >>> bstree = [84,41,96,24,52,91,98,10,26,43,None,85,94,None,None]
         [84,41,96,24,52,91,98,10,26,43,None,85,94,None,None]
         >>> bst_search(bstree, 52)
         True
         >>> bst_search(bstree, 51)
         False
         >>> bst_search(bstree, 41)
         True
         >>> bst_search(bstree, 97)
         False
       
```
Submission

You should now have a pa6 directory, containing:
1. triplets.py
2. left_index.py
3. right_index.py
4. parent_index.py
5. leaf.py
6. missing_child.py
7. bst_search.py
Zip up your directory and hand it in.

15-110 Summer 2015

Programming Assignment 6

Overview

Problems

Submission