CSE 373 - Analysis of Algorithms

Fall 2021

  • Course Time: 1:15PM - 2:35PM Tuesday-Thursday
    Place: on Zoom The Zoom link is available on Piazza if you can't find it on Blackboard
  • Steven Skiena's office hours are 11:05AM-12:35PM Tuesday-Thursday, on Zoom, and by appointment. You can also catch me right after class.
  • The course bulletin board will be Piazza. Sign up by clicking here.
  • Our graduate TAs and their special responsibilities are:
  • The undergraduate course assistants are listed below. Their office hours will be in the undergrad TA rooms 2203 and 2217 Old Computer Science.
  • The undergraduate TAs will have one review session each week on Zoom (two before midterms). The schedule is:

Lecture Notes

Course Documents

  • Course Syllabus and lecture schedule in pdf format.
  • Daily Homework Problems in pdf format.
  • A list of hard problems suitable to challenge me on.

Homework Assignments

  • Homework 1 - DUE 9/16/21 in pdf format.

    An answer key is now available.

  • Homework 2 - DUE 9/30/21 in pdf format.

    An answer key is now available.

  • Midterm 1 will be held Thursday, September 23 and will cover big oh, data structures, and sorting. I have posted a copy of a prior year's Midterm 1 to help you study. Note: we will not provide an answer key, especially for the multiple choice problems, to encourage you to work them out on your own.
  • Homework 3 - DUE 10/21/21 in pdf format. 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.

    An answer key is now available.

  • Homework 4 - DUE 11/4/21 in pdf format. Test your program on our collection of datasets for HW4.
  • Midterm 2 will be held Tuesday, November 16 and will cover graph algorithms, backtracking, and dynamic programming. I have posted a copy of a prior year's Midterm 2 to help you study. Note: we will not provide an answer key, especially for the multiple choice problems, to encourage you to work them out on your own.
  • Homework 5 - DUE 12/2/21 in pdf. Try to do the dynamic programming problems before the midterm. An 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.

    Related Links

    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.

    You can submit these problems through the UVA Online Judge. I have given the corresponding UVA Judge number for each problem in parentheses. Google "

    A schedule for doing these problems that is somewhat consistant with this course is:

    Send me all your work at the end of the semester to receive credit.

    Objectives

    Read about the CS accreditation ABET program. The ABET 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
    251 New Computer Science Building
    Department of Computer Science
    State University of New York at Stony Brook
    Stony Brook, NY 11794-2424, USA
    skiena@cs.stonybrook.edu
    631-632-9026

    Join the Stony Brook Computer Science Society