ICS 621 Analysis of Algorithms (Fall 2015 CRN 79405)
General Information
- Class Meets: Tue and Thu 10:30 - 11:45 am Room Holm 248
- Final Exam : Maybe.
- Instructor : Lipyeow Lim
- Office Hours : Wed 2-4pm 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
- 10 % Exam
- 30 % Homework Assignments
- 50 % Research Project
Class participation grades will be based on presentation
of homework problems.
Homework Assignments will be assigned on the Thursday
every 2 weeks and are due on the Thursday 2 weeks later at 2359 hours
in hardcopy AND in Laulima. 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)
Week |
Date |
Topic |
Readings |
Videos |
Exercises
|
Other Readings
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 Fall 2015 Academic Calender