CSE 201 Course Description:

    * Rigorous analysis of the time and space requirements of important algorithms, including worst case, average case, and amortized analysis.
    * Techniques include order-notation, recurrence relations, decision trees, information-theoretic lower bounds, adversary arguments.
    * Analysis of the key data structures: graphs, trees, hash tables, balanced trees, priority queues, heaps.
    * Algorithmic paradigms such as divide and conquer, dynamic programming, greedy algorithms, union-find with path compression.
    * Selected advanced algorithms.
    * Introduction to NP-completeness.
    * Approximation algorithms

Enrollment is restricted to graduate students; undergraduate students may enroll in this course if they have completed either CSE 102 or CSE 106, and have the consent of the instructor.

General Information

Textbook

“Introduction to Algorithms”, Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein (CLRS), Third Edition.
The Science and Engineering Library has this textbook on Reserve. Second Edition is also available, but this course uses the Third Edition. You should already be familiar with most of the following CLRS material:
     * Appendix A (Summations),
     * Appendix B (Sets, Relations, Functions, Graphs, Trees)
     * Appendix C.1-C.2 (Counting and Probability)
     * Appendix D.1 (Matrices and Matrix Operations—just the basic stuff)
     * Chapter 10 (Elementary Data Structures, including Linked Lists, Stacks, Queues, and Trees)
     * Parts of Chapter 22 (Elementary Graph Algorithms), e.g., Graph terminology, Graph representations, and Depth-First Search and Breadth-First Search Some other good textbooks:

     * "Fundamentals of Algorithms" by Gilles Brassard and Paul Bratley.
     * "Computers and intractability: A Guide to the Theory of NP-completeness" by Michael R. Garey and David S. Johnson.
     * "Algorithms", Fourth Edition, by Robert Sedgewick and David Wayne.

Hope that most of you are already familiar with proof techniques:  Mathematical Induction (Weak and Strong Induction), Proof by Contradiction, etc. "Book of Proof" is freely available for download at http://www.people.vcu.edu/~rhammack/BookOfProof/Main.pdfPDF. This book is an excellent introduction to standard methods of proving mathematical theorems, which might be helpful even for students who already have a good background in proof techniques.

Math Assignments

Although an Algorithms course that does not require programming feels wrong, the focus of CSE 201: Analysis of Algorithms is principally Mathematics, and it’s a tough course, dealing with both efficiency and correctness of algorithms, so there won’t be any Programming Assignments, but there will be Math Assignments. There will be approximately 7 Math Assignments (MAs), each consisting of a series of questions, sometimes based on CLRS or the Handouts.
    * Deadlines are 11:59pm on the due date; deadlines are strictly enforced.
    * You must do MAs individually. Other students, TAs and I may help with concepts, but solutions must be your own!
    * Do not post even partial solutions publicly on Piazza, whether correct or incorrect.
    * Your solutions must be submitted using CrowdGrader, a “peer grading site”, using your UCSC email address as your CrowdGrader id.
    * You’ll learn more about CrowdGrader in your Discussion Sections and from a Piazza notice; there's also a little more info in the Syllabus.

Lectures, Discussion Sections and Course Evaluation

    ShelZoomID (for Lectures and Office Hours)
    BrianZoomID (for Lab Sections and Office Hours)

CSE 201, Analysis of Algorithms, Fall 2020
    Classes: MWF 10:40AM - 11:45AM, via ShelZoomID

Instructor: Sheldon (Shel) Finkelstein, shel@ucsc.edu
     Office Hours (via ShelZoomID):
         Friday 3:00PM - 5:00PM            (or by appointment)

Zoom recordings of all Lectures will be posted on Piazza under Resources->Recordings, usually on same day as Lecture. No Lecture or Discussion Section on Wednesday, November 11 (Veterans Day), and no Lecture on Friday, November 27 (Thanksgiving).

Teaching Assistant:    Brian Schwarzmann, brschwar@ucsc.edu
     Office Hours (via BrianZoomID):
     01A:  Tuesday 11:40AM - 1:15PM
     01B:  Wednesday 4:00PM - 5:35PM
          (or by appointment)

Discussion Sections (via BrianZoomID):
     01A:  Tuesday 11:40AM - 1:15PM
     01B:  Wednesday 4:00PM - 5:35PM

Discussion Sections are a required part of course, although attendance will not be taken in Lectures or Discussion Sections. Discussion Sections are not recorded. Discussion Sections begin on Tuesday, October 6.