COMP3711: Design and Analysis of Algorithms
(Fall 2015)

Course Information

Announcements:

· In preparation of the final exam, the instructors and TAs will hold office hours as follows:
Dec 9, 2-3pm: Prof. Dimitris Papadias (3555)
Dec 9, 4-5pm: Chen Yu (4209)
Dec 10, 2-3pm: Prof. Dimitris Papadias (3555)
Dec 11, 2:30-3:30pm: Lau Man Kit (4214A)
Dec 11, 4-5pm: Prof. Ke Yi (3552)
Dec 14, 4-5pm: Prof. Ke Yi (3552)
Dec 15, 4-5pm: Hu Xiao (4209)

· Mathematical background sheet

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 (intended learning outcomes):

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

T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, Third Edition, MIT Press. [e-version]

References

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

Time and Place

Lectures:

L1: Wed & Fri 4:30-5:50pm, Room 2464.
L2: Wed & Fri 3:00-4:20pm, Room 2502.

Tutorials:

Section	Day	Time	Room
T1	Fri	6-6:50pm	LSK 1033
T2	Wed	12:30-1:20pm	4502
T3	Fri	12-12:50pm	4502
T4	Fri	9:30-10:20am	4504

Instructor

L1: Dimitris Papadias
Office hours (in Room 3555): by email appointment.

L2: Ke Yi
Office hours (in Room 3552): by email appointment.

TAs

TA	Email	Office
LAU Man Kit	lmkia@ust.hk	4214A
HU Xiao	xhuam@cse.ust.hk	4209
CHEN Yu	ychenbh@cse.ust.hk	4209

Grading

4 Written Assignments:	5% * 4 = 20%
4 Programming Assignments:	1% * 4 = 4% (bonus)
Midterm exam:	30%
Final exam:	50%

No make-ups will be given for midterm and final exams 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.

Mark Appeals:

Mark appeals for assignments must be made within one week of the date of the return (if you pick up your assignments late, your appeal period does not lengthen). You should first consult the TA who marked the question. Only if the problem is still unresolved should you then bring the case to the instructor’s attention.

For the midterm and final exam, appeals must be made during the exam paper checking session. If you cannot attend the checking session, please inform the instructor for special arrangement.

COMP3711: Design and Analysis of Algorithms (Fall 2015)