# Need help to prepare for International Olympiad in Informatics



## The Conqueror (Sep 19, 2010)

Hi Friends,
IoI 2011 will be held in Pattaya, Thailand.
The International Olympiad in Informatics (IOI) is one of the most recognized computer science competitions in the world. The competition tasks are of algorithmic nature; however, the contestants have to show such basic IT skills as problem analysis, design of algorithms and data structures, programming and testing. The winners of the IOI belong to the best young computer scientists in the world.

I got the syllabus. I need some good resources to study. My programming Language is C. I know the basics but please suggest me some good books. Also I am new to algorithms. I have copy-pasted the syllabus below. 

*PF1. Fundamental programming constructs (for abstract machines)*
~ Basic syntax and semantics of a higher-level language (C,C++ or Pascal). I have selected C
~ Variables, types, expressions, and assignment
~ Simple I/O
~ Conditional and iterative control structures
~ Functions and parameter passing
     Structured decomposition
*PF2. Algorithms and problem-solving*
     Problem-solving strategies (understand{plan{do{check, separation
of concerns, generalization, specialization, case distinction, work-
ing backwards; see e.g. [5])
     The role of algorithms in the problem-solving process
     Implementation strategies for algorithms 
     Debugging strategies
4 The concept and properties of algorithms (correctness, efficiency)
*PF3. Fundamental data structures
*~ Primitive types (boolean, signed/unsigned integer, character)
~ Arrays (incl. multidimensional arrays)
~ Records
~ Strings and string processing
4 Static and stack allocation (elementary automatic memory manage-
ment)
4 Linked structures (linear and branching)
4 Static memory implementation strategies for linked structures
4 Implementation strategies for stacks and queues
4 Implementation strategies for graphs and trees
4 Strategies for choosing the right data structure
4 Abstract data types, priority queue, dynamic set, dynamic map
*PF4. Recursion*
~ The concept of recursion
~ Recursive mathematical functions
~ Simple recursive procedures (incl. mutual recursion)
     Divide-and-conquer strategies
     Recursive backtracking*
AL1. Basic algorithmic analysis*
4 Algorithm specication, precondition, postcondition, correctness,
invariants
     Asymptotic analysis of upper complexity bounds (informally if possible)
     Big O notation
     Standard complexity classes (constant, logarithmic, linear, O(N logN),
quadratic, cubic, exponential)
     Time and space tradeos in algorithms
AL2. Algorithmic strategies
     Simple loop design strategies
     Brute-force algorithms (exhaustive search)
     Greedy algorithms (insofar that understanding correctness is ele-
mentary)
     Divide-and-conquer (insofar that understanding eciency is elemen-
tary)
     Backtracking (recursive and non-recursive)
     Branch-and-bound (insofar that understanding correctness and ef-
ciency are elementary)
     Pattern matching and string/text algorithms (insofar that understand-
ing correctness and eciency is elementary)
     Dynamic programming9
     Discrete approximation algorithms10

*AL3. Fundamental computing algorithms*
     Simple numerical algorithms involving integers (radix conversion, Eu-
clid's algorithm, primality test by O(
p
N) trial division, Sieve of
Eratosthenes, factorization, ecient exponentiation)
     Simple operations on arbitrary precision integers (addition, sub-
traction, simple multiplication)11
     Simple array manipulation (lling, shifting, rotating, reversal, re-
sizing, minimum/maximum, prex sums, histogram, bucket sort)
     Sequential processing, sequential and binary search algorithms
     Search by elimination, \slope" search
     Quadratic sorting algorithms (selection, insertion)
     Partitioning, order statistics by repeated partitioning, Quicksort
     O(N logN) worst-case sorting algorithms (heap sort, merge sort)
     Binary heap data structure
     Binary search trees
     Fenwick trees
     Representations of graphs (adjacency list, adjacency matrix)
     Traversals of ordered trees
     Depth- and breadth-rst traversals of graphs, determining connected
components of an undirected graph
     Shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall)
     Transitive closure (Floyd's algorithm)
     Minimum spanning tree (Jarnk-Prim and Kruskal14 algorithms)
     Topological sort
     Algorithms to determine (existence of) an Euler path/cycle

Please suggest me good books for these algorithms. 

Thank you!


----------



## gopi_vbboy (Sep 19, 2010)

*books.google.com*


----------

