CS 5800: Algorithms
Fall 2017 (San Jose, CA)
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
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.
You will learn the foundations of designing, analyzing, (to
an extent) implementing, and ultimately
understanding algorithms. This involves questions
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 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?
- 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.
- Instructor: Thomas Wahl
- Teaching assistant: Xingrong (Phoebe) Wu
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)
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
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])
- 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
- 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
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
Participation in class is not only highly desirable but required for
credit (see Course components
Communication of general interest to this class will mostly be done
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.
- 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
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;
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
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 exams will be open-book (the books mentioned
here) and open-notes, but no electronic
devices (cell phones, laptops, tablets) will be allowed, whether
connected to the internet or not.
Please make every effort to be available during the exam days, as
there will be no make-ups.
|A ||A- ||B+ ||B ||B- ||C+ ||C ||C- ||F |
|95 ||90 ||85 ||80 ||75 ||70 ||65 ||60 ||<60 |
- 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
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: 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
Academic Integrity Policy in this course.
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.
- 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.