ISE 390 -- Programming Challenges -- Week 1 Notes Course Goals: To provide a challenging, self-motivating course for good students to learn what makes programming/computer science fun and exciting. To strengthen the algorithmic/procedural intuition of students raised in a world of object-oriented programming. To provide an enthusiastic cadre of good students for Stony Brook's ACM Programming Team, and perhaps strength the SBCSS/UPE societies/culture. About the ACM Contest: The International Programming Contest stresses teamwork (3 people with 1 or 2 computers per team) as well as individual efforts, since small programs are best written by one person, perhaps after group discussions. Many of the problems are well-known exercises couched in different guises. The judges provide very little feedback about why your program is wrong. Often you must debug it by reading the specifications again. The team score is the number of problems solved correctly over the course of the contest, typically 5 hours. Ties are broken by the cumulative elapsed time taken to correct submissions, with time penalties given for each incorrect submission of an (ultimately) correctly solved problem. Maxims to Live by: RTFM -- Read the *bleeping* manual Read each problem statement carefully. Skim it first, as much of the description may be general background/history which may not impact the solution. Pay particular attention to the input and output descriptions, and sample input/output, but ... Don't ASSUME -- You make an ass of you and me The problem authors try to be tricky and picky, leaving unspecified traps for students to fall in. Just because the given examples have some nice property does not mean the test data does. Anything which is not explicitly permitted is forbidden! KISS -- Keep it simple, stupid. Simplicity means use elementary data structures like arrays instead of pointers, use built-in library functions instead of writing your own, and straightforward algorithms instead of trying to be too clever. Short programs are better than long programs. Efficiency is usually not an issue except with the difference between polynomial and exponential algorithms, so don't worry about it until you have (or can predict) trouble. Use good programming practices (variable names, indentation, simple comments) since *you* will have to read it for a few hours. Stay focused, but wear your tennis shoes Work on the next problem while you are waiting for the judge to rule on your latest submission. Since you only get credit for correct solutions, identify the easiest problems and work on them first. Assigned Problems: 100 -- The Collatz or Hailstone number sequences, a famous open problem in number theory. Why doesn't it ever cycle? 151 -- A variation of the Josephus problem, associated with mass suicide in the days of the Roman empire 254 -- A non-recursive algorithm for solving the Towers of Hanoi problem. 256 -- A simple number theory problem with possible efficiency issues. 340 -- Simulate the hints in the game of Mastermind 349 -- Implement a nice voting scheme which makes a lot of sense after the Bush-Gore-Nader election.