CCC Style Questions Book Recommendation

Programming Challenges

Canadian Computing Competition 2015 is coming up in 4 days so it’s good time to just skim through study material again to see what I need to practice. University of Waterloo provides past contest questions and Milliken Mills High School provides unofficial solutions in Python. But as students, we always need as many problems to practice as possible so we have a comprehensive experience in all types of algorithm problems for CCC.

On CEMC website it recommends the book Programming Challenges by Skiena and Revilla (published by Springer), and honestly this is probably one of few good books that provide abundant algorithm problems and also has brief introduction in C++ and java for each topic. Personally I’m fluent in C and its dialects such as Objective-C and C++, so I find this book extremely helpful. The style of questions (how it’s presented) is similar to that of CCC, where firstly introduction is presented, then input explanation, output explanation, example input and output, and finally (sometimes) example output explanation.

This book serves as an extra resources if you have exhausted all CCC past exams available, or would like to learn about various types of problems before attacking real CCC problems.

The book is available on Amazon.ca currently for around $55, either paperback or Kindle Edition.

Breadth-First Search Algorithm in C++ implementation note

breadth-first search (BFS): Finds a path between two nodes by taking one step down all paths and then immediately backtracking.
– Often implemented by maintaining a queue of vertices to visit

Well.. CCC 2015 is on Feb. 18 so now it’s probably a good time to review all kind of stuff in C++. BFS is an important algorithm for searching paths, and here is how it works.

Pseudocode (CS106B Stanford Lecture note, distributed under CC 2.5 License):

function bfs(v1, v2):
    queue := {v1}.
    mark v 1 as visited.
    
    while queue is not empty:
        dequeue a vertex v from the queue.
        if v is v2:
            a path is found!
        for each unvisited neighbor n of v
            mark n as visited, and enqueue n in queue
     //if we get here, no path exists.

An implementation in C++ follows (CCC 2008 Senior Problem No. 3, did it quickly probably poor code style): Continue Reading…