CSE 461: Algorithm Engineering
August 2011 Semester
Starting from 16-th August 2011
Dr. Masud Hasan
Associate Professor
Department of CSE, BUET
Office: West Polashi 117
Phone: PABX: 8614640-44, 9665650-80, Ext. 6113
Email: mhasan2010 "at" gmail
"dot" com
and
Nur-bahar Yeasha (special thanks to her): For query
on online repository of audios and other documents.
1. [CLRS] Introduction
to Algorithms, by Cormen, Leiserson, Rivest, Stein, 3rd Edition, 2009
2. [MR] Randomized
Algorithms, by Rajeev Motwani and Prabhakar Raghavan
3. [GT] Algorithm
Design: Foundations, Analysis, and Internet Examples, Michael Goodrich and Robarto Tamassia
4. [GJ] Computers
and Intractability: A Guide to Theory of NP-Completeness, Michael Garey and David Johnson
5. [NC] Quantum
Computation and Quantum Information, Michael Nielson and Isaac Chuang,
Indian Edition 2002
6. [JP] An
Introduction to Bioinformatics Algorithms, by Neil C. Jones and Pavel A. Pevzner, MIT Press, 1st Edition, 2004
7. [DPV] Algorithms, by Dasgupta, Papadimitriou, and Vazirani [Online copy]
8. Other materials/references will be supplied
as required
Time: Sunday, Monday, Tuesday 10-11
Location: Room 205, CSE Department, West Polashi
Course syllabus (will gradually grow and be updated):
Introduction
Review of NP-Completeness
The class P, NP,
NPC; Encoding; Polynomial Verification, Polynomial Reduction; Proving
NP-Completeness
Text: [CLRS]
Chapter 34.1, 34.2, 34.3 (up to page 1072), 34.5.1. 34.5.2
Lecture Audio:
[np-1] [np-2]
Sample
Questions: [np]
Randomized Algorithms
Review of
Randomized Quick Sort
Randomized
Min-Cut
Las Vegas and
Monte Carlo Algorithms
Randomized
Complexity Classes
Text: [CLRS]
Chapter 7 (full)
[MR] Chapter
1.preamble, 1.1, 1.2, 1.5
Lecture Audio: [rand-1]
[rand-2]
[rand-3]
Sample
Questions: [Rand QS + LB for Sorting] [rand-algo]
Randomized Data Structures: Skip List
Text: [GT]
Chapter 3.5
Lecture Audio: [skip]
Sample
Questions: [skip]
Class Test 1 [Marks] [Answer sheet with explanation]
Approximation Algorithms
Review the
Concept of Lower Bound
Lower Bound for
Sorting
Constant-factor
Approximation Algorithms
FPTAS
Inapproximability
LP Based
Approximation Algorithms
Randomized
Approximation Algorithms
Text: [CLRS]
Chapter 8.1, 35.preample, 35.1, 35.4, 35.5
[GJ] Page 139 [pdf]
Lecture Audio: [Lower Bound and Approx-1]
[Approx-2] [Approx-3] [Approx-4] [LP-based Approx]
Sample Questions
[Rand QS + LB for Sorting],
[Approx]
Class Test 2 [Marks]
Amortized Analysis
Different
Methods: Aggregate analysis, Accounting Method, Potential Method
Examples: PUSH,
POP, MULTIPOP; Binary Counter, Dynamic Tables
Text: [CLRS]
Chapter 17 (full)
Lecture Audio: [Amortized-1] [Amortized-2]
Sample Questions
[Amortized]
Online Algorithms
Competitive
Analysis
Online
Paging Problem
Randomized
Online Algorithms
Adversary
Models
Marker
Algorithm
Text: [MR]
Chapter 13.Preamble, 13.1, 13.2, 13.3 (no proof for Theorem 13.2 and Theorem
13.3)
Lecture Audio: [Online-1] [Online-2]
Sample
Questions: [Online]
Class Test 3 [Marks] [Sample answer 1] [Sample answer 2]
Bioinformatics Algorithms
Introduction
Genome Sorting
Text: [JP] Ch 3,
5.1, 5.2, 5.3, 5.4
Lecture Audio: [bio-algo-1] [bio-algo-2]
Slides: [bio-algo-1] [bio-algo-2]
Sample Questions
[]
Linear Programming
Follow what Kaykobad Sir taught in the class
Standard and Slack Forms
Problem Formulation
Simplex Method
How to formulate computational problems
in to linear programming
Duality
Text:
Lecture Audio:
Sample Questions
Quantum Computing
Quantum Bits (Qbits)
Quantum Gates
and Circuits
Quantum
Algorithms
Quantum
Parallelism
Text: [NC]
1.1-1.4.3
[DPV] 10.1, 10.2, 10.5.1,
10.5.2
Lecture Audio:
[Quantum-1] [Quantum-2] [Quantum-3]
Sample Questions
[Quantum]
Class Test 4 [Marks] [Sample answer 1] [Sample answer 2]
Practical Computing and Heuristics
Back tracking
Branch and Bound
Text: [DPV]
Pages 283-189 [pdf]
Lecture Audio: [BackTracking + Branch and Bound]
Sample Questions
[pdf]
Parallel/Distributed/Multithreaded Algorithms
Preamble
The basics of dynamic multithreading
Recursive Fibonacci Number computation
Multithreaded matrix multiplication
Text: [CLRS] Chapter 27.1 (up to page 781, excluding “scheduling”)
Lecture Audio: [Multi-thread]
Sample questions
Parameterized Algorithms
Fixed Parameter
Tractability
Parameterized
Algorithm (Buss’ Algorithm) for Vertex Cover
Text: [pdf]
page 163, 164 (column 1)
Lecture Audio: [Parameterized Algo]
Sample Questions
Algorithms for
Massive Datasets
External Memory Algorithms
Cache-Oblivious Algorithms
Text:
Lecture Audio:
Sample Questions
Class Tests and Announcements:
- CT 1: Wednesday, 21-9-2011,
8:00am, in class, Syllabus: Lectures up to 19-9-2011 (inclusive); see above for
detail.
- CT 2: Monday, 10-10-2011, 10:00am, in class, Syllabus: Approximation
Algorithms; see above for detail.
- CT 3: Tuesday, 18-10-2011,
10:00am in class, Syllabus: Amortized analysis and Online algorithms; see above
for detail.
- CT 4: Monday, 19-12-2011, 10:00am
in class, Syllabus: Quantum Computing; see above for detail.