Categories
xacdo

Algorithm CheckList 43

Basics1. recursive functions
2. Int, long, float, double (memory size)
3. bit operations : &, |, ^, <<, >>, ~
4. big integers(>=10^19) +, -, * operations (without API like BigInteger)
Search & Sort5. depth-first & breadth-first search
6. time & space complexity
7. binary search
8. bubble sort
9. quick sort vs. merge sort (pros & cons)
10. counting sort & radix sort
11. largest rectangular in histogram in O(n)
Data Structure12. stack, queue, deque(double ended queue)
13. Vector(ArrayList) vs. List(LinkedList) (pros & cons)
14. Heap(Priority Queue) push(), pop()
15. DSU(Disjoint Set Union) & Union Find + path compression
16. Indexed Tree & Sparse Table + range sum / min / max
Probability17. permutations (multiset, circular, bracelet, complete)
18. combinations (with duplicated numbers, Binomial theorem, Pascal’s triangle, Catalan numbers)
19. conditional probability (Bayesian)
20. Binomial Distribution, Gaussian Distribution
Discrete Math21. Euler’s Totient function using (not GCD but) sieve of Eratosthenes
22. Fermat’s little theorem, modular multiplicative inverse
23. Extended Euclidean Algorithm
24. Chinese remainder theorem
25. calculate the number of cases, using Inclusion–exclusion principle
Graph26. Adjacency matrix vs. Adjacency list (pros & cons)
27. Dijkstra, Floyd-Warshall, Bellman-Ford algorithm
28. Prim’s algorithm, Kruskal’s algorithm to get MST(Minimum Spanning Tree)
29. DAG(Directed Acyclic Graph)
30. LCA(Lowest Common Ancestor) in Time O(log n)
31. Find Articulation Points & Bridges of bidirectional graph
32. Network Flow theory
String33. String match with KMP, Rabin-Karp fingerprinting, Suffix Array & LCP
34. String to Trie
35. Aho-Corasick algorithm
Geometry36. CCW(Counter ClockWise) function & vector outer product
37. shoelace formula (to calculate polygon area)
38. collision detection of two lines & point detection inside a polygon (using CCW function)
39. Convex hull using CCW function; Time O(n log n)
40. Plane Sweeping (Overlapping rectangles)
Dynamic Prgramming41. Top-down, Bottom-up, Recursive (Pros & Cons)
42. Base cases, Value function, Memoization
43. well-known problems (Knapsack, LIS, Bit Mask DP)

There is a link to this document too.

By xacdo

Kyungwoo Hyun

Leave a Reply

Your email address will not be published.