CSE 373 - Analysis of Algorithms

Spring 2014

  • Course Time: 1PM - 2:20PM Tuesday-Thursday
    Place: Humanities 1006
  • Steven Skiena's office hours are 11:30AM-1PM Tuesday-Thursday, in 1417 Computer Science, and by appointment. You can also catch me right after class.
  • The course assistants will be:
  • The course final exam will be held on Monday, May 19 in Humanities 1006 from 5:30PM-8PM. It will be cumulative and cover everything we did this semester. Students who's last names start from S - Z should report to Humanities 3018. Good luck!

    Lecture Notes

    Course Documents

    Homework Assignments

    • Homework 1 - DUE 2/25/14 (change due to snow cancellation), in pdf format.

      An answer key is now available.

    • Homework 2 - DUE 3/11/14 in pdf format.

      An answer key is now available.

    • Midterm 1 solution -- Spring 2014
    • Homework 3 - DUE 4/3/14 in pdf format. The answer key is now available.

      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, and each subsequent line represents an edge between the pair of numbered vertices.

    • Homework 4 - DUE 4/16/14 in pdf format. Test your program on our collection of datasets for HW4.
    • Midterm 2 solution -- Spring 2014
    • Homework 5 - DUE 5/8/14 in pdf. Try to do the dynamic programming problems before the midterm. The answer key is now available.
    • Please fill out the course evaluation form on line. I do value your feedback to improve the course the next time it is offered.

    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
    1417 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