CS146 notes PDF

Preview

Summary

lecture notes for 146 data structures...

Description

D1 Sort and Algorithm D2 Data Structures8 Insertion Delete detrimental for B trees but there are solutions

1/29/2015 Stacks, Queues, Nests, Trees

Stacks LIFO pancakes push insert pop remove size is fixed so need to adjust accordingly Example stack S, to find 6th index use peek[S]-6 Not needed to remove empty areas of a stack

pop function can adjust pointer to element that is below desired popped value, then return "above" the below value to desired value EX: 5 & 4 pointer @ 5 pointer @ 4 pop index w/ 5 - 1 return pop index w/ 4 + 1 to get 5

Queues FIFO enqueue insert dequeue remove Queues more efficient if implemented as a circular (linked) list

Linked Lists sequential & dynamic size vs array list (which is randomly accesible & fixed size) Doubly linked better but at cost of more memory one element in linked list, next is null one element in doubly linked list, next and prev is that element sentinels extra dummy pointers to use for head & tail, efficient to avoid having to traverse through insertion/deletion(?)

2/3/2015 Trees cont. Binary Trees need to look out for balance because insertion/deletion causes unbalance and thus ruins the speed of searching

2/5/2015 Hash

2/10/2015 2i+1 right child 2i left child i/2 for parent ^^in a binary heap (mimicks binary tree in an array), root to half of array is all intermediate nodes & root, half of array to end is all leaves Leaves for most part will be unbalanced but everything above that in heap should be balanced.

2/11/2015 Binomial Heaps, smaller top, higher bottom height measured from leaves up

depth measured from root down (formula: k choose i) cannot have same degree k (depth) in one binomial tree binomial link to merge 2 binomial trees of same degree to one of higher degree binomial heap union is essentially a repetitive binomial link binomial heap insert, if want to insert, create a new heap with one node and then use union again to properly place it union can be used for traditional union, insert and delete methods

2/16/2015 Fibonacci Heaps Set of unordered trees, each node has a boolean to check whether or not child of a node exists has union, extract min,consolidate,link,decrease key, cut, cascading cut, heap delete

2/18/2015 Binary Search Tree Tree insert

2/26/2015 AVL tree (goal of this model is maintaining O(logn) of tree) difference between left and right will never exceed 1. |left-right|>>> greater than or equal to ~

Disjoint Sets

4/30 Shortest Paths Can be applied for shortest path, or compatibility/etc Expect Dijkstra algorithm for graph on final (TBD, its a possibility high one) Floyd-Warshall Algorithm (not that applicable in real world but still suggested to know) Bellman-Ford algorithm

5/7 P(Polynomial) NP(Non-Polynomial) NPC(NP-complete) - Completeness P is just polynomial algorithms such as worst case O(n^k) NP is just hard algorithms that aren't P

NPC is a type of NP in which no polynomial algorithm has been found, demonstrated that no efficient algorithm is likely to exist all NPC are NP, not all NP are NPC NP has a verifible solution, but cannot be discretely solved NPC has been unproven to be solveable, nearly impossible if NPC can be solved in polynomial-time then all NP can be solved in polynomial time (not proven but recognized as so til not)

*FUNDAMENTALS of CS...