Final Exam Review
Proper(binary tree?) - each node has either 0 children (leaf) or 2 children; no node has 1 child
Complete - filled in rows, except maybe last which is filled from left to right
In-order traversal - like squishing nodes to a horizontal line, and then going from left to right
Breadth first search
Depth first search
BST
Search Insert Delete
Best case O(1)
Average case O(log n) - only need to search number of levels
Worse case O(n) - search all nodes
Fix worst case BST by balancing it
AVL Tree (Self-Balancing BST)
Rotate RIGHT if left subtree is too heavy/ leans to the left
Rotate LEFT if right subtree is too heavy/ leans to the right
Balancing algorithm
Dynamic Programming
Similar to divide and conquer
Reuse solved subproblems to solve the bigger problems
Need to store values -> memoization
Top down DP
save return values form recursive functions
Bottom down DP - easier to implement
make base case, fill up from there
save values to DP, but only store minimum amount needed
values can be stored in a vector
Assume that you have solutions leading up to big problem, you can make a recurrence relation
Recurrence relation leads to dynamic programming
Prim - buid tree up
Kruskal - add edges that don't form cycle, build subtrees up
O(ElogE)
Backtracking - pruning when you tell a choice is not best/wrong
does the solution exist and if so what is it (any solution)?
Branch & Bound - what is the best solution, backtracking + checking if pre-solution is worse than best, and if solution is better than best
B&B Constraints - pruning with constraints
- TSP: path is cycle, all points
- Knapsack, cost <= budget
- Promising
Backtracking
- Bounds need to be calculated
Backtracking complexity is exponential, but can make it lower exponential with branch and bound?
Maximum: Best so far is a lower bound
Best I can do: highest value I can attain, prune solution is already worse
Minimum: Best so far is an upper bound
Best I can do: lowest value I can attain
Algorithm families
Brute force - simple, optimal, horribly inefficient
Greedy - local heuristics, locally optimal choices
not always optimal, not always efficiency
Selection sort is greedy
Divide and Conquer - partitions
Finding global min of array - greedy
Finding local min of array - divide and conquer