Course Outline (Tentative) 

Texts:

• J. Kleinberg and E. Tardos, Algorithm Design, Addison-Wesley 2005 (main)
• M. Soltys, An Introduction to the Analysis of Algorithms, World Scientific 2010 (auxiliary)

The course may not always follow any text-book closely.
Lecture Notes will be on the website either before class or a few days after class.

Calendar Description: 

• Basic computability models; the Church-Turing thesis, complexity classes; P versus NP; NP-completeness, reduction techniques; algorithmic design strategies; flows, distributed algorithms, advanced techniques such as randomization.

Mission: 

• This course is designed to provide students with an understanding of the principles and techniques in the design and analysis of efficient data structures and algorithms. We shall discuss and analyze a variety of data structures and algorithms chosen for their importance and their illustration of fundamental concepts. We shall emphasize analyzing the worst-case running time of an algorithm as a function of input size. We shall also spend some time exploring the boundary between feasible (polynomial time) computations and infeasible computations. This will include discussion of the notorious P vs. NP question.

Outline of Course Topics (Tentative).

1. Introduction and Representative Problems
2. Greedy Algorithms
3. Divide-and-conquer
4. Dynamic programming
5. Network flow
6. Intractability and coping with intractability
7. Approximation algorithms
8. Randomized algorithms
9. Online algorithms

Learning Objectives: Preconditions: 

Learning Objectives: Postconditions 

1. Students should know and understand
1. Greedy algorithms
2. Divide-and-conquer techniques
3. Dynamic programming
4. Network flow
5. Intractability
6. Approximation algorithms
7. Randomized algorithms
8. Online algorithms
2. Students should be able to use and/or implement, dependently of the need, each of the below
   
   1. Greedy algorithms
   2. Divide-and-conquer techniques
   3. Dynamic programming
   4. Network flow
   5. Approximation algorithms
   6. Randomized algorithms
   7. Online algorithms
      

Evaluation 

Late assignments will not be accepted. Although you may discuss the general concept of the course material with your classmates, your assignment must be your individual effort.

MSAF policy: 

For each MSAF the weight will be moved to the final exam. More information on the MSAF procedure can be found at this link.

Important

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.

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: AGrade 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.
2. Improper collaboration in group work.
3. Copying and using unauthorized aids in tests and examinations.