ECE 606 - Algorithm Design and Analysis
Instructor
Professor
Mark
Crowley
Office:
DC
2526
e-mail:
mcrowley@uwaterloo.ca
Office
hours:
Email
me
to
arrange
an
appointment.
Lectures
Lectures will be held in CPH 3604 on Mondays from 8:30am – 11:30am.
Course teaching assistant
Shankha Chatterjee, office hours to be announced
Course description
This course provides an introduction to the analysis and design of algorithms. Algorithms are at the very foundations of computing. It is important to understand how to design them, and analyse them for correctness and efficiency. It is also very important to able to recognize whether a given problem is intractable so you don’t naively seek efficient solutions where none may exist. This course will introduce you to a broad set of different types of computational problems and the most well known algorithms for solving them. Along the way we will learn how to prove the correctness of algorithms, analyse their computational complexity and understand where it fits in the hierarchy of computational complexity classes. The intent is to provide students with training to recognize the complexity of problems, understand the inherent tradeoffs of different solutions and take an appropriate approach to solving them. Emphasis will be placed on rigorous mathematical analysis of complexity, efficiency and correctness.
Recommended background
Data Structures and Algorithms, Probability, or consent of instructor.
Assessment
The
final
grade
for
the
course
will
be
based
on
a
final
exam
plus
small
in-class
quizzes,
1
or
2
every
lecture
which
will
be
based
mostly
on
the
unmarked
homework
questions
from
previous
weeks.
In-class
quizzes:
50%
Final
Exam:
50%
Course outline
Introduction and Background
- Motivation and overview, stable matching
- Growth of functions, asymptotic notation
Data Structures
- Arrays, Linked-lists, Heaps, Priority Queues, B-trees
Design and Analysis Techniques
- Greedy algorithms
- Dynamic programming
Graph Algorithms
- Graph representations, searching on graphs
- Spanning trees, shortest paths
- Network flow problems
Computational Complexity
- Turing Machine model of computation
- Optimization vs. decision problems
- P, NP, coNP, PSPACE, EXPTIME
- Cook and Karp Reductions, Gap Preserving Reductions
- Approximation algorithms
Probabilistic Analysis and Randomized Algorithms
- Introduction to randomized algorithms
- Probability theory and randomized min-cut
- Expected run-time of quicksort
- Markov and Chebyshev Inequalities, randomized median computation
Textbooks
There is no required textbook, course notes will be provided after each lecture. But most of the course is based on the following books and will be useful to take a look at them. Assigned (but unmarked) homework questions will often come from some of these texts:
-
J.
Kleinberg
and
E.
Tardos,
Algorithm
Design,
2005
- This text is on 3 hour reserve in the Davis Centre Library.
-
T.
H.
Cormen,
C.
E.
Leiserson,
R.
L.
Rivest
and
C.
Stein,
Introduction
to
Algorithms,
3rd
edition,
2009
- This text is on 3 hour reserve in the Davis Centre Library
- It is also available for free online through the University of Waterloo library website.
- S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009
- M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, 2005
Papers and electronic references will be made available on the course website which is on LEARN.
Recipe for success
Attend lectures. Do complementary work at home. Ask questions. Have fun.
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. All new graduate students must complete this module.
- 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.