EECS 3101: Design and Analysis of Algorithms

EECS 3101: Design and Analysis of Algorithms
Fall 2017

General Information

Instructor: Suprakash Datta
Office: CSEB, room 3043
Telephone: (416) 736-2100 ext. 77875
Facsimile: (416) 736-5872
Lectures: MW 4 - 5:30 pm in DB 001 (Formerly TEL building)
Tutorial: Thurs 4 - 5:30 pm in DB 001 (Formerly TEL building)
Office Hours : Wed 2-3:30 pm, Thu 1:30-2:30 pm, or by appointment
Email: [lastname]@cse.yorku.ca (To the extent possible, please use your yorku account when sending me email.)
TA:

News:

Hw4 and final grades are online.
HW 3, final examination marks are on ePost.
HW 2 marks are on ePost.
Test 3 marks are on ePost.
Do not do the second part of Q2 in assignment 4. Also, please complete the online class evaluations.
Test 2 marks are on ePost. Tests will be available on Monday.
Office hours for Nov 22 are being moved to 1:30 pm - 3:30 pm Nov 24.
Assignment 3 is due on Monday before class. For q2, you can assume that the n pieces listed need not be rearranged, i.e., if the pieces are 3,5,12, then cuts are made at locations 3,8 on the rod and the algorithm determines the order in which these cuts are made.
Sample questions for test 2 are online.
Office hours in Oct 26, Thursday, 11:30-12:30 instead of the usual time (1:30-2:30).
Hw 2 can be handed in up to 12 noon Friday 27th Oct in the dropbox. Note that Thursday and Friday are reading days (no classes) so you are welcome to hand it in before that.
Hw 1 and Test 1 marks are online.
The second test is postponed from Nov 1 to Nov 2.
Solutions to test 1 are online.
I will have extra office hours Fri Oct 6, 1 pm - 5 pm. Solutions to the sample midterm are online (see below).
Solutions to tutorial 3 are online. A sample midterm is published (see below). Note that it was a 2 hour test and had a larger syllabus.
HW 1 and Solutions to tutorial 2 are online. My office hours for this week will be Sept 27 1- 2:30 pm and 12 noon-2 pm on Sept 28. This is to make up for last week as well as work around meetings I have. These times are only for this week.
There will be NO office hours on Sept 21, due to an unforeseen contingency. I will hold extra office hours next week.
There is no tutorial Sept 7.

Assignments

Assignment 1. Solutions are here.
Assignment 2. Solutions are here.
Assignment 3. Solutions are here.
Assignment 4. Solutions are here.

Tutorials

Tutorial 1, Sept 14: We covered sums (sum of the first n positive integers, sum of the squares of the first n positive integers), Induction examples and definitions of graphs. Some relevant slides (not used in tutorial 1) are here.
Tutorial 2, Sept 21: The session will be run by a TA, Abdullah Sawas. He will cover problems in time complexity (run-time analysis) of algorithms. The problems are here. Solutions to the questions are here.
Tutorial 3, Sept 28: We will cover problems in proving correctness of algorithms with loop invariants. Solutions to the questions are here.
Tutorial 4, Oct 5: We will cover problems in proving correctness of algorithms with loop invariants as well as solving recurrences. The questions are here. Solutions are here.
Tutorial 5, Oct 12: We studied solutions to test 1 problems and recurrences with full history.
Tutorial 6, Oct 19: The questions are here.
Tutorial 7, Nov 9: Dynamic programming examples. The questions are here.
Tutorial 8, Nov 16: Dynamic programming and greedy algorithm examples. The questions are here.
Tutorial 9, Nov 23: We went over the sample questions fot test 3.

Lecture schedule

Notes
1. on the use of slides: I would much rather that you listened actively and understood concepts at real time than take notes in class for later use. Ideally, I would like you to read the slides after class and identify concepts that you did not understand and ask questions about them in the next class.

Sep 11: Administrivia. Introduction to algorithm analysis. My slides are here. We covered the first 15 slides.
Sep 13: Introduction to algorithm analysis - contd. We covered slides 16 through 30.
Sep 18: Introduction to algorithm analysis - contd. The next set of slides are here.
Sep 20: Introduction to algorithm analysis - contd. The next set of slides are here.
Sep 25: Introduction to algorithm analysis - proving correctness contd. The next set of slides are here.
Sep 27: The divide and conquer design paradigm. My slides are here.
Oct 2: The divide and conquer design paradigm - Continued. No new slides.
Oct 4: Solving recurrences. No new slides.
Oct 9: Holiday
Oct 11: Test 1
Oct 16: Sorting algorithms - heapsort. My slides are here.
Oct 18: Sorting algorithms - quicksort, priority queues.
Oct 23: Lower bounds. My slides are here.
Oct 25: Lower bounds. Linear Time sorting. My slides are here.
Oct 30: Linear time sorting. The median algorithm.
Nov 1: Dynamic programming. My slides are here.
Nov 6: Dynamic programming. No new slides.
Nov 8: Dynamic programming. No new slides.
Nov 13: Finish Dynamic programming.
Nov 15: Greedy algorithms. My slides are here.
Nov 20: Greedy algorithms.
Nov 22: Graph Algorithms. MST (Ch 23). My slides are here.
Nov 29: Graph Algorithms. MST (Ch 23). Prim's algorithm.
Nov 30: Graph Algorithms.Kruskal's algorithm. BFS, DFS.
Dec 4: Shortest Path Algorithms. My slides are here. We did not cover any material after slide 21 and so you are not required to know topics after slide 21 for the final examination.

Course summary:

The list of topics we will try to cover includes the following. The Section numbers refer to the required text.

Mathematical background (asymptotic notation, recurrence relations, bounding sums, induction, etc.) [Ch 1, 2.2, 3, 4]
Proofs of correctness, including loop invariants [Ch 2]
Recursive algorithms; divide and conquer technique [Ch 2.3, 4]
Sorting algorithms and lower bounds [Ch 6,7,8]
Selection [Ch 9]
Greedy algorithms [Ch 16]
Dynamic programming [Ch 15]
Graph algorithms (searching, spanning trees, shortest path, etc.) [Ch 22,23,24,25,26]
(If time permits) A brief introduction to NP-completeness. [Ch 34]

Relevant chapters: 1,2,3,4,6,7,8,9,15,16,22,23,24,25,26,34,Appendix A,B.

Enrollment

Enrollment in EECS 3101 is managed by the Computer Science Undergraduate Office (UGO) (operating hours posted on the door). Please note that your professor will not be able to enroll you.

Textbook (required)

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 problems and known errata, follow this link. This book will be carried by the University Bookstore

Optional Supplementary Reading

Jeff Edmonds, How to Think About Algorithms.
Ian Parberry's book, Problems on Algorithms, is a terrific source for practice problems on many topics covered in this course. Solutions to selected problems are also given. Follow this link to access the book.

Other References

Daniel Solow, How to Read and Do Proofs (3rd edition), Wiley, 2002.
Gilles Brassard and Paul Bratley, Fundamentals of Algorithmics, Prentice Hall, 1996.
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.
Robert Sedgewick, Algorithms (2nd edition), Addison-Wesley, 1988.
Other references may be added later.

Course policies:

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.
Missed tests: If you miss a test or the final due to medical reasons you are required to contact the instructor within 7 days of the scheduled exam with documentation. York University has a new form that your doctor should fill out. You can download it by clicking here.
If you miss an assignment or test the weight will be transferred to the final. If you miss the final, you have to get the instructor to sign a deferred standing agreement within 7 days of the scheduled exam (the instructor has the right to refuse to agree, and in that case the student can petition to take the deferred examination). The department will arrange for a deferred examination at the beginning of the following term.

Important Dates:

Sep 11: First class
Drop deadline (drop without receiving a grade): Nov 10
Dec 4: Last class
Holidays : Oct 9.
Finals: scheduled by the registrar's office during Dec 6-21.

Grades

Assignments: 20%, We will try to have at least 5 short assignments.
Test 1 (10%): Oct 11, in class. Syllabus: everything covered upto, and including, Oct 4. A sample test is here. The solutions are here.
Solutions to test 1 are version 1 and version 2.
Test 2 (10%): Nov 2, in class. Syllabus: Divide and Conquer, Solving recurrences, comparison-based sorting algorithms, lower bounds. Linear time sorting, loop invariants will not be tested.
Some sample questions are here. The solutions are here.
Solutions to test 2 are version 1 and version 2.
Test 3 (10%): Nov 27, in class. Syllabus: Linear time sorting, medians and order statistics (1 question), Dynamic programming (1 question), greedy algorithms (1 question).
Ch 8, Ch 9 (ignore 9.2), Ch 15 (ignore 15.5), Ch 16.1, 16.2, 16.3.
Some sample questions are here. The solutions are here.
Solutions to test 3 are version 1 and version 2.
Final Exam: 50%, scheduled by the registrar -- Sat, 16 Dec 2017, 14:00-17:00 hours, TM Tait.
Syllabus: Everything covered in the course. An old final is here.
The final is out of 70 points, of which 13 points are from dynamic programming and greedy algorithms, 13 points from graph algorithms, 6 points on proving algoritms correct using loop invariants, 10 points from algorithm analysis, 16 on sorting and searching, the rest on lower bounds, recursion, and basic algorithms and data structures.

NOTE: Grades will be available on ePost. Please use your CSE id/password after clicking here to access your grades.