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: No more office hours for this course.
TA's office Hours: No more office hours for this course.

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

(Apr 19) UNOFFICAL course grades have now been posted. I made a small (upward) adjustment when calculating final grades. You can check your grades with the command "courseInfo 3101 2011-12 W" on a departmental unix machine. You may view your exam in my office for the next little while: email me to make an appointment or just drop by when I'm there. (I'll be away from April 25 to May 2.)
(Apr 11) If there is a strike by CUPE 3903, the CSE3101 exam will still proceed as scheduled. (However, note that it might take extra time to get to campus if there are picket lines, so make sure you leave enough time to get to the exam on time.)
(Mar 28) I will continue having office hours at the regular times up until the exam. In addition, my office hour on Apr 9 will be extra long (1pm to 3pm) and there will be an exam review session in Lassonde 3033 on Apr 11 from 11am to 1pm (bring questions).
(Mar 28) You are allowed to bring one 8.5 x 11 inch sheet of handwritten notes (both sides) into the exam.
(Mar 28) Today's tutorial is cancelled because the TA is ill. I still have my office hour this afternoon if you need extra help.
(Mar 22) Trevor Brown was a student who took this course the last time I taught it. For fun, he created a web page with pointers to several hundred algorithmic problems, and he wrote hints and full solutions in C++ for all of them. It's a handy source of practice problems to look at as you prepare for the exam. (If you solve as many problems as he did, you are pretty much guaranteed to do well.)
(Mar 14) There was a mistake in my solution to part (c) of assignment 7. I wasn't clear about exactly how to change the algorithm for the new denominations 1, 3 and 5. If you change the algorithm of part (a) just by changing occurrences of 1, 5 and 10 to 1, 3 and 5, respectively, then it does work for n=5. However, it does not output an optimal solution for n=8. (The algorithm will output 1,1,3,3 but the optimal solution is 3,5.)
(Mar 13) You are invited to attend Poster Day on March 30 from 11:30 to 2:00 p.m. in the foyer of the Lassonde (CSE) Building and the reception following from 2:30 to 4:00 in Lassonde 3033. Graduate students in our department will be presenting posters describing their research. The graduate programme assistant will be there to answer any questions you might have about graduate school.
(Mar 7) You can use "courseInfo 3101" to check your grades on all work that you have submitted up to this point.
(Feb 27) The class voted today to change the date of Test #2 to March 14.
(Feb 22) The make-up test (see Feb 15 announcement below) will be on Saturday, March 3 from 11:00 am to 12:30 pm in TEL0001.
(Feb 19) The university is closed on Monday Feb 20, so there will be no office hour. I will have my usual office hour on Wednesday and an extra one on Friday at 2pm. You can also send me email if you want to see me at another time for extra help. Because of reading week, Wednesday's tutorial will not be held on Feb 22.
(Feb 17) You can check your course grades by typing "courseInfo 3101" on a departmental unix machine.
(Feb 15) The class average on Test 1 was quite low. I've decided to give you a second chance to learn this material. There will be a makeup test, which will cover the same material (i.e., material from the Jan 4 to Jan 27 lectures). When calculating your final grade, I will use max(your grade on Test 1, your grade on the makeup test) as the 20% that was allocated to Test 1. The tentative date for the makeup test is Saturday, March 3. (I'll post the exact time and location when I have been able to book a room for it.) In the meantime, reading week is a good time to put some extra effort into this course. Please use that extra time well! PRACTICE on LOTS of problems. Come talk to me if you're having trouble with any material in the course. I want every student to do better on the makeup test than on the original one.
(Feb 13) Clarification for Assignment 5, part (a): Some students have asked about the notation

max ( T(x, floor(k/2)) + T(n-x, ceiling(k/2)) + cn).
0 ≤ x ≤ n

This just means that you should substitute every (integer) value of x in the range 0..n into the expression in the brackets and choose the maximum value that you get. In other words, it is the maximum element in the set
{T(x, floor(k/2)) + T(n-x, ceiling(k/2)) + cn) : 0 ≤ x ≤ n}.
Note also that your argument in part (a) should work for every possible choice of the constant c. (So, given any constant c, you have to be able to find a constant d that makes your proof work.)
Further hint for part (b). Let T(n,k) be the worst case running time of CHOOSE(A[1..n],b,k). You should design your algorithm CHOOSE so that T(n,k) satisfies the recurrence in part (a). Then, you will know that the running time is O(nlog k). Think about how a divide-and-conquer algorithm would look if it has a running time described by the recurrence of part (a).
(Feb 10) There is a typo in the solutions for assignment 4: in the second solution to part (a), the definitions of b and c are reversed.
(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
Make-up test	Sat, March 3, 11:00 in TEL0001
Last date to drop course without receiving a grade	Friday, March 9
Test #2	Wednesday, March 14
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
Pa Kettle demonstrates 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.

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-189, Section 8.2, 8.3, 8.4 (a lot of this will be a review), Prof. Datta's slides for Monday and Wednesday	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.2-4, 8.3-1, 8.3-2, 8.3-3, 8.3-4, 8.4-4
Feb 13	Sorting lower bound, Greedy Algorithms	8.1, 16.1, 16.2	8.1-1, 8-4, 16.1-2, 16.1-3, 16.1-4, 16.2-1, 16.2-3, 16.2-5, 16.2-7
Feb 27	Greedy Algorithms, including MST algorithms	16.3, 23	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
March 5	Dynamic Programming	21.1-21.2 (for implementation of Prim's algorithm), 15.1-15.3	21.1-3, 21.2-2, 21.2-5, 21.2-6, 15.1-1 to 15.1-5, 15.2-2, 15.2-6, 15.3-2 to 15.3-6
March 12	Dynamic Programming	15.4, 15.5	15.4-2, 15.4-5, 15-2 (in linear time), 15-5, 15-6, 15-9, 15-10, 15-11
March 19	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
March 26	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, Exercises from Chapter 24 TBA

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
Assignment 7
Assignment 8
Assignment 9
Assignment 10 (last one!)

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

Updated April 19, 2012

CSE 3101: Design and Analysis of Algorithms Winter 2012