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 Staff


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)

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

  1. A Taste of Algorithms
  2. Analysis of Algorithms

Part II: Exploring the Realm of Algorithms

  1. Algorithmic Principles
  2. Algorithms that Crawl over Data Structures

Part III: Hardness of Algorithmic Problems

  1. Algorithmic Complexity Classes
  2. Solutions to Hardness and Undecidability

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:
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

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

  1. Algorithms, by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. McGraw-Hill Education, First Edition.
  2. 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.