CSE 3101: Design and Analysis of Algorithms
Important: The test scheduled for June 29 will be held next week.
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.
2. Tests will be held in the first hour of designated classes and the remaining time will be used for lectures.
- May 4: my slides are here.
- May 11: Please note the change in classroom. My slides are here. The first two slides in this set were covered in the
last lecture but had typos that have been fixed in this set.
We covered upto slide 69 in this set.
Hw 1 is here. Solutions are in /cs/course/3101/3101a1-sol.pdf. You can access it from the computer labs in CSEB, or by ftp. In either case
login with your normal login id/password combination and change directory/folder to /cs/course/3101/. You should be able to access the solution file in pdf format. Please do not look at the solution before trying the problems.
This sample test is posted for you to prepare for test 1.
- May 13: Tutorial session 7-8 pm CB 129: OPTIONAL, no new material covered. I will work out these problems, and answer questions.
- May 18: test 1, followed by 90 minutes of lecture. We covered slides
70 through 107 in the set linked above.
- May 25: The forum has been set up. We will finish the previous set of slides and move to this set. The topic is Divide and Conquer algorithms.
Hw 2 is here. Solutions are in /cs/course/3101/3101a2-sol.pdf.
Programming contest on May 26, 6:30 pm. More details are here.
- May 27: Tutorial session 7-8 pm CSEB 3033: OPTIONAL, no new material covered. I will work out some problems, and answer questions. Please email me any questions you want solved.
- June 1: test 2 (Sample test here).
Solutions are in /cs/course/3101/sample2-sol.pdf. A typo in Q3 has been fixed. Thanks to Michael Movshovich for pointing this out.
Solutions to test 1 are in /cs/course/3101/3101test1-sol.pdf.
Lecture slides are here, one per page (as requested). We covered up to slide 18 in this set.
- June 2: Tutorial 7-8pm, in Ross S 137. We covered loop invariants for 3 problems from Problems on Algorithms: 253/254, 261, 264.
- June 8: Solutions to Test 2 are in /cs/course/3101/3101test2-sol.pdf.
Same slides as the last class will be covered. If we have time, will start this set.
- June 10: Tutorial 6-7 pm in CSEB 3033. We covered problems 536, 543, 608, Q5 (page 246) of PoA.
- Junes here 15 test 3 : Syllabus - Ch 4 (Divide and Conquer) Ch 6(Heapsort) and Ch 7 (Quicksort). Lower bounds are not included in this test. The same sheet of formulas as test 2 will be provided with this test, and is in /cs/course/3101/formulas.pdf.
HW 3 is here (updated 3:30 pm, Jun 11 - there is an error with a problem previously on this assignment). The solutions to a3 are in /cs/course/3101/3101a3-sol.pdf. Some typos have been fixed (June 14) - thanks to all that pointed them out.
Instead of a sample test, some practice questions are here. Solutions are in /cs/course/3101/sample3-sol.pdf.
- June 18 Friday: tutorial 6:30-7:30 pm CSEB 3033.
I will go over solutions to hw and tests and maybe some problems.
- June 22: Median computation in linear time (same slides as before). Introduction to Dynamic Programming (slides).
HW 4 is here
- June 24: Tutorial 7-8 pm in CSEB 3033.
- June 29: The solutions to test 3 are in /cs/course/3101/3101test3-sol.pdf.
Dynamic programming continued -- new set of slides are here.
There will be no tutorial this week.
-
The test is POSTPONED by 1 week, to July 6 .
The solutions to HW 4 are in /cs/course/3101/3101a4-sol.pdf.
July 6: test 4: the syllabus is Lower bounds, linear time sorting and Medians and order statistics (Note that we will not cover randomized quicksort and randomized selection (7.3, 9.2 in Edition 2).
Some practice problems are here.
Solution sketches to the above problems are in /cs/course/3101/sample4-hints.txt.
Greedy Algorithms - slides are here.
The set of easier problems on DP are here.
Problems on greedy algorithms are here.
A set of more difficult problems on DP are here.
- July 8: Tutorial 7-8 pm, CSEB 3033.
- July 13: Graph algorithms. My slides are here.
- July 15: Tutorial 7-8 pm, CSEB 3033. The elevator may noy be accessible after 7 pm, so please come early.
- July 20: Test 5: the syllabus is Dynamic programming and Greedy Algorithms.
Skip Sections 15.5 (Optimal binary search trees), 16.4,16.5 (both deal with matroids). All section numbers are from the 3rd edition.
Solutions to the easy DP set are in /cs/course/3101/3101-a5-DP1-sol.pdf.
Solutions to the harder DP set are in /cs/course/3101/3101a5-DP-hw2-sol.pdf.
Solutions to the greedy algorithms questions are in /cs/course/3101/3101a6-greedy-sol.pdf.
Lecture: Graph algorithms continued.
- July 22: Tutorial 7-8 pm, CSEB 3033. The elevator may not be accessible after 7 pm, so please come early.
Problems on graph algorithms are here.
Solutions are in /cs/course/3101/3101-a7-sol.pdf.
- July 27: Test 6 (optional): the syllabus is Graph Algorithms -- DFS, BFS, Topological sort, MST.
Lecture: Finish graph algorithms(slides), Intractability and NP completeness (slides).
- July 29: Tutorial 7-8 pm, CSEB 3033. The elevator may not be accessible after 7 pm, so please come early.
More problems on graph algorithms are here.
- Office hours as usual on Aug 11. Solutions to the last to tests are in /cs/course/3101/. Some typos in the solutions to test 5 have been fixed.
The solution to the last homework is in /cs/course/3101/3101-a8-sol.pdf.
Solutions to test 4 now in /cs/course/3101.
A previous final is here.
Section info:
Instructor: Suprakash Datta
Telephone: (416) 736-2100 ext. 77875
Facsimile: (416) 736-5872
Email: My last name (all 5 letters are in lowercase) at cs.yorku.ca
Lectures : Tue 7pm -10:00 pm, in BC 215 (changed from PSE 321)
Office hours: Wed 4-6 pm, or by appointment, in CSEB 3043
Twitter (for this course): Yorku3101S10
forum (for this course): Login here with your normal CSE account/password.
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 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)
- 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: We take matters of academic honesty very seriously. If you wish to have more information on this topic, please visit
this page.
- Missed tests: Any student missing a test for any reason other than medical automatically gets a score of zero for the test. If the student has medical grounds and provides proper documentation, then the marks will be transferred to the final. There will NOT be any substitute or make up tests.
Important Dates:
- May 4: First class
- Drop deadline: July 5
- July 27: Last class
- Holidays : May 24, July 1, Aug 2 (none of these coincide with lectures)
- Finals: scheduled by the registrar's office during Aug 3-13.
Grades
- Tests (best 4 out of 5): 50 %
- Final Exam: % 50 %
The conversion from a metric scale to a letter grade will be made in
accordance to the department standard as follows:
|
F |
E |
D |
D+ |
C |
C+ |
B |
B+ |
A |
A+ |
|
<40% |
>=40% |
>=50% |
>=55% |
>=60% |
>=65% |
>=70% |
>=75% |
>=80% |
>=90% |
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.