Algorithms
CSCI 3104, Spring 2018, Section 002
Time: Tuesday, Thursday, 12:30pm - 1:45pm
Room: CHEM 140

Instructor: Aaron Clauset
Office: ECES 118B
Office hours: Tuesday 10:00-11:00am and Thursday 10:00-11:00am
Email: zzilm.xozfhvg@xlolizwl.vwf (an Atbash cipher)
Teaching Assistants: Tao Ruan, Wanshan Yang, Wanshan Yang, Chris Gavin, Sebastian Laudenschlager, and Shivendra Agrawal
Course Assistants: Devon Jones, Samuel Eubanks, Jarrod Raine, Ian Smith, Jacob Liebow, and Adam Ten Hoeve
CA Office hours: See course Moodle page
Course information: Syllabus (read this first)

Description
Algorithms are the heart of computer science, and their essential nature is to automate some aspect of the collecting, organizing and processing of information. Today, information of all kinds is increasingly available in enormous quantities. However, our ability to make sense of all this information, to manage, organize and search it, and to use it for practical purposes, e.g., self-driving cars, adaptive computation, search algorithms for the Internet or for social networks, artificial intelligence, and many scientific applications, relies on the design of efficient algorithms, that is, algorithms that are efficient with time and space resources, and which provide guarantees on their performance.

This undergraduate-level course will cover topics related to algorithm design and analysis. Topics will include asymptotic analysis, time and space constraints, dynamic programming, divide and conquer, greedy algorithms, graph algorithms, computability, and a selection of advanced topics. The focus throughout will be on algorithmic thinking, performance guarantees and boundary cases, efficient solutions to practical problems and understanding how to analyze algorithms. Advanced topics will cover a selection of modern algorithms, many of which come from real-world applications.

Learning Goals
In this course, students will

  • become familiar with standard algorithms for abstract problem solving;
  • learn how to mathematically prove properties of algorithms, including their correctness;
  • analyze the time and space complexity of algorithms;
  • understand the relative merits or demerits of different algorithms in practice;
  • adapt and combine algorithms to solve problems that may arise in practice; and,
  • learn common strategies in the design of new algorithms for emerging applications.

Text
Introduction to Algorithms (3rd ed.), by Cormen, Leiserson, Rivest and Stein
(aka "CLRS"; available at the CU Bookstore).

Schedule
Week 1: Fundamentals of algorithms (Lecture 1)
Week 2: Time and space complexity (Lecture 2)
Week 3: Divide and conquer (Lecture 3)
Week 4: Efficient data structures (Lecture 4)
Week 5: Greedy algorithms (Lecture 5)
Week 6: Dynamic programming, Knapsack (Lecture 6)
Week 7: Dynamic programming, Sequences (Lecture 7)
Week 8: Midterm exam
Week 9: Graph algorithms, SSSP (Lecture 8)
Week 10: Graph algorithms, APSP (Lecture 9)
Week 11: Spring Break
Week 12: Graph algorithms, MST (Lecture 10)
Week 13: Graph algorithms, Max-flow (Lecture 11)
Week 14: Problems in P and NP (Lecture 12)
Week 15: Stable matchings (Lecture 13)
Week 16: Internet algorithms
Week 17: Final exam (scheduled)

Problem Sets
There will be 10 problem sets. Problem sets will always be due on Thursday. A LaTeX template for writing up your solutions can be found here. All problem set files and submissions will be through the course Moodle page

Examinations
There will be a midterm exam (in class), and a final exam. There may also be pop or online quizzes during the semester.

Resources
Advice on writing proofs, by Cathy O'Neil.
Advice on proofs by induction, by Jeff Erickson (UIUC)
Mathematics for Computer Scientists; advice by Eric Lehman (Google), F. Thomson Leighton (MIT) and Albert R Meyer (MIT)
TeXShop (LaTeX installation for Mac OS X)
MiKTeX (LaTeX instalation for Windows)
TeX Live (LaTeX instalation for Linux)
LaTeX resources and guides (here, here, here and here).
Algorithms Course Materials by Jeff Erickson (UIUC)
Algorithm Design, by J. Kleinberg and E. Tardos (textbook)
Algorithms, by S. Dasgupta, C. Papadimitriou and U. Vazirani (textbook)