EECS 4171, Fall 2025
EECS 4171: Advanced Algorithms (Parallel and Concurrent Algorithms)
Fall 2025
Web page contents:
General Information
Announcements
Important Dates
Resources
Reading
Course Handouts
General Information
Instructor: Eric Ruppert
Office: Room 3052 of the Lassonde Building
Telephone: (416) 736-2100 ext. 33948
Email: eruppert (a) yorku.ca (Please use a York email account when sending me email, and start your subject line with "[4171]".)
Lectures: Mondays and Wednesdays 14:30-15:50 in room 107 of the Life Sciences Building.
Professor's Office Hours: To be announced
Learning Outcomes
In this course, you are invited to further develop your abilities in designing and analyzing algorithms. This includes reasoning about algorithms and discussing them in a precise way. The particular focus of the course this year will be on parallel/concurrent algorithms. With the ubiquity of multicore machines and networked systems, it is increasingly important for computer scientists to unerstand concurrency.
The adjectives concurrent, parallel and distributed are often used with overlapping meanings. In all cases, there are multiple processes running at the same time and communicating with one another in order to be able to perform their tasks. The communication may be through a shared memory or by messages passed between processes. The processes may be synchronous or asynchronous or even prone to failures. We will look at a variety of settings in this course.
By the end of this course, you will be able to do the following things.
-
Describe concurrent algorithms precisely, for example using pseudocode, and choose an appropriate one to solve a problem.
Before trying to design your own concurrent algorithms, it is helpful be aware of existing algorithms and the techniques that they use.
-
Design concurrent algorithms, either by combining existing building blocks or from scratch.
Concurrent algorithms can often be more challenging to design than sequential algorithms, particularly when there is an element of non-determinism in how the algorithms are executed. For example, if processes are asynchronous, a scheduler determines how the steps of the processes are interleaved, and the algorithm must be correct in all possible interleavings.
-
Argue about the correctness of concurrent algorithms.
The aforementioned difficulty of designing concurrent algorithms also makes it harder to avoid bugs. So, it is even more important to be able to reason formally about correctness.
-
Quantify resource usage of concurrent algorithms.
When multiple algorithms solve the same problem, choosing the one that solves the problem most efficiently requires understanding the resources used by each algorithm. The measures used for concurrent algorithms are somewhat different than the ones used for traditional sequential algorithms.
-
Understand important themes in concurrent computing, such as synchrony, race conditions, fault-tolerance.
We will see that some common themes appear repeatedly in different contexts, so understanding them wil help see how algorithms can be used or designed for new settings.
Academic Honesty
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 use course materials 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 or using AI tools (such as LLM-based software), 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 data structures on your own.
Furthermore, AI tools and the web will not be available during your exam (or during your job interviews), 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 is unpleasant for everyone. 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 senate
policy
on academic honesty and the faculty's academic integrity resources.
Marking Scheme
To be determined.
Announcements
Important Dates
| First class | Wedneday, September 3 |
| Reading week (no classes) | October 13-17 |
| Last date to drop course without receiving a grade | Tuesday, November 4 |
| Last class | Monday, December 1 |
| Last date to withdraw from course (receiving W on transcript) | Tuesday, December 2 |
| Exam period | December 4-19 |
Resources
Textbook
- Course kit will be available from York Bookstore.
Other References
Reading
To be filled in.
Course Handouts
Updated July 9, 2025