CSE 6408: Advanced Algorithms
April 2011 Semester
Starting from 16-th April 2011
Quick
Links: Contact/Course teacher: Books Schedule
and Course syllabus
Announcements
Marks
Distribution Study Topics
Web
resource Presentation
Project Final
Exam Bonus/Open
Problems Exercise
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
1.
[CLRS] Introduction to Algorithms, by Coreman, 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.
Other
materials/references will be supplied as required
Time:
Saturday 10-1
Location:
CSE Department, West Polashi
We will
try to cover the following topics as per the following tentative sequence:
|
Date,
Class |
Topics |
Text |
Presentation
schedule |
|
Lecture
1, 16/04/2011 |
- Course policies - Randomized Algorithms: Las Vegas and Monte
Carlo Algorithms - Randomized Data Structures: Skip
Lists |
[MR]: 1.Preamble, 1.1, 1.2, 8.3 [GT]: 3.5 |
|
|
Lecture
2, 23/04/2011 |
|
||
|
Lecture
3, 30/04/2011 |
- Amortized Analysis: Different
methods - NP-Completeness review |
[CLRS]: 17 (full) [CLRS]: 34.5.1, 34.5.2,34.5.4 |
|
|
Lecture
4, 07/05/2011 |
|
||
|
Lecture
5, 14/05/2011 |
- Approximation Algorithms: Approximation Schemes, Hardness of Approximation |
[CLRS]: 35.1,35.2, 35.5, [GJ]: |
|
|
Lecture
6, 21/05/2011 |
- Online Algorithms: Competitive
Analysis, Online Paging Problem, Randomized online algorithms, Adversary
models, Marker algorithm |
[MR]: 13.Preamble, 13.1, 13.2, 13.3 (only Marker
Algorithm) |
|
|
Lecture
7, 28/05/2011 |
|||
|
Lecture
8, 04/06/2011 |
- Multithreaded Algorithms |
[CLRS] 27.Preamble,
27.1 (except scheduling), 27.2, 27 |
|
|
Lecture
9, 11/06/2011 |
- Van Emde Boas tree |
[CLRS]: 20.Preamble, 20.1, 20.2 |
|
|
Lecture
10, 18/06/2011 |
- Algorithms for Massive Data Sets - External Memory Algorithms -
Cache-Oblivious Algorithms |
[Demaine paper]: 1, 2, 3.1, 3.2.1,
3.3.1, 4.1 [Arge paper]: 38.1, 38.2.1
(except range query) |
|
|
Lecture
11, 25/06/2011 |
- Quantum Algorithms |
[NC] 1.2, 1.3, 1.4 |
|
|
Lecture
12, 02/07/2011 |
- Quantum Algorithms - |
|
[Jisan, Ashik],
[Khalid, Tandra], [Shampa],
[Rakib, Jayanto], [Mahbub,
Fahim] |
|
Lecture
13, 09/07/2011 |
- |
|
[Kawsar,
Aftabudduza], [Sylvia, Novia],
[Sharif, Rajiur]
[Samiul, Mahbub] [Rushafi + Samir], [Rezwan], [Mustafiz+Hasib] |
|
Lecture
14, 16/07/2008 |
- |
|
[Osman, Marzia],
[Mahmud, Raqibul] [Mostafiz,
Hasib], [Shaila, Tanvir] [Manazir, Tusar] [Sammi], [Sumiaya], [Ashraf, Nazmun], [Samiul, Jahed], [Nashid, Tanvir] |
|
1/8/2011, 2-5pm |
Final Exam |
|
|
|
|
o
Active
participation in the class: 10%
Select
a study topic and give a presentation on that: 15%
Write
a project on that topic: 15%
Final
exam: 60%
Bonus:
depending upon the level of work in finding any new result on your research
topic or an open problem mentioned in the class.
o
You have to spend
some time for selecting your topic first. I will suggest a list of topics. The
list will grow in the coming weeks. You may also suggest a topic, but
that must be verified by me. For most of the topics suggested below I have
tried to make them limited and specific.
o
To choose a
topic, first select one according to your interest. Then read (not in
detail) the accompanied papers that I have suggested (or more if necessary). If
you does not like it, go by another topic. Once you
have finally selected your topic, read the suggested papers carefully.
If necessary, explore other related papers mentioned in the the
references of the initial papers and/or the related papers where the initial
papers have been referred. Google Scholar, Citeseer or IEEE Explorer will help you
a lot to get most of the papers online and to find the earlier and following
papers. Throughout your adventure on the papers you should identify the
important papers and the results therein.
o
In each topic I
have pointed out what is to be done under this topic, but that is not enough.
After you have finally selected your topic, come to me, I will tell you what to
cover in your presentation and project. Try to do what I suggest. You are
always welcome with any new/additional/better idea other than that I have
suggested, with more recent papers that I missed, etc. And any such good
idea/findings will add marks to your presentation and project. It would be
superb if you can find any new result on your topic and you will get some bonus
mark for that.
o
It may happen
that you can not select any topic yourself. Do not worry for that, feel free to
inform me, I will help you selecting a topic.
o
Throughout the
course you will study this topic and the accompanied papers in detail and you
will give a presentation and write a project on it.
Possible topics: [In primary stage, more topics and more details to come...] [You
need GhostView to view ps files]
1. [Khalid, Tandra]: Adaptive
approximation algorithms.
2. [Jisan and Ashik]: Explore the concept of van Emde
Boas tree in genome sorting and related problems.
3. [Mahbub, Fahim]
Study of Approximation algorithms
4. [Osman, Marzia]
Quantum Fedkin gate.
5. [Salam, Raqibul] Quantum Toffoli gate.
6. [Sylvia, Novia] Survey of
external memory algorithms
7. [Rakib, Jayanto]
Survey of cache oblivious computational geometry algorithms
8. [Shampa]: Cache-oblivious
RMQ and RMSQ and related problems.
9. [Kawsar, Aftabudduza]:
Time space trade off, Distributed algorithms
10. [Sharif, Rajiur]: Randomized
data structures
11. [Samiul, Mahbub]:
Algorithms for massive data
12. [Rushafi, Samir]: Cache oblivious convex hull
13. [Mostafiz, Hasib]: Quantum search.
14. [Shaila, Tanvir]:
Quantum realization
15. [Manazir, Tusar]: Quantum Turing machine
16. [Rezwan]: Algorithms for
massive string data
17. [Sammi] Algorithms for
median finding
18. [Nashid, Tanvir]:
19. [Ashraf, Nazmun]:
Deutch-Josha Algorithm for Quantum Parallelism
20. [Samiul, Jahed]:
Paging for multicore processor
Presentation [15%]:
Follow
the guideline below in your presentation.
o
Complete your
presentation within 10-15 minutes
o
Give a summary
first
o
Clearly explain
the topic and its key features that you are covering (should include what I
have suggested)
o
Application of
this topic
o
Related work done
so far (should be recent works)
o
Future work
possible (as it comes to your mind and as it is mentioned in related papers)
o
Remember that
this is a graduate course. So try to make your presentation attractive, informative,
and friendly. Try to become less formal and communicative with the audience.
o
You may visit
"How to give a good presentation" here: http://203.208.166.84/masudhasan/
Project
will be the written form of what you find on your topic and during your
presentation. It must be written in LaTeX.
Report size is expected to be within10 to 15 pages with 11 size fonts and
single spacing. You can collect latex installation files for Windows from me
(~450 MB).
Points you should cover in your project:
-
Title of your project, Student IDs and Names
-
Introduction to the problem/topic
-
Results you found
-
Briefly explain most important results
-
Possible future works
-
Conclusion
-
References
Project submission deadline: 13/8/2011, Saturday, 12:00 noon (Extended from
Friday); Hard copy only; Slide under my office door or put in my box. Late
submissions are not acceptable.
o
Active participation in the class [10%]:
You
will get this mark when you actively participate in the class, where by
an "active participation" means you come to the class in time, turn
your mobile off, attentively listen, ask (logical) questions, give comments,
etc. It is not necessary that you ask questions or give comments all the time;
even, your body language without any verbose participation may indicate you are
attentive in the class. In your final exam some marks may be reserved for
questions that will judge whether you actively participated in the class or
not.
Syllabus:
See the schedule and course syllabus table.
Bonus/Open Problems:
If
you can find any new result on your/others topic or solve any problem mentioned
in the class you will get some bonus marks on top of your total marks.
·