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

Outline of Topics (roughly per week)

1. Analysis of algorithms (Chapter 2, slides, KT slides)
2. Divide-and-Conquer and recurrences, the class P (5.1 - 5.5, KT slides)
3. Greedy algorithms (4.1 - 4.7, slides, KT slides)
4. Dynamic Programming (Chapter 6, slides, KT slides
5. Network Flow (7.1-7.3, 7.5-7.12, KT slides1, KT slides2)
6. Turing Machines, the Turing-Church Thesis, the class NP (Chapter 8, slides, KT slides1, KT slides2, KT slides3)
7. The class PSPACE (Chapter 9, KT slides)
8. Approximation algorithms (11.1 - 11.3, 11.8, KT slides)
9. 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), Covers: Topics 1-8 above, except 11.3)

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 3 (Due Part I: Wed 14/1, Part II: Tue 6/3):
The questions are here. The solutions are here.
Assignment 4 (Due
Part I: Tue 13/3, Part II: Fri 23/3):  The questions are here. The solutions are here.
Assignment 5 (Due (both Parts): Fri. 6/4):
The questions are here. The solutions 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.