Announcements

• Nov 30:

  • Problem 026 and Problem 027 are due at midnight on Friday, December 4th.
  • Problem 025 solution posted.
    
    

• Nov 23:

  • Problem 025 is due at midnight on Friday, November 27th.
    
    

Description

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.

Prerequisites

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.

Classroom

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

Contact

• 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

Grading

Grades will be based on the following formula:

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

Dropbox

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

/afs/nd.edu/coursefa.09/cse/cse40872.01/dropbox/<afsid>/problem<XXX>/problem<XXX>.c

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.

August

September

October

November

December

Textbooks

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.

References

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.

Organizations

• 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.

Miscellaneous

• 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.