17 September 2010

Competitive Programming

Author(s): Steven Halim, Felix Halim

Competitive Programming Book’s 23 sample pages: click here

This book contains a collection of relevant data structures, algorithms, and programming tips written mainly for University students who want to be more competitive in the ACM International Collegiate Programming Contest (ICPC). Although written with predominantly ICPC format and University students in mind, this book can also be used by selected high school students who want to be competitive in the International Olympiad in Informatics (IOI) or anyone who wants to participate in other relevant programming competitions.

Steven Halim and his book (Image from Facebook)

According to the Author’s objective:

“Our objective in writing this book is similar with the ICPC vision: to further improve humanity by training current students to be more competitive in programming contests. The possible long term effect is future Computer Science researchers who are well versed in problem solving skills”.

The reader must have some background knowledge in basic data structures, algorithms, and programming languages. Typically, a 2nd year Computer Science students in a University (who have passed a kind of “programming methodology” and “basic data structures and algorithms” modules) or selected high school students who have participated in National or International Olympiad in Informatics should have the necessary background.

Book Information

  1. Introduction
    • Introducing the world of Competitive Programming
    • Tips to be a competitive programmer, shared by people who are involved in ICPC + IOI
  2. Data Structures (DS) and Libraries
    • Are you aware that many DS have built-in libraries? Do you use them often?
    • Are you aware that there are many other useful DS out there without built-in libraries as of 2010?
  3. Problem Solving Paradigms (the second largest chapter in the book with 32 pages)
      1. Complete Search that is not that brute…
      2. Divide and Conquer (D&C)
      3. Greedy
      4. Dynamic Programming (DP)
    • Do you hammer every contest problem with bruce force?
    • Are you sure that you are familiar with these terms:
  4. Graph (the largest chapter in the book with 35 pages)
    • Graph Traversals, Minimum Spanning Trees, Various Shortest Paths Problems, Maximum Flow Problems
    • Special Graphs (our highlight, this section usually does not exist in other algorithm books)
  5. Mathematics
    • Number Theory, Big Integer, and many more topics in mathematics that are frequently appear in programming contests
  6. String Processing
    • Ad hoc string problems, String problems solvable with DP,
      Large string problems that must be solved with efficient DS: Suffix Tree/Array
  7. (Computational) Geometry
    • Library of “Geometry Basics”, Convex Hull, Intersection Problems, D&C in Geometry Problems

More Details: http://sites.google.com/site/stevenhalim/

You may have missed:

Comments are closed.