Please enable JavaScript.
Coggle requires JavaScript to display documents.
COMP252 Algorithm & Data Structure - Coggle Diagram
COMP252 Algorithm & Data Structure
Introduction
Stable Matching Problem
Proof of Correctness
Give an algorithm
Analyze Time Complexity
Man-optimal and Woman-optimal version
Extends to hospital-student matching
Proof of Termination
Five Representative Problems
Time Complexity
Polynomial Time
Asymptotic Order of Growth
Lower
Tight
Upper: O
P and NP diagram
Limit Theorems
Addition Rule: f+g is O(max{f,g}))
Compare asymptotic notations
Divide and Conquer
Master Theorem
Solve with homogeneous equations
Applications
Find closest pair
Integer Multiplication
Merge Sort (recursion/ iteration)
Matrix Multiplication
Solve by constructive induction
Selection Algorithm (Find median of numbers)
Graphs
Breadth First Search
Use BFS to Check Bipartiteness
DAG: Directed Acyclic Graphs
Check connectivity
Graph basics
Binary Search Tree
Red Black Tree
Floyd's Algorithm
Greedy Algorithm
Interval scheduling (Sort by finish time)
Interval partitioning (Sort by start time)
Minimize Lateness (Sort by earliest deadline)
Dijkstra's Shortest Path Algorithm (Keep selecting nearest node)
Minimal Spanning Tree
Prim's Algorithm (Keep selecting nearest node)
Kruskal's Algorithm (Sort by increasing cost of edges)
Reverse-Delete Algorithm
Lemma: Union-Find Data Structure
Clustering
Dynamic Programming
Bellman-Ford Algorithm for shortest path
Segmented Least Squares
Weighted Interval Scheduling
RNA secondary structure
Sequence alignment
Network Flow
Generic Ford-Fulkerson algorithm
Scaling-Max-Flow algorithm
Max Flow & Min Cut
Applications
Bipartite Matching
Edge-disjoint Paths
Baseball Elimination
Image Segmentation
Project Selection
Circulation
Linear time sorting &Randomized algorithm
Counting sort and Radix sort
Global Min Cut (Karger's Contraction)
Contention Resolution
Randomized Quicksort
Universal Hashing