EECS 3101, Fall 2015

EECS 3101: Design and Analysis of Algorithms
Fall 2015

Web page contents:

General Information
Announcements
Important Dates
Resources
Reading
Course Handouts

General Information

Instructor: Eric Ruppert
Office: Room 3042 of the Lassonde Building
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Lectures: Mondays and Wednesdays, 16:00-17:30 in room 115 of the Chemistry Building
Tutorials: Thursdays, 16:00-17:30 in room 115 of the Chemistry Building
Email: [my last name]@cse.yorku.ca (Please use a York email account when sending me email, and start your subject line with "[3101]".)
Professor's Office Hours: Since the course is over, there will be no more office hours.

Here is a list of frequently asked questions about the course.

Academic Honesty

It is important that you look at the departmental guidelines on academic honesty.

Although you may discuss the general approach to solving a 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.

Marking Scheme

Homework exercises	10%
Quiz	5%
Test #1	20%
Test #2	20%
Exam	45%

Announcements

(December 28) UNOFFICIAL final grades have now been posted. (They will not become official until they are approved by the department.) You may check all of the grades that I have recorded for you by logging into a departmental machine and using the command "courseInfo 3101 2015-16 F". If you wish to view your exam, you can drop by my office at the beginning of the winter term. (If you want to be sure that I will be there, you can send me email to set up an appointment.) Happy new year.
(December 4) Office hours between now and the exam:
- Mon Dec 7 14:30-15:30
- Wed Dec 9 14:30-15:30 (note no office hour on Dec 10)
- Mon Dec 14 14:30-15:30
- Tue Dec 15 15:00-16:00 in Lassonde 2013 (TA)
- Wed Dec 16 15:00-16:00 in Lassonde 2013 (TA)
- Thu Dec 17 14:30-15:30
- Fri Dec 18 14:00-16:00 review session Bethune College 215; bring all remaining questions
(December 2) The deadline for assignment 11 has been postponed to 4:00p.m. on December 7.
(December 1) In assignment 11, question 1, the desired departure time in the input should be treated as the earliest possible time the passenger can depart. So, the result should be the earliest possible arrival time in the destination city, among all itineraries that leave the starting city at or after the desired departure time.
(November 28) My office hour on Thursday, December 3 will be held from 12:30-13:30 instead of the usual time.
(November 27) As decided in yesterday's class, there will be a bonus quiz in the tutorial on Thursday, December 3 covering dynamic programming and greedy algorithms.
(November 27) The last assignment has been posted below.
(November 14) Extra TA office hours will be held in Lassonde 2013 on Tuesday November 17 from 15:00 to 16:00 and on Thursday November 19 from 9:00 to 10:00.
(November 9) My office hour on Thursday, November 12 will be from 12:30 to 13:30 instead of the usual time.
(November 4) For Assignment 7, parts (b),(c) and (d): I mean what value should be assigned to these array entries (0 or 1)?
(October 31) You can check my records of your grades by logging into a departmental machine and typing "courseInfo 3101". (See this link for information about logging into departmental machines remotely.)
(October 28) There will be no office hour on October 29.
(October 21) Since Thursday October 29 is a reading day, there will be no homework assignment due that day. Thus, Assignment 7 will be due on November 5. (You get a break for one week, but use it to do lots of exercises on your own!)
(October 13) Office hours this week:
- Tue Oct 13 15:00-16:00 in Lassonde 2013 (TA)
- Wed Oct 14 13:00-14:00 in Lassonde 2013 (TA)
- Wed Oct 14 14:30-15:30 in Lassonde 3042
- Thu Oct 15 13:00-14:00 in Lassonde 3042 (note unusual time)
(October 5) There is a nice article by Aviv Zohar in the September issue of CACM about how bitcoin works. It shows the importance of understanding running times of algorithms. (If you access this link on a computer at school, you should be able to download the pdf version. Otherwise, you can get it via York's Library; search for "Communications of the ACM" and go to the September 2015 issue.)
(October 5) In assignment 4, question 3, the ≤ symbol in the definition of T(n) should be an = sign.
(September 28) The quiz on October 1 will be held in CLH C.
(September 22) Programming contests continue on Fridays from 16:30-18:30. See this link for details.
(September 22) For assignment 2, part (c) should refer to the proof in part (d) (not part (c)), and part (d) should refer to the algorithm in part (c) (not part (b)).
(September 15) The Boyer-Moore Majority algorithm that we discussed in the September 14 lecture is described on this page
(September 11) There will be an extra-curricular programming contest on September 18 from 16:30 to 18:30 in Lassonde 1004. These contests are a good way to reinforce the algorithm skills that you learn in this course. Follow this link for details.
(August 6) The first tutorial on September 10 will be used to review some prerequisite material for the course.

Important Dates

First class	Thursday, September 10
Quiz in CLH C	Thursday, October 1
Thanksgiving Day (no class)	Monday, October 12
Test 1 in CLH C	Thursday, October 15
Reading Day (no class)	Thursday, October 29
Last date to drop course without receiving a grade	Monday, November 9
Test 2 in CLH C	Thursday, November 19
Bonus quiz	Thursday, December 3
Last class	Monday, December 7
Exam period	December 9-23

Resources

Textbook

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, 3rd edition, MIT Press & McGraw-Hill, 2009. For solutions to some of the textbook's exercises and known bugs in the text, see the textbook's web page. 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 different 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 will be filled in as the term progresses. Don't fall behind with your reading.

Date	Topics	Reading in CLRS (3rd ed)	Suggested questions, mostly from CLRS (3rd ed)
September 10	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
September 14	Introduction	1	1-1
September 16	Proving correctness of recursive algorithms, divide and conquer	2.3, 31.2 (up to Lame's Theorem), 4.0, 4.1	2-1, 31.2-4, 31.2-8, 4.1-1, 4.1-5; see also chapter 5.2 and 7 of Parberry's book
September 23	Proving correctness of loops	2.1, 2.2	2.1-3, 2.1-4, 2.2-2, 2-2, 2-3; see also chapter 5.1 of Parberry's book
October 5	More divide and conquer, analysing running time of recursive algorithms	4.2-4.5, 33.4, skim 4.6	2.3-3, 2.3-4, 2.3-6, 2.3-7, 4.2-3, 4.2-7, 4.3-1, 4.3-6, 4.4-2, 4.5-1, 4.5-4, 4-1, 4-2, 33.4-1, ; see also chapter 4 of Parberry's book
October 14	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
October 19	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
October 21	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
October 26	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 (in linear time), 15-5, 15-6, 15-9, 15-10, 15-11
November 9	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
November 11	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,
November 18	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
November 30	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
December 2	NP-completeness	34.0-34.2	34.1-1, 34.1-5

Course Handouts

Mathematical prerequisites
Some review questions on mathematical prerequisites (not to be handed in)
Declaration to be completed before working on Assignment 1
If you missed the September 10 tutorial, here are some rough notes on what we did.
Notes on binary search
Sample test 1 from the last time I taught this course.
Sample Test 2
A sample EECS3101 exam from a previous year

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

Updated December 28, 2015

EECS 3101: Design and Analysis of Algorithms Fall 2015