COMP 554: Algorithms
Michael Soltys, email:
- Course Outline:
This course is an introduction to the art of algorithm analysis,
intended for both Computer Science and Mathematics students. It will
cover the main families of algorithms: Greedy, Dynamic Programming,
Divide and Conquer, Online, and Randomized. The course will present
all the necessary background, and it is intended to be a fun
introduction to the fundamentals of this beautiful field. We are
going to use the instructor's own textbook,
An introduction to
the analysis of algorithms. If time allows, we will also look at
- Lectures: Mondays 6:00-8:50 in Bell Tower
An introduction to the analysis of algorithms
here for a sample of Chapter 1]
Published by the
- Grading: Six assignments, about one every two
weeks, selecting best five, for 20% of the final grade each. The
assignments are going to be a combination of theoretical aspects of
algorithms, and implementation of some concepts in the Python
programming language. We are going to use Python 2.7.6.
- Check this web page regularly for announcements.
- May 3: Slides for Chapter 6
- Apr 7: updated Homework 4 to be due on April 8.
- First class on Monday January 26, 2015, starting at 6pm, in Bell
- Feb 6: Homework 1: Problem 1.40, Implement Algorithm 1.14,
Gale-Shapley, in Python, due on February 16 — please submit
- Feb 19: Homework 2: For this homework, please hand in solutions
to problems 2.28, 2.29, 2.30. Please type them up, and submit as PDFs,
together with a Python code solution to Problem 2.34. The due date is
- Mar 2: Homework 3: This homework covers Divide and
Conquer; please hand in Problems 3.11, 3.12, and 3.13. The due
date is March 23rd.
- Mar 23: Homework 4: This homework is about Dynamic Programming,
which is chapter 4 in the textbook; it does not have a programming
exercise: please submit a PDF containing solutions to: Problems 4.15,
20, 34. The due date is April 8.
- Apr 13: Homework 5: Recall that Kongi's Theorem says that in a
0-1 matrix, the maximum number of 1s no two on the same line (call
this rho) is the same as the minimal number of lines necessary to
cover all the ones (call this rho'). We showed in class that rho is
less than or equal to rho'. Show the other direction, and submit your
solution by April 21.
- Apr 20: Homework 6: Problem 6.26 in the textbook; you are going
to implement a cryptosystem based on Knapsack problem. Please submit
your homework on May 4.