Web page contents:

General Information

Learning Outcomes

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

Academic Honesty

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 guidelines on academic honesty.

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

Announcements

• (Apr 7) I have booked a room for a session prior to the exam where you can come and ask any questions about the course, and hear my answers to other students. It will be in room 120 of the Chemistry Building at 13:00 on April 20.
• (Apr 2) There was an error on the solutions I handed out for Test 2, Question 3(d): I forgot to include the Θ(n log n) time to build the BST for Available, so the total running time should be Θ((n+m)log n).
• (Mar 29) Please fill out a course evaluation at this link until April 11. If more than 80 per cent of the class fill them out, I will drop your lowest assignment when computing final grades.
• (Mar 14) There will be no tutorial on March 17. (Instead, I will schedule a review session during in the days before the final exam.)
• (Feb 15) On Feb 17, there will be a lecture instead of a tutorial, and there will be no lecture on Feb 27.
• (Feb 1) You can bring one 8.5x11-inch sheet of paper with handwritten notes on both sides into Test 1.
• (Jan 23) My office hour on Wed, Jan 25 will be cancelled. Instead, I will be available on Thu, Jan 27 from 12:00 to 13:00.

Important Dates

First class	Monday, January 9
Quiz	Friday, January 27
Test 1	Friday, February 10
Reading week (no classes)	February 20-24
Last date to drop course without receiving a grade	Friday, March 17
Test 2	Wednesday, March 22
Good Friday (no class)	Friday, April 7
Last class	Monday, April 10 (Friday schedule)
Last date to withdraw from course (receiving W on transcript)	Monday, April 10
Exam period	April 12-27

Resources

Textbook

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 4th edition, MIT Press, 2022. 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

• 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 this link to access the book.

Other References

• 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), 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

Course Documents

• Mathematical prerequisites
• Some review questions on mathematical prerequisites (not to be handed in)
• Assignment 1
• Assignment 2
• Assignment 3
• Sample Test 1 from a previous year
• Assignment 4
• Assignment 5
• Assignment 6
• Assignment 7
• Sample Test 2 from a previous year
• Assignment 8
• Assignment 9
• Sample exam from a previous year
• Assignment 10

Updated April 7, 2023