Update Note:
I will revise the whole content of this notes from Chapter 1 until Chapter 12 using my own wordings... I will remove or rewrite texts that I have copied from other places (e.g. USACO texts) to avoid copyright issue. I will also give illustrations and notes to help the readers in understanding the concepts. This updating project was started on 8 May 2007, currently suspended..., and will only be resumed after I submitted my PhD thesis (late 2008).

Preface

Target Audience (Intermediate Programmers)

The reader should have some background knowledge in basic data structures, algorithms, and programming languages. Typically, a 2nd year Computer Science students should have the necessary background. I will be using explanations using two main programming languages, C++ (the STL), and C#. The contents in this website are not targeted for expert programmers. To gain access to newer and more sophisticated data structures or algorithms, browse the Internet for other sources.

Acknowledgements

I thanks God, for giving me some talent in algorithmic and programming skill, without that, all the stuffs that I have written here will not even exist. I also want to thanks my parents, who forced me to learn something with my new PC (at that time it was new) long long time ago, eventually I picked programming book, and since then I am interested to learn algorithm and programming. I have a lot of friends who introduced me to programming contest environment, and since then, I have participated in several contests and gained so much knowledge and experience. And to a lot others whom I cannot name one by one, thanks :).

Steven Halim (PhD candidate)
Instructor
Department of Computer Science
National University of Singapore
05 Jan 2009

Competitive Programming

Table of Contents

1. Introduction: what is algorithm?, what is data structure?, basic skills, where to practice?
2. Basic Data Structures: Array, Linked List, Stack, Queue.
3. Basic Algorithms: Brute Force, Recursion/Backtracking, Divide/Transform and Conquer,
4. Specialized Algorithm 1: Mathematical Algorithms
5. Specialized Algorithm 2: Sorting Algorithms
6. Specialized Algorithm 3: Searching Algorithms
7. Specialized Algorithm 4: Greedy Algorithms
8. Specialized Algorithm 5: Dynamic Programming Algorithms
9. Graph Data Structure and its Algorithms: DFS/BFS, MST, Single/All-Pairs Shortest Paths, Network Flows
10. Specialized Algorithm 6: Computational Geometry Algorithms
11. Advanced Data Structures: Heap, BST, Dictionary, Set, Data Structure Augmentation, Mix and Match
12. Links to Stochastic Local Search: NP-hardness, exact/complete algorithm, inexact/local searches