**AlgorithmsCSCI 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)