CSE 551 Spring 2018 
Foundations of Algorithms

Course Description: Advanced topics in formal algorithm design and analysis, including advanced shortest-paths algorithms, amortized analysis, network flows, NP-completeness, and selected topics in computational geometry, distributed\parallel, randomized, and approximation algorithms.

Course Objectives: The goal of this course is to give you advanced fundamental knowledge in algorithms. We describe some useful algorithms and explain how they work and why they are considered good, in order to (1) help you recognize situations in which you would be better off looking in the literature or asking someone knowledgeable for a good algorithm to solve your problem instead of just coding the first idea that comes to your mind, and (2) give you enough background so that you are able to understand and navigate the literature on algorithms. In order to achieve this, you will have to work through and understand several algorithmic techniques (e.g., divide-and-conquer, dynamic programming, greedy algorithms, network flow algorithms, self-adjusting data structures, basic randomized/approximation techniques) and the mathematical background necessary for analyzing the properties of these techniques and the algorithms based on them (e.g., amortized analysis, recurrence relations, basic graph theory, NP-completeness).

Students must have already mastered the material typically covered in a junior level CS Data Structures and Algorithms class (e.g., CSE310 at ASU) and its prerequisites such as Discrete Mathematics (e.g., MAT243 at ASU). In particular, you should know how quicksort and mergesort work (and be able to write and solve recurrence relations for those), you should be able to use the "big-Oh" notation and you should have seen the algorithms of Dijkstra and Prim and have an understanding of how and why they work. We also assume you know the definitions and basic properties of heaps and binary search trees.

This is a graduate-level Computer Science course; obviously we assume you know computer programming.

Students are expected to have background in Advanced data structures and algorithms (CSE 310), Mathematical foundations (MAT 243).

CSE 551:  Foundations of Algorithms  
Class Meeting Time:
    T Th 7:30-8:45 

    CAVC 351


Office Hours:


Office Hours:

    Ryan Dougherty
    Office:  Brickyard 221 
    Wednesdays 11:00-12:00, Fridays 8:15-9:15 a.m. starting 01/15
Data structures; Discrete mathematics.
Special Needs: If you are entitled to extra accommodation for any reason (such as a disability), we make every reasonable attempt to accommodate you. However, it is your responsibility to discuss this with the instructor at the beginning of the course. 
Absences: If you will miss a test or homework submission because of a documented medical or family issue, or because of a religious observance, you must (1) bring it to the instructor's attention as early as is feasible, and (2) provide documentation. In these circumstances, arrangements will be made to replace the test or homework missed; under no other circumstances is make-up or replacement work available.
Academic Honesty: Students are expected to abide by the FSE Honor Code (http://engineering.asu.edu/integrity/).

Work in this course, unless explicitly stated in writing to the contrary, is to be an effort by the individual student. It is not acceptable to use work other than your own without full attribution and acknowledgment. While you are welcome to discuss problems with others, it is not acceptable to discuss solutions with them.

Depending on the severity of the infraction, penalties may include a grade of zero on the offending item, a grade of zero on the offending item and a reduction of the final grade by one full letter grade, a failing grade in the course with an indication of academic dishonesty. Such penalties might result in a requirement to withdraw from the university. All instances of academic integrity violations are reported automatically (no exceptions) to the dean's office.

If in doubt about anything related to academic integrity, see the instructor.

Title IX Title IX is a federal law that provides that no person be excluded on the basis of sex from participation in, be denied benefits of, or be subjected to discrimination under any education program or activity. Both Title IX and university policy make clear that sexual violence and harassment based on sex is prohibited. An individual who believes they have been subjected to sexual violence or harassed on the basis of sex can seek support, including counseling and academic support, from the university. If you or someone you know has been harassed on the basis of sex or sexually assaulted, you can find information and resources at https://sexualviolenceprevention.asu.edu/faqs.

As a mandated reporter, I am obligated to report any information I become aware of regarding alleged acts of sexual discrimination, including sexual violence and dating violence. ASU Counseling Services, https://eoss.asu.edu/counseling, is available if you wish discuss any concerns confidentially and privately.

Required Text: Algorithm Design, J. Kleinberg and E. Tardos. Addison Wesley, 2006.
Recommended Text: Introduction to Algorithms, Cormen, T. H., Leiserson, C.E., Rivest, R.L., and Stein, C., , MIT Press, , 3rd ed., 2009.