[ General Information
| Lectures
| Handouts and Resources
| Requirements
]
[ Announcements
]
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/
Lectures
All topics will be covered through examples and extended with problem
solving in class. The schedule is tentative.
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.
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
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.