Place: 079 Earth and Space Sciences
Lecture Notes
- Video lectures of my course are now available at http://www.cs.sunysb.edu/~algorith/video-lectures/.
- Lecture notes from the current semester are available here.
- Lecture notes from previous semesters are available in HTML, postscript and pdf formats. The complete set is 300 pages -- do not print them on departmental machines!
- Lecture notes from previous semesters with audio and (maybe, but probably not) video are available online!
- Full-lecture audio from Fall 2004 is also available, although they are not keyed directly to the lecture notes.
-
Course Documents
- Course Syllabus and lecture schedule in postscript and pdf formats.
- Daily Homework Problems in postscript and pdf formats.
Homework Assignments
- Homework 1 - DUE 2/19/08, in postscript and pdf formats. The answer key is now available.
- HW1 programs for experimenting with execution times. Note that one of them must be compiled with the -lm option..
- Midterm 1 will be held Tuesday, March 4 in class and will cover big oh, data structures, and sorting.
- Homework 2 - DUE 3/6/08 in postscript and pdf formats. The answer key is now available.
-
Homework 3 - DUE 4/3/08 in
postscript
and
pdf
The four testfiles for Homework 3 are file 1, file 2, file 3, file 4. The first number represents the number of edges, the second the number of vertices.
- CSE 392 backtracking Lecture Notes in html and PDF.
- Homework 3 Solutions
- Homework 4 - DUE 4/22/08 in postscript and pdf formats. Test your program on our collection of datasets for HW4.
- Homework 4 Solutions
- Midterm 2 will be held Thursday, April 24 in class and will cover graph algorithms, backtracking, and dynamic programming.
- Homework 5 - DUE 5/15/08 in postscript and pdf formats. The answer key is now available.
- Fill out an ABET course objectives survey evaluation form for the course to help me do a better job!
- The course final exam will be held May 20, 2008 from 11AM-1:30PM. Good luck!
Extra Credit
Interested students may attempt the following extra credit programming challenges from Skiena/Revilla for a small amount of additional points -- small enough that you should be motivated primarily by interest and not greed.The solutions to these problems must be submitted on www.programming-challenges.com. Register for an account and join my CSE 373 extra credit class if you are intersted.
A schedule for doing these problems that is somewhat consistant with this course is:
- week 1: 110101 3n+1
- week 2: 110201 Jolly Jumpers
- week 3: 110303 Common Permutation
- week 4: 110401 Vito's family
- week 5: 110405 Shoemakers problem
- week 6: 111101 Is Bigger Smarter?
- week 7: 111104 Unidirectional TSP
- week 8: 110801 Little Bishops
- week 9: 110901 Bicoloring
- week 10: 110902 Playing with Wheels
- week 11: 111006 Tourist Guide
- week 12: 111105 Cutting Sticks
- week 13: 110806 Garden of Eden
- week 14: 111005 War
- week 15: 110805 Tug of War
Objectives
The objectives for the course are
- Provide a rigorous introduction to worst-case asymptotic algorithm analysis.
- Develop classical graph and combinatorial algorithms for such problems as sorting, shortest paths and minimum spanning trees.
- Introduce the concept of computational intractability and NP completeness.
The course will also satisfy the following program objective:
- (S6) have a solid understanding of computational theory and foundational mathematics.
Professor
- Steven S. Skiena
- 1411 Computer Science Building
- Department of Computer Science
- State University of New York at Stony Brook
- Stony Brook, NY 11794-4400, USA
- skiena@cs.sunysb.edu
- 631-632-9026
Join the Stony Brook Computer Science Society