COMP9601 Theory of Computation and Algorithms Design [Section 1A, 2015]

Course category2015-16

Scope: Automata, computability and complexity 50%; online algorithms and data struc- tures for text indexing 50%

Prerequisite: undergraduate courses on algorithms and data structures. 

Teaching plan:

  • Models of computation; finite automata and pushdown automata; automata and lan- guages; deterministic versus nondeterministic computation

  • Turing machines and random access machines; equivalence in terms of computability

  • Decidability (computability); the halting problem; reduction techniques

  • Computational complexity; classes of languages; time-complexity classes

  • The classes P and NP; polynomial time reduction; NP-completeness

  • Additional NP-complete problems; Cook-Levin theorem

  • Approximation algorithms

  • Space-complexity; relationship between time and space;

  • Online algorithms and competitive analysis

  • Paging algorithms and other online problems

  • Job scheduling; deadline and flow time scheduling; resource augmentation; energy

    efficient scheduling;

  • Text indexing: suffix trees and suffix arrays

  • Compressed indexes


Teacher: Lam Tak Wah

COMP8101 Advanced topics in data engineering [Section 2A, 2015]

Course category2015-16

This course will discuss and study research topics and current problems of interest in the field of data engineering.

COMP7802 Introduction to financial computing [Section 1B, 2015]

Course category2015-16

This module introduces the students to different aspects of financial computing in the investment banking area. The topics include yield curve construction in practice, financial modelling and modern risk management practice, etc. Financial engineering is an area of growing demand. The module is a combination of financial product knowledge, financial mathematics and computational techniques. This module will be suitable for students who want to pursue a career in this fast growing area.

This is a very practical module. The module is assessed on the basis of individual assignments and a final exam.

Teacher: Ng Tat Lun

COMP7506 Smart phone apps development [Section 1B, 2015]

Course category2015-16

Smart phones are now indispensible tool for everyone. They can be used not only for traditional voice communications, but also serve as personal digital assistant, gaming console, media box, or miniature PC that perform tasks that could originally be done only on PC. The versatility of smart phones’ capabilities is actually backup by a wide range of applications (or simply apps).

Smart phones open up another dimension for software developer to develop applications that interact with their users. But since smart phones are nothing like desktop computers (e.g. substantially smaller monitor screen, touch-screen oriented, etc.), special care has to be taken in order to develop successful apps. In this course, students will learn about the design issues of smart phone apps, as well as apps development environments and programming techniques (e.g. Java for Android and Objective-C for iPhones).