Course syllabus for ICS621 Fall 2017

a. Course alpha and number, and course title.

ICS 621 Analysis of Algorithms

b. Instructor name and contact information.

Lipyeow Lim

lipyeow@hawaii.edu

c. Course description.

Analysis and design of algorithms: modeling, comparison, measures, applications.

d. Course objectives.

To teach students:

1. common algorithms and data structures
2. how to conceptualize computational problems and design algorithmic solutions
3. how to analyze algorithms.
4. how to deal with computationally intractable problems

e. Student Learning Outcomes

At the end of this course the successfull student should

1. have gained a broad understanding of the design and analysis of algorithms
2. have gained a broad understanding of elementary data structures and their performance characteristics
3. be able to design an algorithm to solve a computational problem
4. be able to analyze an algorithm to charaterize its performance
5. be able to analyze a computational problem to characterize its tractability
6. be able to prototype and evaluate an algorithm empirically

f. Number of credit hours

3.

g. Prerequisites

None.

h. Textbooks, required readings

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

i. Grading and Student Evaluation

• 10 % Class Participation
• 10 % Mid-term Exam
• 30 % Homework Assignments
• 50 % Research Project

j. Classroom policies

Standard classroom policies of the College of Natural Science apply.

Late policy: work submitted past due date and time will receive zero credits.

Examinations: No make-up exams will be given.

Student Conduct: All students are expected to conduct themselves above and beyond the standard set forth in UH Systemwide Student Conduct Code.

Disability: 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 Liliuokalani Center for Student Services.

k. Weekly schedule of topics and readings, including exam dates.

Week 1: Review of Algorithm Analysis fundamentals

Week 2-3: Sorting

Week 4: Order Statistics & Binary Search Trees

Week 5: Red-Black Trees, Interval Trees, B+ Trees

Week 6: Amortized Analysis

Week 7: Binomial Heaps & Fibonacci Heaps

Week 8: Mid-term Exam & Post-exam review.

Week 9: Dynamic Programming

Week 10: Greedy Algorithms & Hashing

Week 11-12: Graph Algorithms

Week 13: NP-Completeness

Week 14: Approximation Algorithms

Week 15: Approximate Counting

Week 16: Presentation of Course Projects. Final project report due.