Learning Profile for Assignment #2 - Computer Science 272: Data Structures and Algorithms

Name: Mo Khan Student ID: 3431709

Question 1

Problem Statement

Design an algorithm for the following operations for a binary tree BT, and show the worst-case running times for each implementation:

preorderNext(x): return the node visited after node x in a pre-order traversal of BT.
postorderNext(x): return the node visited after node x in a post-order traversal of BT.
inorderNext(x): return the node visited after node x in an in-order traversal of BT.

Description of the Code

I chose to implement the binary tree traversal using a Visitor design pattern. The traverse function accepts a binary tree node, a callback function and the type of traversal to perform.

The traversal uses recursion to visit each node in the binary tree in linear time. The space complexity is determined by the size of the tree because each recursive call adds another frame to the call stack.

Errors and Warnings

I wrote unit tests to to cover several different happy path scenarios and to cover the base case conditions of the recursive function.

モ cd 01/ && make clean && make test && ./build/test
rm -fr build
mkdir build
clang    -c -o build/binary_tree.o binary_tree.c
clang    -c -o build/binary_tree_test.o binary_tree_test.c
clang build/binary_tree.o build/binary_tree_test.o -lcgreen -o build/test
Running "main" (21 tests)...
  "binary_tree_tests": 72 passes in 10ms.
  Completed "main": 72 passes in 10ms.

Sample Input and Output

The file 01/main.c includes a small program that provides and example of the tree traversal. It starts by print out the binary tree to the console then prints the order each node is visited during each type of traversal.

モ cd 01/ && make clean && make && ./build/program
rm -fr build
mkdir build
clang    -c -o build/binary_tree.o binary_tree.c
clang    -c -o build/main.o main.c
clang build/binary_tree.o build/main.o -o build/program
=== COMP-272 - Assignment 02 - Question 01 ===
(100)
  (200)
    (400)
    (500)
  (300)

=== Pre order traversal ===
100 200 400 500 300

=== In order traversal ===
400 200 500 100 300

=== Post order traversal ===
400 500 200 300 100

Discussion

This version of the traversal requires the calling code to capture each node that is visited during the traversal. This ensures that the traversal operates in O(n) time but allows the calling code to cache the result of the traversal in a way that makes sense for it.

Question 2

Problem Statement

Design a recursive linear-time algorithm that tests whether a binary tree satisfies the search tree order property at every node.

Description of the Code

To determine if a binary tree satisfies the binary search tree order property I needed to check each node in the binary tree to make sure that the item in the left side of the node is less than the node itself and that the item in the right side of the node is greater than itself. Each descendant node must also be greater or less than each ancestor node depending on which side of the tree that node is relative to the ancestor.

To perform this check I kept track of the minimum and maximum values that any node can be while traversing down the tree.

For example, when traversing down a left sub tree each node in the left sub tree must be between the minimum value and the current node. When traversing down the right subtree each node must be between the value in the current node and the maximum value.

To kick start the recursive call I specified an arbitrary min and max values that matched the boundary of the size of the integer. So a range (2^32/2 * -1) and (2^32/2 - 1) was used.

The base case for the recursive call is when the subtree that is visited is a NULL.

Errors and Warnings

I wrote unit tests to test the happy day scenarios, the base case and a couple of edge cases.

モ make clean && make test && ./build/test
rm -fr build
mkdir build
clang    -c -o build/btree.o btree.c
clang    -c -o build/btree_test.o btree_test.c
clang build/btree.o build/btree_test.o -lcgreen -o build/test
Running "main" (7 tests)...
  "binary_search_tree_tests": 7 passes in 3ms.
  Completed "main": 7 passes in 4ms.

A full list of tests cases can be found in 02/*_test.c.

Sample Input and Output

To make it easier to see that the checks are working as expected, I included a program in 02/main.c that will build a binary search tree and a regular binary tree and check to see if either matches the properties of a binary search tree.

Sample output can be seen below:

モ cd 02/ && make clean && make && ./build/program
rm -fr build
mkdir build
clang    -c -o build/btree.o btree.c
clang    -c -o build/main.o main.c
clang build/btree.o build/main.o -o build/program
=== COMP-272 - Assignment 02 - Question 02 ===
Binary Search Tree
---------
10
  -5
    -10
     5
  25
    23
    36
Is a binary search tree? y

Binary Tree
---------
10
   0
    -1
    21
  25
    16
    32
Is a binary search tree? n

Bye

Discussion

The recursive version of the check operates in O(n) time and O(n) space. The space is due to the allocation of a stack frame for each recursive call in the call stack. An iterative version of this same algorithm would also operate in linear time but could benefit from O(1) space by using pointers.

Question 3

Problem Statement

Illustrate what happens when the sequence 1, 5, 2, 4, 3 is added to an empty ScapegoatTree, and show where the credits described in the proof of Lemma 8.3 go, and how they are used during this sequence of additions.

In an unbalanced binary tree the insertion of 1,5,2,4,3 would look like the following:

The above diagram illustrates some negative consequences for having an unbalanced binary tree. This includes needing to visit more nodes than necessary to perform a search and can lead to worst case searches of O(n) time.

For example:

The scapegoat tree allows the binary tree to remain balanced so that searches can operate in O(logn) time. It also does this by maintaining constant space O(1). Other, balanced binary search tree algorithms like the AVL tree or Red-Black tree typically require adding additional data to each node in the tree in order to keep the tree balanced.

The insertion of 1,5,2,4,3 into a scapegoat tree would look like the following:

Insert 1:
           (1)

Insert 5:
           (1)     1/2
              \
              (5)

Insert 2:
           (1)     2/3 > 2/3: false
              \
              (5)  1/2 > 2/3: false
              /
            (2)

Insert 4:
           (1)     3/4 > 2/3: true (scapegoat)
              \
              (5)  2/3 > 2/3: false
              /
            (2)    1/2 > 2/3: false
              \
              (4)

The next step is to rebalance from the scapegoat node.

Rebalance:

collect nodes in sorted order: [1,2,4,5]
find new root: size/2 = 4/2 = 2
2 is the second node and is selected as the new root
[1] is moved to the left subtree
[4,5] are moved to the right subtree

          (2)
         /   \
       (1)   (4)
               \
               (5)

Insert 3:

          (2)       3/5 > 2/3: false
         /   \
       (1)   (4)    1/3 > 2/3: false
            /   \
          (3)   (5)

Description of the Code

The code implements the regular binary tree insertion but it does not implement the rebalancing.

Errors and Warnings

The tests can be viewed in 03/*_test.c.

モ make clean && make test && ./build/test
rm -fr build
mkdir build
clang    -c -o build/btree.o btree.c
clang    -c -o build/btree_test.o btree_test.c
clang build/btree.o build/btree_test.o -lcgreen -o build/test
Running "main" (6 tests)...
 1
   5
     2
       4
         3
  "binary_search_tree_tests": 20 passes in 3ms.
Completed "main": 20 passes in 3ms.

Sample Input and Output

The example program in 03/main.c displays a visual representation of an unbalanced and a balanced binary search tree.

モ cd 03/ && make clean && make && ./build/program
rm -fr build
mkdir build
clang    -c -o build/btree.o btree.c
clang    -c -o build/main.o main.c
clang build/btree.o build/main.o -o build/program
=== COMP-272 - Assignment 02 - Question 03 ===
Tree 1: unbalanced tree
 1
   5
     2
       4
         3
Tree 2: balanced tree
 3
   2
     1
   4
     5
Bye

Discussion

Rebalancing a tree can be a tricky operation and it can slow down insertions into the tree. During rebalancing it is important to choose a new root to reduce too much rebalancing operations.

Question 4

Problem Statement

Implement a commonly used hash table in a program that handles collision using linear probing.

Using (K mod 13) as the hash function, store the following elements in the table:

{1, 5, 21, 26, 39, 14, 15, 16, 17, 18, 19, 20, 111, 145, 146}.

Description of the Code

To implement a hash table I chose to store a linked list in each bucket and perform a linear, O(n), scan to find the correct node.

This could have been optimized further by using a balanced binary search tree and performing a binary search to find the correct node when a collision occurs.

Each node in the linked list is stored as a 2-Tuple (two-ple) to store the key and associated value.

Errors and Warnings

Unit tests for the Tuple, List and Btree can be found in the corresponding files with a 04/*_test.c suffix.

モ cd 04 && make clean && make test && ./build/test
rm -fr build
mkdir build
clang -std=c99   -c -o build/hash.o hash.c
clang -std=c99   -c -o build/list.o list.c
clang -std=c99   -c -o build/tuple.o tuple.c
clang -std=c99   -c -o build/hash_test.o hash_test.c
clang -std=c99   -c -o build/list_test.o list_test.c
clang -std=c99   -c -o build/tuple_test.o tuple_test.c
clang build/hash.o build/list.o build/tuple.o build/hash_test.o build/list_test.o build/tuple_test.o -lcgreen -o build/test
Running "main" (13 tests)...
  "hash_table_tests": 20 passes in 2ms.
  "list_tests": 15 passes in 3ms.
  "tuple_tests": 2 passes in 1ms.
Completed "main": 37 passes in 6ms.

Sample Input and Output

An example program is included in 04/main.c that prints a visual representation of the content of the hash table.

モ cd 04 && make clean && make && ./build/program
rm -fr build
mkdir build
clang -std=c99   -c -o build/hash.o hash.c
clang -std=c99   -c -o build/list.o list.c
clang -std=c99   -c -o build/tuple.o tuple.c
clang -std=c99   -c -o build/main.o main.c
clang build/hash.o build/list.o build/tuple.o build/main.o -o build/program
=== COMP-272 - Assignment 02 - Question 04 ===
Insert items into hash
(1:10) (5:50) (21:210) (26:260) (39:390) (14:140) (15:150) (16:160) (17:170) (18:180) (19:190) (20:200) (111:1110) (145:1450) (146:1460)
Inspect hash table
 0: [(26:260)(39:390)]
 1: [(1:10)(14:140)]
 2: [(15:150)(145:1450)]
 3: [(16:160)(146:1460)]
 4: [(17:170)]
 5: [(5:50)(18:180)]
 6: [(19:190)]
 7: [(20:200)(111:1110)]
 8: [(21:210)]
 9: [(nil)]
10: [(nil)]
11: [(nil)]
12: [(nil)]
Retrieve each item from the table
(1:10) (5:50) (21:210) (26:260) (39:390) (14:140) (15:150) (16:160) (17:170) (18:180) (19:190) (20:200) (111:1110) (145:1450) (146:1460)
Bye

Discussion

Choosing to back the hash table with a linked list made it easier to implement the code but it does come with the cost of time complexity.

By using a balanced binary search tree the time to look up a key would have been O(1) (compute hash) + O(logn) i.e. O(logn). Using, a linked list changes the time complexity to O(1) + O(n) i.e. O(n).

Question 5

Problem Statement

Create a subclass of BinaryTree whose nodes have fields for storing preorder, post-order, and in-order numbers. Write methods preOrderNumber(), inOrderNumber(), and postOrderNumbers() that assign these numbers correctly. These methods should each run in O(n) time.

Description of the Code

I chose to write this assignment in C, so the notion of subclassing and inheritance does not apply.

To accommodate the problem statement, I updated the binary tree struct to include an integer array that can store up to 32 entries. Each array includes a cached copy of the traversal order for pre order, in order and post order traversals.

To fill the cache, the function btree_(pre|in|post)_order_number must be called. The cached traversal is stored in the root of the tree that is provided.

I chose to use a Stack to perform the traversal in an iterative way. In previous implementations of the traversal algorithm for the other questsions in this assignment I chose to use recursion. This implementation explicitly uses a stack instead of implicitly through stack frames in the call stack.

Errors and Warnings

Unit tests for this can be found in 05/*_test.c.

モ make clean && make test && ./build/test
rm -fr build
mkdir build
clang -std=c99   -c -o build/btree.o btree.c
clang -std=c99   -c -o build/stack.o stack.c
clang -std=c99   -c -o build/btree_test.o btree_test.c
clang -std=c99   -c -o build/stack_test.o stack_test.c
clang build/btree.o build/stack.o build/btree_test.o build/stack_test.o -lcgreen -o build/test
Running "main" (14 tests)...
  "btree_tests": 42 passes in 5ms.
  "stack_tests": 10 passes in 2ms.
Completed "main": 52 passes in 7ms.

Sample Input and Output

A sample program can be found in 05/main.c that prints out the traversal for an example tree.

モ cd 05 && make clean && make && ./build/program
rm -fr build
mkdir build
clang -std=c99   -c -o build/btree.o btree.c
clang -std=c99   -c -o build/stack.o stack.c
clang -std=c99   -c -o build/main.o main.c
clang build/btree.o build/stack.o build/main.o -o build/program
=== COMP-272 - Assignment 02 - Question 05 ===
10
   5
     3
     7
  15
    12
    18
Pre order traversal:
10 5 3 7 15 12 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

In order traversal:
3 5 7 10 12 15 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Post order traversal:
3 7 5 12 18 15 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Bye

Discussion

Allocating space for 32 values for the pre order, in order and post order representation for each node in a binary tree is quite wasteful.

An alternative implementation might have returned a linked list instead of storing this data in an array on each node.