|
Cs 61b: Final Review Data Structures
|
tarix | 28.06.2018 | ölçüsü | 0,6 Mb. | | #52047 |
|
Data Structures Amir Kamil and Jack Sampson
DISCLAIMER We have NOT seen the exam. We do NOT know the format of the exam What we are presenting is what we “think is important” for the exam
Review Topics Inheritance, Method Calls Data Structures - Binary Search Trees
- B-Trees
- Heaps
- Hash Tables
- AVL Trees
Graphs - DFS, BFS
- Topological Sort
- Strongly Connected Components
Inheritance/Method Calls Given the class definitions on the next slide, which lines in class foobarbaz are illegal?
Inheritance
Inheritance/Method Calls Access table: Static methods called according to static type Child type can be assigned to parent variable without a cast, but the reverse requires one, and the dynamic types must match
Inheritance
Asymptotic Analysis O – Upper bound/Worst case Ω – Lower bound Ө – both o – strictly Upper bound More detail…
Asymptotic Analysis T(n) is O( f(n) ) if and only if there exists positive constants C and N such that T(n) <= C f(n) for all n >= N
Asymptotic Analysis T(n) is O( f(n) ) if and only if there exists positive constants C and N such that T(n) <= C f(n) for all n >= N
Asymptotic Analysis T(n) is O( f(n) ) if and only if there exists positive constants C and N such that T(n) <= C f(n) for all n >= N
Asymptotic Analysis T(n) is Ө( f(n) ) if and only if T(n) is O( f(n) ) and T(n) is Ω( f(n) ) Examples 5n2+1 is Ө(n2) 3n is O(n2), but 3n is NOT Ө(n2) because 3n is not Ω(n2)
Asymptotic Analysis Problem Find the running time of the following code:
Asymptotic Analysis Solution The nested loops give away the answer: the outer loop executes x times, the inner loop an average of x/2 times, for a running time of O(x2).
Trees: Binary Tree Tree: Preorder : ABCEGFD Inorder : CEBAGDF Postorder: ECBDFGA
Trees: BST Problem
Trees: BST Problem
Trees: BST Solution
Trees: B-Tree of Order 4 / 2-3-4 Tree Insert 4 and 6 into the following 2-3-4 tree
Trees: B-Tree of Order 4 / 2-3-4 Tree
Trees: B-Tree of Order 4 / 2-3-4 Tree
Trees: B-Tree of Order 4 / 2-3-4 Tree
Trees: B-Tree of Order 4 / 2-3-4 Tree Remove 16 from the following 2-3-4 tree
Trees: B-Tree of Order 4 / 2-3-4 Tree
Trees: B-Tree of Order 4 / 2-3-4 Tree
Priority Queues – Problem
Priority Queues – Insertion Insert at the last position in the heap Reheapify up: if the element is greater than its parent, swap them and repeat For an element at position n, its children are at 2n+1 and 2n+2 For an element at position n, its parent is at floor[(n-1)/2]
Priority Queues – Solution Add 9, 76, 54, 3, 33, 21 to a max heap, using only the array based representation
Priority Queues – Solution Add 9, 76, 54, 3, 33, 21 to a max heap, using only the array based representation
Priority Queues – Solution Add 9, 76, 54, 3, 33, 21 to a max heap, using only the array based representation
Priority Queues – Solution Add 9, 76, 54, 3, 33, 21 to a max heap, using only the array based representation
Priority Queues – Solution Add 9, 76, 54, 3, 33, 21 to a max heap, using only the array based representation
Priority Queues – Solution Add 9, 76, 54, 3, 33, 21 to a max heap, using only the array based representation
Priority Queues – Problem Remove the max from the heap
Priority Queues – Removal Replace the max element with the last element in the heap Reheapify down: if one or both of its children is larger than it, swap with the larger of the children and repeat For an element at position n, its children are at 2n+1 and 2n+2 For an element at position n, its parent is at floor[(n-1)/2]
Priority Queues – Solution Remove the max from the heap
Priority Queues – Solution Remove the max from the heap
Priority Queues – Solution Remove the max from the heap
Hash Table Problem Draw the structure of a size 7 hash table after insertion of keys with the following hash codes: 0, 95, 21, 6, 64, 74, 3, 54, 34, 75, 10.
Hash Tables High-level idea – 2 components - Big array called hash table of size M
- Function h which maps keys to integer values
For (key, item), use h(key) % M to find location of item in table Linked list in each entry that stores all items that map to that location (chaining)
Hash Table Solution Draw the structure of a size 7 hash table after insertion of keys with the following hash codes: 0, 95, 21, 6, 64, 74, 3, 54, 34, 75, 10.
AVL Tree Problem Given the following AVL Tree, performs these consecutive operations and draw out the tree in each step: - Remove(7)
- Insert (11)
- Insert(12)
AVL Trees AVL Trees are just Binary Search Trees that can rotate their nodes to try to maintain balance. - Two kinds of rotations – single and double
- Can decide which to do based on structure of tree
Insertions/Removals You have 3 nodes of importance, which we will call x, y, and z (z is the parent of y which is the parent of x) - If x is the right child of y, and y is the right child of z, you do a single rotation (same goes for left child of left child)
- If x is the right child of y, and y is the left child of z, you do a double rotation (same goes for left child of right child)
Remove(7)
Remove(7)
Remove(7)
Insert(11)
Insert(12)
Insert(12)
Insert(12)
Searches (BFS and DFS) BFS uses a queue, DFS uses a stack
Searches (BFS and DFS) Problem Perform BFS and DFS on the graph, starting at node 1
Searches (BFS and DFS) Solution Perform BFS and DFS on the graph, starting at node 1
Topological Sort Problem Perform a topological sort on the graph
Topological Sort Perform DFS, computing start/finish times Order nodes by decreasing finish times
Topological Sort Solution Perform a topological sort on the graph
SCC Problem
SCC Algorithm Perform DFS, computing start/finish times Invert graph Repeatedly run DFS on the remaining node with the highest finishing time The nodes marked in each DFS run compose a strongly connected component
SCC Solution Find the strongly connected components of the graph
SCC Solution Find the strongly connected components of the graph
SCC Solution Find the strongly connected components of the graph
SCC Solution Find the strongly connected components of the graph
SCC Solution Find the strongly connected components of the graph
Dijkstra’s Algorithm Problem Find the shortest distances to each node from node 1
Dijkstra’s Algorithm Set all distances initially to ∞, except the start node, which should be set to 0 Construct a min priority queue of the nodes, with their distances as keys Repeatedly remove the minimum element, updating each of its adjacent node’s distances if they are still in the queue and if the updated distance is less than the current distance
Find the shortest distances to each node from node 1
Dijkstra’s Algorithm Solution Find the shortest distances to each node from node 1
Dijkstra’s Algorithm Solution Find the shortest distances to each node from node 1
Dijkstra’s Algorithm Solution Find the shortest distances to each node from node 1
Dijkstra’s Algorithm Solution Find the shortest distances to each node from node 1
Dijkstra’s Algorithm Solution Find the shortest distances to each node from node 1
Dijkstra’s Algorithm Solution Find the shortest distances to each node from node 1
Dijkstra’s Algorithm Solution Find the shortest distances to each node from node 1
Kruskal’s Algorithm Problem
Kruskal’s Algorithm Put each node into a set by itself Sort all the edges in ascending order by their weights Pick the least-weight edge, if the edge connects two nodes in different sets, add the edge to the MST and merge the two sets
Kruskal’s Algorithm Solution Find the MST of the graph, using Kruskal’s Algorithm
Kruskal’s Algorithm Solution Find the MST of the graph, using Kruskal’s Algorithm
Kruskal’s Algorithm Solution Find the MST of the graph, using Kruskal’s Algorithm
Kruskal’s Algorithm Solution Find the MST of the graph, using Kruskal’s Algorithm
Kruskal’s Algorithm Solution Find the MST of the graph, using Kruskal’s Algorithm
Kruskal’s Algorithm Solution Find the MST of the graph, using Kruskal’s Algorithm
Kruskal’s Algorithm Solution Find the MST of the graph, using Kruskal’s Algorithm
Kruskal’s Algorithm Solution Find the MST of the graph, using Kruskal’s Algorithm
Sorting Given the following steps, which sorting algorithms were used in each case?
Sorting Selection Sort Quick Sort
Sorting Do a radix sort on the following sequence, showing each step (1087 643 2532 954 8174 65 340 1752)
Sorting Step 1: sort by ones place (1087 643 2532 954 8174 65 340 1752) (340 2532 1752 643 954 8174 65 1087)
Sorting Step 2: sort by tens place (340 2532 1752 643 954 8174 65 1087) (2532 340 643 1752 954 65 8174 1087)
Sorting Step 3: sort by hundreds place (2532 340 643 1752 954 65 8174 1087) (65 1087 8174 340 2532 643 1752 954)
Sorting Step 4: sort by thousands place (65 1087 8174 340 2532 643 1752 954) (65 340 643 954 1087 1752 2532 8174)
Skip List Problem Write code for searching a skip list for a key. Assume a skip list node is defined as and that the skip list pointer references the top left node.
Skip Lists 2D linked lists Bottom level contains all keys, and each subsequent level contains probabilistically half the keys of the previous level Each level starts at -∞ and ends at +∞ The keys in each level are in ascending order
Skip List Searching Start at top left node If the current key is equal to the search key, return the node If the next key is greater than the search key, go down and repeat search Otherwise go right and repeat search
Skip List Solution Write code for searching a skip list for a key
Skip List Searching
Skip List Searching
Skip List Searching
Skip List Searching
Skip List Searching
Threading Motivations: - Modeling of simultaneous actions
- Counteract I/O Latency
Mechanism: Multiple threads of control - Shared memory space, multiple program counters
Dangers: - Shared access to memory can result in conflicts
- Multiple threads per processor can result in unequal time sharing (see scheduling)
Conflict types: - WAR (write after read)
- WAW (write after write)
- RAW (read after write)
How to avoid shared data conflicts? Locking Dangers of locking? Deadlock
Scheduling Throughput – Average number of tasks completed per unit time CPU Utilization – Average usage of the processor Wait time – time spent waiting for processor Response time – time between assignment of task and first work on task Large values => GOOD: - throughput
- cpu utilization
Large values => BAD (maybe): - wait time
- turnaround time
- response time
I/O ?
The Min-Max Algorithm An algorithm for making the best possible move in a ZERO-SUM-GAME (not applicable to other types of games) MinMax( State, maxtype) if gameover(State) return [null move, score(State)] if (maxtype) return pair with max score from for each valid move from State MinMax(NewState, ! maxtype) else return pair with min score from for each valid move from State MinMax(NewState, ! maxtype) Justification: - In a zero-sum-game, the best move for an opponent is to minimize your score, just as your best move is to maximize your score. This will therefore return the best possible move under the assumption that one’s opponent plays perfectly.
The Min-Max Algorithm The following is an implementation of Min-Max in Common Lisp: ;;; The minimax decision procedure returns the optimal move in the game ;;; using exhaustive generation of the entire game tree. Implementation ;;; uses the fact that the evaluation and utility functions return a list of ;;; values from the point of view of each player, with the "current" player ;;; first. Hence, rather than using #'min, we always use #'max for the ;;; current player. A successor value is passed up the tree using ;;; right-rotation. This works for any number of players. ;;; The notation "a+s" means an (action . state) pair. (defun minimax-decision (state game) (car (the-biggest #'(lambda (a+s) (first (right-rotate (minimax-value (cdr a+s) game)))) (game-successors state game)))) (defun minimax-value (state game) (if (game-over? game state) (terminal-values state) (right-rotate (the-biggest #'(lambda (values) (first (right-rotate values))) (mapcar #'(lambda (a+s) (minimax-value (cdr a+s) game)) (game-successors state game))))))
Min-Max with cutoff (defun minimax-cutoff-decision (state game eval-fn limit) "Return the best action, according to backed-up evaluation down to LIMIT. After we search LIMIT levels seep, we use EVAL-FN to provide an estimate of the true value of a state; thus the action may not actually be best." (car (the-biggest #'(lambda (a+s) (first (right-rotate (minimax-cutoff-value (cdr a+s) game eval-fn (- limit 1))))) (game-successors state game)))) (defun minimax-cutoff-value (state game eval-fn limit) (cond ((game-over? game state) (terminal-values state)) ((<= limit 0) (funcall eval-fn state)) (t (right-rotate (the-biggest #'(lambda (values) (first (right-rotate values))) (mapcar #'(lambda (a+s) (minimax-cutoff-value (cdr a+s) game eval-fn (- limit 1))) (game-successors state game)))))))
Min-Max with cutoff (defun game-successors (state game) "Return a list of (move . state) pairs that can be reached from this state." (mapcar #'(lambda (move) (cons move (make-move game state move))) (legal-moves game state))) (defun terminal-values (state) "Return the values of the state for each player." (mapcar #'(lambda (player) (getf (game-state-scores state) player)) (game-state-players state)))
alpha-beta pruning (defun alpha-beta-decision (state game eval-fn &optional (limit 4)) "Return the estimated best action, searching up to LIMIT and then applying the EVAL-FN." (car (the-biggest #'(lambda (a+s) (first (right-rotate (alpha-value (cdr a+s) game (game-worst game) (game-worst game) eval-fn (- limit 1))))) (game-successors state game)))) (defun alpha-value (state game alpha beta eval-fn limit) (cond ((game-over? game state) (terminal-values state)) ((= 0 limit) (funcall eval-fn state)) (t (dolist (a+s (game-successors state game) (list alpha (- alpha))) (setq alpha (max alpha (first (right-rotate eval-fn (- limit 1)))))) (when (>= alpha (- beta)) (return (list (- beta) beta)))))))
alpha-beta pruning (defun beta-value (state game alpha beta eval-fn limit) (cond ((game-over? game state) (terminal-values state)) ((= 0 limit) (funcall eval-fn state)) (t (dolist (a+s (game-successors state game) (list beta (- beta))) (setq beta (max beta (first (right-rotate (alpha-value (cdr a+s) game alpha beta eval-fn (- limit 1)))))) (when (>= beta (- alpha)) (return (list (- alpha) alpha)))))))
Cool tree variants The threaded tree: - Motivations:
- Inorder traversals are common
- Naive BST implementation can waste space (~half of all child pointers are null)
- Mechanism:
- Add boolean flag to pointers (or do fun polymorphism) so as to have leaf nodes point to the next node in an inorder traversal
- Results:
- For a minimal change in the space requirements and structure of a tree, inorder traversals can now be computed using a straightforward iterative algorithm
Cool tree variants continued The B+ tree: - Motivations:
- Range queries are common
- size of Data >> size of Key, so treat differently
- Mechanism:
- Start with B-tree
- Differentiate between Leaf and index nodes. Index nodes hold keys, leaf nodes hold data. Key values for all data are in leaf nodes.
- Insert and delete as before, except keys are copied up on split, not moved, and keys may remain on delete for data that no longer exists
- Add next and previous fields to all leaf nodes, forming a doubly linked list
- Results:
- Range query now straightforward to return result for - tree now optimized for contiguous storage on physical media
Credits Thanks to CS 61b staff of Thanks to Steve Sinha and Winston Liaw Thanks to - CMU – MIT
- Cornell – Johns Hopkins U
for slide and example ideas
Dostları ilə paylaş: |
|
|