EECS 3101, Winter 2018

EECS 3101: Design and Analysis of Algorithms
Winter 2018

Web page contents:

General Information
Important Dates
Course Handouts

General Information

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] (Please use a York email account when sending me email, and start your subject line with "[3101]".)
Professor's Office Hours: Since the regular term is over, office hours are by appointment.

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.

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

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

Marking Scheme

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.


Important Dates

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 gradeFriday, 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



Optional Supplementary Reading

Other References

Web Links


This section will be filled in as the term progresses. Don't fall behind with your reading.

DateTopics 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 Introduction 1; optional supplementary reading: Boyer-Moore algorithm 1-1
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 Sorting 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

Course Handouts

Remediation Material Solutions to assignments will be handed out in class on the day they are due.

Updated October 18, 2018