CSE 373 - Analysis of Algorithms

Spring 2012

• Course Time: 12:50 - 2:10PM Tuesday-Thursday
  Place: Humanities 1006
• Steven Skiena's office hours are after class 2:15PM-3:45PM Tuesday-Thursday, in 1417 Computer Science, and by appointment.
• The course assistants will be:
  • Andrii Soviak (Andrew). His email address is asoviak@cs.stonybrook.edu. He will have office hours Monday and Wednesday from noon to 1:30PM in 2110 CS.
  • Himanshu Jindal (grader). His email address is hjindal@cs.stonybrook.edu. Feel free to make an appointment with him.
• The course final exam will be held May 10, 2012 from 2:15PM-4:45PM, in Humanities 1006. Good luck!

  Lecture Notes

  • Video and audio 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!
  • There is a Wiki with possible solutions to odd numbered problems from the book.
  • There are two excellent talks of algorithmic interest this week at the Simons Center:

    Thursday, April 12 2:30 PM-3:30 PM Eva Tardos, Cornell University The Price of Anarchy

    Interaction of users with different incentives is a keyfeature of many domains ranging from communication networks through social networks and markets. In light of such competing forces, it is surprising how well some of these mechanisms work. In this talk we consider a range of games modeling such interactions, and consider the degradation of quality of solution caused by the selfish behaviors of users.
    

    Friday, April 13 3:00 PM-4:00 PM Avi Wigderson, Institute for Advanced Study Randomness

    Is the universe inherently deterministic or probabilistic? Perhaps more importantly - can we tell the difference between the two? Humanity has pondered the meaning and utility of randomness for millennia. There is a remarkable variety of ways in which we utilize perfect coin tosses to our advantage: in statistics, cryptography, game theory, algorithms and gambling. Indeed, randomness seems indispensable! Which of these applications survive if the universe had no randomness in it at all? Which of them survive if only poor quality randomness is available, e.g. that arises from "unpredictable" phenomena like the weather or the stock market?

    A computational theory of randomness, developed in the past three decades, reveals (perhaps counter-intuitively) that very little is lost in such deterministic or weakly random worlds. In the talk I'll explain themain ideas and results of this theory

    The talk is aimed at a general science audience, and no particular background will be assumed.

  Course Documents

  • Course Syllabus and lecture schedule in pdf format.
  • Daily Homework Problems in pdf format.
  • A picture of the highest degree node in the road network that I am aware of.
  • The course textbook as the way to get a job at Google
  • Videos of sorting algorithms as folk dances.
  • A list of hard problems suitable to challenge me on.

  Homework Assignments

  • Homework 1 - DUE 2/16/12, in pdf format.

    An answer key is now available. Here are the keys for problems 3.11 and 1.17 which were missing.

  • Midterm 1 will be held Tuesday, February 28 in class and will cover big oh, data structures, and sorting.
  • Homework 2 - DUE 3/6/12 in pdf format. The answer key is now available. The grading plan and answers to two other problems are also available.
  • Homework 3 - DUE 3/27/12 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. The answer key is now available. The answers to two another problem is also available.

  • Homework 4 - DUE 4/12/12 in pdf format. Test your program on our collection of datasets for HW4.
  • Come by my office door to sign up for Pizza with the Prof, Wednesday April 11 at 12PM. Registration is limited to the first ten students to sign up.
  • Midterm 2 will be held Thursday, April 19 in class and will cover graph algorithms, backtracking, and dynamic programming.
  • Homework 5 - DUE 5/3/12 in pdf format.

  Extra Credit

  Interested students who are not taking CSE 392 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