CSE 3101: Design and Analysis of Algorithms
Summer 2013

General Information

Instructor: Suprakash Datta
Office: CSEB, room 3043
Telephone: (416) 736-2100 ext. 77875
Facsimile: (416) 736-5872
Lectures: Tue 7 - 10 pm in TEL 0016
Office Hours (tentative): Wed 4-6 pm, Tue 6-7 pm, or by appointment
Email: [lastname]@cse.yorku.ca (While you are free to send me email from any account, please realize that email from domains other than yorku.ca have a higher chance of entering my spam folder. I do check my spam folder irregularly , but to be safe, consider using your cs account when sending me email.)
TA: Mohammad Sajjadieh (mohammad at cse dot yorku dot ca).




Lecture schedule

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.
2. Quizzes will be held in the first hour of designated classes (unless otherwise specified) and the remaining time will be used for lectures.
  1. May 7: Administrivia. Introduction to algorithm analysis. My slides are here (pdf).
  2. May 14: Introduction to algorithm analysis - continued. My slides are here (pdf). Here are some solved problems on proving correctness using loop invariants.
  3. May 21: Introduction to divide and conquer. My slides are here (pdf).
  4. May 28: Recurrence relations and the Master Theorem (Ch 4). Same slides as before. More sorting algorithms (Ch 6,7). My slides are here (pdf).
  5. June 4: Lower Bounds. Sorting in Linear time (Ch 8). My slides are here (pdf).
  6. June 11: Selection in Linear time (Ch 9). My slides are here (pdf).
  7. June 18: Dynamic Programming: Ch 15. My slides are here (pdf).
  8. July 2: Dynamic programming, no new slides. Some practice problems are here.
  9. July 9: Introduction to greedy algorithms. Ch 16. My slides are here (pdf).
  10. July 16: Quiz 2. Finish greedy algorithms (same slides as before). Start graph algorithms. My slides are here (pdf).
  11. July 23: Continue graph algorithms. BFS, DFS, Topological sort. Start shortest path problems (Ch 23, 24). My slides are here (pdf) and here (pdf).
  12. July 30: Finish shortest paths, transitive closure (same slides as last class). Introduction to NP-completeness. My slides are here (pdf).

 Course summary:

The list of topics we will try to cover includes the following. The Section numbers refer to the required text. Relevant chapters: 1,2,3,4,6,7,8,9,15,16,22,23,24,25,26,34,Appendix A,B.


Enrollment in CSE 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)

Optional Supplementary Reading

Other References 

    Course policies:

    Important Dates:


    NOTE: Grades of tests and the final exam will be available on ePost. Please use your CSE id/password after clicking here to access your grades.