T
The Conqueror
Guest
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 eciency 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 eciency 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, ecient 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 (Jarnk-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!
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 eciency 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 eciency 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, ecient 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 (Jarnk-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!