CSE 373 - Analysis of Algorithms

Fall 2017

  • Course Time: 1PM - 2:20PM Tuesday-Thursday
    Place: Javits 102
  • Steven Skiena's office hours are 2:30-4PM Tuesday-Thursday, in 251 New Computer Science, 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:

    • Allen Kim. His email address is allen.kim@stonybrook.edu. His office hours will be 5:30pm-7:00pm, Monday and Wednesday in the CS TA room 2203 old Computer Science. Allen will serve as the official complaints department for homework and midterm/exam grading. He will be the sole point of contact on such matters.
    • Xuan Xu. Her email address is xuaxu@cs.stonybrook.edu. Her office hours will be 2PM to 3:30PM on Monday and Wednesday, in the Old Computer Science 2208.
    • Lihan Huang. His email address is lihahuang@cs.stonybrook.edu. His office hours will be 4PM to 7PM Friday in the CS TA room Old Computer Science 2203.
  • The undergraduate course assistants are listed below. Their office hours will be in the undergrad TA rooms 2203 and 2217 Old Computer Science.
    • Edwin Alvarez (edwin.alvarez@stonybrook.edu). Office hour: Tuesday 11:30-12:30PM.
    • Kenneth Chiguichon (kenneth.chiguichon@stonybrook.edu). Office hour: Friday 2:30-3:30PM.
    • Calvin Li (calvin.li@stonybrook.edu) Office hour: Monday 3:30-4:30PM.
    • Victor Zhen (victor.zhen@stonybrook.edu). Office hour: Wednesday 12-1PM.
  • The undergraduate TAs will have one review session each week (two by midterms) in Old Computer Science (OCS). The schedule is:
    • 9/6 - Victor and Calvin @ 1:00 PM in OCS 2120
    • 9/15 - Edwin and Kenneth @ 10:00 AM in OCS 2311
    • 9/20 - Victor and Calvin @ 1:00 PM in OCS 2120
    • 9/27 - Victor and Calvin @ 1:00 PM in OCS 2120
    • 9/29 - Edwin and Kenneth @ 10:00 AM in OCS 2311
    • 10/6 - Edwin and Kenneth @ 10:00 AM in OCS 2311
    • 10/11 - Victor and Calvin @ 1:00 PM in OCS 2120
    • 10/20 - Edwin and Kenneth @ 10:00 AM in OCS 2311
    • 10/25 - Victor and Calvin @ 1:00 PM in OCS 2120
    • 11/3 - Edwin and Kenneth @ 10:00 AM in OCS 2311
    • 11/8 - Victor and Calvin @ 1:00 PM in OCS 2120
    • 11/15 - Victor and Calvin @ 1:00 PM in OCS 2120
    • 11/17 - Edwin and Kenneth @ 10:00 AM in OCS 2311
    • 12/1 - Edwin and Kenneth @ 10:00 AM in OCS 2311
    • 12/6 - Victor and Calvin @ 1:00 PM in OCS 2120
    • 12/8 - Edwin and Kenneth @ 10:00 AM in OCS 2311
  • The CEAS tutoring services claims to offer help in CSE 373 every Monday (6:00-8:00PM) evening, in Engineering room 236B. Students may request tutoring information by visiting or calling the CEAS Undergraduate Student Office or visiting the CEAS Tutoring Services Website.

Lecture Notes

  • The lecture notes from the current semester are available here.
  • Video and audio lectures with links to lecture notes from previous offerings of my course are available at my YouTube channel or http://www.cs.stonybrook.edu/~skiena/373/videos/. The associated lecture notes from these old offerings are available here.
  • There is a Wiki with possible solutions to odd numbered problems from the book.

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/26/17 in pdf format.

    An answer key is now available.

  • Homework 2 - DUE 10/10/17 in pdf format.
  • Midterm 1 will be held Tuesday, October 3 in class 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.

    Students whose last names begin A-H will take the midterm in New Computer Science 120. Students I-Z should go to the usual classroom Javits 102.

  • Midterm 1 grade breakdown
  • Many students in the class have been submitting homeworks with strong resemblance to previous answer keys. This is a self-defeating strategy. My TAs identified 39 students who submitted blatant copies of the key. The copiers average on Midterm 1 was 52.74, compared to an average of 63.57 for the rest of the class. The key to doing well in CSE 373 is beating your head on the HW problems, and getting help when you are stuck.
  • Homework 3 - DUE 10/26/17 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/9/17 in pdf format. Test your program on our collection of datasets for HW4.

    Contest results for HW4.

  • Midterm 2 will be held Tuesday, November 22 in class 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.

    Students whose last names begin A-H will take the midterm in New Computer Science 120. Students I-Z should go to the usual classroom Javits 102.

  • Homework 5 - DUE 12/7/17 in pdf. Try to do the dynamic programming problems before the midterm. The answer key is now available.

    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.

    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.

    If this judge is not working, note that you can also submit them through the UVA Online Judge. I have given the corresponding UVA Judge number for each problem in parentheses.

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

    • week 1: 110101 3n+1 (100)
    • week 2: 110201 Jolly Jumpers (10038)
    • week 3: 110303 Common Permutation (10252)
    • week 4: 110401 Vito's family (10041)
    • week 5: 110405 Shoemakers problem (10026)
    • week 6: 111101 Is Bigger Smarter? (10131)
    • week 7: 111104 Unidirectional TSP (116)
    • week 8: 110801 Little Bishops (861)
    • week 9: 110901 Bicoloring (10004)
    • week 10: 110902 Playing with Wheels (10067)
    • week 11: 111006 Tourist Guide (10099)
    • week 12: 111105 Cutting Sticks (10003)
    • week 13: 110806 Garden of Eden (10001)
    • week 14: 111005 War (10158)
    • week 15: 110805 Tug of War (10032)

    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-4400, USA
    skiena@cs.stonybrook.edu
    631-632-9026

    Join the Stony Brook Computer Science Society