The University of Michigan
Electrical Engineering & Computer Science
EECS 281: Data Structures and Algorithms
Winter 2015
MIDTERM EXAM, PRACTICE
Wednesday February 25, 2015
7:10PM – 8:40PM (90 minutes)
Name: Uniqname:
Student ID: Discussion section: (circle one)
MON 10:30 MON 3:00 MON 5:00 TUE 5:00 WED 9:30 WED 3:00
WED 4:30 THU 5:00 FRI 10:30 FRI 11:30 FRI 1:30 FRI 2:30 FRI 3:30
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 can be used). All electronic device use is prohibited during the exam (calculators, phones,
laptops, etc.).
• Print your name, student ID number and uniqname LEGIBLY. Sign the honor pledge. Your
exam will not be graded without your signature.
• Record the UNIQUE NAME of the students to both your left and right. Write down “Empty”
if you are at the end of a row and there is no one on a given side.
• Record your NAME, STUDENT ID number and exam KEY number on the Scantron
form. There will be a penalty for incorrectly filling out the form.
• Circle the discussion section where you want to pick up your exam. This does not have
to be the same one for which you are registered. The exams will be returned FIRST during
discussion sections.
• Record your choices for all multiple choice questions on the computer-graded (Scantron)
answer form. Use a number 2 pencil, not a pen. Fill the circle completely. There is only
Page 2 of 13 Midterm Exam · Winter 2015
one correct answer to each question. There is no partial credit for multiple-choice questions. It
is to your benefit to record an answer to each multiple-choice question, even if you’re not sure
what the correct answer is; there is no penalty for wrong answers.
• The questions vary in difficulty — try not to spend too much time on any one question. Use
your time wisely.
• Turn in both the exam book and the answer form. One will not be accepted without the other.
PROBLEM TYPE SCORE
MULTIPLE CHOICE (10 @ 4 POINTS EACH) /40
FILL IN THE BLANK /7
SHORT CALCULATIONS /13
LINEAR-TIME ALGORITHMS AND THE STL /20
LISTS AND INTERVALS /20
Total /100
Please do not write above this line.
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Page 3 of 13 Midterm Exam · Winter 2015
Record your answers to this page on the Scantron sheet
1. Asymptotic complexity
Find one statement that is false.
A log3(N) = O(log2(N))
B log2(N
3) = O(log2(N
2))
C log2(3N) = O(log2(2N))
D 3N = O(2N)
E 23N = O(22N)
For A-C, use properties of log-functions.
For D, use the property of Big-O notation (dropping constants).
For E, show that limN→∞ 8N/4N =∞.
2. Algorithms for linked lists
Consider two singly-linked lists implemented without classes. You are given non-const pointers to
the head and the tail elements (four pointers total). The last element of each list can have its .next
pointer uninitialized and later overwritten. During all operations the head and tail pointers must
remain valid.
Which statement below is false?
A Copying a singly-linked list to a doubly-linked list takes Θ(N) time.
B The first element of each linked list can be deleted in O(1) time.
C The last element of each linked list can be deleted in O(1) time.
D The merger(concatenation) of the two linked lists can be created in O(1) time.
E Reversing a singly-linked list in place can be performed in O(N) time.
In a linked list, deleting an element typically requires knowing its previous element.
Since our list is singly-linked, it would take linear time to find the second last element.
Note that when deleting the last element, the copying trick discussed in class won’t work.
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Page 4 of 13 Midterm Exam · Winter 2015
Record your answers to this page on the Scantron sheet
3. Program analysis
(Please read the description entirely before proceeding further.)
Consider the following piece of code.
int pickOne(vector
// rand() produces a different unsigned every time it is called
return v[rand() % v.size()]; // rand() and v.size() take O(1) time
}
vector
vector
for (unsigned k = 0; k != v.size(); ++k)
newVec[k] = pickOne(v);
return newVec;
}
Assume that the claims in the comments are correct. Which one of the following is a correct and
tight bound on the asymptotic runtime of function myRandomSample() including all calls to
pickOne()?
A O(N2)
B Θ(N)
C Ω(N)
D Θ(N logN)
E O(NN)
Note: we are not using move semantics from C++11 (so you don’t need to know what it is)
OPTIONAL: improve the asymtotic complexity of this code in two different ways —
(a) by adding one character,
(b) by adding one C++ keyword.
Each call to pickOne() involves copying a vector, which takes linear time. This can be improved
by passing the vector by reference in pickOne() (add an & after vector
the function (add inline before int pickOne and compile with -O3).
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Page 5 of 13 Midterm Exam · Winter 2015
Record your answers to this page on the Scantron sheet
4. Linear-time algorithms with sorted ranges
The following function claims to compute set-union of two sorted ranges in linear time.
template
OutputIterator set_what(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result) {
while (first1 != last1 && first2 != last2) {
if (*first1 < *first2)
++first1;
else if (*first2 < *first1)
++first2;
else {
*result++ = *first1++;
++first2;
} // else
} // while
return result;
}
Which of the following best describes its actual performance?
A It computes what it claims, but may take longer than linear time.
B Iterators may go out of range on some inputs, and the function may crash.
C It computes set-difference.
D It computes set-intersection in linear time.
E None of the above.
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Page 6 of 13 Midterm Exam · Winter 2015
Record your answers to this page on the Scantron sheet
5. The Standard Template Library: containers and iterators
STL iterators are used with container classes and are conceptually similar to pointers to specific
elements stored in the container.
One of the statements below is true. Which one?
A An iterator typically holds an address (pointer), and operator++ applied to the iterator always
increases that address.
B When iterator it goes out of scope in a program, it gets destructed, which automatically invokes
delete it;.
C For a valid STL container myC, when the expression myC.end() - myC.begin() is well-
defined, it returns the same value as myC.size().
D When a container goes out of scope, all iterators that point to it are automatically modified.
E For a valid STL container myC, the iterator returned by myC.end() refers to the last valid
element in myC.
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Page 7 of 13 Midterm Exam · Winter 2015
Record your answers to this page on the Scantron sheet
6. Memory allocation & ownership, and container data structures
Recall that the concept of memory ownership is used to prevent memory leaks
(memory that has not been deallocated but is not pointed to) and crashes due to double delete calls.
Which of the following statements is false?
A This piece of C++ code may lead to a crash or memory corruption:
int *p, *r; p = r = new int; delete p; delete r;
B If a member of a class is a pointer that owns memory, then the destructor of that class must
always use the delete[] operator on that pointer.
C If a pointer or an iterator is the only legal way to access a chunk of memory,
then it must be the direct owner of that chunk of memory.
D If a member of a class is a pointer that owns memory, then the copy-constructor
of the class must invoke operator new in some way.
E Memory allocated with new int[10] must be deallocated with delete[].
B is false because sometimes one must use a different operator — delete without brackets.
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Page 8 of 13 Midterm Exam · Winter 2015
Record your answers to this page on the Scantron sheet
7. 2D Maze Search
Consider a space station that has a single level (consisting of walls, floors, and exits), the level has
dimensions are N ×M , and it has multiple (E > 1) exits. Your robot friend is to be programmed to
count the exits reachable from your current location and it should use the fastest algorithm available.
Which one of the asymptotic worst-case complexity bounds below is both correct and tight?
A O(N +M)
B O(NM)
C O(ENM)
D O(ENM)
E O(NEME)
Use either a queue-based or stack-based algorithm to search the entire maze (in the worst-case) and
record the number of exits seen.
8. Binary search
Consider an array ofN C++ strings, each string with exactlyM characters. No additional information
is available about individual strings, but the array lists strings in a dictionary order (lexicographically
increasing). We wish to find one particular string without building additional data structures. Which
expression below represents most accurately the complexity of binary search on such an array?
A O(logN)
B O(logM)
C O(M logN)
D O(N logM)
E O(logM + logN)
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Page 9 of 13 Midterm Exam · Winter 2015
Record your answers to this page on the Scantron sheet
9. Algorithm design
Consider struct Segment {double xMin, xMax;}; and a vector
task is to determine if any two segments in the input vector intersect (allowed operators for doubles
are assignment, comparisons and copy-construction). Assuming a fastest possible algorithm, what
will its worst-case asymptotic complexity be in terms of N = vector
A N
B N log(N)
C N(log(N))2
D N2
E N2 log(N)
CLARIFICATION : If an algorithm finds two intersecting segments, it can report “some segments
intersect” and stop.
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Page 10 of 13 Midterm Exam · Winter 2015
Record your answers on this page
10. Fill in the blanks [7 points]
Insert missing words and code. No credit will be given for answers that are too general.
1. Priority queues with log(N) access time are often implemented using the heap data structure.
2. The worst-case complexity and the amortized complexity are different for the push back()
operation of the vector container class in STL.
3. Bubble sort and Insertion sort exhibit linear best-case runtime but quadratic worst-case
runtime.
4. A class that implements the functionality of a one-dimensional array with range checking
(using the conventional array interface) must implement two versions of operator[].
Similarly, a two-dimensional array class would implement two versions of operator()
(must be a member of the class).
Note that operator[][] would not be correct for the last question.
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Page 11 of 13 Midterm Exam · Winter 2015
11. Short calculation [13 pts]
A. You are given a square-shaped terrain map (of total area A > 0) assembled from satellite
photographs. You need to add names of rivers, streets, etc. Your strategy is to subdivide the map
into 4 quadrants, process each quadrant individually, and assemble the results. Processing consists
of subdividing a quadrant further until the sub-quadrants are small enough (when area ≤ A0) to be
labeled directly in O(1) time. As labeling errors tend to be more frequent near the division lines, your
quadrants overlap a little, and you carefully check the overlaps. At each subdivision step, each of
the four quadrants contains 1
3
of the area. The effort (time) to subdivide into quadrants and check the
overlaps is estimated as γA for constant γ > 0. Denoting by T (A) the time required to label a square
map of area A, write down a recurrence for T (A) and solve it:
Recurrence: T (n) = 4T (n/3) + γn
Closed-form solution: T (A) = O(Alog
4
3 )
HINT: Since labeling a map of area ≤ A0 takes O(1) time, the amount of work depends on the ratio
n = A/A0. Use the Master theorem in terms of n. Then get rid of n.
You may use a standard function (such as sqrt, exp, log, sin) in your answers, but only once.
B. We are enumerating all permutations of 5 elements using a stack and a queue (as described in
lectures). Initially, the stack is empty, but the queue is full. Count the number of different 3-element
configurations observed in the stack during this process.
Your answer:
There are 5! = 120 permutations, starting with all possible 3-element prefixes. The first element can
be selected in 5 different ways, the second in 4 different ways, and the third in 3 different ways: 5*4*3
= 60. Thus the answer is 60. There are several other counting formulas leading to the same answer.
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Page 12 of 13 Midterm Exam · Winter 2015
12. Programming: Linear-time Algorithms and the STL [20 points]
Implement STL’s uniq_copy() function according to its official interface and description.
template
OutputIterator unique_copy(InputIterator first, InputIterator last,
OutputIterator result);
Quoting from http://www.sgi.com/tech/stl/unique copy.html:
unique_copy() copies elements from the range [first, last) to a range beginning
with result, except that in a consecutive group of duplicate elements only the first one is
copied. The return value is the end of the range to which the elements are copied.
Complexity: Linear. For elements in the ranges, exactly last – first applications of
operator==() and at most last – first assignments.
For example, if you executed this code:
int data[6] = {1, 3, 3, 1, 1, 0}, output[6];
unique_copy(data, data + 6, output);
You would have this in array output:
1 3 1 0
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 other STL algorithms/functions.
template
OutputIterator unique_copy(InputIterator first, InputIterator last,
OutputIterator result) {
if (first == last)
return result;
else
*result++ = *first; // establish a starting point
InputIterator prev = first++;
while (first != last) {
if (!(*first == *prev++)) // *first != *prev++
*result++ = *first;
++first;
} // while
return result;
}
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti
Page 13 of 13 Midterm Exam · Winter 2015
13. Stacks, queues and priority queues [20 points]
Implement the following function
int idContainerType(MysteryContainer& myC);
The class MysteryContainer may implement a stack, or a queue, or a min-priority queue or
a max-priority queue. Depending on the container type, the function should return 1, 2, 3 or 4
respectively. The behavior of the function in other cases is not defined, for example it may return
0 (for clarity), or one of the valid values.
You may access myC only through void MysteryContainer::addElement(int) and
int MysteryContainer::removeElement(), but you may assume that the container is
initially empty. The worst-case number of accesses to myC should be as small as possible. Subject to
that, keep the function short.
int idContainerType(MysteryContainer &myC) {
myC.addElement(2);
myC.addElement(1);
myC.addElement(4);
myC.addElement(3);
int removed = myC.removeElement();
if (removed == 1)
return 3; // min-pq
if (removed == 2)
return 2; // queue
if (removed == 3)
return 1; // stack
if (removed == 4)
return 4; // max-pq
}
// Shorter end
static const int results[] = {3, 2, 1, 4};
return results[myC.removeElement() – 1];
University of Michigan EECS 281 : Data Structures and Algorithms Darden/Paoletti