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:
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.
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:
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.
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.
|Wed, Aug 26||Overview, Linux Programming Environment||Problem 001|
|Fri, Aug 28||I/O Parsing and Manipulation||Problem 002|
|Mon, Aug 31||Data Structures (Arrays)||Problem 003|
|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|
|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|
|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|
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.
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.
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.
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.
This is the student organization that runs the local programming contests and fields the teams that compete in the regional events.
This site has information about common questions and concepts often used in technical programming interviews, along with some answers to the questions.
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.