| CSE 373 | Analysis of Algorithms |
| Fall 2008 | |
| Prof. George Hart | Phone: (631) 632-8959 email: george@cs.sunysb.edu Office: 1438 Computer Science Office hours: Tuesdays and Thursdays 2:15-3:30, and by appt. |
| Class hours: | Tuesdays and Thursdays, |
| Class web page: | http://www.cs.sunysb.edu/~cse373 |
| Announcements: | Note that Monday, Jan 15 is scheduled as a thursday; it will
be our last class before the final. |
| Homework: | HW #0: Get the text and start reading it. HW #1, due tuesday Sept 23 HW #2, due thursday Oct 2 Programming problem #1, due tuesday Oct 14 HW #3, due thursday Oct 30 HW #4, due thursday, Nov 6 Programming problem #2, due thursday Nov 20 HW #5, due tuesday Nov 9 |
| TA: | Leif Walsh, rlwalsh@ic.sunysb.edu Office hours: Thursdays, 2:30-3:30, room 2110 Comp. Sci. |
| Syllabus: | We will largely follow the text, focusing on the design
issues in Chapters 4-7 and then NP-completeness from Chapter 8.
We will minimize the more mathematical analysis and review the
mathematical
background from earlier chapters as needed. |
| Material: | Mathematical analysis of a variety of computer algorithms including searching, sorting, matrix multiplication, fast Fourier transform, and graph algorithms. Time and space complexity. Upper-bound, lower-bound, and average-case analysis. Introduction to NP completeness. Some machine computation is required for the implementation and comparison of algorithms. This course is offered as AMS 373, CSE 373, and MAT 373. |
| Prerequisite: | Prerequisites: MAT 211 or AMS 210; CSE 214 |
| Text book: | Jon Kleinberg and Eva Tardos Algorithm Design Pearson / Addison Wesley, 2006, ISBN 0-321-29535-8 |
| Grading basis: | The semester grade is based on: 20% homeworks and programming projects, 25% test #1, 25% test #2, and 30% final exam. Programming projects can be done in groups and in the language of your choice. The Pass/No Credit (P/NC) option is not available for this course. Semester grades will be made available on the university's Solar System web site. |
| Policies: | Regular lecture attendance is essential or you will probably fail the course. You are encouraged to work together discussing the ideas and techniques for all homework assignments, but then write your own solutions rather than copying a group solution. If you do not get in the habit of learning to solve new problems, you will not do well on the tests. Late homeworks are not accepted. Makeup tests are not given without a (very good) written excuse. |
| Final Exam: | Thursday, Dec 18, 2008, 5:00PM-7:30PM (schedule) |
| Disabilities: | If you have a physical, psychiatric/emotional, medical or learning disability that may impact on your ability to carry out assigned course work, you are strongly urged to contact the staff in the Disabled Students Services (DSS) office, in the ECC building (phone: 632-6748/TDD). DSS will review your concerns and determine, with you, what accommodations are necessary and appropriate. All information and documentation of disability is confidential. |