The assignments given for this module are described below. Although the assignments could be done in C++ which I was much more familiar with at the time, I decided it would be uselful experience to write these assignments in C.
- Implement a double-hashing hash table in C or C++ with your own hash functions. Evaluate it against typical criteria using some test data. Write a brief summary.
- Find an interesting implementation of a hash table. Review it in a formal written report.
- Implement any sorting algorithm of your choice and also implement quicksort.
- Comment your code to demonstrate you understand the sorting process. Summarise each sort in your report to show your understanding of each algorithm and how this relates to your code.
- Create an array of test data to run your sorting functions on. You may manually assign array values, or generate them randomly. e.g. an array of integers.
- Count the number of investigated elements or probes made by each of the search functions on the test data.
- Put the results in a table comparing your implementations, giving your test results, and the big-O complexities. State the size of the test array used, and if it was randomly distributed, mostly sorted, or sorted but in reverse.
- The goal of this assignment is to build a program with the data structure and functions of a typical binary search tree.
- The goal of this assignment is to write a program that represents the graph, shown in Figure 1, as a data structure, and write C or C++ implementations of Depth-First Search and Dijkstra’s Algorithm, which you will then call to traverse the graph.
- Exact input and output requirements are given. Comment out any test code that produces other output before submission.
- Traversal sequences should be correct with respect to your system for ordering the edges - therefore the correct sequence for your program might not exactly match the example output. Do not use any pre-made graph data structures or algorithms from libraries e.g. from Boost.
