ECE 606 - Fall 2017

ECE 606 - Algorithms

Instructor

Mahesh Tripunitara, DC 2532
519 888 4567 x32864
tripunit@uwaterloo.ca
Office hours: By appointment (send me an email). I’m usually around. What to call me: “Mahesh,” “Dr. T,” “Prof. T,” “Dr. Tripunitara,” or “Prof. Tripunitara”

Lectures

Mondays 2:30 – 5:20 PM in room RCH 305

Teaching Assistants

To be determined.

Philosophy

Algorithms are at the very foundations of computing. It is important that one understands how to design them, and analyze them for correctness and efficiency. It is important also that one recognizes whether a problem is intractable so one does not naively seek efficient solutions where none may exist. This course will be driven by computational complexity classes. The intent is to provide students with training to recognize the complexity of problems, and take an appropriate approach to solving them..

Content

Introduction: data structures, algorithms, correctness criteria, non-existence result. Complexity classes – L, NL, P, NP, PSPACE, EXPTIME, EXPSPACE, DECIDABLE, UNDECIDABLE. The class P, and examples of analysis of worst- and expected-case efficiency. Optimization vs. decision problems, the class NP, Cooke and Karp reductions, the polynomial hierarchy. Recognizing optimal substructure, dynamic programming, when not to be naive. Reconciling NP- completeness – NP as an upper-bound, reduction to SAT and SAT solvers. Reconciling PSPACE- completeness – model checking, PSPACE as an upper-bound. The class of counting problems in NP, #P. Approximation algorithms for NP-complete problems – gap preserving reductions.

Prerequisite

An undergraduate course in data structures and algorithms, similar to ECE 250.

Marking

In-class quizzes: 50%, Final exam: 50%.

Quizzes

1 or 2 every lecture, for a total of 20–24. They are based on weekly, unmarked problem-sets I assign.

Course materials

Course materials will be available on LEARN

Topics covered in lectures

  • week 1: Properties and strategies via example I — Existence, correctness, termination, bounded-error, approximation ratio, time-efficiency, space-efficiency, . . .
  • week 2: Properties and strategies via example II
  • week 3: Properties and strategies via example III
  • week 4: Deeper dive I – data structures and associated algorithms Tables, lists, trees, graphs,. . .
  • week 5: Deeper dive II – data structures and associated algorithms
  • week 6: Deeper dive III – data structures and associated algorithms
  • week 7: Deeper dive IV – data structures and associated algorithms
  • week 8: Deeper dive V – data structures and associated algorithms
  • week 9: Computational Complexity I – complexity classes and reductions
  • week 10: Computational Complexity II – tractable vs. intractable classes
  • week 11: Computational Complexity III – intractable classes
  • week 12: Computational Complexity IV and wrap-up

Textbook

None. The following will be used as reference books. It may be useful for you to acquire one of them, e.g., (1) below.

  1. Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms
  2. Kleinberg & Tardos, Algorithm Design
  3. Arora & Barak, Computational Complexity, a Modern Approach
  4. Hopcroft, Motwani & Ullman, Automata Theory, Languages & Computation
  5. Vazirani, Approximation Algorithms
  6. Knuth, The Art of Computer Programming

This course is about

Common sense, basic math, organized reasoning.

Recipe for success

Attend lectures. Do complementary work at home, in particular, the weekly problem-sets.

University policies

  • Academic integrity: In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility.
  • Grievance: A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70, Student Petitions and Grievances, Section 4. When in doubt please be certain to contact the department’s administrative assistant who will provide further assistance.
  • Discipline: A student is expected to know what constitutes academic integrity to avoid committing an academic offence, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offence, or who needs help in learning how to avoid offences (e.g., plagiarism, cheating) or about “rules” for group work/collaboration should seek guidance from the course instructor, academic advisor, or the undergraduate Associate Dean. For information on categories of offences and types of penalties, students should refer to Policy 71, Student Discipline. For typical penalties check Guidelines for the Assessment of Penalties.
  • Appeals: A decision made or penalty imposed under Policy 70 (Student Petitions and Grievances) (other than a petition) or Policy 71 (Student Discipline) may be appealed if there is a ground. A student who believes he/she has a ground for an appeal should refer to Policy 72 (Student Appeals).
  • Note for students with disabilities: The AccessAbility Services, located in Needles Hall, Room 1132, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with the AccessAbility Services at the beginning of each academic term.