SUNY Geneseo Department of Computer Science

CSci 240 — Foundations of Algorithms

Spring 2007

Last updated January 22, 2007

Time and Place:
Lecture: MWF 9:30 - 10:20, Welles 121
Lab: W 10:30 - 12:20, South 345

Final Exam: Thursday, May 3, 8:00 AM

Instructor: Doug Baldwin
Office: South 320
Phone: 245-5322
E-Mail: baldwin@geneseo.edu
Office Hours: Monday 3:00 - 4:00, Thursday 10:30 - 11:30 or By Appointment

WWW Pages:
Syllabus: http://cs.geneseo.edu/~baldwin/csci240/spring2007/syllabus.html
Lecture Notes: http://cs.geneseo.edu/~baldwin/csci240/spring2007/lectures.html
Exercises: http://cs.geneseo.edu/~baldwin/csci240/spring2007/exercises.html
Mailing List: csci24001-spr07-l@geneseo.edu

"Computer science" is one of those phrases that should be instantly suspect: a "computer" is a machine made by humans; "science" generally denotes the study of some natural, or at least not-human-made, phenomenon. How, then, can there be a science in computers? In fact, the phrase "computer science" is a misnomer. It should really be "algorithm science", because it is in the abstract notion of algorithms that we find the elements of computing that are independent of human whims: algorithms exist independently of their implementations, whether those implementations are programs, electronic devices, or something else; every algorithm has limits to how efficiently it executes, regardless of how cleverly it is implemented; there are limits to how efficiently any algorithm, no matter how clever, can solve certain problems, and there are even problems that we can prove no-one will ever find an algorithm to solve. Algorithms are thus the real heart of computer science.

This course teaches you to think about algorithms as entities distinct from programs or other implementations. The course explores computer science's three characteristic methods of inquiry for dealing with algorithms: design of algorithms and their concrete implementations, theoretical analysis of algorithms, and experimentation to verify the physical reality of theoretical predictions. These methods of inquiry are mutually reinforcing, and it is only by applying all three that you can really understand algorithms and computing.

Prerequisite. CSci 142

Learning Outcomes

Upon completing this course, students who meet my expectations will be able to...

• Use preconditions, postconditions, loop invariants, and inductive definitions as guidelines for designing algorithms.
• Prove the correctness of both iterative and recursive algorithms.
• Derive the time and space complexities of both iterative and recursive algorithms, and express these complexities asymptotically.
• Design and conduct convincing experiments pertaining to the resource use of programs.
• Form conclusions about the extent to which experimental data support a hypothesis, and defend those conclusions with quantitative analysis of experimental data, including analysis for consistency with an asymptotic hypothesis.
• Express conclusions in writing, using standards of argument appropriate for professional writing in computer science.
• Analyze (both theoretically and experimentally) and implement classical sorting algorithms.
• Design, analyze (both theoretically and experimentally), and implement algorithms that use binary search trees, priority queues, and dictionaries as abstract data types.
• Design, analyze (both theoretically and experimentally), and implement binary search tree, priority queue, and dictionary classes.

Books and Other Resources

Text

The required text for this course is

D. Baldwin & G. Scragg, Algorithms and Data Structures: The Science of Computing

It is available from Sundance Books and other sources.

Computing

The main programming language for this course will be Java. I may rely on features of the latest Java version (1.5) in programming exercises for this course, but you should be able to do those exercises in any up-to-date Java programming environment. However, I will develop programming exercises for this course in the XCode programming environment, which is available in the Computer Science Department's Macintosh lab.

The default computing facility for this course will be the Computer Science Department's Macintosh laboratory, in South 345. However, I encourage you to bring your own laptop computer to use in the lab if you wish. Just as with programming environments, you should be able to use any laptop you are comfortable with, as long as it has an up-to-date Java installed.

On-Line

A Companion Web Site for the text is at http://www.charlesriver.com/algorithms/

Course Materials from last time I taught this course's predecessor are available at http://cs.geneseo.edu/~baldwin/csci141/spring2005/

Tutorials on Java are available at http://java.sun.com/docs/books/tutorial/

Documentation for the standard Java 1.5 Class Library is available at http://java.sun.com/j2se/1.5.0/docs/api/

Some popular Java programming environments are available for free downloading, including...

• Eclipse, available at http://www.eclipse.org/
• NetBeans, available at http://www.netbeans.org/
• XCode, available through the Apple Developer Connection at http://developer.apple.com/ (only Apple Developer Connection members can download XCode for free, but On-Line ADC membership is itself free).

Course Schedule

The following dates are best estimates. They may well change as students' actual needs become apparent. Refer to the Web version of this syllabus for the most current information, I will keep it as up-to-date as possible:

Grades and Such

Your grade for this course will be calculated from your grades on exercises, exams, etc. as follows:

Late Policy

I will accept work that is turned in late, but with a 10% per day compound late penalty. For example, homework turned in 1 day late gets 10% taken off its grade; homework turned in 2 days late gets 10% taken off for the first day, then 10% of what's left gets taken off for the second day. Similarly for 3 days, 4 days, and so forth. I round grades to the nearest whole number, so it is possible for something to be so late that its grade rounds to 0.

Computer Science Writing Requirement

Every Geneseo student has to satisfy a writing requirement in their major in order to graduate. The official Computer Science writing requirement is printed in the Geneseo College Bulletin. To summarize the requirement's main points, every Computer Science major must maintain an acceptable quality of writing throughout their computer science coursework. Any student whose writing is deemed unacceptable on three or more occasions during their first 28 credit hours of Computer Science coursework towards the major is required to take an additional writing course, typically in the English Department.

Written work you do for this course (lab reports, project reports, etc.) will be evaluated for acceptability under this requirement.

Policy on Collaboration

My policy on group work for this course, which is on-line at http://cs.geneseo.edu/~baldwin/collab-intro.html is an important part of this syllabus. A printed copy accompanies the printed copy of this syllabus.

Accommodations

SUNY Geneseo will make reasonable accommodations for persons with documented physical, emotional or learning disabilities. Students should consult with the Director in the Office of Disability Services (Tabitha Buggie-Hunt, 105D Erwin, 245-5112) and their individual faculty regarding any needed accommodations as early as possible in the semester.