Information Systems 390 - Programming Challenges
Spring 2001

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: 11:15AM-12:45PM Tuesday-Thursday, and by appointment.

Course Time: Tuesday-Thursday 12:50-2:10PM Place: Life Sciences 30

Textbook: none

Recommended Books:

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

Sedgewick, Algorithms in C

O'Rourke, Computational Geometry in C

Kernighan and Ritchie, The C Programming Language

• Grading: Grades will be assigned based on the following formula, with cut-offs determined by my opinion of students on the boundary.

  13 weekly problem sets at 7% each - 78%

  Midterm Exam - Team Programming Contest - 11%

  Final Exam - Team Programming Contest - 11%

• Homeworks: There will be 13 problem sets over the course of the semester, each given out on a Thursday and due the following Tuesday. This deadline may be extended to Thursday if there is a class consensus. Each problem set will consist of about 5 to 6 programming problems. The goal is to maximize the number of problems solved correctly each week - there is will be no partial credit.

• Exams: The midterm and final exams will be a timed programming contest with three-person teams designed to simulate an actual ACM tournament.

Rules of the Game:

1.

Despite the official course name/number, this is intended as a computer science course for primarily computer science.

2.

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

3.

This course is designed to have a weekly flow. Each Thursday, a new set of problems will be assigned, and a lecture or two devoted to the algorithmic theory and ideas associated with them. Over the weekend, students will work on the problems, with experiences and problems discussed in Tuesday's class. You are not expected to complete all problems, but you can impress me if you do!

4.

This course is intended to be a positive, fun experience for a small, enthusiastic group of students. Everyone participating on a regular basis during class and seriously attempting the programming projects (at least 5 hours per week) will get a grade no lower than a B.

5.

The grading of class assignments will be done by the robot judge of the Univ. de Valladolid, Spain ACM Problem Set Archive, at http://acm.uva.es/problemset/. Students are urged immediately to go the site and register as a new member (use your real name). All class assignments will be problems from this site which have a robot judge.

6.

Email me your Valladolid name and ID number soon as it is issued so I can monitor your progress.

7.

You are strongly encouraged to do your programming in C language or C++, to take advantage of the robot judge. If you insist on using Java, you will have to submit a test file containing at least 7 test cases for each problem you solve. The programs to solve these problems are sufficiently short that they do not benefit from the advanced features of Java or C++, so you will likely be using a very C-like subset of Java, anyway.

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.

Each week, you are also to submit to me an electronic version of all the programming problems solved. 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, but all lecture materials I prepare I will put on the WWW.

13.

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

14.

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.

15.

Homework assignments will be due at the beginning of class on Tuesday. The class will vote to decide whether to allow/encourage work from Tuesday to Thursday.

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, every few weeks there will be 'Pizza with the Prof'. Outside my office will be a sheet for you to sign-up to join 5-10 other students from the class for a pizza lunch (on me). I look forward to getting to know you.

DATE	TOPIC
----	-----
1/24	arrays and iteration problems out -- 100 151 254 256 340 349

1/30	understanding specifications
2/1	game and puzzle problems out -- 127 170 227 339 395

2/6	strings and library functions
2/8	string problems out -- 175 272 306 333 335 385

2/13	sorting and library functions
2/15	sorting problems out -- 120 156 230 299 390

2/20	arithmetic and algebra
2/22	arithmetic problems out -- 138 200 338 343 344 369

2/27	divisiblity and modular arithmetic
3/1	number theory problems out -- 180 202 294 324 374 382

3/6	constructing subsets and permutations
3/8	backtracking problems out -- 148 165 167 195 386

3/13	contest strategy
3/15	midterm programming contest (teams)

3/20-22	Spring Break

3/27	DFS/BFS
3/29	graph traversal problems out -- 112 168 193 315 352 

4/3	shortest paths and topological sorting
4/5	graph path problems out -- 157 196 336 314 318

4/10	edit distance and making change
4/12	dynamic programming problems out -- 116 147 164 231 357

4/17	rectangular and hexagonal grids
4/19	geometry grid problems out -- 155 201 260 320 356

4/24*	convex hulls, areas, and intersection
4/26*	computation geometry problems out -- 152 191 218 313 361 378

5/1	recursive descent parsing
5/3	parsing problems out -- 172 271 310 327 384

5/8	final programming contest?
Final exam: May 10, 11-1:30PM  (if not held 5/8)