An awesome list of resources and references for competitive programming in VJC!
How to start off well and make good progress.
It is recommended that you learn C++11. To start off, borrow this book: Stroustrup: The C++ Programming Language (4th Edition). It's a great book on C++11 by the creator himself.
For a good source of documentation, use C++ Reference and avoid other websites like cplusplus.com.
Those new to Github and version control may find this cheatsheet and the other materials on their training website helpful. Another solution is to learn Git from the bottom up.
For those new to algorithms, take a look at online courses. The Algorithms specialization on Coursera by Stanford university is highly recommended. (One of the authors (Wei En) have not tried out the new courses since the old course was split up into 4 courses, but believes that the quality should be consistent.)
An alternative course, of very high quality too, is Algorithms, Part I and Algorithms, Part II by Princeton University. However, this course is in Java and may not be very useful.
For an overview of the main topics covered which are relevant to competitive programming, take a look at this table. Double ticks indicates a very comprehensive analysis of the topic in the course, relative to the other course. The important topics for competitive programming are marked with an asterisk (* means you should know why it works in great detail).
| Topic | Stanford | Princeton |
|---|---|---|
| Asymptotic notation (Big-O) | ✓ | ✓✓ |
| Balanced Search Trees | ✓ | ✓✓ |
| Binary Search* | ✓ | ✓ |
| Convex Hull | x | ✓ |
| Dynamic Programming (Knapsack)* | ✓ | x |
| Dynamic Programming (Sequence Alignment)* | ✓ | x |
| Dynamic Programming (Optimal Search Trees)* | ✓ | x |
| Graphs (Connectivity)* | ✓ | ✓ |
| Graphs (Minimum Cut Problem)* | ✓ | ✓ |
| Graphs (Representations)* | ✓ | ✓ |
| Graphs (Search)* | ✓ | ✓ |
| Graphs (Shortest-Path Problem)* | ✓✓ | ✓✓ |
| Hash Tables | x | ✓ |
| Heaps | ✓ | ✓ |
| Minimum Spanning Tree* | ✓ | ✓✓ |
| Priority Queues* | x | ✓ |
| Sorting (Mergesort)* | X | ✓✓ |
| Sorting (Quicksort)* | ✓ | ✓✓ |
| Stacks and Queues | x | ✓ |
| Substring Search | x | ✓ |
| Symbol Tables | x | ✓ |
| Tries | x | ✓ |
| Union Find* | x | ✓ |
- Project Euler: An archive of 568 math-oriented problems, ranking from easy to extremely difficult.
- Australian Informatics Olympiad Sample Questions and the AIOC Training Site.
- (Singapore) National Olympiad in Informatics: The first question of each year is relatively easier. One of the authors (Ivan) think that the 2008 questions are quite manageable.
Some recommended books for competitive programming.
| ☆ | Name | Description |
|---|---|---|
| ★☆☆ | Think Like a Programmer: An Introduction to Creative Problem Solving, by V. Anton Sprawl | This book is a highly accessible text which uses C++ on problem solving, covering basic concepts such as classes, pointers, and recursion. One of the authors (Wayne) is using this to begin his journey. |
| ★★☆ | Competitive Programming, by Steven and Felix Halim | This book contains a collection of relevant data structures, algorithms, and programming tips. It's a well-received book, although advanced. The first edition is free for download (pdf). |
| ★★★ | Introduction to Algorithms, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein | This immensely popular undergraduate textbook is both rigorous and comprehensive, and covers algorithms and data structures in huge detail. The writing can be difficult to those just starting out. We've made it available for download here. |
| ☆ | Name | Description |
|---|