CS 161

Design and Analysis of Algorithms

Summer 2018

Policies

Late Days You will be allowed 5 late days to use on homework assignments with a maximum of two per assignment (except for Homework 3, you're not allowed to use late days). The original deadline for an assignment is listed on the course schedule. The "hard deadline" for an assignment occurs 48 hours after the original deadline (the hard deadline for Homework 3 is the same as the original deadline). Assignments submitted after the hard deadline or after all late days have been exhausted automatically will receive a score of 0%.

Exam Cheat-Sheet Exams will be closed-book, but you will be allowed one page back and front (or, I suppose, two one-sided pages) of notes, which can be handwritten or typed.

Alternate Exams If you are going to miss an exam for any reason (illness, family emergency, etc.), you must communicate this to the instructors prior to the exam via Piazza.

LaTeX Extra Credit We strongly recommend typesetting solutions to homework in LaTeX. LaTeX is the standard for typesetting CS/math/etc papers, and will likely come in handy outside CS 161. To encourage you to typeset solutions in LaTeX, we will offer extra credit for typed submissions: 2.5% of the value of the assignment. For first-time LaTeX users, please see the Resources page for some materials that will help you get started.

Course Logistics

Piazza Join our Piazza to receive important announcements and get answers to your questions and not troll the course staff anonymously.

Gradescope Join our Gradescope to submit your homework, using entry code MY7DKP.

Lectures Lectures occur on Tues/Thurs 9:30-11:20 a.m. in Skillaud.

Lecture Videos Lecture videos will be recorded and posted on Canvas.

Tutorials Tutorials occur on Fri 3:30-4:50 p.m. in STLC 115. Attendance at these sessions is optional. These tutorials will consist of a short review, group activity, and individual follow-up activity.

Textbook The main text is CLRS: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 3rd Edition, MIT Press. It's available online for free from the Stanford library.

Accomodations Students who may need an academic accommodation based on the impact of a disability must initiate the request with the Office of Accessible Education (OAE) and notify us at least 7 days (ONE week) prior to the Midterm and/or Final Exam.

Course Description

Overview This course will cover the basic approaches and mindsets for analyzing and designing algorithms and data structures. Topics include the following: Worst and average case analysis. Recurrences and asymptotics. Efficient algorithms for sorting, searching, and selection. Data structures: binary search trees, heaps, hash tables. Algorithm design techniques: divide-and-conquer, dynamic programming, greedy algorithms, randomization. Algorithms for fundamental graph problems: minimum-cost spanning tree, connected components, topological sort, and shortest paths. Possible additional topics: network flow, string searching.

Prerequisites CS 103, CS 109 or STATS 116.

Assessment Midterm Exam (7/26): 25%, Final Exam (cumulative) (8/17): 40%, Homework 0: 0%, Other 5 Homeworks (equally weighted): 35%