EECS 3101A: Design and Analysis of Algorithms

EECS 3101: Design and Analysis of Algorithms
Fall 2019

General Information

Instructor: Suprakash Datta
Office: LAS, room 3043
Telephone: (416) 736-2100 ext. 77875
Lectures: Tue, Thu 8:30 - 10 am in R S137
Tutorial: Mon 8:30 - 10 am in LSB 105
Office Hours : Tuesday, Thursday: 10 - 11 am, or by appointment
Email: [lastname]@cse.yorku.ca (To the extent possible, please use your yorku account when sending me email.)
TA:

News:

Please note the change in office hours.
There will be a Moodle page for this course but it has not been set up yet by UIT.
Welcome to EECS 3101A!

Assignments

Assignment 1 released on Moodle on Sept 19.
Assignment 2 released on Moodle on Oct 11.
Assignment 3 released on Moodle on Nov 11.
Assignment 4 released on Moodle on Nov 27.

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 5: Administrivia. Introduction to Algorithms. My slides.
Sep 10: Finish previous set. Start proving correctness of algorithms. My slides.
Sep 12: Algorithm correctness continued.
Sep 17: Algorithm correctness continued.
Sep 19: Finish algorithm correctness. My slides. We covered the first 7 slides on Sept 19.
Sept 24: Algorithm Analysis examples. My slides.
Sept 26: Start divide and conquer.
Oct 1: Test 1
Oct 3: Solving recurrences. My slides.
Oct 8: More sorting algorithms. My slides.
Oct 10: Finish quicksort from the last set of slides. Start Lower Bounds. My slides.
Oct 22: Linear sorting algorithms. My slides. We did not finish radix sort.
Oct 24: Finish radix sort. Start Median and Order Statistics. My slides.
Oct 29: Test 2
Oct 31: Finish Median and Order Statistics. Start Dynamic Programming. My slides.
Nov 5: DP continued. My slides.
Nov 7: DP continued.
Nov 12: DP continued.
Nov 14: Greedy Algorithms, My slides.
Nov 19: Greedy Algorithms - continued
Nov 21: Greedy Algorithms - continued
Nov 26: Graph Algorithms. My slides.
Nov 28: Graph Algorithms. Finish previous set of slides. Start shortest paths. My slides.
Dec 4: Graph Algorithms. Intractability. My slides.

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.

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:

Copied from this page maintained by the registrars office

Sep 4: First day of class
Oct 12-18: Reading week (no classes or tests)
Nov 8: Drop deadline
Dec 3: Classes end
Dec 4: Study day
Dec 5-20: Exam period

Grades

Assignments: 15%, We will try to have at least 3 short assignments.
Tests (35%). Three in-class tests (15% each): [Note that the test in which a student gets her/his minimum mark will be weighted down to 5%]
1. Test 1 (15%): Oct 1, in class. Syllabus: Given on moodle
2. Test 2 (15%): Oct 29, in class. Syllabus: Everything covered up to and including Oct 22
3. Test 3 (15%): Nov 21 (NOTE the change), in class. Syllabus: Radix Sort, Order Statistics, Dynamic Programming.
Final Exam: 50%, scheduled by the registrar -- Syllabus: Everything covered in the course.

NOTE: Grades will be available on moodle.