Eecs281 final sheet

Eecs281 final sheet Hash tables are really good at inserting, removing, and finding elements in a dataset with lots of distinct keys Bad for < > queries on numbers Bad when load factor is high (N/M), N=number of keys M= table size Separate Chaining – store a linked list in each bucket, append key value pair to the end Open Addressing Linear probing – T(K) = (T(k) +i) mode M for I = 0,1,2,3,4 Quadratic probing- T(K) = (T(K) +i^2) 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> Ordered list Post-order - visit left subtree, right subtree, parent BST searh, insert, delete, average O(logn) worst O(n) BFS = visist every node on a level from left to right then go down a level (Breadth First Search, Depth First search) AVL TREE RULES search, insert, delete Average = worst = O(logn) Ensure that a tree stays balanced – [Height(left subtree) – Height(right subtree)] <= 1 for all nodes Four cases- rotate right, rotate left, rotate right then left, rotate left than right Insertions and deletion are the same as BST,b but require checking balance all parents of a new node up to the root for balance and rotating if necessary If node youre deleting has no children, just remove it If it only has one child, move that child up 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 Dijkstras Algorithm Floyd-Warshall algorithm is essentially running Dijkstras with every starting class room MST –given an edge-weighted ,undirected graph, find a spanning tree of minimum weight Spanning tree – a subgraph containg all vertices in the original, connected and acyclic PRIMSKruskalsDijkstras Divide and conquer -divide a problem solution into two or more smaller problems: pref or equal size, solve the smaller instances, and combine the solutions -often recursive -often involves logn complexities (look at the master theorem for why) -quicksort, mergesort Dynamic Programming -remember partial solutions (memorization) -typically fast (faster than non-DP solution) -requires a lot of memory -often looks like D & C, but used when not distinct subproblems This study source was downloaded by 100000857952895 from CourseHero.com on 12-12-2022 01:52:12 GMT -06:00

https://www.coursehero.com/file/37187364/Eecs281-final-sheetdocx/

-we remember the solutions to subproblems because the subproblems overlap Backtracking is used to answer “What choices should I make to satisfy some constraints” Brand+Bound is used to answer “What choices should I make to obtain the best solution” Knapsack approaches, Bruteforce 2^n, optimal Greedy – O(n), not optimal, DP – O(nC), optimal, backtracking, no Brand and bound – initial estimate of best solution is lower bound on knapsack value, nee to estimate upper bound on remaing value of partial solution Memoization Top-Down – write a recursive function, at the start, check if we-ve already done this one, before returning store the result Bottom-Up - store the results in an array/map, build up the array/map starting from a base case, stop when you get to the input youre trying to compute DP tips – 1.what is the recursive solution to this problem 2.how many possible inputs are their? (size of memo) 3.Where can I use the saved information

directed: there are arrows (A points to B, but not vice-versa)

undirected: there are no arrows (there is a connection between A and B)

simple graph: no multiple edges, no loops

multigraph: multiple edges, no loops

lower bound: used in Branch and Bound in the TSP problem. If your lower bound + current path is longer than current best path then break upper bound: used in TSP problem to get a fast, relatively close starting best length to compare against for bounding Hamiltonian path & cycle: a path that visits each vertex only once, is a cycle if the path begins and ends at the same node

From homework 4:

oA SIMPLE graph is a graph that has no loops or more than one edge between any pair of two different vertices.oA graph is CONNECTED if there is a path between each pair of vertices oAn adjacency matrix of an empty graph is an EMPTY matrix oA connected graph T without any cycle is called a TREE oIn a graph, if there exists an edge e = [u, v], then u and v are ADJACENT oA QUEUE data structure is used for BFS, whereas a STACK data structure is used for DFS oA COMPLETE graph of n vertices has n(n-1)/2 edges oThe number of edges in a DENSE graph is close to the maximal possible number of edges oA SPANNING TREE of a connected graph is a tree that contains all vertices and some edges of any weight of G A MINIMUM SPANNING TREE (MST) of a connected, undirected graph is a tree with all vertices connected via the cheapest possible set of n-1 edges Prim's, Kruskal's, and Dijkstra's are considered GREEDY algorithms because they solve the problems by progressively making locally optimal choice at each state of iteration.adjacency lists – good for sparse graphs adjacency matrix – good for dense graphs This study source was downloaded by 100000857952895 from CourseHero.com on 12-12-2022 01:52:12 GMT -06:00

https://www.coursehero.com/file/37187364/Eecs281-final-sheetdocx/

This study source was downloaded by 100000857952895 from CourseHero.com on 12-12-2022 01:52:12 GMT -06:00

https://www.coursehero.com/file/37187364/Eecs281-final-sheetdocx/