ITS102 (Spring `09)
How to Solve Them

Course description: This course introduces students to a number of well-known interesting problems in computer science, their applications, and solutions. In addition to presenting the solutions, we will introduce the basic ideas underlying a general method for developing efficient solutions to many problems. Previous experience with computer programming or problem solving is not required.

Instructor: Annie Liu, liu@cs.sunysb.edu, Computer Science 1433, 632-8463. | Office hours: Tue 9:50-11:20AM, Fri 3:30-5:00PM, by appointment (send email), or stop by any time I'm around.

Lectures: Wednesday 2:20-3:15PM, in ITS Center.

Textbook: There is no required textbook for this course.

Grading: Attendance with in-class work, and a project with report/presentation, worth 60% and 40%, respectively, of the grade. Extra credit work will be given as appropriate.

Course homepage: http://www.cs.sunysb.edu/~liu/its102/

Lecture 1 (01/28/09): Problems are everywhere with everyone. Solutions need to be correct and efficient.
An example: from repeated multiplications to Difference Engine and ENIAC.

Lecture 2 (02/04/09): Review and refine a basic idea: iterate---repeat at small steps.
Arithmetic operations and compiler optimizations.

Lecture 3 (02/11/09): Review and refine a basic idea: incrementalize---reuse computed results.
Binary operations and hardware design.

Lecture 4 (02/18/09): Review and refine a basic idea: implement---map to supported operations.
Command flows and general programming.

Lecture 5 (02/25/09): Review and refine programming with loops.
Segment sums and sequence processing.

Lecture 6 (03/04/09): Review and refine programming with arrays.
Local summation and image processing.

Lecture 7 (03/11/09): Problems are often recursive. Solutions need to be constructed from the basis.
An example: to factorial from Droste effect.

Lecture 8 (03/18/09): Review and refine: iterate---at bigger steps.
Fibonacci numbers and stream processing.

Lecture 9 (03/25/09): Review and refine: incrementalize---using additional values.
Recursive functions and general optimizations.

Lecture 10 (04/01/09): Review and refine: implement---on different machines.
Hanoi tower and math puzzles.

Spring break: April 6-10.

Lecture 11 (04/15/09): Review and refine programming with recursion.
Logic rules and trust management.

Lecture 12 (04/22/09): Review programming with loops and recursion.
Graph models and path queries. Concurrency, fault-tolerance, and more.

Lecture 13 (04/29/09): Project preparations.

Lecture 14 (05/06/09): Project presentations.

Q: Questionnaire

Difference Engine of Charles Babbage: history, operation, and method of differences
Pictures: At London Science Museum | Closeup | Part assembled by his son after his death using parts in his lab

ENIAC, the first general-purpose electronic computer: description, including reliability and programmability | square root
Pictures: With programmers in room | Main control panel operated | Part on display at Univ of Pennsylvania

Blurring for Beginners in Jerry's Java Image Processing Pages: many kinds of blurs

recursion vs iteration
Fractal | Self-similarity

Escher and the Droste effect: method, steps, images, animation
Gallery: The Droste effect in Jos Ley's Mathematical Imagery

Factorial

Fibonacci Numbers and the Golden Section: in nature, easier puzzles, harder puzzles, architecture and art

Tower of Hanoi | Display of moves for 4 disks
Play for upto 12 disks | Play for upto 10 disks with move counts

Math puzzles at mathpuzzle.com and cut-the-knot.org

Python | Download | The Python Tutorial

Learn information on the course homepage. Check the homepage periodically for Announcements.

Attend lectures and take notes. I will start promptly on time, if only to be fair to people who come on time. We will have students form groups to participate in problem solving in the class.

Do course work. The course work is to let you have some independent experiences based on the topics discussed in class.

Ask questions and get help. Ask questions in class, and visit the professor with any remaining questions. Talk with your classmates, and share ideas (but nothing written or electronic).

Academic honesty: Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Any plagiarism or other forms of cheating discovered will have a permanent consequence in your university record. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at http://www.stonybrook.edu/uaa/academicjudiciary/

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