Bismillahir Rahmanir Raheem

Course Teacher:

Dr. Masud Hasan

Office: B20

Email: mhasan2010@gmail.com (in English please)

Website: https://sites.google.com/view/masudhasan

Book:

• CLRS: Introduction to Algorithms, by Cormen, Leiserson, Rivest, Stein. Third Edition, 2009, MIT Press.

Class Schedule:

• Boys: Sunday and Tuesday, 6:15pm-7:30pm, B12-G91
• Girls: Sunday and Tuesday, 4:30pm-5:45pm, TV 15

Course Plan: [pdf]

Course Website: https://sites.google.com/view/tumscs800september2017

Office Hours: Sunday and Monday 11:00am - 12:00noon

Marks Distribution:

• Assignment: 20%
• Project: 20%
  • Presentation: 10%
  • 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:

• Preliminaries (Self Study): (review of high school and undergrad math preliminaries)
  • Chapter 1: Introduction
  • Chapter 3.2: Standard Notations and Common Functions
  • Appendix A: Summations
• Lecture 1: Complexity Analysis: Growth of Functions (Chapter 3 of CLRS)
  • Slides [pdf]. Modified slides 14, 36, 43 [pdf]
  • Textbook reading: Chapter 3.1.
• Lecture 2: Complexity Analysis of Sorting Algorithms
  • Slides [pdf]
  • Textbook reading: Chapter 2, 7.1
• Lecture 3: Complexity Analysis of Recursive Algorithms
  • Slides [pdf]. Two extra slides 40, 41 [pdf]. Modified slides 27, 35 [pdf].
  • Textbook reading: Chapter 4.5
• Lecture 4: Complexity Analysis of Randomized Quick Sort
  • Slides [pdf]. Modified slides 10, 11 [pdf]
  • Textbook reading: Chapter 7.3, 7.4
• Lecture 5: Dynamic Programming
  • Slides [pdf]. Extra example [pdf]
  • Textbook reading: Chapter 15.4
• Lecture 6: Amortized Analysis
  • Slides [pdf]
  • Textbook reading: Chapter 17 Preamble, 17.4.1 up to Page 466 first paragraph
• Lecture 7: Heaps
  • Slides [pdf]
  • Textbook reading: Chapter 6
• Lecture 8: Skip List
  • Slides [pdf]. Extra example and modified slide 12 [pdf]. Why forward steps is O(log n) in search [pdf].
  • Textbook reading: [pdf]
• Lecture 9: Disjoint Set Data Structures
  • Slides [pdf]. Extra example of improved strategy [pdf].
  • Textbook reading: Chapter 21.1, 21.2
• Lecture 10: Minimum Spanning Tree
  • Slides [pdf]
  • Textbook reading: Chapter 23.2 (only Kruskal's algorithm from the textbook)
• Lecture 11: Shortest Path Algorithms
  • Slides [pdf]
  • Textbook reading:
• Lecture 12: NP-Completeness
  • Slides [pdf]. Modified slides 24, 25 [pdf]. Extra example 1, 2
  • Textbook reading:
    • [CLRS] Chapter 34.Preamble, 34.1, 34.2, 34.3 (up to page 1069), 34.4, 34.5.
    • [GJ] Relevant texts from Chapter 1, 2, 3 [pdf]
• Lecture 13: Approximation Algorithms
  • Slides [pdf]. Extra example 1, 2
  • Textbook reading: Chapter 35.Preamble, 35.1
• Lecture 14: Lower Bound Theory
  • Slides [pdf]. Extra example [pdf]
  • Textbook reading: Chapter 8.Preamble, 8.1

Exercise:

• Lecture 1, 2, 3, 4, 5 [pdf]. Solution of Exercise 3, 4 in Lecture 1 [pdf]
• Lecture 6, 7, 8 [pdf]
• Lecture 9, 10, 11 [pdf]
• Lecture 12 [pdf]
• Lecture 13, 14 [pdf]

Midterm Exam:

• Date: 12-11-2017, Sunday.
• Time: 1:00pm. Girls please confirm with your department. New!
• Syllabus: Lectures 4, 5, 6, 7, 8
• Question type: Short questions, similar to Assignment 1.

Final Exam:

• Syllabus: All lectures
• Question type: Short questions

Assignments:

• Assignment 1 [pdf]
  • Solution: [pdf]. Solution contains my answers, answer from text book, and also good answers from some of you.
• Assignment 2 [pdf]
  • One good solution of Q4 from one student [pdf]

Marks:

• Boys [pdf]
• Girls [pdf]
• A good presentation [pdf] and a good project report from boys side [pdf].