East-West University
May 2011 Semester
CSE 501: Design and Analysis of Algorithms
Contact:
Dr. Masud Hasan
Associate Professor, Department of CSE, BUET
Phone: 9665650-80, Ext. 6113
Email: mhasan2010 AT gmail.com
Announcements:
Class Test marks:
Text reading:
Syllabus:
Chapter 3: Growth of Functions
Preamble
3.1: Asymptotic notations (up to page 50)
3.2: Standard notations and common function (self study for review)
Chapter 7: Quick Sort
Full
Follow class note
Chapter 8:
Preamble
8.1 Lower bounds for sorting
Chapter 15: Dynamic Programming
Preamble
15.2 Matrix-chain multiplication
[lecture audio-1] [lecture audio-2] [lecture audio-3]
Chapter 16: Greedy Algorithms
Preamble
16.3: Huffman coding
[lecture audio-1] [lecture audio-2]
Chapter 22: Elementary Graph Algorithms
22.1: Graph Representations (self study)
22.2: BFS
22.3: DFS
22.4: Topological Sort
[lecture audio-1] [lecture audio-2]
Chapter 23: Minimum Spanning Tree
23.2: Prims and Krushkals Algorithms
[lecture audio-1] [lecture audio-2]
Chapter 24: Single Source Shortest Paths
Preamble
24.3: Dijkstra Algorithm
[lecture audio-1] [lecture audio-2]
Chapter 34: NP-Completeness
Follow class notes and audios.
[lecture audio-1] [lecture audio-2] [lecture audio-3] [lecture audio-4]
Coping with NP-Completeness
Backtracking: Pages 283-186 of this [PDF]
Final Exam: 18-08-2011, Thursday, 4:00pm. Syllabus: Chapters 22, 23, 24, 34, PDF
Marks Distribution:
Attendance: 10
Class Test (Best 2): 10x2=20
Mid-1: 20
Mid-2: 20
Final: 30
Your Marks [pdf]