TOPICS
• Divide-and-conquer.
• Merge Sort
• Binary Search
• Dynamic programming
• Knapsack Problem
• Longest Common Subsequence
• Matrix Chain Multiplication
• The sorting and searching algorithms we have studied, and applications of those algorithms to solve problems.
• Insertion Sort
• Merge Sort
• Binary search
• QuickSort
• Randomized QuickSort (Randomized Algorithm)
• Hashing, binary search trees, and heaps.
• Hashing
• Chained Hash Tables
• Open Addressing
• Binary SearchTrees
• Graph search algorithms (BFS and DFS), and applications of those algorithms to solve problems.
• Breadth-First Search
• Depth-First Search
• Shortest paths algorithms, and applications of those algorithms to solve problems.
• DIJKSTRA’S ALGORITHM TO FIND SHORTEST WEIGHT PATH (CAN’T DEAL WITH NEGATIVE WEIGHT EDGE GRAPH) (USE ARRAY SLOW, USE MIN-HEAP QUEUE FAST)
• BELLMAN-FORD ALGORITHM TO FIND SHORTEST WEIGHT PATH ON GRAPH THAT CAN HAVE NEGATIVE WEIGHT EDGES (SLOW)
• DAG-SHORTEST PATH ALGORITHM TO FIND SHORTEST WEIGHT PATH ON GRAPH THAT CAN HAVE NEGATIVE WEIGHT EDGES(FAST), FIRST RUN DFS TO RANK VERTICES IN TOPOLOGICAL ORDER – DECREASING THEN JUST RUN ONE ITERATION OF BELLMAN-FORD USING VERTICES IN THE TOPOLOGICAL ORDER.
• REDUCTION METHOD: MODIFY INPUT OF A GIVEN ALGRORITHM TO SOLVE A DIFFERENT ALGORTIHM
• MST algorithms, and applications of those algorithms to solve problems.
• KRUSKAL’S ALGORITHM (GREEDY)
• PRIM’S ALGRITHM (ALSO GREEDY)
• Network flow and the Ford-Fulkerson algorithm, applications of network flow to solve problems.
Runtime analysis:
• Master theorem
• Recursion tree
ALGORITHM PSEUDOCODE
• Insertion sort
• Merge sort
• Recursive Binary Search
• QuickSort
• Randomized-QuickSort
• Knapsack Problem
• Longest Common Subsequence
• Matrix Chain Multiplication
• Chained Hash Tables
• Search
• Insertion
• Deletion
• Open Addressing
• Search
• Insertion
• Deletion
• Binary Search Tree
• Query BST
• Insertion and Deletion
• Breadth-First Search
• Depth-First Search
• Dijkstra’s Algorithm(using Min-Heap data structure)
• Min-Heap Operations
• Bellman-Ford Algorithm
• DAG Shortest Paths
• Prim’s Algorithm
• Kruskal’s Algorithm
• FordFulkerson