EECS 3101B, Fall 2026

EECS 3101B: Design and Analysis of Algorithms
Fall 2026

Web page contents:

General Information
Announcements
Important Dates
Resources
Reading
Course Documents

General Information

Instructor: Eric Ruppert
Office: Room 3052 of the Lassonde Building
Telephone: (416) 736-2100 ext. 33948
Email: [my first initial and last name]@yorku.ca (Please use a York email account when sending me email, and start your subject line with "[3101]".)
Lectures: Mondays and Wednesdays, 17:30-18:50 in room 103 of the Life Sciences Building
Tutorials: Wednesdays, 19:00-20:20 in room 105 of the Life Sciences Building
Professor's Office Hours: Mondays and Thursdays 14:00-15:00 in room 3052 of the Lassonde Building or by appointment.
TA Office hours: Mondays 19:00-20:00 in room 3052 of the Lassonde Building.

Learning Outcomes

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 (e.g., recursion, greedy algorithm, dynamic programming)
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. 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. AI and the web can also be useful but don't become overly reliant on these aids; it is important to develop your own, independent skills too. (Ideally, you would use an AI model that is not very good, so that you have to learn to look at the answers it provides critically.)

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.

Academic Honesty

Evaluation in this course will be through in-person tests during tutorials. You will not be permitted to use electronic devices during the tests.

It is important that you look at the senate policy on academic honesty and the faculty's academic integrity resources.

Marking Scheme

4 Quizzes, equally weighted	30%
2 Tests, equally weighted	30%
Exam	40%

If one evaluation during the term is missed due to illness, the weight of the missed evaluation will ordinarily be moved to the final exam. If, for some extraordinarily unusual reason, you miss two assessments during the term, alternate arrangements will have to be made. This may include an oral examination or some other means of assessing the course learning outcomes.

Announcements

(Nov 1) To replace the Nov 4 lecture, I have posted some videos on the course eclass page.
(Oct 30) No lecture on Nov 4; quiz takes place from 7:15 to 8:15 in LSB103/105. No aids allowed for the quiz. Extra office hour on Nov 4 5:30-6:30 in Lassonde 3052. No office hour at 2pm on Nov 5 or 9.
(Oct 19) For test 1, you may bring in one 8.5x11-inch sheet of paper with handwritten notes on both sides.
(Oct 19) York's co-op and career office is hosting a Career & Further Education Expo on Oct 21 from 10am to 2pm. See this link for more information.
(Oct 7) My office hour on Oct 8 will be 30 minutes later than usual, from 2:30 to 3:30.
(Sep 23) The office of Student Accessibility Services is looking for a student volunteer to provide class notes for this course. If you are interested in volunteering, please see this link for more information.
(Sep 18) The EECS department is running programming contest training sessions on Mondays from 3pm to 5pm starting on Sep 21. They are fun and a good way to practice ideas you are learning in this course. See detailed announcement for more information.

Important Dates

First class	Wednesday, September 9
Quiz 1	Wednesday, September 23
Quiz 2	Wednesday, October 7
Reading week (no classes)	October 12-16
Test 1	Wednesday, October 21
Quiz 3	Wednesday, November 4
Last date to drop course without receiving a grade	Tuesday, November 10
Test 2	Wednesday, November 18
Quiz 4	Wednesday, December 2
Last class	Monday, December 7
Last date to withdraw from course (receiving W on transcript)	Tuesday, December 8
Exam period	December 10-23

Resources

Textbook

[CLRS] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 4th edition, MIT Press, 2022. Cost: $195 (may be available from online retailers for less). For solutions to some of the textbook's exercises and known bugs in the text, see the textbook's web page, under Resources. 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

[DPV] Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Algorithms, McGraw Hill, 2008. Nice book for very succinct discussions of key topics on algorithms.
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 this link to access the book.

Other References

Jeff Edmonds, How to Think About Algorithms, 2nd edition, Cambridge University Press, 2024.
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), Addison-Wesley, 1994.
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.

Web Links

Algorithmics Animation Workshop
links to web pages on theoretical computer science
web page of this course the last time I taught it
Ma and Pa Kettle demonstrate the importance of proving arithmetic algorithms correct

Reading

This section may be adjusted as the term progresses. Don't fall behind with your reading.

Date	Topics	Reading in CLRS (4th ed)	Suggested questions, mostly from CLRS (4th ed)	Alternate reading in DPV
Sep 9	Introduction	1; optional supplementary reading: Boyer-Moore algorithm and notes on correctness	1-1
Sep 9	Proving loops correct. Two examples of multiplication algorithms.	2.1, 2.2	2.1-2, 2.1-4, 2.1-5, 2.2-2, 2.2-4	1.1
Sep 14	Proving loops correct: binary search		Section 5.1 of Parberry's book
Sep 16	Euclid's algorithm, recursive algorithms	2.3, 31.2 up to Lame's Theorem	31.2-8, 2.3-2, 2.3-3, 2.3-5 to 2.3-8	1.2.3
Sep 16	Review of asymptotic notation, examples of proofs of correctness	3	3.2-1, 3.2-2, 3.2-3, 3.2-5, 3.3-8, 3-2	0.3
Sep 21	Proving recursive algorithms correct. Examples: repeated squaring, binary search	2.3.1, p.934-935,	2-3, Section 5.2 of Parberry's book	1.2 up to end of 1.2.2, 2.3
Sep 23	Divide and Conquer	4.0-4.2, time bound for fast multiplication	4.1-3, 30-1	2.1
Sep 28	Analyzing divide-and-conquer algorithms	4.3-4.5	4.3-1, 4.4-1, 4.5-1	2.2
Sep 28	Example of divide and conquer: Linear time selection	9.1, 9.3 (and skim 9.2)	9.1-1, 9.1-2, 9.1-3, 9.3-1, 9.3-6, 9.3-7, 9.3-8, 9.3-9, 9.3-10, 9-1	2.4
Sep 28	Finding the closest pair of points; Sorting lower bound	Section 33.4 (in chapter on Computational Geometry) from removed material, 8.1	33.4-1, 33.4-6 in removed material; 8.1-1, 8-6	pp.52-53
Sep 30	Review of sorting techniques	pages 157-204 (this should be a review)	6.1-1 to 6.1-6, 6.2-7, 6.4-2, 6.4-4, 6.5-7, 6-2, 7.2-4, 7.3-1, 7-1, 7-2
Sep 30	Counting Sort, Radix Sort	8.2, 8.3	8.2-1, 8.2-3, 8.2-5, 8.2-6, 8.2-7, 8.3-2, 8.3-4, 8.3-5, 8-2, 8-3
Oct 5	Bucket sort	Use C.2, C.3 as references if you need to look up something about probability. 8.4	8.4-1, 8.4-2, 8.4-5
Oct 7	One-dimensional Dynamic Programming (canoe rental, rod cutting)	14.1	14.1-2, 14.1-3, 14.1-6, 14-4, 14-11	6.1, 6.2
Oct 19	Two-dimensional Dynamic Programming	14.2-14.4	14.2-1, 14.2-3, 14.3-3, 14.3-4, 14-2	6.3, 6.4, 6.5
Oct 21	Examples of dynamic programming		14.4-1, 14.4-5, 14.9	6.6
Oct 26	All pairs shortest paths, including Floyd-Warshall algorithm	23.1, 23.2	23.1-3, 23.1-7, 23.1-8, 23.2-4, 23.2-5	pp.172-173
Oct 28	Greedy algorithms	15.1, 15.2	15.1-2, 15.1-3, 15.1-4, 15.2-1, 15.2-4, 15.2-5
Nov 2	Greedy algorithms, continued	15.3, 15.4	15.4-1, 15.4-2, 15-2
Nov 4	Graphs	22.0		3.1
Nov 4	Minimum Spanning Trees: Kruskal's Algorithm, Prim's algorithm	20.1, 21	21.1-1, 21.1-6, 21.1-7, 21.2-2, 21.2-4, 21.2-5	5.1 up to 5.1.3, 5.1.5
Nov 9	Single-source shortest paths using Dijkstra's algorithm	22.0, 22.3	22.3-2, 22.3-3, 22.3-5, 22.3-7, 22.3-9	4.3, 4.4, review 4.5
Nov 11	Graph Algorithms	20.1, 20.2	20.1-1 to 20.1-6, 20.1-8, 20.2-2, 20.2-4, 20.2-6, 20.2-7	4.1, 4.2
Nov 16	Graph Algorithm	20.3, 20.4	20.3-1, 20.3-2, 20.3-4, 20.3-7, 20.3-8, 20.3-10, 20.3-11, 20.4-2, 20.4-3, 20.4-5	3.2,3.3
Nov 18	Strongly connected components	20.5	20.5-1, 20.5-3, 20.5-7	3.4
Nov 23	Maximum Flow	24.1, 24.2	24.1-2, 24.1-6, 24.1-7, 24.2-2, 24-1
Nov 25	Examples of solving problems using graph algorithms
Nov 30	Quick introduction to linear progrmming	29.0-29.2	29.1-1, 29.1-3, 29.1-5, 29.1-6, 29.1-7, 29.1-8, 29.2-2, 29.2-5	7.1, 7.3
Dec 2	Brief introduction to NP-completeness	34.0-34.3	34.1-1, 34.1-5	8.1, 8.2

Course Documents

Mathematical prerequisites
Some review questions on mathematical prerequisites (not to be handed in)
exercises on loop invariants (Earlier, there was a typo in the code for P2(x): the variable p should have been d. It is now corrected.)
exercises on recursive algorithms
exercises on sorting and 1-d dynamic programming
Sample Test 1, Sample Test 2, Sample Exam from a previous year.
exercises on multi-dimensional dynamic programming
exercises on greedy algorithms

Updated November 1, 2026

EECS 3101B: Design and Analysis of Algorithms Fall 2026