CS 5800: Algorithms
Fall 2017 (San Jose, CA)

The story. An algorithm is a recipe for mechanically, i.e. without intuition, accomplishing a given task, typically formulated over a number of input parameters. More technically, it is a mathematical structure that consists of a description of: (i) inputs, (ii) mechanical steps, often in human-readable form, and (iii) outputs. The intention is that, being mechanical, the steps can be translated into a computer program, called an implementation of the algorithm, which then accomplishes the task, for a given concrete input. The translation of the steps into a program depends on other choices, such as appropriate data structures.
In addition to the requirement of correctness of the algorithm (and its implementation), we typically have certain expectations on the amount of consumed resources, such as time and memory.

The course. You will learn the foundations of designing, analyzing, (to an extent) implementing, and ultimately understanding algorithms. This involves questions like:

how do we turn an informal task description into a precise definition?
how do we abstract the task definition into an algorithmically solvable problem?
how do we design (or choose) an algorithm to solve this problem?
how do we reason about the algorithm, namely:
- is it correct?
- does it terminate? how quickly?
- can this problem be solved in a better way? how do we even measure that?

We will discuss some of these questions in a stand-alone fashion to introduce concepts, but more commonly we will apply them to a variety of algorithms and algorithmic principles that we explore in this course.

How to Tie a Tie

Synopsis

Course number: CS 5800
Course reference number (CRN): 18218
Class meeting times: Mondays 3-6pm
Class meeting location: San Jose campus, 6024 Silver Creek Valley Rd.

Course Staff

Instructor: Thomas Wahl
- Email: wahl–ät–ccs.neu.edu
- Office hours: Mon 12-3pm and Thu 3-6pm
Teaching assistant: Xingrong (Phoebe) Wu
- Email: wu.xingr–ät–husky.neu.edu
- Office hours: Fri 3-5pm

Prerequisites

Formal: enrollment at the Graduate level. The course is intended mainly for MS-level students, including students of the ALIGN program.
Content: (a basic level of knowledge in the following is sufficient for the course; we will review at the beginning)

Discrete math: arithmetic; series and sums; sets; propositional logic; graphs
Programming: ability to read, write, and understand code written in basic programming languages or pseudo code (assignments, conditional branches, subroutines, loops, recursion)

Course Topics

The following list is tentative. It depends on the pace of the course and also, to some extent, on the students' interests. Information in parentheses in the form

(09/25 [1, Ch. 2.3, 2.1; 2, Ch. 4.1])

indicates that we covered/will cover the particular topic on September 25, and that the recommended reading for that lecture is from textbook reference 1, chapters 2.3 and 2.1, and textbook reference 2, chapter 4.1, in this order.

Part I: Introduction, Basic Concepts, Whetting Appetite

A Taste of Algorithms
- Numeric algorithms: integers and primes (09/11 [1, Ch. 1, esp. 1.3])
- Applications to cryptography (09/11 [1, Ch. 1, esp. 1.4])
Analysis of Algorithms
- Termination & Invariants (09/18 [2, Ch. 2.1; treated as part of Insertion Sort])
- Induction
- Growth of functions & “big-O” notation (09/18 [2, Ch. 3.1])
- Solving recurrences (09/25 [1, Ch. 2.2])

Part II: Exploring Algorithms

Algorithmic Principles
- Divide and conquer (09/25 [1, Ch. 2.3, 2.1; 2, Ch. 4.1])
- Greedy strategies (10/02 [1, Ch. 5.3; 2, Ch. 16.3; 1, Ch. 5.4])
- Dynamic programming (10/16 [1, Ch. 6.1, 6.2, 6.3])
Graph Algorithms
- Breadth and Depth First Search, Strongly Connected Components (10/30 [1, Ch. 3, 4; 2, Ch. 22])
- Shortest-Path Problems (11/04 [1, Ch. 4; 2, Ch. 24, 25])
- Spanning Trees (11/13 [1, Ch. 5.1; 2, Ch. 23])
- Flow networks (11/20 [2, Ch. 26; 1, Ch. 7.2], 11/27 [1, Ch. 7.1, 7.3, 7.6])

Part III: Hardness of Algorithmic Problems

Algorithmic Complexity Classes (11/27 [1, Ch. 8])
- NP and beyond
- Complexity classes; reducibility; hierarchy
- Undecidability
Solutions to Hardness and Undecidability (12/04 [1, Ch. 9, 10; 2, Ch. 5, 35])
- Partial and semi-algorithms
- Approximation algorithms
- Randomized algorithms
- Quantum algorithms

Methodology

In principle this is a classical lecture course. In practice, class time will be spent on interactive lectures, discussions, presentations by students, and sometimes practical exercises, guided but without grades. In addition, there will be practical homework exercises and two exams. Participation in class is not only highly desirable but required for credit (see Course components and grading).

Communication of general interest to this class will mostly be done via Piazza. Personal matters should be sent via email to the appropriate course staff.

Course Components and Grading

Your final grade will depend on the following contributions to the class:

10%: class participation.
This can take many forms (all of these count): correct answers, incorrect answers, good questions, not so good questions, volunteer presentations, suggestions for improving the class.

20%: homeworks.
Homeworks will be given out approximately once a week on Mondays, will be due the next Monday, and should be graded the Monday after that.
We will do homeworks in groups of two. The same grade is assigned to both group members. We do not directly track who contributed what to each homework; however, see "presentations" in the next paragraph. You can pair up with anyone you want, and you can change group membership every week. We leave group building mostly to you; Piazza is a resource that can help.

Homeworks should be turned in to the TA each Monday when due, at the beginning of class (since we will discuss some homework problems when class starts), printed on paper or neatly hand-written. We do not accept electronic submissions (email or otherwise). If you cannot make it to class, have your groupmate submit. If your entire group misses class or is substantially late, you have to make arrangements with the TA.

Full credit for the homework portion of your course grade requires the ability to present and defend the solution in front of the class when called upon. Every individual (not every group) must do one such presentation in class. Your turn will be decided on the day of the presentation, by volunteering, or by random drawing if there are no volunteers, or by a combination of the two if there are several volunteers.
The point of the class presentation is two-fold: (i) to make sure everyone in a group contributes to the homework; (ii) to give you an opportunity to practice professional demonstration and defense techniques in front of a friendly crowd, and provide you with feedback.
Please do not get stressed out about the presentation. It is meant to help you. If you do the presentation, your homework grade is determined solely by what you turn in.

30%: midterm exam.
This will last at most 90mins (1⁄2 class session) and happen during class time on October 23.

40%: final exam.
This will last at most 120mins (2⁄3 class session), be cumulative and happen during the official exam period.

The following table shows which percentages guarantee each letter grade. This means that, per the instructor's discretion, they may be adjusted down, class-wide or on an individual basis.

A	A-	B+	B	B-	C+	C	C-	F
95	90	85	80	75	70	65	60	<60

Course Milestones

Mon Sep 11: first meeting of class
Mon Oct 09: no class: Columbus Day
Mon Oct 23: midterm exam
Mon Dec 04: last meeting of class
Dec 11--16: final exam period
Mon Dec 18: course grades due to registrar
Tue Dec 19: course grades released

Course Rules

Attendance: highly recommended and to some extent required for your 10% class participation score, but we will not keep attendance records. If you need to miss class, courtesy suggests to inform your instructor, but otherwise you are responsible for catching up on missed material, turning in homeworks, etc.

Homeworks: they will be due at the beginning of class, since we will use part of that class to have you present some of the homework problems. For these and other reasons, late homeworks will not be accepted. This class meets only once a week, so we cannot afford to derail the schedule by giving extensions. If you cannot finish the homework, turn in partial solutions.

Collaboration: You may and should discuss lecture contents with your classmates at any time. You may also ask clarification questions on the homeworks of your peers or, better, in public forums such as Piazza. The solutions, on the other hand, need to be worked out and formulated by yourself (and any partners, if we decide to do homeworks in groups). Therefore, clarification questions on public forums must not (implicitly) give away any information. You are also not allowed to consult printed or online material to search for solutions. We will discuss in class why such behavior would not even make any sense.

We will of course apply Northeastern's Academic Integrity Policy in this course.

Textbooks

Algorithms, by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. McGraw-Hill Education, First Edition.
Introduction to Algorithms, by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. MIT Press, Third Edition.

These books are available in print for little money, and as e-books. However, before you buy anything: we will discuss on the first day of class how we use these books. You can postpone purchasing anything until after that day.