Data Structure and Algorithm

• Presentations in weekly "Data structure & algorithm" study
• This study curriculum follows the Roadmap by 'stack07142'.
• This repo is maintained by 오서영, 강성원, 정명지
• Jul. 10, 2020 ~ Aug. 21, 2020

Reference

[1] [Algorithm Problem Solving Roadmap] stack07142/BOJ  
https://github.com/stack07142/BOJ/blob/master/README.md

     

1. Complexity Predictions & Analysis

• Time Complexity -> Big O notation
• Space Complexity

| Presentation |

2. Mathematic #1

• Permutation
• Combination
• Prime Number -> Eratostheneen seula
• GCD, LCM -> Euclidean algorithm
• Matrix

| Presentation |

3. Data Structure #1

• Stack
• Quene
• Deque
• Disjoint Set (Union - Find)
• PriorityQueue

| Presentation |

4. Data Structure #2 - Tree

• Heap -> Max Heap, Min Heap
• Segment Tree
• Fenwick Tree
• Red Black Tree
• Treap
• Binary Search Tree

| Presentation |

5. Exhaustive Search

• Brute-Force
• Backtracking -> N Queens
• Optimization Problems -> TSP
• Divide & Conquer -> Binary Search

| Presentation |

6. Greedy Algorithm , Bitmask

| Presentation |

7. String

• Palindrome -> Manacher's Algorithm
• Huffman coding
• Trie
• Suffix Tree

| Presentation |

8. Matching Problems

• KMP Algorithm
• Karp-Rabin Algorithm
• Boyer-Moore Algorithm
• Aho-corasick
• Z Algorithm
• Suffix Array

| Presentation |

9. Dynamic Programming #1

• 0-1 Knapsack Problem
• LCS, LIS -> O(N^2), O(NlogN)
• Subset

| Presentation |

10. MST (Minimum Spanning Tree)

• Kruskal's Algorithm
• Prim's Algorithm

| Presentation |

11. Sorting

• Bubble Sort
• Insertion Sort
• Selection Sort
• Quick Sort
• Merge Sort
• Heap Sort
• Radix Sort
• Couting Sort
• Shell Sort

| Presentation |

12. Graph #1

• Searching
  • DFS
  • BFS
• Shortest Path
  • Dijkstra's Algorithm
  • Bellman-Ford Algorithm
  • Floyd-Warshall Algorithm
  • SPFA (Shortest Path Faster Algorithm)
• Graph modeiling
• Topological Sort

| Presentation |

13. Geometry

• Cross / Dot Product
• Convex Hull
• Graham Scan
• Angle Sort
• CCW
• Line Intersection
• Plane / Line Sweeping
• Rotating Calipers

| Presentation |

14. Mathematics #2

• binomial coefficient -> Pascal's triangle
• Catalan Number
• Euler's phi function
• Fermat's little theorem
• Gaussian elimination
• Modular Arithemetic
• Discrete Mathematics -> The Pigeonhole Principle
• Stirling numbers of the second kind

| Presentation |

15. Tree #2

• LCA (Lowest Common Ancestor)
  • Using Preorder DFS & Segment Tree
  • Using Sparse Table (recommended)

16. Range Query

• Segment Tree -> Segment Tree Lazy Propagation
• Two Pointers Algorithm
• Sliding Window Algorithm

17. Graph #2 - Network Flow - Maximum Flow

• Ford - Fulkerson -> Edmond Karp
• Dinic's Algorithm
• MCMF (Minimum Cut Maximum Flow)
• MCMF(Minimum Cost Maximum Flow)
  • Using Bellman-Ford Algorithm of SPFA
  • Hungarian Method
• Bipartite Matching

18. Graph #3

• Eulerian Path -> Hierholzer's Algorithm
• SSC (Strongly Connected Component)
  • Tarjan's Algorithm
  • Kosaraju's Algorithm

19. Dynamic Programming #2

• DP Optimization
  • Knuth Optimization
  • Divide & Conquer Optimization
  • Convex Hull Optimization