EECS 281 Fall 2021 Final Exam (December 15, 8:00am)
Started: Dec 15 at 8:02am
Quiz Instructions
EECS 281: Data Structures and Algorithms
Copyright By PowCoder代写 加微信 powcoder
Final Exam, Fall 2021
Wednesday, December 15, 2021
Do NOT start this exam unless you are taking the exam at 8 AM!
Please read the following directions carefully.
DO NOT DISCUSS THE EXAM AFTER YOU TAKE IT! Cheating on this exam will not be tolerated. If you attempt to share any of these questions before all the exam sessions are done, you will be reported to the honor council and will receive a zero on this exam.
Instructions:
This exam is an open-book and open-note exam. You may use any resources on this exam, but you are NOT allowed to communicate with other people, with the exception of your course instructors (e.g., you cannot contact other students, you cannot post a question on a public online forum, etc.). If you have any questions, please post them to Piazza as a private post. This is to ensure that students in a later exam period don’t have access to the questions that may show up.
You should be able to complete the exam in 120 minutes (2 hours) if you are under normal time (3 hours for 1.5x accommodation and 4 hours for 2x accommodation). However, you will be given a 20 minute grace period to deal with any technical difficulties that could occur. It is your responsibility to have everything prepared for submission by this time; do NOT wait until the last minute. All code submissions made to Gradescope after your deadline will not be counted. Even though all exam periods will submit code to the same Gradescope assignment (for cheat checking purposes), we will not tolerate submissions outside your exam period. If you attempt to submit code to Gradescope during an exam period that is not yours, or attempt to submit code more than 5 minutes after your exam closes without giving us a reason, you will get a zero on the exam.
There will be 26 questions in this exam, 24 of which are multiple choice questions, and 2 of which are coding questions. The breakdown of questions is summarized below:
Questions 1-24 will be single-answer multiple choice questions, each worth 2.5 points (no partial credit) Question 25 will be a programming question, worth 20 points
Question 26 will be a dynamic programming question, worth 20 points
You will be submitting your code for questions 25-26 to Gradescope. Please budget enough time to do this! Gradescope will run your code against several test cases (which will be private to you). However, partial credit may still be awarded for both questions, even if your solutions do not pass the test cases on Gradescope.
*** PLEASE BUDGET YOUR TIME WISELY! ***
DO NOT SPEND TOO MUCH TIME FIXING COMPILATION ERRORS! It is better for you to have three solutions that are nearly correct but don’t compile, than one solution that is perfect and two solutions that are incomplete because you spent too much time finding compiler errors in the first problem.
You will only be able to submit this CANVAS assignment once. Please check your work before you submit! However, you may submit your written solutions to Gradescope as many times as you want, as long as you do so before the deadline.
Good luck!
Questions 1-24: Multiple Choice [60 points]
Each question in this section is worth 2.5 points. There is ONLY ONE correct answer per
There is no penalty for wrong answers on the multiple choice section, so it is to your benefit to record an answer to every question, even if you are not sure what the correct answer is. The questions vary in difficulty, so try not to spend too much time on any one question.
When asked about memory complexity, consider all possible sources (stack and heap).
The term “binary search tree” refers to a standard implementation that does not self-balance, unless explicitly stated otherwise.
Please budget your time wisely!
Question 1 2.5 pts
Given a hash table with quadratic probing and a hash function h(k) = k % 11, which of the following accurately depicts the hash table after the following keys are inserted: 4, 19, 23, 1, 34
Question 2 2.5 pts
Suppose you are given an unsorted array of n integers. What is the best possible average-case time complexity to determine if two distinct values exist in this array that sum to 0? For example, given , you would return TRUE.
None of the Above
Question 3 2.5 pts
For a hash table with load factor , that resolves collisions using separate chaining and allows duplicate keys, which one of the following is FALSE?
The average-case time complexity of insertion is The average-case time complexity of search is The average-case time complexity of removal is None of the above
Question 4 2.5 pts
What is an advantage of open addressing when compared to separate chaining?
Clustering is less sensitive to the hash function
Less wasted space
The need to resize where there is not enough space in the hash table Smooth performance degradation
None of the above
Question 5 2.5 pts
Suppose you are given three poor hash functions, , , and , each of which must produce
values in the range about
. Using any one hash function causes collisions frequently (eg.
infrequently (eg.
is likely to be the best composite hash function
times, where about
). Using different hash functions causes collisions times, where ). Which one of the following
(with minimal collisions)?
Question 6 2.5 pts
Which of the following statements about BSTs are FALSE?
Each BST node has at most two children.
Smaller elements in a BST are to the left of the tree and larger elements are to the right. A valid BST must be a complete tree.
Every BST node has a parent node except for the root.
All of the above statements are false
Question 7 2.5 pts
Which one of the following statements about AVL trees is FALSE, as they were described in lecture?
The key of any node is always greater than the keys of all the nodes in its left subtree and less than or equal to the keys of all the nodes in its right subtree.
The complexity of an AVL trees functions depend on the height of the tree.
At most, only 2 rotations are needed to rebalance a tree during insertion, assuming we have been consistently keeping its invariants up to that point.
Once we have rotated a node, we can stop checking the rest of the tree for imbalances. For a double rotation, we do not evaluate the balance after the first rotation.
Question 9 2.5 pts
The pre-order, in-order, and post-order traversal of this tree are:
Pre: [9, 4, 3, 6, 5, 7, 17, 22, 20]; In: [3, 4, 5, 6, 7, 9, 17, 20, 22]; Post: [6, 4, 3, 5, 7, 9, 20, 22, 17] Pre: [9, 17, 22, 20, 4, 6, 7, 5, 3]; In: [3, 4, 6, 5, 7, 9, 17, 22, 20]; Post: [3, 5, 7, 6, 4, 20, 22, 17, 9] Pre: [6, 4, 3, 5, 7, 9, 20, 22, 17]; In: [3, 4, 5, 6, 7, 9, 17, 20, 22]; Post: [20, 22, 17, 7, 5, 6, 3, 4, 9] Pre: [9, 4, 3, 6, 5, 7, 17, 22, 20]; In: [3, 4, 5, 6, 7, 9, 17, 20, 22]; Post: [3, 5, 7, 6, 4, 20, 22, 17, 9] Pre: [9, 17, 22, 20, 4, 6, 7, 5, 3]; In: [3, 4, 5, 6, 7, 9, 17, 20, 22]; Post: [20, 22, 17, 7, 5, 6, 3, 4, 9]
Question 8 2.5 pts
To traverse through and print all values in a binary search tree (std::map
map::begin(), map::upper_bound(K) map::upper_bound(K), map::end() map::find(K), map::begin() map::begin(), map::lower_bound(K) map::begin(), map::end()
Question 10 2.5 pts
After performing the following operations on the given AVL tree, what is the parent node of 9? For the delete operation, assume the inorder successor is used to replace the deleted node.
1. Insert 9 2. Delete 18 3. Insert 17
2 7 12 15 17
Question 11 2.5 pts
For which of the following kinds of graphs do we prefer the adjacency matrix representation over the adjacency list representation?
Dense Directed
Question 12 2.5 pts
If you have to model a router network as a graph, where the vast majority of the routers are connected to a few other routers, which type of graph representation should you use?
Adjacency list, which saves space because most nodes will have only a few edges compared to vertices. So the list will save memory by not representing non-existent edges.
Adjacency matrix, due to the increase in access speed (and in this situation a matrix will not use significantly more memory than a list).
It is impossible to know which graph representation is the best.
A graph is not the preferable model for this type of network, you should use some other data structure. None of the above.
Sparse Undirected Weighted
Question 13 2.5 pts
Suppose that you are given a dense graph, where all edge weights are equal. Which of the following algorithms will give you the shortest possible path?
I. II. III. IV.
Breadth-first search Depth-first search Dijkstra’s algorithm Prim’s algorithm
Both I and II Both I and III III only
Both III and IV
Question 14 2.5 pts
Which of the following is TRUE about Kruskal’s algorithm?
Kruskal’s algorithm is used to find the shortest path between two vertices in a graph.
Union-find data structures can be used to efficiently implement Kruskal’s algorithm.
Kruskal’s algorithm is always equivalent to Prim’s algorithm in time complexity, no matter the graph type.
When using Kruskal’a algorithm in practice for large, dense graphs, the time requirements can be problematic, even though the space required is small.
In Kruskal’s algorithm, the edges chosen to be part of the MST under construction always form a single tree.
All of I, II, III, and IV
Question 15 2.5 pts
You are given a graph represented by the adjacency matrix:
abcdef a 1481
Using Kruskal¡¯s algorithm, what would be the order of the lengths of the edges added to the MST?
Ties are broken by alphabetical ordering of the pairs.
1, 2, 3, 4, 5 1, 2, 3, 4, 14
Question 16 2.5 pts
Consider a graph with 4 nodes: MSTs exist for this graph?
, with the following distance matrix. How many distinct
1 4 7 16 20
1, 2, 3, 5, 14 1, 2, 4, 5, 15 1, 5, 2, 3, 15
Question 17 2.5 pts
For which of the following problems will a greedy algorithm always produce the optimal solution, without excessive time spent?
Minimal-color Graph Coloring Knapsack Problem
Question 18 2.5 pts
Which one of the following algorithms is best described as a divide-and-conquer algorithm?
Bubble sort Heapsort Merge sort
Sorting an array
Travelling Salesperson Problem Minimal Spanning Tree
Question 19 2.5 pts
Consider an -by- array filled entirely with 0 and 1 values. The zeros form an -by- rectangle ( and ). This rectangle contains the corner with coordinates (0,0). All other values outside this rectangle are ones. Here is an example with ,
, , , with (0,0) at the top left corner:
You know and , but you need to find and . How long will this take with the fastest possible algorithm?
Question 20 2.5 pts
Suppose we have this solution to the N-Queens problem, in which we want to find all ways to place N queens on an NxN board, such that no queen is on the same row, column, or diagonal as another queen.
vector
vector
if (partialSolution.isInvalid())
return ret;
if (partialSolution.isComplete()) {
ret.push_back(partialSolution);
return ret; }
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
Solution nextSolution = partialSolution;
if (!nextSolution.hasQueenAt(i, j)) {
nextSolution.placeQueenAt(i, j);
for (auto solution : solveNQueens(N, nextSolution))
return ret; }
ret.push_back(solution);
Which of the following are true?
I. This code finds all valid solutions to the N-Queens problem. II. This code may generate duplicate solutions.
III. This code prunes partial solutions in an effective way.
II and III
I, II, and III
Question 21 2.5 pts
There are 20 potatoes, all are the same size, but some are heavier than others. The potatoes are lined up in order of weight. You are given a knapsack large enough to hold 5 potatoes. Which method gives the fastest solution to fitting the most weight in the knapsack?
Brute force (mashed potatoes, anyone?) Greedy
Dynamic programming
Backtracking
Branch and Bound
Question 22 2.5 pts
Which of the following statements is NOT correct about dynamic programming?
Dynamic programming is not useful when a problem divides into independent sub-problems. Dynamic programming trades space for time.
The bottom-up approach is usually implemented in recursive form.
The top-down approach only computes needed sub-cases.
None of the above.
Question 23 2.5 pts
Given the following graph, each of the choices below represent a state of the table used in Dijkstra¡¯s Algorithm. If Djikstra¡¯s Algorithm is applied starting with node A, which of these states does not belong?
All of the above states are visited by the algorithm
Question 24 2.5 pts
Assume you are implementing a dynamic programming approach to the knapsack problem, and we are trying to find the maximum possible value you can take in your knapsack of size/weight 5. (0/1 knapsack: no repetition of items allowed.) You have the following items:
The following table is just for your computations, we will not grade it nor give partial credit. Some of the values in the table have been filled up for convenience.
What would be the value of T?
Questions 25-26: Written Questions [40 points]
The point distribution of questions in this section is as follows: Question 25 20 points
Question 26 20 points
Instructions:
Please type your solutions in the provided starter files.
You do not have to use all of the libraries that are included - they are included in case you need them.
The directions for each problem will specify which STL algorithms/functions may be used in your solution.
Solutions that exceed the allowed line count will lose one (1) point per line over the limit. Partial credit will be awarded for partial solutions.
Errors in program logic or syntax may result in a reduced score.
Be sure to consider all possible sources of memory (stack and heap) and time complexity.
Please budget your time wisely! You may submit to Gradescope as many times as you'd like, provided that you make all submissions before your exam's end time.
DO NOT SPEND TOO MUCH TIME FIXING COMPILATION ERRORS! It is better for you to have two solutions that are nearly correct but don't compile, than one solution that is perfect and one solution that is incomplete because you spent too much time finding compiler errors in the first problem. There will be opportunities for partial credit!
Make sure to pay attention to the indicated time and space complexities. Failure to achieve the correct complexity class could result in a substantial reduction in score.
The following questions are NOT ordered by difficulty, so it may be in your best interest to skim all the questions so that you can tackle the questions in the order you are most comfortable with. For example, if you are confident in your ability to solve dynamic programming problems, it may be better to work on the dynamic programming question first (look at the question titles). However, if you are more comfortable with the other final exam topic (e.g., hash tables, trees, graphs, etc.), it may be better to work on the other written question first. Regardless of what order you tackle the questions in, it is important to keep track of time! If you find yourself stuck on a question, try coming back to it later if you have other questions you still need to answer.
PotatoBot Family Tree [20 points]
See @10 on Piazza (https://piazza.com/class/ksppe8s8o73tz?cid=10) (type @10 in the search box) for instructions how to use the Google Form to download the starter files (https://forms.gle/7YmFxzvDQgL39eGRA) for both questions at once. The file for this problem is named question_25.cpp
Instructions:
The EECS 281 PotatoBot comes from a family of smart Potatoes! The ¡°Potato¡± family tree is represented using the following struct:
In the above, notice that we keep track of the "smart quotient" (SQ) for each potato. To help 281 staff identify the "next-level" PotatoBots, your task is to write a function to calculate the average smart quotient for a potato and all its descendants. If a Potato has no children, its children vector (declared above) will be empty. All SQs will fall in the range [-281, 281], and a Potato¡¯s unique ID is its level order index (i.e. the root potato has ID 0, its leftmost child has ID 1, and so on).
Suppose you have the following potato family tree (integers to the left of the potato are the unique ids):
Average SQ (ASQ) of the root Potato 0 is (20 + (-27) + 9 + 3 + 2 + 2) / 6 = 9 / 6 = 1.5
9 comes from summing the SQs of Potato 0 and all of its descendants
6 comes from the number of potatoes in the subtree with Potato 0 as the root
ASQ of Potato 1 is -27 / 1 = -27
-27 comes from summing the SQs of Potato 1 and all of its descendants (there are none, so we only consider the SQ of Potato 1 itself)
1 comes from the number of potatoes in the subtree with Potato 1 as the root
ASQ of Potato 2 is (9 + 3 + 2 + 2) / 4 = 16 / 4 = 4
16 comes from summing the SQs of Potato 2 and all of its descendants
4 comes from the number of potatoes in the subtree with Potato 2 as the root
ASQ of Potato 3 is 3 / 1 = 3 ASQ of Potato 4 is 2 / 1 = 2 ASQ of Potato 5 is 2 / 1 = 2
You do NOT need to worry about decimal precision or overflow. Do NOT use
Your function will be given a single Potato * that points to the root of the “Potato” family tree.
struct Potato {
double sq;
// smart quotient
// unique potato id
// potato children
vector
Potato(double sq_in, int id_in) : sq{sq_in}, id{id_in} {}
Your function should print out the average SQ values for every Potato in order of Potato ID. For example, if given the above tree, you would print out the following:
Potato 0 ASQ: 1.5
Potato 1 ASQ: -27
Potato 2 ASQ: 4
Potato 3 ASQ: 3
Potato 4 ASQ: 2
Potato 5 ASQ: 2
Constraints
O(n) time and auxiliary space, where n is the total number of potatoes in the input tree. Maximum Lines of Code: 30 lines (points deducted if solution is longer)
Implementation
Upload your file to Gradescope as question_25.cpp, with the same spelling and capitalization. You may use anything from the cstdlib or the STL, create any new data types, or add any helper functions as needed; the starter file has a basic set of includes and is using namespace std.
Dynamic Programming: Mastermind DP [20 points]
See @10 on Piazza (https://piazza.com/class/ksppe8s8o73tz?cid=10) (type @10 in the search box) for instructions how to use the Google Form to download the starter files (https://forms.gle/7YmFxzvDQgL39eGRA) for both questions at once. The file for this problem is named question_26.cpp
Instructions
Mastermind DP is participating in the town’s annual escape room competition. The objective of the competition is to start at the bottom right room of a grid map and unlock adjacent rooms until you reach the top left room in the shortest amount of time (in minutes). DP has trained hard so before even participating in the competition, DP knows the amount of time each room will take for them to break out and move to an adjacent room. Each room has two exits (i. e., each room has two adjacent rooms).
The first exit goes to the room directly west of the current room.
The second exit goes to th
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com