Some basic algorithms/techniques that every successful competitive programmer has in his/her arsenal are:
1. Depth-First Search (Graph Search)
2. Breadth-First Search (Graph Search)(Including Flood-Fill)
3. Dijkstra's Algorithm (Shortest Path)
4. Floyd-Warshall's Algorithm (Shortest Path)
5. Bellman-Ford Algorithm (Shortest Path)
6. Greedy Algorithms
7. Dynamic Programming (including Knapsack problems)
8. Recursion
9. Minimum Spanning Trees
10. Binary and Linear Search
11. Some basic combinatorics and number theory.
You'd also need some data structures:
1. Stack
2. Queue
3. Hash Table
4. Heap
5. Bag (maybe. I haven't seen this used in programming competitions often)
Again, these are the basics. If you want to know more advanced concepts, feel free to read things online or books. I suggest Introduction to Algorithms by Cormen and Algorithms by Sedgewick. Introduction to Algorithms covers a lot, but is a lot more math-oriented. Algorithms by Sedgewick is more practical as it provides Java code whereas Introduction to Algorithms provides pseudocode.
1. Depth-First Search (Graph Search)
2. Breadth-First Search (Graph Search)(Including Flood-Fill)
3. Dijkstra's Algorithm (Shortest Path)
4. Floyd-Warshall's Algorithm (Shortest Path)
5. Bellman-Ford Algorithm (Shortest Path)
6. Greedy Algorithms
7. Dynamic Programming (including Knapsack problems)
8. Recursion
9. Minimum Spanning Trees
10. Binary and Linear Search
11. Some basic combinatorics and number theory.
You'd also need some data structures:
1. Stack
2. Queue
3. Hash Table
4. Heap
5. Bag (maybe. I haven't seen this used in programming competitions often)
Again, these are the basics. If you want to know more advanced concepts, feel free to read things online or books. I suggest Introduction to Algorithms by Cormen and Algorithms by Sedgewick. Introduction to Algorithms covers a lot, but is a lot more math-oriented. Algorithms by Sedgewick is more practical as it provides Java code whereas Introduction to Algorithms provides pseudocode.
No comments:
Post a Comment