The University of Michigan
Electrical Engineering & Computer Science
EECS 281: Data Structures and Algorithms
Winter 2018
MIDTERM EXAM
Written Portion – ANSWERS
Wednesday February 21, 2018
6:30PM – 8:00PM (90 minutes)
Name: Uniqname:
Student ID:
Uniqname of person to your left:
Uniqname of person to your right:
Honor Pledge:
“I have neither given nor received unauthorized aid on this examination,
nor have I concealed any violations of the Honor Code.”
Signature:
INSTRUCTIONS:
• The exam is closed book and notes except for one 8.5”x11” sheet of handwritten notes (one
side only). All electronic devices are prohibited during the exam.
• Print your name, student ID number, and uniqname LEGIBLY. Sign the Honor Pledge; this
applies to both the written and multiple-choice sections. Your exam will not be graded without
your signature. This must be completed BEFORE TIME IS CALLED.
• Record the UNIQNAME of the students to both your left and right. Write down nullptr if
you are at the end of a row and there is no one on a given side.
• Turn in both booklets and the Scantron form. We will not accept your exam unless you turn in
all parts. Keep your cheat sheet.
Page 2 of 4 Midterm Exam · Winter 2018
25. Short Answer: Complexity Analysis [8 points total, 4 per blank]
PotatoBot has gotten smarter, and is implementing its own function! It has the initial code started
below. Write each worst-case time complexity for different incomplete expressions (with missing
components designated like 1 ).
void potato(int n) {
for (int i = 1; i < n;¬ )
for (int j = 1; ;® )
for (int k = 1;̄ ; k++)
cout << "Potato!\n";
} // potato()
1 2 3 4 Complexity
i++ j < n j *= 3 k < j Θ(n
2)
i *= 2 j < n j++ k < j Θ(n
2 log n)
i++ j < i j++ k < n Θ(n3)
i *= 2 j < n j *= 2 k < n Θ(n log
2 n)
xiaosong
Highlight
xiaosong
Highlight
Page 3 of 4 Midterm Exam · Winter 2018
26. Programming: Linear Time Algorithms and the STL [14 points]
Implement the STL’s problem_26() function (the name has been changed for this exam) according
to its official interface and description, given below.
Quoting from http://www.cplusplus.com
problem_26()copies elements from the range [first, last) to the range beginning at
result, but rotating the order of the elements in such a way that the element pointed to by middle
becomes the first element in the resulting range.
Complexity: Linear in the distance between first and last: Performs an assignment for each
element.
For example, if you executed this code:
int data[6] = {1, 2, 3, 4, 5, 6}, output[6];
problem_26(data, data+2, data+6, output);
You would have this in array output:
3 4 5 6 1 2
Implementation: Use the back of this page as a working area, then rewrite NEATLY on the front.
Limit: 15 lines of code (points deducted if longer). You may NOT use any STL algorithms/functions.
template
OutputIterator problem_26(ForwardIterator first, ForwardIterator middle,
ForwardIterator last, OutputIterator result) {
// One line solution using STL (if allowed to use STL)
// return copy(first, middle, copy(middle, last, result));
// Copy middle to end
for (ForwardIterator mid = middle; mid != last; ++mid, ++result)
*result = *mid;
// Copy beginning to middle
for (; first != middle; ++first, ++result)
*result = *first;
return result;
} // problem_26()
http://www.cplusplus.com
Page 4 of 4 Midterm Exam · Winter 2018
27. Programming: Heap Flattening [18 points]
Given a pointer-based binary heap, flatten it into a singly-linked list. The binary heap passed in (as
a Node *) must be modified directly. DO NOT create or destroy any Nodes. The left child should
appear in the linked list before the right child. An example is shown below:
83
78
4975
66
2019
Each Node is defined as:
struct Node {
int val;
Node *left;
Node *right;
};
Turns into:
83 66 78 19 20 75 49 nullptr
The right pointer within each Node must be used as “next”, the left must be set to nullptr.
Complexity: Θ(n) time, Θ(1) additional space.
Implementation: Use the back of this page as a working area, then rewrite NEATLY on the front.
Limit: 18 lines of code (points deducted if longer). You MAY use anything from the STL.
void linearize(Node *binaryHeap) {
queue
myQueue.push(binaryHeap);
while (!myQueue.empty()) {
Node *temp = myQueue.front();
myQueue.pop();
if (temp) {
myQueue.push(temp->left);
myQueue.push(temp->right);
temp->left = nullptr;
temp->right = myQueue.front();
} // if
} // while
} // linearize()
xiaosong
Highlight