Description
CSCI 335 First assignment
Create and test a class called Chain. A chain is just a series of items, e.g. [2 7 -1 43] is a chain
containing four integers.
The purpose of this assignment is to have you create a vector-like class from scratch, however,
so you may not use vector, list or other classes from the STL here. Please note that chains are
similar in many respects to vectors of items. Unless you get permission from me, don’t include
any libraries except iostream and cstdlib.
Pay special attention to Weiss’s “big five,” the destructor, copy constructor, copy assignment
operator, move constructor and move assignment operator. Include cout statements at the
beginning of the constructors and assignment operators in order to see when these functions
are being called.
When your class is complete, the following code should work, with results as commented.
Insert this piece of code as is in your testing function.
Chain a, b, c; //Three empty chains are created
Chain d{10}; // A chain containing just one element: 10
cout << d; // Output is [ 10 ]
cout << a.Length() << endl; // yields 0 cin >> a; // User types [2 3 7]
cout << a; // Output is [2 3 7] cin >> b; // User types [8 4 2 1]
c=a; // Copy assignment
cout << c; // Output should be [2 3 7]
cout << a+b << endl; // Output is [2 3 7 8 4 2 1]
cout << a + 5; //Output is [2 3 7 5]
Chain e{c}; //Copy constructor
cout << e; //Output should be [2 3 7]
cout << a[1] << endl; //Should printout 3
c[1]=100; //Should change c
cout << c; //Should print [2 100 7]
cout << e; //Should print [2 3 7]
Chain f = GetChain()}; // GetChain() should be a function that returns by
value a Chain of some elements. Write this simple function.
cout << f; // Should print whatever GetChain() returned.
Csci 335 Assignment 2
Using and Comparing Tree Implementations
The goal of this assignment is to become familiar with trees and compare the performance
of the basic binary search tree with the self-balancing AVL tree as well as lazy vs non-lazy
deletion for the AVL tree. You will also work with a real world data set and construct a
generic test routine for comparing several different implementations of the tree container
class. You may use the book’s implementation for the BST and AVL trees but will have to
implement lazy deletion variants yourself.
First, create a data structure named SequenceMap that has as data members a string and a
set of strings. This will be the data that we store in our trees and passed in to the template
tree classes. This class should be comparable using the string member as the comparison
key by overloading the operator< function. This class should also have a
merge(SequenceMap other) method that tells a search tree what to do in case of
duplicates, this is described below.
Second, modify the BST and AVL tree implementations to count the number of recursive
calls to the insert, contains, and remove methods. Also create a new template class that
implements the AVL tree using lazy deletion.
For this assignment you will receive as input two text files, rebase210.txt and
sequences.txt. After the header, each line of the database file rebase210.txt
contains the name of a restriction enzyme and possible DNA sites the enzyme may cut (cut
location is indicated by a ‘) in the following format:
enzyme_acronym/recognition_sequence/…/recognition_sequence//
You will create a parser to read in this database and construct a search tree. For each line
of the database and for each recognition sequence in that line, you will create a new
SequenceMap object that contains the recognition sequence as its search key and the
enzyme acronym in the set of strings and you will insert this object into the tree. In the case
of a duplicate on insertion, the search tree will call the x.merge(SequenceMap other)
function of the existing element, x, in the tree which will add the newly created other
SequenceMap’s enzyme acronym to the set of enzyme acronyms contained by the
SequenceMap in the tree.
Now create a small test program named queryTrees which will use your parser to create
a search tree and then allow the user to query it using a recognition sequence. If that
sequence exists in the tree then this routine should print all the corresponding enzymes
that activate on that recognition sequence. Note that the recognition sequence should
include the ‘-symbol which indicates the location of the cut.
Next, create a test routine named testTrees that does the following:
1. Parse the database and construct a search tree. Print the total number of recursive
calls to insert after processing the entire database.
2. Print the number of nodes in your tree �. Compute and print the average depth of
your search tree, i.e. the internal path length divided by �. Also print the ratio of
the average depth to log! �. E.g., if average depth is 6.9 and log! � = 5.0, then you
should print !.!
!.! = 1.38.
3. Search the tree for each sequence in the sequences.txt file. Print the total
number of successful queries and the total number of recursive calls to the
contains method.
4. Remove every other sequence in sequences.txt from the tree. Print the total
number successful removes and number of recursive calls to the remove method.
5. Recompute the statistics in step 2 and repeat the search in step 3 printing the
number of calls to contains. Note these should not change with lazy deletion.
You must write the test routine using templates (or inheritance) so each tree can be used
interchangeably. The trees should have identical interfaces. Code shared by both programs
in this assignment should be included or linked from a separate file. The tree classes
themselves should be well separated from the logic of the SequenceMap object.
Good design practices are an important part of the grade for this assignment.
Your programs should run from the terminal as follows:
queryTrees
testTrees
should be “BST” for binary search tree, “AVL” for AVL tree, and “LazyAVL” for AVL
with lazy deletion.
Create a table comparing the statistics you observed for each of the four search tree
variants. Include a caption comparing these results to what you would expect given the
analysis of these data structures.
Note: Because your program will be tested on Linux, you should make sure the input files
are in the Unix file format and you design your program to expect Unix formatted files.
These files already should be in Unix format but you can use the dos2unix and unix2dos
tools to convert them back and forth. (Mac OS X now uses the Unix convention)
CSCI 335 Third assignment
Hashing (30 points)
Implement quadratic probing and then run tests on the number of probes required at
various load factors to obtain a graph like the one shown in Figure 5.12.
For this assignment, results and analysis are particularly important. You’re not just
programming; you’re experimenting with a program and reporting on the results of those
experiments.
To keep things simple, you may assume that items to be stored are integers and that
there will never be more than 1,000 of them stored at any one time. Do not rehash.
Maps and Hashing (70 points)
(a) Implement the most efficient version of the “word puzzle” algorithm of section
(the one shown in Figure 4.72) using the STL map. Use the exact implementation
provided with the book. Your executable should run as follows:
./testMaps
where is a file that contains a list of words (dictionary).
1. Compute and print out the time it takes for the computation of the adjacent
words.
2. Prompt the user to provide a word, and then print out all its adjacent words.
Print out also the time it took for searching for that word.
(b) For this part of the assignment DO NOT use the STL map. Create your own
templated hash-map class that only supports lookup (find), insert and delete (you
can use lazy deletions) operations. You should also provide an operation that
visits all the elements in the hash-map (in the way they are stored in the hash
table). The hash-map (use quadratic probing) will store a key with an associated
value. Note that you need to provide a good hash function for strings. You don’t
have to implement iterators for your hash-map implementation. Now using your
own hash-map implementation, implement the most efficient version of the “word
puzzle” algorithm. Your executable should run as follows:
./testMyHashMap
The first argument is the list of words (dictionary) and the second argument an
integer that specifies the initial size of the hash table.
Provide the tests (1) and (2) as in part (a). Experiment with different initial sizes
(from very small, i.e. 51 to larger) and measure the change in running time.
CSCI 335 Fourth assignment
Priority queues (100 points)
You are asked to implement a binomial queue (bq) linked with a hash-table. You can use code
provided in the textbook. The bq is used for fast access of the minimum element and the hash-table
for fast access within the elements in the bq.
(1) Implement the binomial queue. For testing use the strings in the document file used in the
previous assignment. These would be the keys to be inserted into the priority queue.
Implement a hash-table of the keys that are already in the priority queue. So, for any pair
<key,p>, where p is the pointer of the the node that holds key in the priority queue, hash on
the key, and store the pair <key,p> in your hash table. Also note that for every insertion,
deleteMin, or merge the hash-table needs to be updated as well. As part of this
implementation you have to create a private function
find( key).
This function will return the pointer p that points to the node of bq that holds the key, or
nullptr if key is not in the bq.
(2) Count and print out the total number of comparisons and assignments executed for the
insertions of all the N elements into the binomial queue.
(3) Test the deleteMin() operation by applying a sequence of 10 deleteMin() and by printing out
the result.
(4) Test the function find() as follows: Prompt the user to input a string key. Execute the private
function find(key). If find returns a pointer to a node that indeed holds key printout that
find() was successful. Otherwise, printout that find() did not find the key.
(5) You are ready to implement now the remove(key) operation. For a given key, find its
position p (p is a pointer) in the priority queue using the hash table. If the key is found delete
it from the bq (Hint: your code should percolate the key up all the way to the root and then
delete the root). Test your implementation by applying a sequence of remove(key)
operations, and verify their correctness. For instance after remove(key), find(key) should
return “not found”. Prompt the user 5 times to input a key. Execute then the remove(key)
operation and verify (by printing whether the removal was successful or not).
(6) Write a faster insert(key) function for the binomial queue. In order to achieve that you have
to modify the merge() function and make it specific to the merging of one element only.
Csci 335 Assignment 5
Graph Representation
You will read a directed graph from a text file. Below is an example:
Graph1.txt
5
0 1 0.2 3 10.1 4 0.5 -1
1 0 1.5 -1
2 1 100.0 3 50.2 -1
3 -1
4 1 10.5 2 13.9 -1
The first line is the number of vertices � (= 5 in this example). Each vertex is represented by an
integer from 0 to � − 1.
For each vertex you have a list of the adjacent vertices with positive edge weights. Each list
terminates with -1 to indicate the end of the line. For instance, in the above example, vertex 0 is
connected to vertex 1 (edge weight 0.2), to vertex 3 (edge weight 10.1) and to vertex 4 (edge
weight 0.5).
Represent a graph using an adjacency list. Read the vertices and edges from a text file.
Dijkstra’s Algorithm
Implement Dijkstra’s Algorithm using a priority queue.
Write a program that runs as follows:
findPaths
This program should use Dijkstra’s Algorithm to find the shortest paths from a given starting vertex to all
vertices in the graph file. The program should then continuously prompt the user to specify a target
vertex. It will then print the sequence of vertices along the shortest path from the starting vertex to the
target vertex as well as the total cost of the path.
