Reading -- CS6234, Spring 2009, NUS-SOC

CS6234: Advanced Algorithms
School of Computing, National University of Singapore
(Spring Sememster 2009)
Reading & Presentation (20%) (Draft)

1. Description

For this assignment, students are expected to complete a reading assignment which includes

reading up on the topic chosen -- based on papers/textbook-sections,
learning the pre-requisite materials, if necessary, and
giving a technical presentation (?? min) on the topic to the class.

The topics for this assignment are related to the subject areas covered in the course. Typically, the instructors gives an introduction to the various algorithmic topics and possibly several sub-topics. Additional sub-topics are assigned as possible reading assignments. (A list of possible topics is given below. You can also propose your own topic and get it approved by the instructors.)

2. Grading: (draft)

The grade you receive for the reading assignment will depend on how well you have

organized the material,
presented the material,
your ability to answer questions (from instructor and class-mates), and
your evaluation of the results, namely, your thoughts on things like
- how good the result is (compared to others),
- do your think it is possible to do better and maybe how?,
- does it has other applications, or
- any other remarks you can make about the work.

A detailed grading sheet will be given later.

3. Deadlines

Milestone R1: Choose a topic and on presentation date (ASAP, but by 04-Feb-2009, Week 4)
Or propose your own topic.

Milestone R2: Your chosen presentation date.
A week (or several days), you should show your presentation slides to the instructors for comments and suggestions. You can use the comments/suggestions to improve your presentation. (You should also find time to test run the presentation using the equipment in the lecture venue.)

On the day of your presentation, you should arrive at least 15 minutes early and have loaded up your presentation material and be "ready to go" with your presentation.

4. Possible Topics:

We have included a list of possible reading topics and for each topic, some representative reading material, and possible presentation dates. Your task is to select a topic, select a presentation date, and start working on it.

Topic: Weighted Matching in General Graphs
Reference:
1. Ch-11.3 of [PS82]
2. Additional references from end of Chapter 11
Topic: Applications of Matching and Vertex Covers to Fault Coverage in Redundant Memory Arrays
Reference:
1. References will be coming soon.
Topic: Computational Aspects of Simplex Algorithm for LP
Reference:
1. Ch-2.5--2.8 of [PS82]
2. Additional references from end of Chapter 11
Topic: The Hungarian Method: A Primal-Dual for Weighted Matching
Reference:
1. Ch-11.2 of [PS82]
2. Additional references from end of Chapter 11
Topic: A Polynomial-Time Algorithm for Linear Programming
Reference:
1. Ch-8.6--8.7 of [PS82]
2. Additional references from end of Chapter 11
Topic: Interior Point Methods for Linear Programming
Reference:
1. References will be coming soon.
Topic: Approximation and streaming algorithms for histogram construction problems.
Reference:
1. Sudipto Guha, Nick Koudas, Kyuseok Shim: Approximation and streaming algorithms for histogram construction problems. ACM Trans. Database Syst. 31(1): 396-438 (2006)
  url: http://portal.acm.org.libproxy1.nus.edu.sg/citation.cfm?id=1132873
Topic: Dynamic programming algorithms for synopsis construction.
References:
1. H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Viswanath Poosala, Kenneth C. Sevcik, Torsten Suel: Optimal Histograms with Quality Guarantees. VLDB 1998: 275-286
  http://www.sigmod.org/vldb/conf/1998/p275.pdf
2. Sudipto Guha: Space Efficiency in Synopsis Construction Algorithms. VLDB 2005: 409-420
  http://www.vldb2005.org/program/paper/wed/p409-guha.pdf
3. Panagiotis Karras, Nikos Mamoulis: Lattice Histograms: a Resilient Synopsis Structure. ICDE 2008: 247-256
  http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4497433

5. Accessing online papers (via NUS Library Proxy)

In order to access the papers at the publisher's site, you can use the proxy bookmarklet provided by NUS Libraries. Instruction on this page:

http://www.lib.nus.edu.sg/lion/d/proxybkmrklet_google.html