Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit



CS 160 Take-Home Exam, Fall 2021


1.    (Sorting, 9 points) Design a random, typical array of at least 7 elements (numbers, characters,     strings … your choice) including one duplicate element that occurs at least twice in your array.     Use this array as the starting point in the tracing of each of the algorithms in this question. Also, use subscripts to identify duplicate elements, such as A1 and A2,to keep track of these elements  and show the algorithms’ stability properties.

For each of the sorting algorithms covered in chapter 2, except 3-way quick sort (since it is for arrays mostly consisting of duplicate elements, not the scope here)

a.    give a high-level description of how it work in a few sentences, but not code or pseudo- code.

b.   State the characteristics of best-case inputs and  the algorithm’s best-case time                complexity, and the characteristics of worst-case inputs the algorithm’s worst-case time complexity.

If the algorithm works the same for all arrays and doesn’t really have best-case or worst- case inputs, explain why that is so, and give the algorithm’s time complexity.

c.    Trace the sorting algorithm on your random, typical array, and show all the steps from     the start to the sorted array.  Also, choose an intermediate step to explain the invariants of the sorting algorithm, such as which part of the sub-array is sort, what about the          other elements, etc.

 

2.    (BST, 3 points) Assume that the following isBST( ) method is inside a BST class. This method has logic bugs and produces correct results from some trees and wrong results for other trees.


For each of the following subproblems, try to design a Binary tree with 7 or more nodes, with   the required outcome from the faulty isBST() method. Just draw the tree and explain why the isBST() method produces the specified outcome. You don’t need to show how the tree is          created.   If no binary tree with the required properties exists, explain why that is the case.


//Assume the following code has no syntax error and runs

public boolean isBST( ) {

return isBST (root);

}

private boolean isBST (Node x) {

if (x == null)

return true; //this is fine, a null tree is a BST as it does not violate any BST properties

Node leftChild = x.left;

Node rightChild = x.right;

boolean leftOkHere = (leftChild == null) || (leftChild.key < x.key);

boolean rightOkHere = (rightChild == null) || (rightChild.key > x.key);

boolean okHere = leftOkHere & rightOkHere;

if (!okHere)

return false;

else

return isBST(leftChild) & isBST(rightChild);

}

(cases getting correct results)

a.    Binary tree A is a general binary search tree and isBST( ) returns true, correctly

b.    Binary tree B is a left-leaning red-black tree and isBST( ) returns true, correctly

c.    Binary tree C is not a binary search tree and isBST() returns false, correctly (cases getting incorrect results)

d.    Binary tree D is a binary search tree and isBST() returns false, incorrectly

e.    Binary tree E is not a binary search tree and isBST() returns true, incorrectly

(If you want to know how to solve this problem correctly, check out algs4’s BST class and    relevant methods after the finals)

3.    (Hash Attack, 1.5 points) Consider the following hashCode( ) function for the String class:

 

 

public int hashCode() {

int hash = 0;

for (int i = 0; i < length(); i++)

hash = (hash * 31) + charAt(i);

return hash;

}

a.    Compute the hash code for the String “Aa” . Note that the Ascii codes for A and a are 65 and

97 respectively. Show your formula and result for computing the hash code for “Aa”.


b.    Compute the hash code for the String “BB” . Note that the Ascii code for B is 66. Show your

formula and result for computing the hash code for “BB”.

c.    What do you think about the hash codes for AaBBBBAaAaBB and BBBBBBBBBBBB? Are they equal or not?

d.    Find information from the Princeton textbook and/or slides about hash attack and use your own words to explain this concept.

4.    (Connected Components, 2 points) Recall that movies.txt is a data file with information about     movies and actors. It is used as an example input for SymbolGraph. Let’s get more information   from the corresponding symbol graph, again using movies.txt. You can start with the algs4 code and make changes when needed. You don’t need to submit the modified code.

a.    Find the numbers of nodes, edges, actors and movies. Note that the graph nodes             include both actors and movies. You need new code to compute and print the numbers of actors and movies. Briefly explain how you find all these numbers, and report the       numbers here.

b.    Find the number of connected components and sizes of all the connected components     in the movies symbol graph.  You can start with the CC class given in the algs4. On my       computer, this code crashed because of deep recursions.  Instead of using dfs, figure out how to use bfs to solve the connected components.

 

Describe your bfs algorithm for this problem and write down your results, including the number of connected components and the sizes of the connected components.

Please note that bfs and dfs are different algorithms and are not interexchange. While    some problems can be solved by either, some other problems such as the shortest path problem on unweighted graphs  can only be solved by bfs and the topological order        program on DAGs are only be solved by dfs.

5.    (Minimum Spanning Trees, 1.5 points)  Create a weighted graph with at least 7 nodes, pick one MST algorithm, give a high-level description of the algorithm, trace the algorithm on your           weighted graph, showing the intermediate results and the final MST.

 

6.    (Shortest  Paths, 1.5 points)  Create a weighted digraph with at least 7 nodes, pick one shortest path algorithm, give a high-level description of the algorithm, and , trace the algorithm on your weighted digraph and a source node, showing the intermediate results and the final shortest     path tree.

 

7.    (Real World Graph Applications, 1.5 point) Describe one real world problem that you are                interested in, can be formulated as a graph problem, and has not been covered in our class or      textbook. First describe the problem, then give its graph formulation:  what are the nodes and     edges,  and what is the underlying graph problem (e.g. finding cycles, connected components, or shortest paths)

 

8.    (Graph of data structures and algorithms, 5 points) We have covered and used many important data structures in this class: stacks, queues, union-find (aka disjoint sets), priority queues


(including the basic and indexed versions),  binary trees, hasthables, hashsets,  and graphs         (undirected/directed, unweighted/weighted), not explicitly including arrays or linked lists since they are everywhere. We have also learned a good number of graph algorithms, including the   smaller algorithms in the first two sections e.g. on connected components & topological order.

In this problem, draw a graph that reflects the connectivity between data structures used in this course and graph algorithms in chapter 4. Note that edges can be

•    from simpler data structures (E.g. queues and stacks) to more complex data structures (e.g. BSTs, graphs),

•    from data structures to algorithms, for example from queues to bfs and stacks to dfs (implicitly through recursions in some implementations,

•    from utility algorithms (e.g. bfs and dfs) to client, derived algorithms (e.g. connected components),

Some people might prefer to also draw edges from stacks and queues to connected                    components. That’s fine, especially if your graph does not get too cluttered. Conceptually,  we can use the influence concept in the last coding exam to infer the relationship from stacks and queues to connected components through dfs and bfs.

The graph can become quite big with many nodes and edges. You can use multiple drawings to represent the whole graph. Make sure each drawing is clear, with its node names and edges      easily readable, in fonts 11 or up. Approximation in handwriting is fine.

 

For each edge in your graph, label it with a number, and give a brief explanation (e.g. in one or two sentences) for that  edge, and put these explanations in a list, such as the following.

•    Edge 1: stacks are used as a supporting data structure in Graph, and by inference, also the WeightedGraph (not explicitly shown with an edge)

•    Edge 2: stacks are used in dfs

•    …

As you can see, there is overlapping information here. You can exercise your judgement in selecting nodes and edges, to make your graph comprehensive and clear.