CMSY10
The University of Michigan
Electrical Engineering & Computer Science
EECS 281: Data Structures and Algorithms
Fall 2017
MIDTERM EXAM
Written Portion – ANSWERS
Wednesday October 25, 2017
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 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; this
applies to both the written and multiple-choice sections. Your exam will not be graded without
your signature.
• 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 the written portion exam book and the Scantron answer form. One will not be accepted
without the other. Keep your notes sheet and multiple-choice book.
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 2 of 5 Midterm Exam · Fall 2017
25. Short Answer: Markov Chain Reaction [4 points]
Professor Markov implemented bubblesort on a queue, but his evil twin changed one line in the
program. It still compiles, but running it causes an infinite loop!
1 template
2 void sortQ(queue
3 const size_t sz = q.size();
4 bool sorted = false;
5
6 if (sz < 2) 7 return; 8 9 while (!sorted) { 10 T prev = q.front(); 11 q.pop(); 12 sorted = true; 13 14 for (size_t k = sz; k > 0; –k) {
15 T next = q.front();
16 q.pop();
17 if (prev > next) {
18 sorted = false;
19 swap(prev, next);
20 } // if
21 q.push(prev);
22 prev = next;
23 } // for
24
25 q.push(prev);
26 } // while
27 } // sortQ()
Find a one-line change (modifying an existing line of code, not adding or deleting one) so that the
code sorts the queue into ascending order for all inputs. Write the entire corrected line of code below;
to make it easier to grade, include the line number that you changed.
14) for (size_t k = sz; k > 1; –k) {
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 3 of 5 Midterm Exam · Fall 2017
26. Programming: Linear Time Algorithms and the STL [18 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.sgi.com/tech/stl/
problem_26()searches for a subsequence of count consecutive elements in the range
[first, last), where each element is equal to value, using pred for comparing equality.
It returns an iterator pointing to the beginning of that subsequence, or else last if no such
subsequence exists. More specifically, problem_26()returns the first iterator i in the range
[first, last – count) such that, for every iterator j in the range [i, i + count),
pred(*j, value) is true.
Complexity: problem_26()performs at most last – first comparisons.
For example, if called with input a = {5, 1, 5, 5, 5, 3}, count = 2, and value = 5,
problem_26()will return an iterator corresponding to index 2 (the second 5) in a.
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.
You can assume that type Integer will be compatible with unsigned int.
template
ForwardIterator problem_26(ForwardIterator first, ForwardIterator last,
Integer count, const T& value,
BinaryPredicate pred) {
while (first != last) {
auto it = first;
Integer currentCount = 0;
while (first != last && pred(*first++, value)) {
currentCount++;
if (currentCount == count)
return it;
} // while
} // while
return last;
} // problem_26()
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
http://www.sgi.com/tech/stl/
Page 4 of 5 Midterm Exam · Fall 2017
27. Programming: When Words Collide [18 points]
You are given a container of N strings (each of length up to M characters) and a fingerprint functor
f() that can be invoked on a string as if it were a function, and has int return type (it accepts
a string and returns a fingerprint). Implement the function findFpCollisions() that should
return true if words includes at least one pair of strings s1, s2 such that s1 ̸= s2 and f(s1) = f(s2).
Otherwise, the function should return false. In particular, for input {“yadda”, “yadda”,
“yadda”} the output should be false. Lower-case and upper-case characters are considered
different, and the fingerprint function f will treat them as different.
Complexity: Assuming that fingerprints are computed in linear time Θ(M), your function must
run faster than Θ(MN +N2) worst-case time, even in the {“yadda”, “yadda”, “yadda”,
…} case. Your function can use O(N) additional space. However you are NOT allowed to create
any new string variables.
Implementation: Use the back of this page as a working area, then rewrite NEATLY on the front.
Limit: 20 lines of code (points deducted if longer). You MAY use any STL algorithms/functions/etc.
template
bool findFpCollisions(const vector
using FPandIdx = pair
vector
for (size_t i = 0; i < words.size(); ++i)
fps.push_back(FPandIdx(f(words[i]), i));
sort(fps.begin(), fps.end()); // Comparisons are defined for pairs
for (size_t i = 1; i < words.size(); ++i) {
if ((fps[i - 1].first == fps[i].first)
&& (words[fps[i - 1].second] != words[fps[i].second]))
return true;
}
return false;
} // findFPCollisions()
Downloaded by Xiao Song ( )
lOMoARcPSD|3188099
Page 5 of 5 Midterm Exam · Fall 2017
Here’s a solution if you didn’t know that pair already had a comparator AND defined a constructor for your
struct (13 lines).
template
bool findFpCollisions(const vector
struct FPandIdx {
int fp, idx;
FPandIdx(int f, int i) : fp{ f }, idx{ i } {}
bool operator<(const FPandIdx &b) const {
return fp < b.fp;
}
};
vector
for (int i = 0; i < (int)words.size(); ++i) fps.push_back(FPandIdx(f(words[i]), i)); sort(fps.begin(), fps.end()); for (size_t i = 1; i < words.size(); ++i) { if ((fps[i - 1].fp == fps[i].fp) && (words[fps[i - 1].idx] != words[fps[i].idx])) return true; } // for return false; } // findFPCollisions() Downloaded by Xiao Song ( ) lOMoARcPSD|3188099 Page 6 of 5 Midterm Exam · Fall 2017 28. Extra Credit Problem [3 points] Credit: all or nothing. The 281 pirates aboard The Virtual Dutchman need to select their captain. Every pirate is eligible and willing to serve as the captain, but above all each pirate wants to stay alive! Any one pirate can either do nothing or step forward to become the captain (their reaction times are different, so two pirates will never step forward at the same time). Once there is a captain, any pirate can throw the captain overboard, but that pirate then immediately becomes the new captain. The pirates do not cooperate with each other - they act upon their personal priorities (which are identical). But otherwise, pirates act rationally, and they are clever enough to consider all possible outcomes correctly. In this problem, no decisions are random or based on likelihoods - the answer must be backed up by logic. Summary of pirate priorities, from highest to lowest: 1. Stay alive. 2. Be the captain. 3. Have a captain. What will happen on The Virtual Dutchman? Will any pirate step forward to become the first captain? Will there be a captain at the end? How many pirates will remain on the ship? Use one sentence to answer all of these questions, then provide justification. Hint: Which EECS 281 topic covered so far can help solve this problem? The fastest pirate steps forward and becomes the captain, no one challenges him/her, so all remain alive. We generalize this problem to N pirates. For N = 1, the single pirate becomes the captain and remains unchallenged. For N = 2, both pirates remain indifferent, otherwise the first captain would be thrown overboard. For N = 3, the fastest pirate becomes the captain, knowing that the remaining two pirates will stay indifferent. In general, an even number of pirates fail to elect a captain, but an odd number of pirates elect the captain who is not challenged. This can be proven directly by induc- tion. In all cases, all pirates remain alive, which is not surprising given that survival is their top priority. Downloaded by Xiao Song ( ) lOMoARcPSD|3188099