DOC PREVIEW
Berkeley COMPSCI 61B - CS 61B - Final Exam

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

University of California at BerkeleyDepartment of Electrical Engineering and Computer SciencesComputer Science DivisionSpring 2005 Jonathan ShewchukCS 61B: Final ExamThis is an open book, open notes exam. Electronic devices are forbidden on your person, including cellphones and laptops. Please put them on the desk at the front of the room (and turn your cell phone off) orrisk losing a point. Do not open your exam until you are told to do so!Name:Login:Lab TA:Lab time:Do not write in these boxes.Problem # Possible Score1. Miscellany 82. Data structures 63. Sorting 124. Augmented trees 55. Asymptotic analysis 66. Amortized analysis 67. Index sort 7Total 501Name: Login: 2Problem 1. (8 points) A Miscellany.a. (2 points) Consider the following method to make all the nodes in a doubly-linked list (circularlylinked, with sentinel) available for garbage collection. Recall that head references the sentinel. As-sume that listnodes are referenced only by other listnodes in the same list.public void garbageList() {if (size > 0) {head.next.prev = null; // ? Erase references to sentinel.head.prev.next = null; // ?}head.next = null; // ? Erase references to other nodes.head.prev = null; // ?head = null;}Are the lines marked with question marks necessary to ensure that all the listnodes are available to begarbage collected? Explain.b. (1 point) Recall that a SimpleBoard object stores an 8 × 8 array grid in which each cell hasvalue 0, 1, or 2. Suppose you want to store lots of SimpleBoards in a hash table. Can you thinkof a reason why the following hash code will not distribute SimpleBoard objects evenly among thebuckets? (Assume the compression function is good.)public class SimpleBoard {private int[][] grid;public int hashCode() {int code = 0;for (int i = 0; i < 8; i++) {for (int j = 0; j < 8; j++) {code = code + (i + j) * grid[i][j];}}return code;}}Name: Login: 3c. (2 points) Every word falls into one of eight categories: nouns, verbs, pronouns, adjectives, adverbs,prepositions, conjunctions, and interjections. Suppose you want to be able to look up the category ofany English word in O(1) time. You could use a hash table to map each word to a category. The hashtable’s chains could use ListNodes, wherein each ListNode contains a reference to a word, andan extra field (perhaps a short) that indicates the category of the word.However, we want to use as little memory as possible. We can save some memory by eliminating theextra field from each ListNode. Explain how we can do this, yet still determine a word’s category inO(1) time. Hint: you can adjust the data structure in some other way, but don’t increase the memoryuse by more than a small constant. (That’s an added constant, not a constant factor.)d. (1 point) What does the following Java code print?try {int[][] x = new int[5][5];Object y = x[5];} catch (ClassCastException e1) {System.out.println("First");throw new NullPointerException();} catch (ArrayIndexOutOfBoundsException e2) {System.out.println("Second");throw new NullPointerException();} catch (NullPointerException e3) {System.out.println("Third");} finally {System.out.println("Fourth");}e. (1 point) Circle the sorting algorithms whose asymptotic running time is affected by the input keys(their values and their order). Do not circle algorithms whose worst-case and best-case asymptoticrunning times are the same.mergesort bucket sort insertion sort selection sort quicksort (with first item as pivot)f. (1 point) Suppose you insert fifteen keys, the integers 1 through 15, into a splay tree in an arbitraryorder, and you happen to get a perfectly balanced tree. The last key inserted was.Name: Login: 4Problem 2. (6 points) Operations on Data Structures.a. (2 points) What does the following binary heap look like after insert(1)?9Fill in youranswer here2 4 3 4 7 5 6 746b. (2 points) Draw the following splay tree after execution of the operation remove(6).2 9687341c. (2 points) Draw the following 2-3-4 tree after execution of the operation insert(30).11 20 335 21 23 26 4515Name: Login: 5Problem 3. (12 points) Sorting.a. (3 points) Show how array-based quicksort sorts the array 5 9 7 4 0 2 8 8. Always choose thelast key in an array (or subarray) to be the pivot. Draw the array once for each swap.b. (1 point) Consider a list-based quicksort that computes the average (mean) value i of all the keys inthe list, then chooses the pivot to be i + 1. As usual, we partition the list into three separate lists: keysless than i + 1, keys equal to i + 1 (of which there might be none), and keys greater than i + 1. Wesort the first and last lists recursively, then concatenate the three lists together. What’s wrong with thisalgorithm?c. (2 points) Consider the following sorting algorithm. Loop through the list of input items, insertingeach item in turn into an ordinary binary search tree. Then, perform an inorder traversal of the tree,and output the items in inorder.The worst-case running time of this algorithm is in Θ( ).The best-case running time of this algorithm is in Θ( ).d. (2 points) Describe how to modify the tree in part (c) so that the algorithm does both of the following.• it runs in O(n log n) worst-case time, and• it runs in O(n) time if the input array is already sorted.Explain why it runs in O (n) time in the latter case.Name: Login: 6e. (2 points) Suppose you are using radix sort to sort a list of Java ints, and it is important to sort themas quickly as possible. Explain why you would never choose to use exactly 512 buckets for this sort.f. (2 points) Professor Pretentious claims to have a comparison-based sorting algorithm that can take avalid binary heap, and sort its items in O(n) time. The good Professor claims that he gets around theΩ(n log n)-time lower bound for comparison-based sorting by taking advantage of the fact that theitems in a binary heap are already “partly sorted.” Give a convincing argument that the Professor’sclaims are bogus.g. (2 bonus points) Suppose you have a directed graph G = (V, E) represented by an adjacency list.You want to “sort” the vertices in V in an ordering such that for every edge (v, w) ∈ E, vertex vcomes before vertex w. Note that there may be many such orderings, or (if the graph has a directedloop) none at all.Suggest (in English) an algorithm that produces such an order in O(|V | + |E|) time if one exists.Hint: you may add extra fields to the Vertex objects if you like.Name: Login: 7Problem 4. (5 points) Augmented Binary


View Full Document

Berkeley COMPSCI 61B - CS 61B - Final Exam

Documents in this Course
Lab

Lab

4 pages

Matrix

Matrix

3 pages

Numbers

Numbers

14 pages

Lectures

Lectures

12 pages

Project 1

Project 1

24 pages

Exam

Exam

8 pages

Load more
Download CS 61B - Final Exam
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CS 61B - Final Exam and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CS 61B - Final Exam 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?