EECS 3101, Winter 2018
EECS 3101: Design and Analysis of Algorithms
Web page contents:
Instructor: Eric Ruppert
Office: Room 1003H of the Lassonde Building (enter through Lassonde 1012 hallway)
Telephone: (416) 736-2100 ext. 33993
Lectures: Mondays and Wednesdays, 14:30-16:00 in room 0016 of the Dahdaleh Building; during remediation period lectures will be Tuesdays 19:00-22:00 in room 0016 of the Dahdaleh Building
Tutorials: Fridays, 14:30-16:00 in room 0016 of the Dahdaleh Building; no separate tutorials during remediation period
Email: [my last name]@cse.yorku.ca (Please use a York email account when sending me email, and start your subject line with "".)
Professor's Office Hours: Since the regular term is over, office hours are by appointment.
In this course, you will be invited to develop your ability to think clearly and carefully about algorithms, and to improve your skills in expressing those thoughts about algorithms in a precise way.
Algorithms lie at the heart of computer science; in fact, some would say that computer science is the study of algorithms, so this course plays a central role in your education as a computer scientist.
By the end of this course, you will be able to do the following things.
Choose an appropriate algorithm to solve a given computational problem, and justify that choice
The first step in studying algorithms is to become familiar with a number of standard algorithms that can be applied in a wide variety of contexts. Then, you will be able to recognize when they can be applied. This sometimes requires finding the underlying structure of the problem, and seeing exactly what properties a solution to the problem must have.
Design new algorithms using a variety of techniques (recursion, greedy algorithm, dynamic programming, backtracking)
The next level of studying algorithms is to design your own novel algorithms. Sometimes this can be done by plugging together existing algorithms like modules. In other cases it requires more originality, but you will learn several algorithmic techniques that can be applied to design algorithms for a wide variety of problems.
Prove correctness of an algorithm using pre- and post-conditions and loop invariants
Once you have an algorithm to solve a problem, you want to be sure that it does produce the correct solution. The process of proving it correct helps you find mistakes in the design of the algorithm. Once those bugs are fixed, you can then go on to prove correctness to convince yourself and others that the algorithm is correct.
Prove bounds on the running time or space used by an algorithm
If there are several different algorithms that can be used to solve a problem, we typically want to choose the one that will run in a reasonable amount of time or space. Proving bounds on the resources used by an algorithm allows you to make this choice, and to justify your choice to others.
Apply standard graph algorithms to a variety of problems
Graphs can be used to model a very wide variety of problems from many areas of computer science, so a few standard algorithms for graphs should be part of the toolbox of algorithms that you know about. Sometimes applying one of these graph algorithms requires some ingenuity to look at the problem in the right way to recognize how it can be applied.
How to Learn This Material
Some of the skills that you will develop in this course may be quite new to you, and different from things you have done in previous courses. This is good: it means you're learning new and (I hope) exciting things. However, it means that you will need practice to master them. Just participating in classes isn't enough. There are suggested exercises from the textbook. Web pages for this course in previous terms also include many more problems to work on. The books listed below under "Additional Resources" include more exercises. Do lots.
You learn by struggling with problems. However, if you get too stuck or don't know how to begin, help is available. Talk to your classmates (however; see the notes below about academic honesty regarding discussing assignment problems with others). Go to office hours; the instructor and TA are there to help you! You also learn by making mistakes and getting feedback about them. Just make sure that you use the feedback to improve your understanding.
Groups of students can learn a lot by explaining their solutions to the suggested exercises from the textbook to one another and critiquing the solutions of others. After all, learning how to explain solutions clearly is one of the learning objectives of this course. Seeing where other students' solutions are unclear to you helps you make your own explanations clearer. Be aware that a problem may have many different correct solutions; just because someone's solution is different from yours doesn't necessarily mean that one of them is wrong.
It takes time to build new skills, so it helps if you work on exercises regularly: don't leave all the work to the days right before a test.
The key to academic honesty for this course is simply this: Solutions that you submit should be your own work.
Although you may discuss the general approach to solving a homework problem
with other people, you should not discuss the solution in detail.
You must not take any written notes away from such a discussion.
Also, you must list on the cover page of your solutions any
people with whom you have discussed the problems.
The solutions you hand in should be your own work. While
writing them, you may look at the course textbook and your own
lecture notes but no other outside sources.
It is not acceptable to try to find the answer to a homework question on the web, put it in your own words and submit it. You may learn a little by doing this, but you will learn much, much more by working on the problem yourself, and the purpose of this course is to help you learn how to design and analyze algorithms on your own.
Furthermore, the web will not be available during your exam (or during your job interview at Google), so you should learn to solve problems yourself, instead of relying on others to do your thinking for you.
As time runs out, students are sometimes tempted to get help from other students on assignments in a way that would violate the preceding policy on academic honesty. DO NOT DO THIS! If you do, I will refer the case to the Dean's Office, which will be very unpleasant for you. The assignments are worth very little, so it is not worth risking a sizable punishment. (Furthermore, I have noticed that the students who cheat on the homework assignments almost always fail the tests and exams, so even if I do not catch you cheating, you will likely fail the course if you do not do your own work on the homework assignments.)
It is important that you look at the departmental
on academic honesty.
|Homework exercises || 10% |
|Test #1 || 25% |
|Test #2 || 25% |
|Exam || 40% |
It's a very good idea to type your solutions to homework assignments, since it allows you to edit and polish the answers, but handwritten solutions are also acceptable, as long as they are legible. If you want to type your solutions, LaTeX produces elegantly typeset documents, is available for free, and was built to handle even the most complicated mathematical notation. It can take a while to learn how to use it, but once you do, you will probably not want to type documents any other way.
You should make every effort to make your answers as brief as possible, while still being thorough. Brevity requires careful thought and editing. (Pascal once excused himself for writing a long letter, saying that he did not have enough time to write a shorter one.) Students who write copious amounts usually do not know what they want to say, or are saying it in a very disorganized way.
Usually, an answer to a homework question should fit on one sheet of paper. If you are writing much more than that, you probably have not found the best way to solve it. On tests, your answer should usually fit into the space provided for it.
- (Oct 18) The location for the deferred exam on Saturday, October 20 is ACW 109.
- (Sep 17) If you have deferred standing in this course, the deferred exam will be held on Saturday, October 20 from 12:00 to 15:00. (Location to be announced.) You may bring one 8.5-by-11-inch piece of paper with handwritten notes on both sides into the exam.
- (Aug 15) The August exam scheduled has been posted by the registrar.
- (Aug 8) Assignment 8A has been slightly edited to make some notation more consistent. See updated version at bottom of this page.
- (Aug 7) For the deferred final exam, you will be permitted to use one 8.5-by-11-inch sheet of handwritten notes (both sides of page).
- (Jul 30) Makeup test #2 in class on August 7 will cover sorting (lower bound, radix, counting, bucket), dynamic programming and greedy algorithms.
- (Jul 25) Look at the bottom of this page for outlines of makeup classes and makeup assignments. The makeup test #2 will be held during the makeup class of August 7.
- (Jul 23) Makeup classes (mentioned below) will be in room 0016 of the Dahdaleh Building. We will begin on July 24, even if the strike is not quite over yet.
- (Jul 10) Assuming the strike ends in the next two weeks, my plan is to do the following for students who chose not to attend classes during the strike.
Any student in the course is welcome to attend the makeup classes. If you missed any piece of work during the regular term (assignment/test/exam), you may submit the corresponding piece of makeup work.
- Makeup classes will be on Tuesdays from 19:00 to 22:00 from July 24 to August 14 in DB 0016.
- Makeup assignments will be posted here.
- A makeup test 2 will be held during one of the Tuesday classes (August 7).
- A makeup exam will be held shortly after August 20 (exact date to be determined by the registrar).
I chose the time for makeup classes that most students said they could attend. If you are unable to attend the makeup classes:
I will post a list of topics covered in each class. This will just be a few lines of text for each class. They will not be complete lecture notes. I recommend that you obtain a copy of class notes from a friend.
You can then read about the topics in the course textbook, or see Jeff Edmonds' recorded lectures on the appropriate topic from his web page.
- I will be available for office hours (to be announced) if you have difficulties with the material.
- (Apr 5) For the final exam, you will be permitted to use one 8.5-by-11-inch sheet of handwritten notes (both sides of page).
- (Apr 5) There will be a review session on Monday, April 9 at 14:00 in room 0006 of the Dahdaleh Building.
- (Mar 31) There will be a bonus quiz in class on Friday, April 6.
- (Mar 28) Correction to Question 2 on Assignment 9:
The k cities chosen from the bucket list must be visited in the order
they appear on that list. (This restriction makes the problem easier
to solve.) In other words, there must be a common subsequence of your
route and the bucket list such that the length of the common subsequence
is at least k. And you want the route of this form that has the minimum
Note that you can visit locations more than once along the route.
(The route does not have to be a simple path.)
Because of this late change to the assignment, I am extending the deadline
to Wednesday, April 4.
- (Mar 22) The TA office hour on Thursday, March 29 will be cancelled.
- (Mar 12) The lecture and my office hour on Wednesday, March 14 are cancelled. There are extra TA office hours this week on Tuesday March 13 15:00-16:00 and Thursday March 15 14:00-16:00 in Lassonde 2013.
- (Mar 8) The Senate has announced today that the last day to drop a winter term course without academic penalty will be extended (but did not say by how long).
- (Mar 3) In the event of a strike by CUPE 3903, my plan is to continue regularly scheduled classes in EECS3101Z to
minimize the disruption for students who wish to continue.
If you choose not to participate in the academic activities of the
course during the strike, you will not be penalized for this choice.
Some kind of remedy will be offered so that you can make up for
work that you miss, although this remedy may not guarantee
an identical learning experience. For more information, see the Senate Policy.
- (Feb 27) Starting next week, my Monday office hours will be from 11:30 to 12:30.
- (Feb 17) Clarification for assignment 5, question 1: the x- and y- coordinates of a house are real numbers. Do not assume they are integers.
- (Feb 14) The deadline for assignment 4 is extended to Feb 23.
- (Feb 6) If you are interested in spending the summer working on a research project, see this link.
- (Feb 5) The National Society of Black Engineers is holding a student conference downtown on Saturday, February 24. The Lassonde Faculty will reimburse you for the registration fee if you would like to attend. See this link for details.
- (Jan 31) The breakdown of marks for assignment 2 was: 2 marks for 1(a), 4 for 1(b), 1 for 1(c), 1 for 2(a), 2 for 2(b), 5 for 2(c), 1 for 2(d) for a total of 16.
- (Jan 26) There was a typo in my solutions to assignment 2, question 2(b): if Alviine's first roll is i, she should say "pay" if and only if i > 5.5.
- (Jan 22) Women in Science and Engineering is organizing a hackathon for women on Feb 2-4 in the Bergeron Centre. They are also extending an invitation to men to help out with the hackathon. For more information, see this video or this website.
- (Jan 7) The Faculty of Engineering is presenting an event on technology and society on January 24. See this link for details.
- (Dec 30) The first tutorial on January 5 will be used to review some background material that you should know as a prerequisite to taking this course.
|First class || Friday, January 5|
|Test 1 ||Friday, February 9|
|Reading week (no classes)|| February 19-23 |
|Last date to drop course without receiving a grade||Friday, March 9 (this deadline will be extended due to the strike)|
|Test 2 ||Friday, March 16|
|Good Friday (no class) ||Friday, March 30|
|Last date to withdraw from course (receiving W on transcript)||Friday, April 6|
|Last class || Friday, April 6|
|Exam period ||April 9-23|
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and
Clifford Stein, Introduction to Algorithms, 3rd edition,
MIT Press & McGraw-Hill, 2009. For solutions to some of the textbook's exercises and known bugs in the text, see the textbook's web page.
Copies of the text are on reserve at the Steacie Library. You can also access an electronic version of the textbook through the York Library website.
Optional Supplementary Reading
- Jeff Edmonds, How to Think About Algorithms, Cambridge University Press, 2008.
- Ian Parberry's book, Problems on Algorithms,
has lots of practice problems for many topics covered in this
course. Solutions to selected problems are also given. The book is
available online; the author asks that you make a small donation to
charity if you choose to download the book. Follow
to access the book.
- Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani, Algorithms, McGraw Hill, 2008. This is a really nice little book.
- Michael R. Garey, and David S. Johnson, Computers and
Intractability: A Guide to the Theory of NP-Completeness,
W. H. Freeman and Company, 1979.
- Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete
Mathematics: A Foundation for Computer Science (2nd edition),
- Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2006.
- Donald E. Knuth, The Art of Computer Programming (3rd edition),
Volume 1: Fundamental Algorithms, Addison-Wesley, 1997.
Sections 1.1 and 1.2 are a good reference for the material covered
during the first few weeks of the course.
TAOCP also has lots of good exercises with solutions.
- Donald E. Knuth, The Art of Computer Programming (2nd edition),
Volume 3: Sorting and Searching, Addison-Wesley, 1998.
- Anany Levitin, Introduction to the Design and Analysis of
Algorithms (3rd edition), Pearson, 2012.
- Steven S. Skiena, The Algorithm Design Manual (2nd edition), Springer, 2008.
- Steven S. Skiena and Miguel A. Revilla, Programming Challenges: The Programming Contest Training Manual, Springer, 2002. This book covers many topics of the course from a more problem-oriented angle.
- Daniel Solow, How to Read and Do Proofs (6th edition), Wiley, 2013.
- Michael Soltys, An Introduction to the Analysis of Algorithms, World Scientific, 2010.
This section will be filled in as the term progresses.
Don't fall behind with your reading.
|Date||Topics ||Reading in CLRS (3rd ed) ||Suggested questions, mostly from CLRS (3rd ed)|
| January 5
|| Background Math
|| Chapter 3 and handout
|| Review questions
and 3.1-1 to 3.1-6, 3.2-2, 3.2-7, 3-3(a), 3-4(a to d); see also chapter 2 and 3 of Parberry's book
| January 8
|| 1; optional supplementary reading: Boyer-Moore algorithm
| January 10
|| Proving correctness of loops
|| 2.1, 2.2, 31.2 (up to Lame's Theorem)
|| 2.1-3, 2.1-4, 2.2-2, 2-2, 2-3; see also chapter 5.1 of Parberry's book; 31.2-4, 31.2-8
| January 22
|| Proving correctness of recursive algorithms, divide and conquer
|| 2.3, 4.0-4.1, 4.3-4.4, time bound for fast multiplication
|| 2-1, 2.3-3, 2.3-4, 2.3-6, 2.3-7,
4.1-1, 4.1-5, 4.3-1, 4.3-6, 4.4-2; see also chapter 4, 5.2, 7 of Parberry's book
| January 29
|| Selecting kth smallest element from unsorted array
|| 9.1, 9.3 (and skim 9.2)
|| 9.1-1, 9.3-1, 9.3-5, 9.3-6, 9.3-7, 9.3-8, 9-1
| January 31
|| More divide and conquer examples, analysing running time of recursive algorithms
|| 4.2, 4.5, (skim 4.6), 33.4
|| 4.2-3, 4.2-7, 4.5-1, 4.5-4, 4-1, 4-2, 33.4-1, 33.4-6
| February 5
|| pages 147-189 (a lot of this will be a review)
|| 6.1-1 to 6.1-7, 6.2-3, 6.2-6, 6.4-2, 6.4-3, 6.4-4, 6.5-4, 6.5-5, 6.5-8, 6-2,
7.2-4, 7.3-1, 7-1, 7-2
| February 7
|| Sorting lower bound and sorting in linear time
|| All of chapter 8
|| 8.1-1, 8.2-4, 8.3-1, 8.3-2, 8.3-3, 8.3-4, 8.4-4, 8-4
| February 14
|| Dynamic Programming
|| All of chapter 15
|| 15.1-1 to 15.1-5, 15.2-2, 15.2-6, 15.3-2 to 15.3-6, 15.4-2, 15.4-5, 15-2, 15-5, 15-6, 15-9, 15-10, 15-11
| February 28
|| Greedy Algorithms
|| 16.1, 16.2
|| 16.1-2, 16.1-3, 16.1-4, 16.2-1, 16.2-3, 16.2-5, 16.2-7
| March 7
|| Greedy Algorithms, including MST algorithms
|| 16.3, 23, 21.1-21.2 (for implementation of Prim's algorithm)
|| 16.3-1, 16.3-3, 16.3-4, 16.3-7, 16.3-9, 16-2, 16-4(a), 16-5(a,c), 23.1-1, 23.1-4, 23.1-6, 23.1-7, 23.2-2, 23.2-4, 23.2-5, 23.2-8, 23-4, 21.1-3, 21.2-2, 21.2-5, 21.2-6,
| March 14
|| Graph Algorithms
|| 25.1, 25.2, 22
|| 25.1-6, 25.1-7, 25.1-8, 25.2-4, 25.2-5, 25-1(a,b), 22.1-5, 22.2-6, 22.2-9, 22.3-2, 22.3-5, 22.3-7, 22.3-9, 22.4-3, 22.4-5, 22.5-1, 22.5-2, 22-2, 22-3, 22-4
| March 21
|| More Graph Algorithms
|| 24.0, 24.3
|| 22.4-3, 22.4-5, 22.5-1, 22.5-2, 22-2, 22-3, 22-4, 24.3-1 to 24.3-4, 24.3-6, 24.3-8
Solutions to assignments will be handed out in class on the day they are due.
- Alternate assignment 6
- In the July 24 makeup class, we quickly reviewed dynamic programming (canoe rental problem that we saw before the strike, and took up the modified version of it that was question 2 of Assignment #5). Then a quick review of greedy algorithms (the example of scheduling the maximum number of non-overlapping jobs with given start and finish times). Then we finished discussing the greedy algorithm for unit-time jobs with deadlines and profits (which we had started talking about just before the strike). Notes on the latter are available here. Then we discussed Kruskal's minimum spanning tree algorithm, including a proof of correctness and a simple data structure for implementing it in O((m+n)log n) time for a graph of n nodes and m edges.
- Alternate assignment 7
In the Jul 31 makeup class, we covered Prim's algorithm, Dijkstra's algorithm, breadth-first search and depth-first search, and applications of depth-first search to finding a topological sort of an directed acyclic graph and finding strongly connected components of a directed graph.
- Solution to alternate assignment 6 (available only to enrolled students; use your EECS account login)
- Alternate assignment 8 (slightly updated Aug 8 to make notation more consistent)
- In the (short) August 7 lecture, we took up test 2A and then covered the Floyd-Warshall algorithm.
- Solution to alternate assignment 7
- Alternate assignment 9
- In the Aug 14 makeup class, we covered the Ford-Fulkerson algorithm for maximum flow. We looked at one example of modelling a problem using a graph so that the problem could be solved using a standard graph algorithm. We ended with a very brief introduction to NP-completeness:
The class P is the set of problems that can be solved in polynomial time.
The class NP is the set of problems whose solutions can be verified in polynomial time.
There is a subset of NP called NP-complete problems. In some sense, they are the hardest problems in NP. Nobody knows if they are solvable in polynomial time. If any one of those problems has a polytime solution, then they all do. If any one of those problems does not have a polytime solution, then none do. See Garey and Johnson's book Computers and Intractibility for a list of many NP-complete problems from diverse areas of computer science.
If you are faced with an NP-complete problem, it's unlikely that you will be able to come up with a polytime algorithm to solve it. When faced with such a problem, options include: trying to find heuristics that work well in practice, settling for an approximate solution, redefining the problem you want to solve (for example, maybe it is sufficient for your needs to solve an easier special case of the problem).
- Solution to alternate assignment 9
Updated October 18, 2018