The midterm will cover the following topics:
Unit 1: Fundamental Data Structures
Unit 2: Sorting and Priority Queues
Unit 3: Searching and Search Trees
The midterm will consist of short answer and long answer questions.
Below are examples of the type of questions that may be asked on the midterm (many of them come from the exam last year). It is meant to be representative, rather than exhaustive (ie. there may be questions that show up on the midterm that are not shown below).
What is the worst-case time and space complexity of the
following algorithm? Express your answers using Big-O notation in terms of
len1
and len2
.
using namespace std; int edit_distance(const string &s1, const string &s2) { const int len1 = s1.size(), len2 = s2.size(); vector<vector<int>> d(len1+1); for (int i=0; i<=len1; ++i) d[i] = vector<int>(len2+1); d[0][0] = 0; for (int i = 1; i <= len1; ++i) d[i][0] = i; for (int i = 1; i <= len2; ++i) d[0][i] = i; for (int i = 1; i <= len1; ++i) { for (int j = 1; j <= len2; ++j) { d[i][j] = min(d[i-1][j], d[i][j-1]) + 1; if (s1[i-1] == s2[j-1]) d[i][j] = min(d[i][j], d[i-1][j-1]); else d[i][j] = min(d[i][j], d[i-1][j-1] + 1); } } return d[len1][len2]; }
Time complexity:
Space complexity:
Which of the following data structures provide efficient (that is
O(log(n))
or better) insertion?
unsorted array sorted array linked list max binary heap red-black tree treap
Here is a step by step trace of a sorting algorithm. Which one? Briefly explain how you can tell by identifying the underlying data structure used to implement the algorithm.
Original: 7, 1, 5, 6, 8, 3 Pass 1: 1, 7, 5, 6, 8, 3 Pass 2: 1, 5, 7, 6, 8, 3 Pass 3: 1, 5, 6, 7, 8, 3 Pass 4: 1, 5, 6, 7, 8, 3 Pass 5: 1, 3, 5, 6, 7, 8
Consider the following sequence of push and pop operations.
c.clear(); c.push(5); c.push(3); c.pop(); c.push(2);
If c
is of type stack<int>
, what does c
look like after the above operations?
Top [ ] [ ] ... [ ] Bottom [ ]
If c
is of type queue<int>
, what does c
look like after the above operations?
Front [ ][ ]...[ ][ ] Back
For each of the following trees, identify if it is a max binary heap, a binary search tree, or both:
How would you implement a linked list in C++, including the following methods?
Constructor
Destructor
Copy Constructor
operator=
push_front(T &value)
operator[size_t index]
How would you implement a dynamic array in C++, including the following methods?
Constructor
Destructor
Copy Constructor
operator=
push_back(T &value)
operator[size_t index]
How would you implement Merge Sort on a linked list in C++?
How would you implement Quick Sort on a linked list in C++?
What would a B-Tree of order 4 (in which each node has 1-3 values and
2-4 children) look like after inserting the following letters (in the
order shown): A, V, I, L, A
. Show each step in order to get partial
credit.
What would a Red-Black tree look like after inserting the same letters in the same order? Show each step in order to get partial credit. If you don't have red and black pens, clearly indicate what symbol means "black node" and what symbol means "red node."
You are building a contacts organizer for your phone. It needs to:
Display the list of contacts alphabetically by first name or last name
Search for a contact by first name or last name
Display information (phone number, e-mail address) for a contact
Add or remove contacts
Describe what data structures you would use to represent the contacts database, and what algorithms you would use to implement the above operations. You only need to identify the data structures and algorithms; you don't need to provide details about their implementation.