CSC 17 Guide to Final Exam The final exam will be comprehensive, with emphasis on the materials covered after Spring break. You will need to compare the different data structures we've studied during the semester (circular queues, priority queues, hash tables, AVL trees) in terms of their relative advantages. You should also be able to write segments of code using them. Subjects to be covered: Data Structures, Algorithms and their Complexity classes: 1. Hashtables. Understand the roles of the key (versus value), what hash functions compute and how "hash collisions" are resolved. Difference between open hash tables (separate chaining) and closed hash tables (open addressing). 2. Binary Search Trees and AVL trees. Know the algorithms for insert/delete. Know how to apply the AVL rotations to rebalance trees after insert and delete. Study the "modern" style of implementation and be able to ***write some simple function in that context.*** You will also be asked to determine the time complexity of any functions that you have written. 3. Dynamic programming: when to use, how to use... Top down versus bottom-up dynamic programming. 3b. The Needleman-Wunsch algorithm in particular, including traceback. 4. Graph search; Dijkstra's algorithm and Algorithm A*. 6. Time complexity of various algorithms on various structures. For example, inserting into an AVL tree, searching heaps, etc. Also need to understand the difference between average and worst-case complextiy; when it's relevant. Programming Techniques: 1. Classes, inheritance, interfaces, abstract classes (lightly). The Comparable interface in particular. 2. Type casting and the runtime or compiler errors they're related to. 3. The Option type. You need to know who to write code with it. Specifically, know how to apply the .map, .ifPresent, .isPresent and orElse functions. ========================================================================= Practice Problems, sample solutions posted separately. (These questions are a bit on the hard side by design) ---------------- 1. Consider the following class structure for (unbalanced) binary trees of integers. interface node { boolean empty(); //... } class nil implements node { public boolean empty() {return true;} //... } class vertex implements node { int item; node left, right; vertex(int h, node l, node r) {item=h; left=l; right=r;} public boolean empty() {return false;} public boolean leaf() { return left.empty() && right.empty();} //... } // 1a Write a function to return the total number of nodes in the tree. add it to the interface and both subclasses. Choose a recurrence relation that would describe it's time complexity in BOTH the average and worst cases. // 1b Write a function to search for a value in a binary search tree. // Determine also its average time complexity class by writing a // recurrence relation 1c Redo the above problem, but DO NOT assume that the tree is a binary // SEARCH tree. Hint: recursion is virtually unavoidable. 2. Given the above class, consider the following code: nil Nil = new nil(); // single instance of empty tree node A = new vertex(6, new vertex(4,Nil,Nil), Nil); Explain if the following lines of code are valid, and if not valid, whether it will cause a compiler error or runtime error: 2a. node i = A.left; 2b. node i = ((vertex)A).right; 2c. int x = ((vertex)i).item; // where i is from above 3. Show how to augment (edit) the existing interface classes to implement an operation on trees that determines if x is an item in the tree: boolean search(int x) 3b. What are the average and worst case complexity classes of your program. 3c. Given the following tree: 5 / \ 2 7 / \ / \ 1 4 6 8 \ 9 What order will the values be printed using an INORDER, PREORDER and POSTORDER traversal. 4. What are the worst-case time complexities of the following operations: a. inserting into priority heap b. searching for a value in a priority heap c. searching for a value in a hash table d. searching for a value in an AVL binary search tree e. Dijkstra's algorithm in general f. removing a value from an AVL tree g. removing a value from the end of a cicular queue h. an in-order traversal on an AVL tree. 5. Consider the following recursive function: int bif(int n) { if (n<2) return n; else return bif(n-1) * bif(n-2); } 5b. Rewrite the program using a dynamic programming matrix. You may choose between bottom-up and top-down dynamic programming. 5c. Do the same for this: int k(int n, int c) { if (n<1 || c<2) return 0; return Math.max(k(n-1,c), k(n-1,c-2)+2); } 6. Explain the difference between nodes in the closed/interior and nodes on the open/frontier in Dijkstra's algorithm. 7. Insert the following nodes into an AVL tree. Show when (and what) rotations are required. 2 8 6 1 3 9. Insert additional nodes (make up your numbers) so that all 4 rotations are used. 8. Give a specific example of deleting from an AVL tree where more than one rotation is required to balance the tree. There are four distinct rotations: LL, RR, RL and LR, the rotations "RL" and "LR" should be counted as ONE rotation, not two. (If I ask this, it would be considered one of the harder questions.) 9. Assume that you need to record the transcripts of many students. You want to be able search quickly for a student by their ID number, and you want to be able to look up the student with the highest GPA. What kind of data structure(s) would you choose to write this program with? Justify your answer. 10. Assume that you want to represent a SET of integers (these integers can, for example, index some values in an array). You want to be able to insert, delete and search for values in the set with maximum efficiency. Furthermore, you also want to be able to determine quickly both the smallest and the largest index of the "set". For example, if the set consists of {3,2,6,1,8,7}, you want to be able to determine quickly that the smallest value of the set is 1 and that the largest is 8, as well as be able to search/insert/delete other values. What kind of data structure would you use and WHY? 11. In a closed hashmap, which uses a rehash function, when a value is deleted from the table the key is kept (Values[hash(key)] is set to null but not Keys[hash(key)]). Explain why? 12. Given Optional Aopt; String A; a. Write code to print the string inside the optional if it exists b. Assign A to the string inside Aopt if it exists, and to "" if it doesn't Under no circumstances can your code throw an exception. 13. Assume: class A { public void f() {} } class B extends A { public void g() {} } ... A m = new A(); A n = new B(); // determine if there's an error in the following code, and whether // it's a compiler or runtime error: a. n = m; b. n.f(); c. n.g(); d. ((B)n).g(); e. ((B)m).g(); 14. Does the following class always define a binary tree in Java? It doesn't have to be a binary "search" tree. Just a binary tree that uses null pointers to represent the empty tree. class tree { T item; tree left; tree right; } If the answer is no, give a specific example of this structure that would not be a tree. 15. Explain how Dijkstra's algorithm avoids cycles. 15b. What is the absolute worst case time complexity of Dijkstra's algorithm in terms of the number of possible nodes (vertices) in graph. 15c. Given the following weighted graph A ----4----> B ----1----> F | | | 9 2 3 | | | | | | v v v C <----2---- D ----3----> E Apply Dijkstra' single-source shortest path algorithm to source node A Apply Dijkstra' single-source shortest path algorithm to source node B 16. Apply the Needle-Wunsch algorithm to the following sequences: A= .ATGACTG B= .TGATGC with the following scoring scheme: int score(int i, int k) { if (A.charAt(i)==B.charAt(k)) return 1; else return 0; } int W() {return 0;} Show the matrix generated by the algorithm. Display one optimal alignment (traceback) (without the . at the front) How about under the following Scheme: int score(int i, int k) { if (A.charAt(i) == B.charAt(k)) return 2; else return -1; } int W() { return -1; }