COMP3711H : Design and Analysis of Algorithms
Fall 2015

Sunil Arya, Room 3514, Tel 2358-8769, Email: arya@cse.ust.hk

 

 

 

Course Information

Schedule & Notes

Assignments
 Tutorials
Marks

Announcement:

ˇ       COMP3711H Midterm exam will be on Oct 29 (Thursday), 7:00-9:30pm in Room 4502.

Course Description

This course presents the fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their running times. General topics include mathematical analysis of algorithms (summations and recurrences), advanced data structures (balanced search trees), algorithm design techniques (divide-and-conquer, dynamic programming, and greedy algorithms), graph algorithms (breadth-first and depth-first search, minimum spanning trees, shortest paths).

On successful completion of this course, students are expected to be able to:

  1. Describe fundamental concepts and techniques for determining the asymptotic behavior of real-valued functions defined in natural numbers.

  2. Explain recurrence equations and solve common recurrences using a variety of techniques.

  3. Analyze an algorithm described in plain language or some form of pseudocode in terms of its time (or space) efficiency as a function of the size of a problem instance.

  4. Explain how various data structures, including trees, heaps and disjoint set structures, influence the time efficiency of algorithms.

  5. Apply general algorithmic design and analysis techniques to solving problems, including greedy, divide-and-conquer and dynamic programming.

  6. Identify randomization in algorithms and analyze basic randomized algorithms such as randomized quicksort and selection.

Textbook

Jon Kleinberg and Éva Tardos. Algorithm Design, Addison-Wesley.

References

T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, Third Edition, MIT Press.
Dasgupta, Papadimitriou, and Vazirani. Algorithms, McGraw Hill.
Jon Bentley. Programming Pearls, Addison-Wesley.
COMP3711 course webpage

Time and Place

Lectures: Wed & Fri 4:30-5:50pm, Room 4502.

Tutorials:

Section Day Time Room TA
T1 Fri

6:00pm-6:50pm

4502

Yuchen Mao

Instructor

Sunil Arya

Web: http://www.cse.ust.hk/~arya
Office hours: After each lecture, or by appointment. Office: 3514

TAs

TA Email Office Office Hour
Yuchen Mao ymaoad@connect.ust.hk 4209

 Email to make appointment

 

Important dates

Event Hand out date Due date
Homework 1 16 Sep 30 Sep
Homework 2 2 Oct 16 Oct
Midterm exam Oct 29 (Thu) 7-9:30 pm in Room 4502
Homework 3 Nov 2 Nov 13
Homework 4 Nov 13 Nov 25
Final exam Dec 9 (Wed), 12:30-3:30 pm in Room 4620

 

Grading

4 Assignments 5% * 4 = 20%
Midterm 35%
Final 45%

No make-ups will be given for midterm and final unless prior approval is granted by the instructor, or you are in unfavorable medical condition with physician's documentation on the day of the examination. In addition, being absent at the final examination results in automatic failure of the course according to university regulations, unless prior approval is obtained from the department head.

Students are expected to follow the HKUST Academic honor code