DOC PREVIEW
CMU CS 15122 - Exam

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

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 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 11 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 11 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 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Midterm II Exam15-122 Principles of Imperative ComputationFrank Pfenning, Tom Cortina, William LovasNovember 4, 2010Name: Andrew ID: Section:Instructions• This exam is closed-book with one sheet of notes permitted.• You have 80 minutes to complete the exam.• There are 4 problems.• Read each problem carefully before attempting to solve it.• Consider writing out programs on scratch paper first.Red/blackRopes trees BDDs HeapsortProb 1 Prob 2 Prob 3 Prob 4 TotalScoreMax 40 40 30 40 150Grader11 Ropes (40 pts)In C0 and C, strings are typically represented as arrays of characters. This allows constant-timeaccess of a character at an arbitrary position, but it also has some disadvantages. In particular, con-catenating two strings (function string_join) is an expensive operation since we have to create anew character array and copy the two given strings into the new array character by character.Task 1 (10 pts). What is the asymptotic complexity of the following loop as a function of n?Assume that string_fromint is a constant-time operation.string string_fromarray(int[] A, int n)//@requires 0 <= n && n < \length(A);{ string s = "["; int i;for (i = 0; i < n; i++)//@loop_invariant 0 <= i && i <= n;s = string_join(s, string_fromint(A[i]));return string_join(s, "]");}The data structure of ropes attempts to improve efficiency of concatenation by representingstrings as binary trees, where the leaves contain ordinary strings and the intermediate nodes repre-sent concatenations. For example, the string "totally efficient" might look as follows (amongmany other possibilities):“totally'ef”'“fici”' “ent”'Note that ordinary strings are only stored at the leaves. Assuming no rebalancing, concatenationof ropes is a constant-time operation.2Task 2 (10 pts). Assuming no rebalancing, show the final result of concatenating the rope abovefirst on the left with "[" then on the right with "]" to form a rope for the string "[totally efficient]".Task 3 (10 pts). Describe what additional information you might store in the nodes so that ac-cessing the ith character in a string of length n represented by a rope is O(log(n)) if the rope isbalanced.3Task 4 (10 pts). Carefully describe the invariant for your data structure. You do not need to writecode to check it, but your description should be precise and detailed enough that it would be clearhow to write the code.42 Red/Black Trees (40 pts)The transformation below, from the tree on the left to the tree on the right, we called a doublerotation. It was used in rebalancing after insertion into a red/black tree. We assume keys areintegers and x, y, and z are keys for the three nodes shown explicitly.Task 1 (10 pts). Show that the name double rotation is justified by drawing an intermediate treebetween the two, so that each step is a single rotation. Try to obey the data structure invariants asmuch as possible, but see Task 3.z"y"x"x"y"T1"z"red"node"black"node"T2" T3"T4"T1" T2" T3" T4"Task 2 (20 pts). Assume that first tree satisfies all red/black tree invariants except for the colorinvariant at y (whose parent is also red). Also assume that the first tree has no restriction on keysat the root (interval (−∞, +∞)) and black height h.Fill in the following table, indicating the bounding intervals and the black height for eachsubtree.Tree Interval Black HeightT1T2T3T45Task 3 (10 pts). Under the same assumptions as in Task 2, explain which red/black tree invariantshold for the tree you drew in the middle, and which ones are violated and where.63 Binary Decision Diagrams (30 pts)Task 1 (10 pts). Draw a binary decision tree (not a BDD) for the boolean function with argumentsx1, x2, and x3that returns true if and only if exactly two of the inputs are true. It should test thevariables in the given order.7Task 2 (20 pts). Draw a reduced ordered binary decision diagram (ROBDD) for the boolean func-tion above, again using the given variable ordering. Show intermediate steps in the reductionfrom the tree to the ROBDD for partial credit in case your final result is not quite correct.84 Heapsort (40 pts)We can use the invariant behind heaps in order to implement an in-place sorting algorithm forarrays called heapsort. For simplicity, we use max heaps, which satisfy:Max Heap Ordering Invariant: Each node except for the root must be less or equal toits parent.This guarantees that a maximal element is at the root of the heap, rather than a minimal one as wedid in lecture.The algorithm proceeds in two phases. In phase one we build up a heap spanning the wholearray, in phase two we successively delete the maximum element from the heap and move it theend.Here is our implementation, written compactly, with only pre- and post-conditions, but noloop invariants or assertions. Note that we only sort the range A[1, n), ignoring A[0].void heapsort(int[] A, int n)//@requires 1 <= n && n <= \length(A);//@ensures is_sorted(A, 1, n);{ int i;for (i = 2; i < n; i++) {sift_up(A, i, i+1);}for (i = n-1; 2 <= i; i--) {swap(A, 1, i);sift_down(A, 1, i);}}The functions sift_up and sift_down are like the functions we wrote in lecture, except that theytake an array as a first argument and what we called H->next (the index right after the last elementcurrently in the heap) as the third argument. The pre- and post-conditions for both functions aregiven below.Your main task will be to enrich this code with invariants and assertions. You should assumethe following functions:bool is_heap(int[] A, int n);bool is_heap_except_up(int[] A, int i, int n);bool is_heap_except_down(int[] A, int i, int n);bool is_sorted(int[] A, int lower, int upper);with the following interpretation:is_heap(A, n) means that the range A[1, n) satisfies the heap invariant.is_heap_except_up(A, i, n) means that the range A[1, n) satisfies the heap invariant exceptthat A[i] (which must be in the heap) may be greater than its parent.is_heap_except_down(A, i, n) means that the range A[1, n) satisfies the heap invariant exceptthat A[i] (which must be in the heap) may be less than one or both of its children.9is_sorted(A, lower, upper) means that the range A[lower, upper) is sorted in increasing order.Here are the pre- and post-conditions for the sift_up and sift_down functions that are calledfrom heapsort.void sift_up(int[] A, int i, int n)//@requires is_heap_except_up(A, i, n);//@ensures is_heap(A, n);;void sift_down(int[] A, int i, int n)//@requires is_heap_except_down(A, i, n);//@ensures is_heap(A, n);;Task 1 (25


View Full Document

CMU CS 15122 - Exam

Download 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 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 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?