1.)Induction 2.)Asymptotic Analysis 3.)Divide and Conquer 4.)Greedy Algorithms 5.)Dynamic Programing 6.)Graphs
¡ñ graphrepresentation ¡ñ BFS/DFS
¡ñ bellman/dijstra
¡ñ prims/kruskal
¡ñ (iftime)all-pairsshortestpath 7.)Proofs: for greedy choice and suboptimality 8.)some complexity theory if time
The focus will be on
Last half of quarter BUT you will use all skills from the first half specifically
Q0.) Algorithm Analysis – analyze code possibly complexity theory question
Q1.)Implement DFS/BFS on sample graph, know and analyze the run-time off.
Implement Bellman/Dikstra on sample graph, know and analyze the run-time off
Q2.)Prims/ Kruskals on sample graph, know and analyze the run-time off
Q3.) Algorithm Design:
Divide & Conquer (see Similar to quizzes and midterms and hws) Greedy (see Similar to quizzes and midterms and hws)
Dynamic Programming (see Similar to quizzes and midterms and
hws)
Graph algorithm design – similar to hw5 or tehse sample questions from the last part of the quarter that could appear in Q3:
c.)
For the above, if you use greedy show both greedy property and suboptimality. If you use dynamic show suboptimality property holds.