CSE 247 Data Structures and Algorithms Spring 2017

Exam I
Given: 1 March 2017 Due: End of session

This exam is closed-book, closed-notes. No electronic devices or resources of any kind are
allowed. The exception is the cheat sheet as described on our course web pages on which you
may have notes to consult during the exam.

Your work must be legible. Work that is difficult to read will receive no credit. Do not dwell over
punctuation or exact syntax in code; however, be sure to indent your code to show its structure.

You must sign the pledge below for your exam to count. Any cheating will cause the students
involved to receive an F for this course. Other action may be taken.

Your work must be completed on these pages. There is blank space on some pages of the exam
if you need it. Dont spend too much time staying stuck on a question: move on and return to the
question later.

You must fill in your identifying information correctly. When you reach this point in the
instructions, please give the professor or TA a meaningful glance.

Print clearly the following information:

Name (print clearly):

Student 6-digit ID (print really clearly):

Problem Possible Received

Number Points Points
1 20
2 10
3 20
4 10
5 20
6 20
Total 100

Pledge: On my honor, I have neither given nor received any unauthorized aid on this exam.

Signed:
(Be sure you filled in your information in the box above!)
CSE 247 (Exam I) 2 Due by End of session

1. (20 points)

(a) (5 points) log n = O(g(n)) for which of the following definitions of g(n)?
Circle all that apply:
g(n) = 1
g(n) = log n + 247
g(n) = n
g(n) = n log n
g(n) = n2 log n
None of the above

(b) (5 points) log n = (g(n)) for which of the following definitions of g(n)?
Circle all that apply:
g(n) = 1
g(n) = log n + 247
g(n) = n
g(n) = n log n
g(n) = n2 log n
None of the above

Read the following questions carefully: they are phrased different from
the above.

(c) (5 points) f (n) = (n) for which of the following definitions of f (n)?
Circle all that apply:
f (n) = 0
f (n) = 247
f (n) = 247
n

f (n) = 247n
f (n) = 247n + 131
None of the above

(d) (5 points) f (n) = (0) for which of the following definitions of f (n)?
Circle all that apply:
f (n) = 0
f (n) = 247
f (n) = 247
n

f (n) = 247n
f (n) = 247n + 131
None of the above
CSE 247 (Exam I) 3 Due by End of session

2. (10 points) Recall that f (n) = O(g(n)) if

c > 0 n0 > 0 | n n0 f (n) c g(n)

Prove that 2n = O(n!).

To attempt full credit, you do this by induction on n, starting at n = 0. You

must use the induction hypothesis

P (n) : 2n = O(n!)

You must explicitly show P (0) and then show P (k) P (k + 1)

Or, for attempt at most half credit, you do a direct proof based on analysis of 2n
and n!.

(a) Circle only one of the above two methods, indicating which proof technique you
are going to use.
(b) Using the notation above, write your proof below. Where needed, state appropri-
ate values for c and n0 .
CSE 247 (Exam I) 4 Due by End of session

3. (20 points) Consider the insertion of the integers 1, 2, . . . , 7 into a MinHeap that can
hold 7 integers. In this problem you will consider two different orders for insertion of
those integers, and you are asked to show the resulting heap after the insertions have
finished. This requires that you write one correct integer into each of the empty nodes
in the images below. If you need some space to draw temporary results, a blank page
is provided after this one.
(a) Starting with an empty heap, suppose the integers are inserted into the heap in
the following order:
1, 2, 3, 4, 5, 6, 7
Below show the heap after all of those insertions are complete:

(b) Starting with an empty heap, suppose the integers are inserted in the following
order:
7, 6, 5, 4, 3, 2, 1
Below show the heap after all of those insertions are complete:

Continued on next page. . .

CSE 247 (Exam I) 5 Due by End of session

Blank page for your use.

CSE 247 (Exam I) 6 Due by End of session

4. (10 points) Fill in the blanks below with complexity results stated in terms of n.
Assume print produces one line of output.
(a) Fragment:
for i=n downto 1
print(n + " bottles of beer on the wall, " + n + " bottles of beer")
print("you take one down, pass it around, ")
print((n-1) + " bottles of beer on the wall")
end

The above fragment prints ( ) lines.

(b) Fragment:
for i=1 to n
print("On the " + i + "th day of Festivus my true love gave to me")
for j=i downto 1
print(i + " nifty " + i + "-things")
end
end

The above fragment prints ( ) lines.

(c) Fragment:
for i=1 to n
int[] array = new int[5];
end

Worst-case, the above fragment takes ( ) time.

(d) Fragment:
for i=1 to n
int[] array = new int[i];
end

Worst-case, the above fragment takes ( ) time.

(e) Fragment:
i = n
while (i > 0)
print("Zeno is almost there")
i = i / 2 // integer division and result
end

Worst-case, the above fragment prints ( ) lines.

CSE 247 (Exam I) 7 Due by End of session

5. (20 points) This problem considers your MinHeap implementation. Suppose it has been
instantiated with sufficient space to hold n integers. Duplicates are allowed, as usual.
In terms of the code we used for lab, the name of the array representing the binary
tree is array, and we have

n = size
array.length > size

We will consider below some operations on the heap we have not previously seen. You
may express your solution in code, in pseudocode, or in prose, but you must be clear
and precise about what you are doing in your solutions. You will not be penalized for
syntax problems.

(a) (6 points) reduceToParent(int loc): the heap value at array index loc is
decreased to the heap value of locs parent.
i. Complete the inquality below to indicate exactly those values for loc that
are valid for this operation to work:

< loc

ii. Below describe your implementation for this method. Be sure that when your
method is finished, the heap is in a valid state.

iii. If the heap has n elements, your approach takes ( ) time.

Continued on next page. . .

CSE 247 (Exam I) 8 Due by End of session

(b) (7 points) increaseToLeftChild(int loc): the heap value at array index loc
is increased to the heap value of locs left child.
i. Complete the inquality below to indicate exactly those values for loc that
are valid for this operation to work:

< loc

ii. Below describe your implementation for this method. Be sure that when your
method is finished, the heap is in a valid state.

iii. If the heap has n elements, your approach takes ( ) time.

Continued on next page. . .

CSE 247 (Exam I) 9 Due by End of session

(c) (7 points) remove(int loc): the heap element at index loc is removed from the
heap.
i. Complete the inquality below to indicate exactly those values for loc that
are valid for this operation to work:

< loc

ii. Below describe your implementation for this method. Be sure that when your
method is finished, the heap is in a valid state.

iii. If the heap has n elements, your approach takes ( ) time.

CSE 247 (Exam I) 10 Due by End of session

6. (20 points)
Letters for you to use to fill in the blanks:
a (1)
e (n2 )
b (log n)
f linear search
c (n)
g binary search
d (n log n)

For each statement below, fill in the blank with a letter chosen from the above list.
Correct responses may or may not be unique.

As a function of its radius n, the area of a circles grows as .

As a function of its diameter n, the area of a circle grows as .

As a function of its number of nodes n, the height of a binary tree grows as .

The MinHeap we implemented was of a fixed size. Imagine that we are going
to allocate a new array in MinHeap to accommodate more elements when the
existing array is full. Consider the total cost of inserting n items into such a heap
whose size is initially 1, with array.length=2.
When the array is full it is replaced by an array that is one cell larger than the

old array. The cost of inserting n items using this strategy is .

When the array is full, it is replaced by an array that is twice the size of the

old array. The cost of inserting n items using this strategy is .

The time to perform 10 extractMin() operations in a heap initially of size n,

where n 10, is .

Given a heap of size n, the time to extract half of its elements is .

Consider an array such that its elements are already sorted. To find a given

element in O(n) time you can use or .

Consider an existing linked list of n elements without a tail reference. If we

add a tail reference to that implementation, the increase in required storage

is .