CS代考 EECS 281 Final Review Session

EECS 281 Final Review Session

● Friday, June 25th, 2021
● Time slots: 9:00AM – 11:20AM, 4:00PM – 6:20PM (both EST)

● 24 MC, 2 Coding
● Upload your solutions to coding problems on Gradescope
● Try to read through most of the problems before starting
○ This is especially important for the handwritten coding problems
○ Reading through them before starting other parts of the exam lets your mind subconsciously
work on it for the entire time!

● Hash Tables and Hash Collisions
● Binary Trees and Tree Algorithms
● AVL trees
● MST Algorithms
● Algorithm Families
● Backtracking + Branch & Bound
● Knapsack
● Dynamic Programming

Hash Tables and Hash Collisions

Hash Tables – General Overview
● Aims for average case O(1) insert, lookup, and delete.
● Uses a hash function to map keys to an associated hash value (an integer)

Where is it good and where is it bad?
● Remember Project 3
● Hash tables are
○ Good at inserting, removing, and finding elements in a dataset with lots of distinct keys (O(1))
○ Bad for >, < queries on numbers ○ Bad when load factor is high (N/M) ■ N are number of keys ■ M is table size Handling Collisions ● Separate Chaining (Can have load factor > 1)
○ Store a linked list in each bucket, append key value pair to the end

Handling Collisions
● Open Addressing (Load factor must be < 1) ○ Linear Probing ■ T(k) = (T(k) + i) mod M for i = 0, 1, 2, 3, 4... ○ Quadratic Probing ■ T(k) = (T(k) + i2) mod M for i = 0, 1, 2, 3, 4... ○ Double Hashing ■ T(k) = (T(k) + i * T’(k)) mod M for i = 0, 1, 2, 3, 4... ■ T’(k) = q - (T(k) mod q) for some prime q < M Question - Resolution with Double Hashing Consider a hash table storing keys that handles collision with double hashing: ● T(k) = k mod M ● T’(k) = 7 - (k mod 7) ● On collision: T(k) = (T(k) + i * T’(k)) mod M for i = 0, 1, 2, 3, 4... After inserting 35, 22, 44, 33 what would be the index of 33? Question - Resolution with Double Hashing ● On collision: T(k) = (T(k) + i * T’(k)) mod 11 for i = 0, 1, 2, 3, 4... ● T(k) = k mod 11 ● T’(k) = 7 - (k mod 7) Question - Resolution with Double Hashing ● T(k) = k mod 11 ● T’(k) = 7 - (k mod 7) ● T(k) = (T(k) + i * T’(k)) mod 11 Question - Resolution with Double Hashing T(35) = 35%11 = 2 ● T(k) = k mod 11 ● T’(k) = 7 - (k mod 7) ● T(k) = (T(k) + i * T’(k)) mod 11 Question - Resolution with Double Hashing ● T(k) = k mod 11 ● T’(k) = 7 - (k mod 7) ● T(k) = (T(k) + i * T’(k)) mod 11 Question - Resolution with Double Hashing T(22) = 22%11 = 0 ● T(k) = k mod 11 ● T’(k) = 7 - (k mod 7) ● T(k) = (T(k) + i * T’(k)) mod 11 Question - Resolution with Double Hashing Question - Resolution with Double Hashing T(44) = 44%11 = 0 Question - Resolution with Double Hashing T’(k) = 7 - (44 mod 7) = 5 T(k) = (0 + 5 * 1) mod 11 = 5 Question - Resolution with Double Hashing Question - Resolution with Double Hashing T(33) = 33%11 = 0 Question - Resolution with Double Hashing T’(k) = 7 - (33 mod 7) = 2 T(k) = (0 + 2 * 1) mod 11 = 2 Question - Resolution with Double Hashing T’(k) = 7 - (33 mod 7) = 2 T(k) = (0 + 2 * 2) mod 11 = 4 Question - Resolution with Double Hashing Insert 33 -> index 4

Question – Resolution with Double Hashing

Question – Resolution with Double Hashing
T(44) = 59%11 = 4

Question – Resolution with Double Hashing
T(59) = 59%11 = 4
T’(k) = 7 – (59 mod 7) = 4 T(k) = (4 + 1 * 4) mod 11 = 8

Question – Resolution with Double Hashing
T(59) = 59%11 = 4

Question – Invalid Hash Functions
Which of the following are INVALID hash functions for a hash table of size M?
I. H(str) = (str[0] * rand()) % M
II. H(str) = (str[0] – ‘a’) * 503
III. H(str) = (𝚺str[i] * i) % M

Question – Invalid Hash Functions
Which of the following are INVALID hash functions for a hash table of size M? I. H(str) = (str[0] * rand()) % M
This is invalid because hashes must be consistent. II. H(str) = (str[0] – ‘a’) * 503
This is invalid because it might go out of bounds. III. H(str) = (𝚺str[i] * i) % M
This is valid because it fulfills all the properties of a hash.

Trees and Tree Algorithms

Tree Definitions
● Complete
○ All levels filled, except maybe the last, and all nodes in
the last level are as far left as possible. ● Full/Proper
○ Every node has either 2 or 0 children

Traversals
● Preorder
○ Visit the parent, left subtree, right subtree
● In- order
○ Visit left subtree, parent, right subtree
○ BST Squish -> Ordered list
● Post – order
○ Visit left subtree, right subtree, parent
● Level order
○ Breadth First Search
○ Use a queue
○ Think pairing heap destructor

The following code adds 100 numbers to a binary search tree and attempts to find a number.
BinarySearchTree bst;
for (int i = 0; i < 100; ++i) { bst.insert(i); bst.find(280); bst.insert(281); What are the worst-case time complexities of the find(280) and insert(281) operations? The following code adds 100 numbers to a binary search tree and attempts to find a number. BinarySearchTree bst;
for (int i = 0; i < 100; ++i) { bst.insert(i); bst.find(280); bst.insert(281); What are the worst-case time complexities of the find(280) and insert(281) operations? Θ(n), Θ(n) What is the pre-order traversal of this tree? What is the pre-order traversal of this tree? [9, 4, 3, 6, 5, 7, 17, 22, 20] What is the in-order traversal of this tree? What is the in-order traversal of this tree? [3, 4, 5, 6, 7, 9, 17, 20, 22] What is the post-order traversal of this tree? What is the post-order traversal of this tree? [3, 5, 7, 6, 4, 20, 22, 17, 9] Which of these correctly describe this tree? A. Complete, proper, balanced B. Not complete, proper, balanced C. Complete, not proper, not balanced D. Not complete, not proper, balanced, E. Complete, not proper, balanced Which of these correctly describe this tree? A. Complete, proper, balanced B. Not complete, proper, balanced C. Complete, not proper, not balanced D. Not complete, not proper, balanced, E. Complete, not proper, balanced Draw the tree resulting from the post-order and in-order traversals below. Post-order: [2, 1, 4, 3, 7, 6, 8, 5] In-order: [1, 2, 3, 4, 5, 6, 7, 8] Draw the tree resulting from the post-order and in-order traversals below. Post-order: [2, 1, 4, 3, 7, 6, 8, 5] In-order: [1, 2, 3, 4, 5, 6, 7, 8] AVL Tree rules ● Ensure that a tree stays balanced ○ "Balanced" means that |Height(Left subtree) - Height(right subtree)| <= 1 for all nodes ● Four cases ○ Rotate Right ○ Rotate Left ○ Rotate Right then Rotate Left ○ Rotate Left then Rotate Right ● Insertions and deletions are same as BST, but ○ Require checking balance all parents of a new node up to the root for balance and rotating if necessary ○ See https://visualgo.net/en/bst to visualize how a BST works Rotation - Intuition Rotate Right Rotate Left AVL Rotation (Case 1) • Left sub-tree is too heavy, and the left subtree leans to the left Rotate right AVL Rotation (Case 2) Right subtree is too heavy, and the right subtree leans to the right -1 Rotate left 0 1 Is that it? Can this case be handled by the two cases we just saw? Is that it? Can this case be handled by the two cases we just saw? Rotate Right Is that it? Can this case be handled by the two cases we just saw? Rotate Right Rotate Left Is that it? Can this case be handled by the two cases we just saw? Rotate Right Rotate Left AVL Rotation (Case 3) • Left sub-tree is too heavy, and the left subtree leans to the right ○ Rotate the left subtree LEFT and then you have Case 1. +2 AVL Rotation (Case 4) Right sub-tree is too heavy, and the right subtree leans to the ○ left Rotate the right subtree RIGHT and then you have Case 2. Let’s try again Let’s try again Rotate Left on 9 Let’s try again Rotate Left on 9 Rotate Right on 25 Let’s try again Rotate Left on 9 Rotate Right on 25 Algorithm checkAndBal(Node *n) updateHeight(n) if bal(n) > +1
if bal(n->left) < 0 rotateL(n->left)
rotateR(n)
else if bal(n) < -1 if bal(n->right) > 0
rotateR(n->right)
rotateL(n)
checkAndBal(n->parent)
What does the ‘+’ in +1 convey? => Left subtree is bigger!
What if bal(n) > +1?
=> Unbalanced! (since > 1) => Left subtree is bigger

Deletion: 0 Children
If the node you’re deleting has no children, just remove it

Deletion: 1 Child
If it only has one child, move that child up:

Deletion: 2 Children
Otherwise, it has two children. Swap it with its in-order successor or in-order predecessor, then delete it in its new spot. Rebalance from the place it was deleted, if needed.
Both choices always work (but we may tell you which to use)
The successor/predecessor will always have 0 or 1 children (if the node itself has 2 children). It can be thought of as being the rightmost node in the left subtree or the leftmost node in the right subtree respectively.

Deletion: 2 Children
Replace with in-order successor or in-order predecessor, then delete in its new spot.

Let’s replace 25 with inorder predecessor (11)
Delete 25 ? (swap with
predecessor)

Let’s replace 25 with inorder predecessor (11)
(swap with predecessor)

Replace with inorder successor or predecessor (In the exam, you will be told which one). Just remember both work!
Rotate Right on 9

Practice Question
● After inserting 14 and performing any necessary rotations, what would be the produced pre-order traversal?

Practice Question
● After inserting 14 and performing any necessary rotations, what would be the produced pre-order traversal?
● A: 10, 5, 3, 1, 8, 7, 12, 11, 14, 13, 16
● What if the node 10 was deleted, and we
use the successor? (14 isn’t inserted)
● A: 11, 5, 3, 1, 8, 7, 13, 12, 16
● What if nodes 12 and 13 are then
deleted after node 10 is deleted? (14 isn’t inserted)

Graph Representations
Adjacency List
Adjacency Matrix (2D Vector)
Better for sparse graphs (O(E))
Better for dense graphs (always O(V^2))
O(1 + E/V) to find if an edge exists
O(1) look up to find an edge
Either 2D Vector or vector of linked lists

Greedy Algorithms: MSTs

Minimum Spanning Tree
● Given an edge-weighted, undirected graph, find a spanning tree of minimum weight
● Spanning Tree
○ A subgraph containing all the vertices in the original (spanning)
○ Connected and acyclic (tree)

● Start with 2 sets of vertices: ‘innies’ & ‘outies’
○ ‘innies’ are visited set
○ ‘outies ‘ are unvisited set
● Select first innie arbitrarily (usually lowest index)
● Iteratively choose the out-vertex which is closest to any in-vertex
● Best for dense graphs
● Complexity
○ O(V2) with linear search
○ O(E log V) with binary heaps

Starting from vertex 0, in which order would Prim’s algorithm add vertices to the MST in the graph described by the below adjacency matrix?

Starting from vertex 0, in which order would Prim’s algorithm add vertices to the MST in the graph described by the below adjacency matrix?
(0, 4) (0, 1)

Starting from vertex 0, in which order would Prim’s algorithm add vertices to the MST in the graph described by the below adjacency matrix?
(0, 4) (0, 1) (1, 2)

Starting from vertex 0, in which order would Prim’s algorithm add vertices to the MST in the graph described by the below adjacency matrix?
(0, 4) (0, 1) (1, 2) (2, 3)

● Iteratively add lowest weight edges until all vertices connected
● Check for cycle each time
● Best for sparse graphs
● Complexity
○ Pre-sort all Edges O(E log E)
○ Since E < V^2 ■ O(E log E) = O(E log V) MST (True or False) ● If an MST of a graph does not contain some edge of the shortest length, then all edges of the graph must be the same length. ● If this graph is connected and has V vertices, an MST of this graph must contain exactly V − 1 edges. ● When implementing Prim’s algorithm for a dense graph, using a heap is better than using linear search. MST (True or False) ● If an MST of a graph does not contain some edge of the shortest length, then all edges of the graph must be the same length. F. There are some edges with the same length (the shortest). ● If this graph is connected and has V vertices, an MST of this graph must contain exactly V − 1 edges. ● When implementing Prim’s algorithm for a dense graph, using a heap is better than using linear search. MST (True or False) ● If an MST of a graph does not contain some edge of the shortest length, then all edges of the graph must be the same length. F. There are some edges with the same length (the shortest). ● If this graph is connected and has V vertices, an MST of this graph must contain exactly V − 1 edges. T. Have to connect every vertex exactly once. ● When implementing Prim’s algorithm for a dense graph, using a heap is better than using linear search. MST (True or False) ● If an MST of a graph does not contain some edge of the shortest length, then all edges of the graph must be the same length. F. There are some edges with the same length (the shortest). ● If this graph is connected and has V vertices, an MST of this graph must contain exactly V − 1 edges. T. Have to connect every vertex exactly once. ● When implementing Prim’s algorithm for a dense graph, using a heap is better than using linear search. F. Heap: O(ElogV), Linear Search: O(V^2) Dense: |E| ≈ |V|*(|V|-1)/2 MST, Prim’s & Kruskal’s MST, Prim’s & Kruskal’s A: False, multiple potential MSTs B: True, MST algorithms can generally deal with negative edges. C: True, MST is for minimal connection, not shortest paths. D: True, with binary heap -> O(ElogV). When dense, O(ElogV) = O(V^2logV)

DFG forms a cycle.

Greedy Algorithms: Dijkstra’s

Dijkstra’s Algorithm aka Single Source Shortest Path (SSSP)
● Greedy algorithm that finds the shortest path between any one vertex and all other vertices in the graph.
○ Greedily select the next vertex of the shortest distance from the Source
● Complexity
○ V^2 (linear probe to find the closest vertex)
○ |E| log |V| with a priority queue

Dijkstra’s Algorithm

Dijkstra’s Algorithm
A: Dijkstra is greedy.
B: Dijkstra cannot handle negative edge weights.
C: Find the shortest path between the source and every other vertex. D: With priority queue.

Dijkstra’s Algorithm

Algorithm Families

Algorithm Families
● Brute-Force
● Divide and Conquer
● Dynamic Programming (also, later)
● Backtracking
● Branch and Bound

Brute-Force
● Simple – checks all possible solutions, chooses best/satisfactory
● Guaranteed optimal (if it’s an optimization problem)
● Usually inefficient
○ Usually the solution space is enormous

● Use heuristics to make next choice ○ Locally optimal choice
● If locally optimal solutions do not lead to globally optimal then it will not give the optimal
○ E.g., Knapsack
● Sometimes, locally optimal choices do lead to globally optimum
○ E.g., sorting (which algorithms?)
● (Typically) faster than brute-force

Divide and Conquer
● Divide a problem solution into two or more smaller problems, pref o

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts