Syllabus

Course Overview

This course presents the fundamental techniques for designing efficient computer algorithms, proving correctness and analyzing complexity. General topics include graph algorithms, basic algorithm design paradigms (e.g., divide-and-conquer, dynamic programming and greedy algorithms), lower bounds and NP-completeness.

Contacts

To make sure that emails are read, please put [CS336] in your topic when communicated via email.

Instructors

Samir Khuller (samir.khuller@northwestern.edu)

Teaching Assistants

Class Time

With our current situation regarding the virus, we will have our sessions online until further notice.

The Link to Zoom can be found in “Course Summary” below (or in the summary tab if you use the mobile version).

Also, our classes in Zoom will be recorded and we will make them available afterward.

Lecture

9:30 – 10:50 am on Tuesday and Thursday at Swift Hall 107

Discussion

Section 60: 1:00 – 1:50 pm on Friday at Frances Searle Building 2107

Section 61: 2:00 – 2:50 pm on Friday at Frances Searle Building 2107

Section 62: 3:00 – 3:50 pm on Friday at Technological Institute M128

Office hours

Monday

10:30 am – 12:30 pm Nathan

12:30 pm – 3:00 pm Helen (Ziqi)

Tuesday

2:00 pm – 3:30 pm Helen (Ziqi)

Wednesday

10:30 am – 11:30 am Aidao

10:30 am – 12:30 pm Nathan

1:00 pm – 2:00 pm Samir

3:00 pm – 5:00 pm Pat

Thursday

2:00 pm – 3:30 pm Helen (Ziqi)

Saturday

10:30 am – 12:00 pm Nathan

Texts

Required: Algorithm Design by J. Kleinberg and E. Tardos. ISBN 0-321-29535-8, published by Addison Wesley (2005).

Recommended: Introduction to Algorithms (by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, publisher MIT Press, 2009).

Prerequisites

COMP_SCI 212 (Mathematical Foundations of Computer Science) and COMP_SCI 214 (Data Structures and Data Management). Each student is expected to know basic concepts of programming (e.g., loops, pointers, recursion), discrete mathematics (e.g., proof by induction, sets), simple data structures (e.g., lists, stacks, queues, trees, heaps) and calculus (e.g., logarithms, differentiation, integration).

Piazza

We will use Piazza for online class discussions.
This is the best way to get
help fast and efficiently from classmates, the TAs and us.
Rather than emailing questions to the teaching staff, we
strongly encourage you to post questions to Piazza.
The Piazza link is piazza.com/northwestern/spring2020/cs336.

Course Work

Course work will consist of 7-8 homework assignments, quizzes, and two exams (one mid-term and a comprehensive final).

Homework sets will be mathematically oriented. For each set, we may choose a random subset of problems to grade.

Every homework is due on Thursday midnight Chicago time. The homework solutions will be handed after the due date, could be during the discussion sessions.
NO LATE HOMEWORKS WILL BE ACCEPTED. In other words, submit whatever you have finished. Instructions for how to submit homeworks will be given with the posting of Homework 1. If you cannot come to class on the due date, it is your responsibility to make sure that we have your homework before the start of class.

All homeworks are to be done independently,  unless otherwise specified. Posting homework solutions in public online locations is considered a violation of the academic integrity policy. Needless to say, you are expected to maintain the utmost level of academic integrity in this course. If you have questions, please talk to one of the TAs or to us.

Assignments are to be written up neatly and concisely. Poorly written assignments will not be graded.  Staple your homework. It is your responsibility to obtain all homeworks and handouts. All course  information and handouts will be available on the web page.

Grading

Final grades will be determined by performance on homework sets, quizzes, the midterm exam, and the comprehensive final exam.  The following weights are subject to change and will be roughly 25% from the homeworks, 30% from quizzes, 20% from the midterm exam and
25% for the final exam. We will adhere to the

Syllabus

The general topics to be covered:

  • General algorithms background and examples of algorithms and problems.
  • Graph exploration: connected components, topological sorting, strongly connected components.
  • Greedy algorithms: minimal spanning trees, shortest paths.
  • Divide-and-conquer algorithms: geometric algorithms, selection, lower bounds for minimum and sorting, Strassen’s matrix multiplication.
  • Dynamic programming: shortest paths, Warshall’s algorithm, optimal search trees.
  • Network flows and applications.
    NP-completeness: introduction to reductions, the classes P and NP,
    NP-complete problems, approximation algorithms.
  • Randomized algorithms.