CSE 40872 Programming Challenges and Problem Solving (Fall 2009)

Course Information



The purpose of this course is to encourage the development of practical programming and problem solving skills through extensive practice and guided learning. The bulk of the class revolves around solving "brain-teaser" and puzzle-type problems that often appear in programming contests, online challenges, and job interviews.

Possible topics covered in this class include:

  • Linux programming environment
  • I/O parsing and manipulation
  • Data structures and strings
  • Sorting and searching
  • Recursion and backtracking
  • Dynamic programming
  • Graph algorithms, graph traversal
  • Simple number theory and combinatorics

Additionally, basic software engineering practices such as planning, debugging, testing, and source code management may be introduced.


Although there are no formal requirements for this course, a strong background in programming is highly encouraged. Since most of the course involves programming in C/C++, familiarity with these languages is recommended.


  • Location: 177 Fitzpatrick (Cluster)
  • Time: MWF 12:50 - 1:40


  • Instructor: Peter Bui
  • Email: pbui@cse.nd.edu
  • Telephone: (574) 631 8851
  • Office Hours: Tuesday, Wednesday 3PM - 5PM in 313 Cushing, and by appointment
  • Office Location: 222 Cushing


Official office hours will take place in 313 Cushing on Tuesday, Wednesday 3PM - 5PM. However, the instructor's normal office location is 222 Cushing. If there are any questions and the official office hours are not convenient, simply stop by or arrange an appointment.


Grades will be based on the following formula:

  • Attendance: 10%
  • Participation: 10%
  • Problems Solved: 80%



There will be two problems a week that are both due by midnight Friday unless specified otherwise. Please put your source code in:


where <XXX> is the problem number (i.e. 001). Note your solution for the problem should be in one file and include your name and the problem description at the top. All work is subject to Notre Dame's Academic Honor Code.

CLI Judge

You may test your solutions on the command line by using the judge option of the build.sh script provided in the www/tests directory. If you properly followed the naming convention above, then you can do the following:

# Symlink the build script (you can copy instead if you wish)
$ cd /afs/nd.edu/coursefa.09/cse/cse40872.01/dropbox/<afsid>/problem<XXX>
$ ln -s ../../../www/tests/build.sh .

$ ./build.sh    # This will compile your program
$ ./build.sh -c # This will clean up
$ ./build.sh -j # This will judge your program
$ ./build.sh -x # This will execute your program and display the output

Note, this judge will only test your program against the sample input and output tests provided on the problem page, and not the final set of test cases that will be used to determine your grade.

Web Judge

You can test whether or not your solutions pass the final exhaustive test cases by verifying with the Web Judge front-end. Make sure you submit your work to the dropbox before attempting verification.



Date Topics Problems
Wed, Sep 02 Data Structures (STL, Vectors, Deques) Problem 004
Fri, Sep 04 Review and Discussion  
Mon, Sep 07 Data Structures (Linked Lists) Problem 005
Wed, Sep 09 Data Structures (Stacks, Queues) Problem 006
Fri, Sep 11 Review and Discussion  
Mon, Sep 14 Strings (C) Problem 007
Wed, Sep 16 Strings (STL) Problem 008
Fri, Sep 18 Review and Discussion  
Mon, Sep 21 Sorting (C) Problem 009
Wed, Sep 23 Sorting (STL) Problem 010
Fri, Sep 25 Searching, Review and Discussion  
Mon, Sep 28 Trees (Overview, BST) Problem 011
Wed, Sep 30 Graphs (Overview, Traversal) Problem 012


Date Topics Problems
Fri, Oct 02 Review and Discussion  
Mon, Oct 05 Recursion (Backtracking) Problem 013
Wed, Oct 07 Recursion (Iteration) Problem 014
Fri, Oct 09 Review and Discussion  
Mon, Oct 12 Dynamic Programming (Fib, Squirrels) Problem 015
Wed, Oct 14 Dynamic Programming (Subarray, DNA) Problem 016
Fri, Oct 16 Review and Discussion  
Mon, Oct 19 Fall Break  
Wed, Oct 21 Fall Break  
Fri, Oct 23 Fall Break  
Mon, Oct 26 Arithmetic Problem 017
Wed, Oct 28 Number Theory (Primes) Problem 018
Fri, Oct 30 Review and Discussion  


Date Topics Problems
Mon, Nov 02 Combinatorics Problem 019
Wed, Nov 04 Combinatorics Problem 020
Fri, Nov 06 Review and Discussion  
Mon, Nov 09 Graphs (DAGs) Problem 021
Wed, Nov 11 Graphs (MST) Problem 022
Fri, Nov 13 Review and Discussion  
Mon, Nov 16 Graphs (APSP) Problem 023
Wed, Nov 18 Graphs (Convex Hull) Problem 024
Fri, Nov 20 Review and Discussion  
Mon, Nov 23 Grid Problem 025
Wed, Nov 25 Thanksgiving Break  
Fri, Nov 27 Thanksgiving Break  
Mon, Nov 29 Review Problem 026


Date Topics Problems
Wed, Dec 02 Review Problem 027
Fri, Dec 04 Review and Discussion  
Mon, Dec 07    
Wed, Dec 09    


The following is a random assortment of possibly useful resources. If you come across anything else that may be helpful for the class, please feel free to email your suggestion.


There is no required textbook for this class. Instead, students will be provided with some handouts (probably electronically, rather than dead tree) and are expected to take lecture notes. The following are some books which would be useful to have, but are not in any way necessary. Most of the course material is derived from these sources.

  • Programming Challenges By Steven S. Skiena, Miguel A. Revilla:

    This is the textbook normally used for this type of course. Many of the course topics are based on material covered in this book. Most parts of the book may be viewed online through Google books.

    The course website of the class taught by Steven Skiena based on this textbook may also contain further resources.

    There is an online judge associated with this book that allows users to submit solutions to be verified. Feel free to try this service out as it provides good practice for programming contest type problems.

  • Algorithms in a Nutshell by George T. Heineman, Gary Pollice, Stanley Selkow:

    Generally, any data structures and algorithms book (including ones from previous courses such as Cormen) that you are comfortable with referencing and using is fine for the course. The book listed here covers most of the algorithms covered in this class and would be a handy reference to have while doing the assignments or during competition. Some of the course material is based on the information provided here. Moreover, the book contains a lot of pseudo-code along with some (readable) C/C++ implementations of the algorithms.

  • Programming Interviews Exposed by John Mongan, Noah Suojanen, Eric Giguere:

    This book includes a crash course in many of the topics that a programmer may face during a job interview and provides a brief overview of many of the subjects discussed in this course. Though far from exhaustive, it does serve as a decent refresher and includes some example code and puzzles.


Since some sort of reference about C/C++ and the STL library would be helpful for the course and the programming contests, below are links to some online resources. Note that for programming contests, you cannot use online texts, so you may want to purchase a book.

  • C++ Library Reference:

    This site contains a reference to the most common parts of the STL and other aspects of the C++ programming language.

  • C++ Reference:

    This is another C++ and STL reference site.


  • Notre Dame ACM Computer Club:

    This is the student organization that runs the local programming contests and fields the teams that compete in the regional events.


  • Hacking a Google Interview

    This site has information about common questions and concepts often used in technical programming interviews, along with some answers to the questions.

  • Project Euler

    This site is a large set of mathematical and programming problems designed to test your abilities and sharpen your skills. The problems make for good practice.