Web page contents:

General Information

Learning Outcomes

• 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

Although you may discuss the general approach to solving an assignment 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 algorithms 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

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. 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.

Announcements

• (Sep 10) The department is holding a series of sessions to prepare students for the International Collegiate Programming Contest on Tuesdays from 15:00-17:00 in BRG 211. These contests are a great way to hone your programming skills, and they are also fun. For more information, contact Professor Allin.
• (Sep 4) The Fields Institute downtown is holding a celebration later this month for Mark Braverman, who won the prestigious Abacus Medal for contributions to theoretical computer science in 2022. This includes a public lecture on Sep 23 and a Student Night on Sep 24 for undergraduates. Follow the links to register for free tickets.

Important Dates

First class	Wedneday, September 3
Test 1	Monday, September 29
Reading week (no classes)	October 13-17
Test 2	Monday, October 27
Last date to drop course without receiving a grade	Tuesday, November 4
Test 3	Wednesday, November 26
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

• A course kit containing readings is available from York Bookstore. The expected cost is $115. A copy of the kit will be placed on reserve at the Steacie Library.

Other References

• To be filled in.

Reading

Course Handouts

• Assignment 1 typo in part (e): x^{d-2} should be x^{d-1}
• Assignment 2

Updated September 12, 2025