Sample Programs

ICS-46: Data Structure Implementation and Analysis


The following is a list of zipped CLion project files (more might be added during the quarter). Please feel free to download, unzip, run, and study these programs (both their code and their run-time behavior). Programmers gain tremendous insight into all facets of programming by studying the code of other programmers (especially those with more experience; and I am happy to improve my code based on your observations -nothing is perfect). A good programmer typically makes elegant use of the required language features, resulting in smaller, more elegant code.

All downloadable projects are listed alphabetically; you can also search this page for keywords. All are zip files, so unzip them first. Most project files require the Download: standard course library which contains a variety of useful functions and classes. If you followed the CLion installation instructions, you should have already created the courselib folder in your workspace and populated it with these modules.


Download: Backtracking Problem Solving
These programs use generalized (recursive) backtracking to search an implicit solution tree. See the backtrack_exceptions and solver files, which contain the tools to solve any problem; use the problem_template file to build any new application (and see how it compares with the examples below). The n_queens files contain code to determine how to place N queens on a chessboard so that none can attack another). The satifiy files contains code to determine how to assign true and false values to variables in a formula to satisfy it -make it evaluated to true. The sudoku files contain code that reads a Sudoku puzzle from a file and determines how to assign 1-9 values to the empty cells in a Sudoku puzzle to satisfy its constraints.

Download: Testing all Data Types
This project folder contains drivers and GoogleTests for all five standard data types: Stack, Queue, PriorityQueue, Set, and Map. The code tests the array implementations of these data types supplied in the courselib, but it can be easily changed to test any other implementations. Recall that a runnable program can have only one main function: so, only one .cpp file can be uncommented (the code in all the others must be commented-out).

Download: Testing Binary Search Trees Empirically on Integers
This programs builds any number of binary search trees (of any size) from a random permutation of integers. It computes and displays a histogram of the number of tree of each height and the average number of probest to access all values.

Download: Testing Hashing Empirically on Strings
These programs test a hashing function (on std::string): the first uses chaining, computing a histogram of the number of values stored in each bin size and the average number of probes to access all values; the second uses open hashing (with either linear or quadratic probing), computing a histogram of the number of values requiring N probes the average number of probes to access all values (for a variety of increasingt load factors). Use the supplied hash function or your ownn, testing its ability to distribute the values among the bins for random strings.

Download: Testing Sorting Empirically
You must have Java installed to run this program. Run this Java program on a PC by double-clicking the double click me.bat file (see its contents and mimic their use on other operating systems). You can choose (rechoose) an array size, decide how to populate it with values, and run various O(N^2) and O(N Log N) sorting functions (specifying how many times to repeat the process): we can also run a radix sort. It will print the timings for the chosen sorting algorithm, and the average. Note that the clock is accurate to about 1 millisecond: antthing taking less time registers as 0.0 seconds.

Download: State Space Search
These programs (just one now) use a generalized state-space searching to solve various problems involving applying operators. See the solver file, which contains the tools to solve any problem (both using breadth-first and best-first searching); use the problem_template file to build any new application (and see how it compares with the examples below). The water_jugs files contain code to determine how to achieve one distribution of water in jugs, given a starting distribution. Examine the State::how_close function for a pure best_first solution and an A* solution: it typically examines some number of states between pure best-first and breadth-first) but guarantees an optimal solution.

Download: X (cross) Reference
This program produces a cross-reference list of all the words (separated by spaces) in a text file. It uses the map, priority queue, and stack classes from the ITC. The download includes a small data file on which to test the program.