Data Structures and Algorithms
for Computational Science

Computer Science 409
Spring 2000

Announcements

• The Final Exam was difficult: the average was 59 and the high grade was 81 [for weighting purposes in calculating the final grades, I counted the Final Exam as (score received) + 19 points]
• The Schedule has been updated to show readings for recent lecture topics
• The Final Exam will take place Tuesday, May 16 at 3pm in Olin 245
• Review Questions for the Final are now available; Solutions to Review Questions for Final are online as well

Recently Placed on the Web

• Solutions to Review Questions for Final
• HW11 Solution
• HW12 Solution
• Review Questions for the Final
• HW12 (due Thursday, May 4)

Staff and Office Hours

CS410 STAFF	Name	Email	Office
Instructor	Paul Chew	chew@cs.cornell.edu	494 Rhodes
TA	Wei Wei	weiwei@cs.cornell.edu	4121 Upson

• Office hours are listed below.  You can also make an appointment with Paul Chew or any other member of the course staff. The best way to set up an appointment is via email.

OFFICE HOURS	Where	Who
Monday, 2:30-3:30	4121 Upson	Wei Wei
Tuesday, 10:00-11:00	494 Rhodes	Paul Chew
Wednesday, 2:30-4:00	4121 Upson	Wei Wei
Thursday, 10:00-11:00	494 Rhodes	Paul Chew

Handouts

A chronological list of documents handed out in class.

• General Information - basic information on how the course is run.
• Background Survey
• Geometric Hashing Handout (a postscript file; four slides per page)
• Segment Intersection Handout (a postscript file; 6 slides per page)
• Divide & Conquer Handout (postscript)
• Dynamic Programming Handout (postscript)

Web Documents

A chronological list of documents placed on the class web pages.

• General Information - basic information on how the course is run.
• Background Survey
• Schedule for CS409
• HW01 CS409
• HW02 CS409
• HW01 Solution CS409
• Geometric Hashing  plus postscript version
• HW03 CS409
• BSTs and 234-Trees plus postscript version
• HW02 Solution CS409
• HW04 CS409
• Pascal-Java-C Comparisons
• Brief Intro to Java
• Using Microsoft Visual J++
• QTest.java and Queue.java
• HW03 Solution CS409
• HW05 CS409
• Segment Intersection using a Sweepline plus postscript version
• Review Questions for Midterm
• HW05 Solution CS409
• Solutions to Review Questions for Midterm
• HW06 CS409
• Divide & Conquer plus postscript version
• HW07 CS409
• Dynamic Programming plus postscript version
• HW06 Solution CS409
• HW08 CS409
• HW07 Solution
• HW09
• Amortization plus postscript version
• HW10
• Lower Bounds for Sorting plus postscript version
• Reductions (for lower bounds) plus postscript version
• HW11
• SuffixTree.java (needed for HW11)
• HW09 Solution
• HW10 Solution
• HW12
• Review Questions for the Final
• HW12 Solution
• HW11 Solution
• Solutions to Review Questions for Final

Lectures

Lecture topics, corresponding readings, and related Web material appear in the Schedule.

Information on Homework

Graded homework will be available in class or during office hours.

Homework	Topic	Due	Solution
HW01	big-O, arrays and linked lists	Thursday, Feb 3	HW01 Solution
HW02	hashing	Thursday, Feb 10	HW02 Solution
HW03	BSTs, 234-Trees	Thursday, Feb 17	HW03 Solution
HW04	programming (Rectangle)	Thursday, Feb 24	HW04 Solution
HW05	Priority Queues and Heaps	Thursday, Mar 2	HW05 Solution
HW06	Divide & Conquer	Thursday, Mar 16	HW06 Solution
HW07	Dynamic Programming	Thursday, Mar 30	HW07 Solution
HW08	programming (Binary PQ)	Thursday, Apr 6	not yet available
HW09	Greedy Method; Amortization	Thursday, Apr 13	HW09 Solution
HW10	Amortization, Reductions	Thursday, Apr 20	HW10 Solution
HW11	programming (Suffix Tree)	Tuesday, May 2	HW11 Solution
HW12	Max Flow, Reductions	Thursday, May 4	HW12 Solution

Information on Programming

• Local Resources
  • Computer Science Undergraduate Lab - useful information about the CSUGLab.
  • Pascal/Java/C Comparisons - a comparison between Pascal, Java, and C.
  • A Very Brief Introduction to Java - some notes on how to use Java
  • Using Microsoft Visual J++ - some notes on how to use Microsoft Visual J++

• Web Resources
  There are lots of Java resources on-line. See Yahoo, for instance, for a great many such Java resources. Here are a few that I've found to be particularly useful.

  • The JavaSoft Home Page
    This is the key site for official Java information; it is maintained by Sun, the original developer of Java. By following links from here you can get to the Tutorial and the API as well as to lots of other useful Java information.
  • The Java Tutorial
    This is a very useful tutorial on Java using HTML. I've used this a lot. In some ways, it's better than a text because it's all linked.
  • JavaWorld
    This is an on-line magazine about Java. It includes tutorial articles, articles about the history of Java (what there is of it), Java news, and tips for using Java.
  • Java API Documentation (version 1.1)
    The Application Programming Interface. These are all the packages that are part of Java. Includes String, Vector, Hashtable, Applet, the AWT (Abstract Window Toolkit), and lots of other stuff.  Much of the functionality of Java is contained within these packages. If you're using J++ then you don't really need this link since the Java API documentation appears as part of the J++ online documentation.  The link above corresponds to version 1.1 which is the version that appears in Microsoft J++ version 6.0 (the numbers used by Microsoft and the numbers used by Sun have no relationship to each other).  Here is the newer API (version 1.2); this API includes the Collections framework which we will discuss in class.  For those interested, version 1.3 (beta) is also available at the JavaSoft site.
  • The Java Language Specification
    This is where to look for syntax questions. Expands on some material that is only sketchily covered in the Tutorial. Again, if you're using J++ then you don't really need this link since the Java Language Specification is part of the J++ online documentation.

Other Links

• Schedule. Topics covered in lecture and the corresponding chapters in the text. Includes some prediction of future lectures. This will be updated periodically during the semester.

Brief Course Description

• Many fields other than computer science (e.g., engineering, chemistry, biology, and physics) can involve a great deal of computing. Practitioners of such fields can benefit from knowledge of data structures and algorithms. Topics include basic data structures (e.g., hashtables, balanced trees, equivalence relations, and priority queues) as well as more advanced topics (e.g., geometric data structures, very large data sets, and the use of randomness).

Homework (and Exam Question) Grading Criteria:

• Correctness and Completeness (i.e., answer the question)
• Clarity, Precision, and Conciseness (i.e., don't use 2 pages when 2 lines will do)
• Optimality of Result (i.e., find the "best" answer)