Assignments for Data Structures II
Important Note: All homework problems must be submitted as files in your class directory. They will be graded on-line. Unless otherwise stated all "written" assignments are due one week after they are assigned in class and all programming assignments are due two weeks after they are assigned in class.
- Review the contents of the Getting Started web page.
Binary Trees
- Read Chapter 6 - Binary Trees
Do exercises 2, 3, 4, 5b,d, 7, 9, 16, 23 and 24 on pages 290 - 293
- Program #1 - Finish the BST Sort we programmed in lab, test it with large datasets and compare it to BubbleSort. We programmed BubbleSort last semester and used several functions to generate large data sets and time the program. Use these functions to test BSTSort and to compare BSTSort to BubbleSort. Report your findings in a text file that is in the same folder as BSTSort in Programs folder.
- Program #2 - Automated Phone Book implemented with a Binary Search Tree
Your program will create a GSS (Generic Storage Structure) class. GSS will be implemented as a Binary Search Tree. The class definitions for GSS are in GSS.h. Much of the code to implement the API (methods for the binary search tree) are located in GSS.cpp
NOTE: For this year we will simply use bintree.exe as a model rather than the more complex one described above.
- Program #3 - HeapSort
HeapSort is a worst-case N*log2(N) sort.
Your program will have a driver similar to the one described for MergeSort above. After
the numbers are read into an array your program will
- insert each data item, one by one, into a heap and then
- dequeue (remove) each item and place it back into the array
Since a heap is an implementation of a priority queue the data will be extracted in
order; thus sorting the data.
Multiway Trees
- Read Chapter 7 - Multiway Trees
(omit Bit-Trees, 2-4 Trees, vh-Trees)
Do exercises 1, 2, 3, 5, 8, 10, 14 and 19 on pages 369 - 370
- Lab 3 - Create a balanced binary tree- Top to bottom and left to right
Your program will
- Read in randomly generated integers into an array
- Sort them
- Create a balanced binary tree - Top to bottom and left to right
You can accomplish this by writing a function called rootindex that takes as input the total number of data values, N, and returns the number of nodes less than the root. This is the index of the root.
For example, if the total number of nodes is 13 and they are numbered 0 - 12 then there are 7 nodes less than the root node so the root of the tree is in position 7.
You can then perform this same operation recursively with the left subtree and the right subtree to complete the construction of the tree.
The trick here is, of course, to be able to write the function that returns the root index given the number of values.
Let the Binary Search Tree we are creating be named BST.
Observe that a perfectly balanced, top to bottom, left to right tree, consists of a complete binary tree (call it CBT) plus one more level containing 0 or more nodes/values.
Let r be the root of BST (and CBT). Name the left subtree of CBT, LS, its right subtree RS and let N be the number of values in the full data set. Finally let |X| be the number of nodes in the tree, X and let lg be log2.
|CBT| = 2⌊lg(N)⌋-1
|LS| = 2⌊lg(N)⌋-1-1 = |RS|.
The number of nodes at the bottom level is N - |CBT|.
The number of nodes at the bottom level less than the root is N - |CBT| - the number of nodes greater than the root. So, in other words, The number of nodes at the bottom level less than the root is
min(N - |CBT|, 2⌊lg(N)⌋-1)
where the second parameter is the max possible number of nodes at the bottom level less than the root.
This is because the number of leaves in a complete binary tree is equal to one more than the number of internal nodes in the tree.
So, the total number of nodes less than the root is |LS| + min(N - |CBT|, 2⌊lg(N)⌋-1).
Sorting
- Read Chapter 9 - Sorting (We will return to chapter 8 later)
Do Exercises 6, 12, 14 and 15 on pages 520-521.
- Lab 4 - Write and test the function, KSmall, which finds the kth smallest number in a list
See a further description here
- Program #4 - QuickSort and MergeSort Comparison
MergeSort Description, QuickSort Description
Review the pseudocode for
Merge,
Recursive MergeSort and Nonrecursive Mergesort
- Read Chapter 8, Graphs
Do exercises 2, 5, 9, 14, 15, 16, 18, 24, 25, 26b, 28 (see pg 403), 31, 35, 43 on pages 465 - 469.
- Lab 6 - Read, store and write a graph
Your program, named Lab6, should do the following.
1. Ask the user for the name of a graph file
2. Read the graph data from the graph file into internal graph structures (graph, nodes, edges)
3. Ask the user for an output file name
4. Write the graph from the internal graph structures to an output graph file
For information on graph files and internal structures see GraphAlgs.htm.
Your C++ program will create classes for nodes, edges and graphs. I.e., we will be creating ADTs for nodes, graphs and edges.
The first line of a graph file contains the number of nodes in the graph and a flag that indicates whether the graph is directed. It is followed by a list of edges (one edge per line) which is placed into our internal graph representation consisting of the following:
- a graph which is an array of nodes, together with the number of nodes and a "directed" flag.
- a node which consists of 3 components; a string of information about the node, the number of nodes in the adjacency list and a pointer to a list of incident edges.
- a linked list of edges for each node. Each edge consists of the edgeweight, the destination node and a pointer to the next edge in the list.
- Lab 7 and Program #5 - Implement Dijkstra's Algorithm
Dijkstra's Algorithm is a single source shortest path algorithms for weighted graphs with non-negative edge-weights.
You may find a pseudocode solution to Dijksta's Algorithm in GraphAlgs.htm along with pseudocode for the other functions you will need to read in and store a graph. Recall that this was done in our previous lab.
Your program should ask the user for the name of a file containing an undirected graph file (as described earlier) and read in and store the graph. Then the program should ask the user for the source node index and the destination node index. Finally it should write out the length of the path from the source node to the destination node followed by the actually path as a sequence of edges.
- Lab 8 - Implement the WFI all to all shortest path algorithm
- Generate a random directed or undirected graph with nonnegative edgeweights written to a file.
- Read the graph file into an NXN array (an adjacency matrix) where N is the number of nodes in the graph
The (i,j) cell of the adjacency matrix will contain the cost of the best known path from i to j together with the predecessor vertex of j in the path. Initially this will be the weight of edge i,j if the edge exists in the graph. Initialize the diagonal to 0 and all other cells to -1 (∞).
- Write out the adjacency matrix of the input graph
- Execute WFI to find all shortest paths
- Write out the number of vertices and the time required to find all shortest paths
- Write the adjacency matrix as modified by WFI indicating all shortest paths.
The pseudocode for a "proper" way to generate a random graph is located in GraphAlgs.htm. However, we will be using a simpler method, in part, because this will generate graphs with separate components.
- Lab 9 and Program #6 - Implement Prim's Algorithm
You may find a pseudocode solution to Prim's Algorithm in GraphAlgs.htm along with pseudocode for the other functions you will need to read in and store a graph. Recall that these were done in a previous lab.
- Read Chapter 10 - Hashing
Do Exercises 1 and 14 on page 560.
- Program #7 - Hash Function Testing
The program that we did in lab (lab5) is located at cs-netlab-01.lynchburg.edu/courses/DataStII/Lab5.cpp
Your program #7 assignment on hashing is located in HashAssign2.htm
First read an explanation of collision resolution using chaining before attempting this assignment.
- Program #8 - Dictionary Word Look-up Using Hashing
In this assignment we will implement a dictionary word look-up using hashing. Your main menu will read in words from a dictionary file and store them in an array. You may use redirection of input at the DOS level and cin to get started on your program but you are required to use real C++ file input functions in the final version.
This program is a contest. The object of your program is to create an efficient hash function for words in the dictionary.
You will test your program/hash function on large text files.
- Ask the use for a file spec
- Open the file
- Initialize a word counter and a lookup counter
- while more words to read
- read in a word, increment the word counter
- use your hash function/algorithm to look up the word.
- increment the lookup counter by the number of lookups required
- end while loop
- Divide the lookup counter by the word counter
- report the result to the user.
You will be reporting the average number of lookups per word.
I will test your program on certain files I have and compare your results with your classmates' results. The smallest average number of lookups wins. This means it is absolutely critical that you count the number of words and the number of lookups properly.
Useful Resources
1. Here are a couple of hash functions that Marcus Wright found for us. They use the string function library so you may want to modify them for char* instead. You cannot be the "winner" if you use one of these but using one of these will not detract from your grade on this program.
2. I have a number of dictionaries located at ftp://cs-netlab-01.lynchburg.edu/ in the Dictionary folder. I suggest using either LongList.txt or ShortList.txt located in the WordPlay subfolder. LongList has almost 237,000 words and ShortList has almost 37,000 words. ShortList will suffice for our purposes.
3. You will find examples of C++ file I/O at
http://cs-netlab-01.lynchburg.edu/courses/IntroII/Programs/CopyFile/CopyFile.cpp
Top of this page 
Home page 
