CSE 3101, Winter 2012

CSE 3101: Design and Analysis of Algorithms
Winter 2012

Web page contents:

General Information
Announcements
Important Dates
Resources
Reading
Course Handouts

General Information

Instructor: Eric Ruppert
Office: Room 3042 of the Lassonde Building (formerly known as the Computer Science and Engineeering Building)
Telephone: (416) 736-2100 ext. 33979
Facsimile: (416) 736-5872
Lectures: Mondays and Wednesdays, 11:30-13:00 in room 0005 of the Technology Enhanced Learning (TEL) 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: Mondays 13:00-14:00, Wednesdays 15:00-16:00 in Lassonde 3042
TA's office Hours: Wednesdays 13:00-14:00 (ACE 004)

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	15%
Test #1	20%
Test #2	20%
Exam	45%

Announcements

(Feb 9) Tomorrow's office hour has been moved to room 2013 of the (Lassonde) CSE Building.
(Feb 1) If you missed today's test, there is a copy of it posted below. I suggest you print it out, write it under test conditions (closed book, limited time) and hand it in. I will mark it so that you can get feedback on how you are doing (but of course it will not count for credit).
(Feb 1) Since I will be away next week, I posted both assignment 5 and assignment 6 below. Assignment 5 will be due two days later than usual (i.e., on Feb 15 instead of Feb 13). Assignment 6 is due after reading week.
(Jan 31) The test tomorrow will be held in two different rooms. Students with surnames that begin with letters A-L will write in ACE (Accolade East) 005 and students with surnames M-Z will write in TEL 0005 (the usual lecture room).
(Jan 30) I will be away at a workshop for the week of February 6. A guest lecturer will present the lectures that week. My office hours will be cancelled on Feb 6 and Feb 8, but I have scheduled additional TA office hours on Monday, Feb 6 at 3pm in Lassonde (CSEB) 2002 and on Friday, Feb 10 at 10am in Lassonde (CSEB) 2013. The tutorial at 1pm on Wednesday, Feb 8 will go on as usual in ACE 004. I will check email while I'm away, but maybe not as often as usual.
(Jan 28) I may find a bigger room for the test on Wednesday. Check back here for an announcement of the location. There are no aids allowed for the test, but I will print the Master Theorem on the test, so you do not have to memorize it. After the test there will not be a tutorial on February 1 at 1pm (but I will have my office hour at 3pm).
(Jan 19) The multiplication algorithm we did in class yesterday was discovered in 1960 by A.A. Karatsuba (1937-2008). He wrote about his discovery in this article. He mentions that the standard O(n^2) algorithm (in binary!) was already used by Egyptians around 2000 B.C., so his algorithm was the first improved multiplication algorithm in 4000 years, and it took him one week to discover it. Here is the bound on its running time
(Jan 18) Starting on January 25, tutorials will be on Wednesdays at 1pm in ACE 004. (The Registrar's office double-booked the room that the tutorial was supposed to be in today, probably because they use room-booking software written by people who don't know how to the prove correctness of algorithms. Sorry for any inconvenience if you had trouble finding the tutorial today.) (Jan 15) The NSERC Undergraduate Student Research Awards provide funding for undergraduate students to spend the summer doing research with a professor. Applications are due soon. There will be an information session on January 20 at 10:30 in CSEB 3033. For more information, see this link.
(Jan 11) Here are some notes for the material covered in the first two lectures.
(Jan 10) I added a link above to a list of frequently asked questions about the course.
(Jan 5) There was a typo in assignment 1. The two ≥ signs inside the loop are supposed to be > signs. A corrected version of the assignment has now been posted.
(Jan 4) The first homework assignment has been posted below.

Important Dates

First class	Wednesday, January 4
Test #1 (see Jan 31 announcement for location)	Wednesday, February 1
Reading Week (no classes)	February 20-24
Last date to drop course without receiving a grade	Friday, March 9
Test #2	Monday, March 12
Last class	Monday, Apr 2
Exam period	April 4-20

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. If you have a copy of the 2nd edition, that should be fine, but note that some of the chapter and section numbers will be different from the ones I post.

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

Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
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, Addison-Wesley, 2003.
Steven S. Skiena, The Algorithm Design Manual, 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 (3rd edition), Wiley, 2002.

Web Links

Algorithmics Animation Workshop
links to web pages on theoretical computer science
web page of this course the last time I taught it.

Reading

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

Week	Topics	Reading in CLRS (3rd ed)	Suggested questions, mostly from CLRS (3rd ed)
prereq	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
Jan 2	Introduction	1	1-1
Jan 9	Proving correctness of loops	2.1, 2.2, notes	2.1-3, 2.1-4, 2.2-2, 2-2, 2-3; see also chapter 5.1 of Parberry's book
Jan 16	Proving correctness of recursive algorithms, divide and conquer	2.3, 31.2 (up to Lame's Theorem), 4.0, 4.1, a time bound	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
Jan 23	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
Jan 30	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
Feb 6	Sorting	pages 147-211 (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, 8.1-1, 8.2-4, 8.3-1, 8.3-2, 8.3-3, 8.3-4, 8.4-4, 8-4

Course Handouts

Mathematical prerequisites
Some review questions on mathematical prerequisites (not to be handed in)
Declaration to be completed before working on Assignment 1
Assignment 1 (corrected version; see Jan 5 announcement)
Assignment 2
Assignment 3
Some notes on recurrences from CSE1019. Pages 1-5 and 21-27 are the most relevant for this course.
Assignment 4
Assignment 5 (Note that it is due two days later than usual.)
Assignment 6
Test 1

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

Updated February 1, 2012

CSE 3101: Design and Analysis of Algorithms Winter 2012