Final Exam PDF

1. Fill in the worst, guaranteed, and best cases for each algorithm in bigO: Algorithm worst case best case guaranteed Left-leaning RB tree BST heapsort Mergesort Quicksort (pivot at start) Hash table (linear probing) Depth-first sear...

1. Fill in the worst, guaranteed, and best cases for each algorithm in bigO: Algorithm worst case best case guaranteed Left-leaning RB tree BST heapsort Mergesort Quicksort (pivot at start) Hash table (linear probing) Depth-first search Inserting in linked list: 2-3 tree Quick-union Insertion sort Selection sort Linked-list: 1. The following code is trying turn the doubly-linked list into a circular doubly-linked list. Complete the method transform(). Assume that each item is inserted to the end of the list. public class doublycircular{ private Node front; public class Node { private Node prev; private Node next; private int value; public Node(){} public void transform(){  } 2. describe the algorithm for concatenating two separate circular-linked list (no code). BST: 1. a. Draw a BST with the following order of insertions: 10 27 97 86 25 34 63 59 35 94 55 21 b. draw the tree from part a after keys 27 and 35 are deleted (inorder predecessor). c. write the pre-order traversal from part b. Red-black tree & 2-3 tree: 1. a. Draw a left-leaning RB tree with the following insertions: 99 43 82 91 45 6 38 8 33 11 b. draw the tree from part a as a 2-3 tree. Priority queue: 1. insert 75, 51, 7 to the following MinPQ below: 0 1 2 3 4 5 6 7 8 9 10 1 12 10 32 64 65 72 81 87 99 a. insert: 75 0 1 2 3 4 5 6 7 8 9 10 11 b. insert: 51 0 1 2 3 4 5 6 7 8 9 10 11 12 c. insert: 7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 2. delete min 3 times from part 1. a. deleteMin() 0 1 2 3 4 5 6 7 8 9 10 11 12 b. deleteMin() 0 1 2 3 4 5 6 7 8 9 10 11 c. deleteMin() 0 1 2 3 4 5 6 7 8 9 10 Hash tables: 1. complete the code for rehash and insert for separate chaining. The table needs to be resized when n/tablesize >= loadfactor. The hash function is (2 * key) % tablesize public class hash{ private Node[] table; private final int loadfactor = 2: private int n; public class Node{ private Node next; private int key; private int value;  public Node(int key, int value, Node next){} //assume that the constructor is complete } public hash(int capacity){} //the table is initialized in the constructor public void rehash(){//size is doubled when the table needs to rehash } //inserts the key and value into the table, no duplicates are allowed public void insert(int key, int value){ } 2. insert the following keys into a hash table using linear probing. Rehash and double the size of the array when n/m >=2. The initial size of the array is 6 33 31 46 67 74 35 0 88 34 Graphs: 1. Complete the following code to add an edge to an undirected graph using adjacency matrix: private Boolean[] adj[]; //assume that the adj is initialized and all elements are false public void addedge(int v, int w){ } 2. Complete the following code to perform a DFS in an undirected graph and check if there is a cycle from the source. public Graph(int v){}//graph is already created private ArrayList adj(int v){//returns all of the edges adjacent to v } private int V(){//returns the number of vertices } //Complete the method recursively private void dfs(Graph G, int source){ } //complete the method private boolean hasCycle(Graph G, int source){ } 3. Complete the code for bfs in a directed graph //assume that the graph is already set public void V(){} returns the vertices in the graph public void bfs(Graph G, int source){ } 4. Describe the algorithm to find the indegree and outdegree of a vertex 5. Assume an undirected Graph is constructed with adjacency list representation, show the vertex-indexed array of linked lists built by reading the input depicted at right. The first integer 15 represents V, the number of vertices; the second integer 25 represents E, the number of edges. The remaining input lines are the edges to add in sequence. When adding an edge to the linked list, add it to the front. 15 25 02 23 50 14 11 13 46 12 13 14 12 86 75 29 96 10 12 71 8 13 19 0 12 34 49 52 9 12 41 82 1 14 28 6. perform a dfs from (5.) and fill in the edges (null at start) to the corresponding vertex it was visited by and mark visited edges as 1 and unvisited as 0 starting from vertex 4 Vertex edge visited 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 7. perform a bfs from (5.) and fill in the edges (null at start) to the corresponding vertex it was visited by and mark visited edges as 1 and unvisited as 0 starting from vertex 3. Additionally write the distance which starts from 0 at the source Vertex edge visited distance 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 8. perform a topological sort from with the following edge connections in an undirected graph and write the vertices in order or not applicable if a topological sort cannot be done. 0 1 -> 2 2 -> 4 -> 6 3 ->7 4 -> 6 -> 7 5 6 -> 7 7 Top bottom Sorting: 1. show the contents of the array after merge() is called 4 times in merge sort with the array starting at the following order: 78 69 63 22 4 68 29 81 66 10 9 2 98 95 65 2. Trace the quicksort algorithm on the following array. Assume the array is already shuffled. Use the first item as a pivot when doing a partition. Show the full recursion tree, i.e. all partitions, on the original array and subarrays. 78 69 63 22 4 68 29 81 66 10 9 2 98 95 65