Computer Science 392 - Programming Challenges
Spring 2004

At its best, computer science is an exciting blend of programming, mathematics, and problem solving. This course will introduce an interesting variety of subjects in programming, algorithms, and discrete mathematics though puzzles and problems which have appeared in the International ACM Programming Contest and similar venues.

Instructor: Steven Skiena

Office: 1411 Computer Science Building

Phone: 631-632-9026

Email: skiena@cs.sunysb.edu

Office Hours: 9:45AM - 11:15AM Tuesday-Thursday, and by appointment.

Course Time: Tuesday-Thursday 11:20-12:40PM Place: Earth and Space BI 079

Textbook: S. Skiena and M. Revilla, Programming Challenges: The Programming Contest Training Manual Springer-Verlag, 2003.

Recommended Books:

S. Skiena, The Algorithm Design Manual, Telos/Springer-Verlag, 1998.

R. Sedgewick, Algorithms in C

J. O'Rourke, Computational Geometry in C

B. Kernighan and D. Ritchie, The C Programming Language

• Grading: Grades will be assigned based on performance on the 14 weekly programming assignments ( $5 \times 14 = 70 \%$) plus class participation (30%). Students who regularly complete at least one problem per week and attend/participate regularly will likely get some form of B, while students who regularly complete at least two problems per week and attend/participate regularly will likely get some form of A.

• Homeworks: There will be 14 problem sets over the course of the semester, one per week. The problems are due one week after being assigned, and you should not plan on being able to catch up on old problems in subsequent weeks. Each problem set will consist of 4 programming problems. The goal is to maximize the number of problems solved correctly (according to the robot judge).

• Exams: There will be no midterms and no final exam. You will have an opportunity at the end of classes to describe the effort you put into the course and the results. Hopefully we will run one or two timed programming contests for fun, perhaps with three-person teams to simulate the ACM ICPC tournament.

Rules of the Game:

1. The WWW page for the course is http://www.cs.sunysb.edu/$\sim$skiena/392. All course handouts and notes are available there, along with the latest announcements. Please check it out.

2. This semester's course will be a test of our new book Programming Challenges and the judging website www.programming-challenges.com. I will be very interested in your feedback on both matters.

3. This course is designed to have a weekly flow. Each week, a new set of problems will be assigned, and the two lectures devoted to the algorithmic theory and ideas associated with them. Students should read the relevent problems before class so we can intelligently discuss them, and try them before the deadline so we can identify possible difficulties for discussion.

4. This course is intended to be a positive, fun experience for a small, enthusiastic group of students. You are not expected to complete all problems, but you can impress me if you do!

5. The grading of class assignments will be done by the Programming Challenges robot judge at www.programming-challenges.com. Students are urged immediately to go to the site and register. As this judging site is still new, expect difficulties. In particular, be sure you save copies of all your submitted programs, especially the working ones.

6. In the event that the Programming Challenges robot judge is broken, problems should be submitted to the Univ. de Valladolid robot judge, http://online-judge.uva.es. The actual judging scripts should be identical for both sites. Students are urged immediately to go the site and register as a new member (use your real name). Be prepared to email me your Valladolid name and ID number if we make extensive use of it so I can monitor your progress.

7. You are encouraged to do your programming in C language or C++, although Pascal and Java are also acceptable, although some people have experienced difficulty with using Java on the judge.

8. Students are to work on all problems individually. You make discuss the problems among yourselves, but you must write all your own code.

9. You are allowed to look in any books you wish, but are honor bound not to search the WWW for help. This is to mirror the official contest conditions.

10. There may be updates or clarifications to some problems on the Valladolid site, in either the HTML problem version or the newsgroup. You are encouraged to consult these sources.

11. The set of all class solutions will be submitted to similarity testing programs, to identify students who did not work on their own. Since cheating in this course is a particularly stupid thing to do, I will be particularly energetic in pursuing any suspects.

12. I expect my lectures each week will be somewhat informal. Full lecture notes from last year, with audio are available on the web.

13. The Pass/No Credit (P/NC) option is not available for this course.

14. Because a primary goal of the course is to teach professionalism, any academic dishonesty will be viewed as evidence that this goal has not been achieved, and will be grounded for receiving a grade of F. (See CEAS Procedures and Guideline Governing Academic Dishonesty, 1/81.)

15. If you have a physical, psychological, medical or learning disability that may impact on your ability to carry out assigned course work, I would urge that you contact the staff in the Disabled Student Services office (DSS), Room 133, Humanities, 632-6748v/TDD. DSS will review your concerns and determine with you what accommodations are necessary and appropriate. All information and documentation of disability are confidential.

16. I hope to establish as much personal contact with each of you as is possible. Don't be afraid to stop by during office hours to ask questions or say hello. To facilitate interaction, I hope to have a 'Pizza with the Prof' a few times over the course of the semester. Outside my office will be a sheet for you to sign-up to join 5-10 other students from my classes for a pizza lunch (on me). I look forward to getting to know you.

Lecture Schedule:

1/27	arrays and iteration problems out 
1/29	programming style / understanding specifications

2/3	data structure problems out
2/4	elementary data structures

2/10	string problems out 
2/12	strings and library functions

2/17	sorting problems out 
2/19	sorting and library functions

2/24	arithmetic problems out 
2/26	arithmetic and algebra

3/2	combinatorics problems out
3/4	recurrence relations and counting

3/9	number theory problems out 
3/11	divisiblity and modular arithmetic

3/16	backtracking problems out 
3/18	constructing subsets and permutations

3/23	graph traversal problems out
3/25	DFS/BFS

3/30*	graph algorithms problems out
4/1	shortest paths and MST 

4/5-9	Spring Break

4/13	dynamic programming problems out
4/15	edit distance and applications

4/20	grid problems out
4/22	rectangular and hexagonal grids

4/27	geometry problems out
4/29	geometric primatives and trigonometry

5/4	computational geometry out
5/6	convex hulls and triangulation

(*) implies there will likely be a substitute instructor that class.