Lecture 3 – Linked Lists
Lecture 14
Midterm Exam Review
EECS 281: Data Structures & Algorithms
Good News!
http://phdcomics.com/comics/archive.php?comicid=2022
2
http://phdcomics.com/comics/archive.php?comicid=2022
Times
• When: Thursday October 21
– 7:00pm – 9:20pm (Ann Arbor time, 140m)
• Two hours + 20 minutes for down/uploads
• Extended times start at the same time
– Ends 1 hour later for 1.5x time, 2 hours for 2x
3
Locations
• Online, via Canvas and Gradescope
• All questions are shown in your Canvas
“Quiz”
– Submit the multiple choice answers inside
that Canvas Quiz
– Submit written problems on Gradescope
• DO NOT submit until done with both parts
– Honor pledge on a separate Canvas Quiz, fill
out the next day
5
Downloading Starter Files
• In the past we had a link within the exam
to the starter files, but some students
couldn’t open the links
• The starter files are on the autograder
under the Exams tab
• DO NOT DOWNLOAD EARLIER THAN
YOU TAKE THE EXAM
• Don’t rush to download, read question first
6
During the Exam
• We will set Piazza to private posts by
default
• If you have a question, post on Piazza
privately (do not followup a public post!)
• Move on to another question and check
back for an answer in a few minutes
• Set your browser to fill the screen,
standard zoom factor (otherwise some
pictures disappear)
7
Policies
• Use anything that WE have given you
– Lecture PDFs, labs, etc.
• During a “normal” semester we allow a
cheat sheet
• Still a good idea to make one
– Important information all in one place
– Writing by hand improves long-term memory
• Engineering Honor Code applies
8
Multiple Choice Portion
• 24 questions, 2.5 points each (60 points)
• 4-5 possible answers per question
• No deduction for being wrong
– Make sure to answer all 24 questions
– ONE answer per question
10
Exam Itself
• All questions are in the Canvas “quiz”
– Multiple choice will be answered in the “quiz”,
as you do for Labs
– Written questions will be answered on
Gradescope, as you do for lab written
problems
• DO NOT SUBMIT THE QUIZ UNTIL YOU
ARE DONE WITH BOTH PARTS
– Once you submit, you cannot see the written
questions
11
Display Issue
• The exam will be have a “time limit” of the
longest allowed time (usually 2x or 260
minutes)
– Canvas only allows one setting for this
• Each student will have a time limit (140
minutes for most, more for SSD students)
• It may tell you that you “started late”
because you’re not getting 4+ hours
– This is a display issue only; non-SSD
students have 140 minutes start – end
12
Check Remaining Time
• If you have an SSD accommodation for
extended time, check it when you start
• If it’s wrong, post on Piazza, and we can
fix it during the exam, adding the time
you’re allowed, and Canvas will adjust
your remaining time
• Once you submit the quiz, we can’t add
time
13
Study Materials
• Practice exam posted on Canvas
– Answers auto-reveal after last lecture
• Lecture slides and recordings
• In-class exercises
• Lab materials
• Projects
• Study group
16
Topics
• Everything we have covered so far,
especially:
• Complexity analysis, including recurrences
• Contiguous (array) versus linked
containers
• Stacks, queues and priority queues
• Binary heap (not pairing) and Heap Sort
• Elementary, Quick and Merge sorts
• Strings and sequences 17
Answering Coding Questions
• If you decide you want a helper function,
write it above the given function
• If you need a structure, write that inside
the given function, or above it
– Some coding problems given in some
semesters can ONLY be solved if you create
a struct (or use a pair<>)
18
Coding Questions – Lines
• How many lines of code is this?
if (x > 0) result = 0;
• 2 lines of code, same as this:
if (x > 0)
result = 0;
20
Coding Questions – Lines
• How many lines of code is this?
if (x > 0) {
result = 0;
return result;
} // if
• 3 lines of code: the closing curly brace
never counts as a “line of code”
21
Coding Questions – Lines
• How many lines of code is this?
if (x > 0)
result = 0;
else
result = x;
• 4 lines of code, the else statement counts
as a line
• One line with ternary operator:
result = (x > 0) ? 0 : x;
22
Coding – Container of struct
• Once you create a structure, how can you
easily add a member of that structure to a
container? (OBTW: line count = 5)
struct WordCount {
string word;
int count;
};
vector
vwc.push_back({ “abc”, 1});
23
Coding Questions – Libraries
• Each coding question will tell you what you
can or cannot use from the C and STL
libraries
• The function header that we give you will
not be part of the line limit
– If you add a struct or helper function, those
lines will count
– If this is a reasonable way to solve the
question, it is already factored in the line limit
24
Coding Questions – Integers
• For loop variables, use whatever type
makes sense (size_t, int, etc.)
– You don’t have to worry about implicit
conversions on loop variables
• If we pass a vector
and you need to keep a copy of one or
more of those values, use an int variable,
or a container of int
– Stay consistent with data
25
Complexity Analysis
0
5
10
15
20
25
0 1 2 3 4 5 6 7 8 9 10
1
log n
n
n log n
n2
2n
26
What is the complexity? Θ(…)
1 int* bsearch (int* lo, int* hi, int val) {
2 while (hi >= lo) {
3 int* mid = lo + (hi – lo) / 2;
4 if (*mid < val) lo = mid + 1;
5 else if (*mid > val) hi = mid – 1;
6 else return mid;
7 } // while
8 return nullptr;
9 } // bsearch()
10 void f(int *out, const int *in, int size) {
11 for (int i = 0; i < size; ++i) {
12 out[i] = 1;
13 for (int j = 0; j < size; ++j) {
14 if (i == j)
15 continue;
16 out[i] *= in[j];
17 } // for
18 } // for
19 } // f() 27
What is the complexity? Θ(...)
• Write the recurrence relation
• Solve
1 void merge_sort(Item a[], int left, int right) {
2 if (right <= left)
3 return;
4 int mid = left + (left - right) / 2;
5 merge_sort(a, left, mid);
6 merge_sort(a, mid, right);
7 merge(a, left, mid, right);
8 } // merge_sort()
29
Containers
• What is the best container if it will be used primarily to
locate objects within it using binary search?
• What is the best container if new objects will often be
added immediately before specific existing objects?
• What is the best container if you must store a small
number of very large objects. Memory is scarce and the
most important consideration is to store as many of
these objects as possible in the available space?
• Options: singly-linked list, doubly-linked list, vector
• Also: WHY?
32
Containers
• What is the worst container if you must store a large
number of one byte items and memory is the scarcest
resource?
• What is the worst container if you will frequently insert
new items anywhere within the structure?
• What is the worst container if you will frequently insert
new items at the beginning of the structure?
• Options: singly-linked list, doubly-linked list, vector
• Also: WHY?
34
Stacks and queues
• Implement a queue using two stacks. Given the class
below, write the pop() function.
1 class MyQueue {
2 stack
3 public:
4 void push(int num) {
5 s1.push(num);
6 } // push()
7 void pop();
8 int front();
9 }; // MyQueue
36
Sorting
Unless stated otherwise, use the best (most adaptive)
version of a sort that we’ve developed. Which sort is best
in these circumstances?
• Array that is “almost” already sorted
• Very small array
• Medium size array
• Large array (about as big as main memory)
• Very large tape drive
You’re using a quicksort on a very large input, and it’s
taking longer than normal. What happened?
38
Binary Heaps
• Draw the underlying
array for this heap
• Push the value 47
– Use fixUp()
• Draw the resulting
tree and array
81
18 14
4
1 59 7
2
41
Priority Queues
• What is the complexity?
Unordered
Array
Ordered
(Sorted) Array
Binary Heap
create(range)
push()
top()
pop()
43