ICS 621 Analysis of Algorithms (Spring 2012)

General Information

• Class Meets: Mon and Wed 3pm - 4:15 pm Room WAT 114
• Final Exam : None.
• Instructor : Lipyeow Lim
• Office Hours : Thu 12-2pm POST 303 E or by appointment 808-956-3495
• Textbook :
  • Required : Introduction to Algorithms (3rd Ed.) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, ISBN-13 978-0-262-03384-8
  • Optional : Introduction to the Design and Analysis of Algorithms (3rd Edition) by Anany Levitin, ISBN-13 978-0132316811
• Student Learning Outcomes: At the end of this class, the successful student would
  • have gained a broad understanding of the design and analysis of algorithms
  • have gained a broad understanding of elementary data structures and their performance characteristics
  • be able to design an algorithm to solve a computational problem
  • be able to analyze an algorithm to charaterize its performance
  • be able to analyze a computational problem to characterize its tractability
  • be able to prototype and evaluate an algorithm empirically
• Late policy: work submitted past due date and time will receive zero credits.
• All students are expected to conduct themselves above and beyond the standards set forth in the University of Hawaii Systemwide Student Conduct Code.
• Any student who feels s/he may need an accommodation based on the impact of a disability is invited to contact the instructor privately. The instructor would be happy to work with you, and the KOKUA Program (Office for Students with Disabilities) to ensure reasonable accommodations in the course. KOKUA can be reached at (808) 956-7511 or (808) 956-7612 (voice/text) in room 013 of the Queen Lili'uokalani Center for Student Services.
• Pre-requisites: Graduate standing or consent

Topics

• Mathematical Tools for Algorithm Analysis
• Fundamentals of Algorithm Analysis
• Different Approaches to Algorithm Design: Exhaustive Search, Greedy, Divide and Conquer, Transform and Conquer, Dynamic Programming, Iterative Improvement
• Limits of Algorithm Power: NP-Completeness
• Approaches for NPC problems: heuristic, branch and bound, approximation, randomization
• Algorithms for common problems: sorting, string, graph, search, etc

Grading (Tentative)

• 10 % Class Participation
• 40 % Homework Assignments
• 50 % Research Project

Class participation grades will be based on attendance and note taking. Notes must be typeset using LaTeX using the given notes template.

Homework Assignments will be assigned on the Wednesday of each week and are due the following Wednesday at 2359 hours in hardcopy. The homework assignments must be typeset in LaTeX with the homework number and your name displayed clearly on the front page. Please use one of the algorithms latex package (see wikibook) to typeset pseudocode (algorithmic.sty is recommended).

Class Schedule (tentative)

Other Readings

• Robert Morris' Approximate Counting Algo
• P. Flajolet and G. N. Martin. Probabilistic counting. In Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 76.82, 1983
• Design and Analysis of Dynamic Huffman Codes
• Count-Min Sketch and Finding Heavy Hitters
• Approximate Frequency Counts over Data Streams
• Making B+-trees Cache Conscious in Main Memory
• IO Book (pdf) Ch 1-5
• Reservoir Sampling (pdf)
• Burrow Wheeler Transform
• LZ77

Useful Links

• Theoretical Computer Science Cheat Sheet
• GraphViz
• Info on LaTeX. Windows users should install MikTex. Linux users should install latex (usually tetex) using their respective software package managers. Mac users should use MacTex.
• If you need to draw diagrams for inclusion in your homework, use a diagramming software and export to eps or pdf format and include it in your latex source using the includegraphics command. Dia is a good open-source diagramming tool that runs on most platform. If you are using X windows in cygwin or unix or mac, xfig is also a very good diagramming tool.
• Screencast-o-matic Free Screencast software for creating recorded presentations.
• UHM Spring 2012 Academic Calender