I am assuming you know at least one programming language and the concept of object / pointers. I will mention algorithms and data structures in increasing order of difficulty.
First start with Linear data structures and algorithms.
- Arrays
- Linked List
- Stack
- Queues
Then move to basic algorithms :
- Sorting - Merge Sort, Insertion Sort, Quick Sort, Number of inversions
- Matrix Multiplication (just know the algo if not implement it)
- Prime Sieving
- Modular Math including multiplication and division
- Euclidean Algorithm for GCD, Modular Inverse, Fast Exponentiation
- Fibonacci number with matrix multiplication
- Probability distribution and expected value
- Stats - Mean, Median, Variance, Bayes theorem
Then one can learn some popular algorithmic techniques:
- Divide and Conquer - Binary Search, Maximum Subarray
- Greedy Algorithms - Activity Selection, Huffman encoding
- Dynamic Programming - Matrix Chain Multiplication, Knapsack,
- Linear Programming - Variable Maximisation, Linear time sorting
- String Algorithms - Manacher, LCS, Edit Distance
Then comes some typical non-linear data structures:
- Trees - Binary Tree, General Tree, Lowest Common Ancestor
- Binary Search Tree - Inorder Traversal, Level order traversal, finding kth largest element, diameter, depth, number of nodes, etc.
- Heaps - Array Implementation, Heapify, Heap Sort
- Union Find
- Hash Table - Linear Probing, Open addressing, Collision avoidance
Then you can learn about Graphs:
- Adjacency List, Adjacency Matrix, Weighted Edge Graphs
- Basic Traversal algos - Breadth First Search, Depth First Search, etc
- Shortest Path Finding Algorithm - Dijkstra, Floyd Warshal, Bellman Ford
- Minimum Spanning Tree - Kruskal's Algo, Prim's Algo
By this time you are already pretty good with programming. You will do better than most of undergrad CS students. If you want to learn more and delve deep read more.
Advance Tree and Graph :
- Balanced Trees - AVL, Red-Black
- Heavy Light Decomposition, B+ Trees, Quad Tree
- Advance Graph - Min Cut, Max Flow
- Maximum Matching - Hall's Marriage
- Hamiltonian Cycle
- Edge Graphs / Line Graphs
- Strongly Connected Components
- Dominant Sub-Graph, Vertex Cover, Travelling Salesman - Approx algos
Advance String Algorithms :
- Knuth Morris Pratt Algorithm
- Rabin Karp Algorithm
- Tries and Compressed Tries
- Prefix Trees, Suffix Trees, Suffix Automation - Ukkonen Algorithm
Advance Math:
- Fast Fourier Transformation
- Primality Testing
- Computational Geometry - Closest point pair, Voronoi diagram, Convex Hull
General Advance topics :
- Iterating through all combination / permutation
- Bit manipulation
No comments:
Post a Comment