Bismillahir Rahmanir Raheem
Course Teacher:
Dr. Masud Hasan
Email: mhasan2010@gmail.com (in English please)
Book:
- CLRS: Introduction to Algorithms, by Cormen, Leiserson, Rivest, Stein. Third Edition, 2009, MIT Press.
Class Schedule:
- Girls-Section-MCS: Sunday 4:30pm-7:15pm, TV 17
- Girls-Section-MCS1: Tuesday 4:30pm-7:15pm, TV 2
Course Plan: [pdf]
Course Website: https://sites.google.com/view/tumscs800september2019
Office Hours: TBA
Marks Distribution:
- Home Assignment 1, 2: 20%
- Project: 20%
- Presentation: 10% (Slides 5% + Voice audio 5%)
- Report Writing: 10%
- Mid Term Exam: 20%
- Final Exam: 40%
- Bonus on Class Performance: Time to time I may give bonus marks for your class performance.
Topics, Textbook reading, Slides, Handnotes:
- Lecture 0: Review of high school and undergrad math preliminaries
- Slides [pdf]
- Textbook reading:
- Lecture 1: Complexity Analysis: Growth of Functions
- Slides [pdf]. Correction: Slide no 35, 36 (c=1/10, see red color in the corrected pdf).
- Textbook reading: Chapter 3.1
- Video from an older semester: video 1, video 2
- Exercise: [pdf]. Correction: Question 3 right side will be Omega(n^3). See red color in corrected pdf.
- Lecture 2: Complexity Analysis of Sorting Algorithms + Divide and Conquer
- Slides [pdf]
- Textbook Reading: Chapter 2, 7.1
- Video from an older semester: video 1, video 2
- Exercise: [pdf]
- Lecture 3: Complexity Analysis of Recursive Algorithms
- Slides [pdf]
- Textbook reading: Chapter 4.Preamble, 4.5
- Video from an older semester: video-1, video-2
- Exercise [pdf]
- Lecture 4: Randomized Quick Sort
- Slides [pdf] Correction: Slide 11 corrected. See the corrected pdf.
- Textbook reading: Chapter 7.2, 7.3
- Video from an older semester: video-1, video-2
- Exercise [pdf]
- Lecture 5: Dynamic Programming
- Slides [pdf]
- Textbook reading: Chapter 15.Preamble, 15.4
- Video from previous semester: video-1, video-2
- Exercise [pdf]
- Lecture 6: Amortized Analysis
- Slides [pdf]
- Textbook reading: Chapter 17.Preamble, 17.4.1 up to Page 466 first paragraph
- Video from previous semester: video-1, video-2
- Exercise [pdf]
- Lecture 7: Heaps
- Lecture 8: Skip List
- Slides [pdf]. Why forward steps is O(log n) in search [pdf].
- Textbook reading: [pdf]
- Video from previous semester: video-1
- Exercise [pdf]
- Lecture 9: Disjoint Set Data Structures
- Slides [pdf]. Slide 9 clarified. See it now in the updated pdf.
- Textbook reading: Chapter 21.1, 21.2
- Video from previous semester: video-1
- Exercise [pdf]
- Lecture 10: Minimum Spanning Tree (Greedy Algorithm)
- Slides [pdf]
- Textbook reading: Chapter 23.2 (only Kruskal's algorithm from the textbook)
- Video from previous semester: video-1
- Exercise [pdf]
- Lecture 11: Shortest Path Algorithms
- Slides [pdf]
- Textbook reading:
- Video from previous semester: (covered in the video of Lecture 10 above)
- Exercise [pdf]
- Lecture 12: NP-Completeness
- Slides [pdf]. Three new slides added (Slide 16, 17, 18)
- Textbook reading:
- [CLRS] Chapter 34.Preamble, 34.1, 34.2, 34.3 (up to page 1073), 34.5.1.
- [GJ] Relevant texts from Chapter 1, 2, 3 [pdf]
- Video from previous semester: Video-1, video-2, Lecture-12-video-3-Lecture-13-video-1
- Exercise [pdf]
- Lecture 13: Approximation Algorithms
- Slides [pdf]
- Textbook reading: Chapter 35.Preamble, 35.1
- Video from previous semester: See Lecture 12
- Exercise [pdf]
- Lecture 14: Lower Bound Theory
- Slides [pdf]. Up to Slide 10. Audio of Slide 10 for Section MCS [listen]
- Textbook reading: Chapter 8.Preamble, 8.1
- Exercise [pdf]
Midterm Exam:
- Date and Time: October 29, 2019, Tuesday, 4:30pm-5:45pm
- Syllabus: Lecture 0, 1, 2, 3, 4, 5
- Question type: Short questions
- Answer script with common mistakes [pdf]
Final Exam:
- Syllabus: All lectures
- Questions type: Short questions, similar to midterm exam.
Assignments:
- A1
- A1 [word]. Deadline extended to: 31 October, 2019, 11:59pm.
- Answer script with common mistakes [pdf]
- A2
- A2 [word]. Deadline: 30 November, 2019, 11:59pm.
- Some correct answers from some of you [pdf1, pdf2]
- A3 (Optional, best two assignments will be counted. It has 12 marks, so you can earn up to 2 marks of bonus!))
- A3 [pdf]. Deadline: 19 December, 2019 (Thursday) 11:59pm.
- Some good answers from some of you [Q1-2, Q3-4-5]
Marks:
