**ALGORITHMS AND COMPLEXITY**

**CS
3AC3 (Winter 2018)**

*** * * This outline is constantly
updated. Students should consult this page regularly for all
information relevant to this course * * ***

**Instructor**

Dr. George Karakostas

ITB/218, ext 26132, Mac address: karakos

Office hours: by email
appointment

**Course Assistance**

Enamul Haque (haquee@mcmaster.ca),
Office hour: Mon. 4-5 pm, Rm. ITB/223

Yasami Sartipi
(yasamin.sartipi@gmail.com), Office hours: Thu. 2-3 pm, Rm.
ITB/229

**Schedule**

Term II, 2017/18

Tu We Fr 12:30 - 1:20 PM, Rm T13 127

**Tutorials**

Session 1: Mo 1:30 - 2:20
PM, Rm BSB 119

**Prerequisites**

**CS 2C03, CS 2FA3
**

Course Objectives

In this course, we will study the
solution of computational problems from two complementary
perspectives: (i) The **Algorithm Design & Analysis **perspective,
i.e., the design methods one can employ in order to build
efficient algorithms for fundamental problems (e.g., network
flows), and the analysis of their running times. We will study
the design of Divide-and-Conquer, Greedy and Dynamic Programming
algorithms, approximations algorithms that are efficient but can
only provide approximation-of-the-optimal guarantees, and the
use of randomization in our algorithms. (ii) The **Computational
Complexity **perspective, i.e., the study of the inherent
difficulty of solving a problem computationally. As opposed to
the 'easyness' of solving a problem, demonstrated by efficient
algorithms designed in (i), in this part we will study how one
can show that a problem is at least as 'hard' to solve as
another problem, using reductions, and will classify our
problems into complexity classes such as P, NP, PSPACE,
according to their 'hardness'.

More specifically, students should know and understand:

- Worst case analysis of algorithms
- Divide-and-Conquer algorithms
- Greedy algorithms
- Dynamic Programming
- Network Flows
- Turing-Church Thesis, complexity classes (P, NP, PSPACE)
- Approximation algorithms
- Randomized
algorithms

Students should be able to

- Analyze the running time of algorithms
- Design Divide-and-Conquer algorithms
- Design Greedy algorithms
- Design Dynamic Programming algorithms
- Solve Network Flow problems
- Distinguish problems according to their complexity class
- Design simple approximation algorithms
- Use
randomness in algorithms

**Learning
objectives, indicators, and rubrics**** **

**Outline of Topics (roughly per
week)**

- Analysis of algorithms (Chapter 2, slides, KT slides)
- Divide-and-Conquer and recurrences, the class P (5.1 - 5.5, KT slides)
- Greedy algorithms (4.1 - 4.7, slides, KT slides)
- Dynamic Programming (Chapter 6, slides, KT slides)
- Network Flow (7.1-7.3, 7.5-7.12, KT slides1, KT slides2)
- Turing Machines, the Turing-Church Thesis, the class NP (Chapter 8, slides, KT slides1, KT slides2, KT slides3)
- The class PSPACE (Chapter 9, KT slides)
- Approximation algorithms (11.1 - 11.3, 11.8, KT slides)
- Randomized algorithms (13.1- 13.5, KT slides)

**Student Assessment (Grading)**

- Homework
assignments
**15%** - Midterm
exam
**40%****(****Feb. 16, 2:30 - 5:00 pm, Rm. UH 213****, Open book (only original hardcopy of the textbook, no notes), Covers: Topics 1-4 above, and Chapter 7.1-7.6)** - Final
exam
**45%****(Open book (only original hardcopy of the textbook, no notes))**

**
Policy on collaboration for homework assignments: **Collaboration
on the homework assignments is highly encouraged, within
reasonable limits. Students are expected to discuss assignment
problems with each other, and to cooperate on solutions in
groups of no more than 5 people. However, the final write-up
should be done by individual students (i.e. individual students
should be able to explain their solutions by themselves, if such
an explanation is asked for by the instructor) and the names of
the collaborators should appear on the paper. Cooperation and
teamwork are necessary for the success of any complex task (the
design of algorithms being one such task), and it is the
instructor's hope that students will come to appreciate them in
a constructive way. Please see the instructor if you need
someone to collaborate with.

**Policy on delayed assignments: **Assignments
delivered between the lecture they were due and the following
lecture get 50% of total credit. After the following lecture, no
credit given.

**Policy on collaboration during
exams: ****ABSOLUTELY NO
COLLABORATION DURING EXAMS!!!**

**Resources**

**Required textbook:** **"Algorithm
Design", by J. Kleinberg and E. Tardos, Addison-Wesley **

**Recommended textbook: "Introduction to Algorithms", 3rd Ed.,
by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,
MIT Press
Recommended textbook: "Introduction to the Theory od
Computation", 3rd Ed., by M. Sipser, Cengage Learning
**

**Academic Dishonesty**

**"Academic dishonesty consists of
misrepresentation by deception or by other
fraudulent means and can result in serious consequences, e.g.
the grade of
zero on an assignment, loss of credit with a notation on the
transcript
(notation reads: "Grade of F assigned for academic
dishonesty"), and/or
suspension or expulsion from the university.
It is your responsibility to understand what constitutes
academic
dishonesty. For information on the various kinds of
academic dishonesty
please refer to the Academic Integrity Policy, specifically
Appendix 3,
located at
http://www.mcmaster.ca/senate/academic/ac_integrity.htm
The following illustrates only three forms of academic
dishonesty:
1. Plagiarism, e.g. the submission of work
that is not one's own or for which other credit has been
obtained. (e.g. submitting a copy of someone else's
writeup for an assignment)
2. Improper collaboration in group work.
(e.g. collaboration between groups in an assignment)
3. Copying or using unauthorized aids in
tests and examinations."**

**Faculty Notice**

**"The Faculty of Engineering is
concerned with ensuring an environment that is free of all
discrimination. If there is a problem, individuals are
reminded that they should contact the Department Chair, the
Sexual Harrassment Officer or the Human Rights Consultant, as
the problem occurs."
**

**"The instructor and university
reserve the right to modify elements of the course during the
term. The university may change the dates and deadlines for
any or all courses in extreme circumstances. If either type of
modification becomes necessary, reasonable notice and
communication with the students will be given with explanation
and the opportunity to comment on changes. It is the
responsibility of the student to check their McMaster email
and course websites weekly during the term and to note any
changes."
**

Assignments

All assignments are to be submitted
to the instructor at the beginning of the lecture.

Assignment 1 (Due Part I: Tue 16/1,
Part II: 23/1): The questions are
here. The solutions
are here.
**
** Assignment 2 (Due Part I: Tue 30/1, Part II: Fri 9/2): The questions are here. The
solutions are here.

Assignment 5 (Due ?): The questions are here.

To read the assignment files, you'll
need the Adobe Reader, which is here**.**

**Slides**

The lecture slides used in the
lectures are designed by the textbook authors, and are
distributed by Pearson Addison-Wesley.