Spring 2007 CS Course Listings

This file contains the Spring 2007 course listings for the Department of Computer Science and Engineering.

Archive of past courses

Course Code: COMP 530
Course Title: Database Architecture and Implementation

Instructor: Lei Chen
Room: 3546
Telephone: 23586980
Email:
WWW page: http://cse.hkust.edu.hk/~leichen/

Area in which course can be counted: Database

Course description:
This course introduces basic concepts and implementation techniques in database management systems: disk and memory management; advanced access methods; implementation of relational operators; query processing and optimization; concurrency control and recovery. In addition, a few advanced database topics are covered.

Course objective:
This course is a systems-oriented introductory database class for graduate students. The students are expected to learn basic concepts and implementation techniques of relational databases as well as to gain hands-on experience in building components of a small DBMS.

Course outline/content (by major topics):

  • Introduction to the relational model and SQL
  • Disk and memory management
  • Access methods and indexing
  • Implementation of relational operators
  • Query processing and optimization
  • Concurrency control and recovery
  • Logical and Physical database design
  • Advanced Topics

Course organization:
The instructor will teach the majority of the classes. Students will form groups; each group will choose a general database area (e.g., Data Warehouses and OLAP, Data Mining, XML, Stream Processing, Multimedia Databases, Time Series data, etc) and prepare: (i) a survey paper on the topic (about 20-25 pages), (ii) a presentation (covering a full class, i.e., 1.5 hours) and (iii) an implementation project.

Text book:
Database Management Systems, 3rd Edition. Raghu Ramakrishnan and Johannes Gehrke. McGraw Hill, 2002.

Grading Scheme:

  • Presentation (15%)
  • Survey Paper (15%)
  • Project (30%)
  • Final exam (40%)

Background needed: There is no prerequisite for this class. The students are expected to be comfortable with C++ and Java programming. If you are uncertain about your background, come to talk to the instructor during the first weeks.

Available for final year UG students to enroll: Yes.

Course Code: COMP538
Course Title: Reasoning and Decision Under Uncertainty

Instructor: Nevin L. Zhang
Room: 3504
Telephone: 23587015
Email:
WWW page: http://cse.hkust.edu.hk/~lzhang/

Area in which course can be counted: Artificial Intelligence

Course description:
Bayesian networks are a framework for dealing with the complexity that arises when applying probability theory in complex systems. They represent the structure of a system using a directed graph of random variables. Conditional independencies can be readily identified from the graph and are used to drastically reduce the complexity of inference. Model construction can be done manually using the intuitively appealing graphical interface provided. Alternatively, models can be learned from data via statistical principles such as maximum likelihood estimation and Bayesian estimation. The latter is the focus of much recent research and has attracted much attention in the AI, machine learning, and data mining communities.

This course is a comprehensive introduction to Bayesian networks. The coverage includes fundamental issues, recent developments, and applications.

Course objective:
The objective of this course is to bring the students to the forefront of Bayesian network research and application.

Course outline/content (by major topics):

  1. Introduction
  2. Probability Theory Basics
  3. Bayesian networks
  4. Basic inference: the variable elimination algorithm
  5. Conditional independence and graphs
  6. Inference and Caching: Clique tree propagation
  7. Advanced inference: Local structures
  8. Parameter learning
  9. Bayesian structure learning with complete data
  10. Bayesian structure learning with incomplete data
  11. Constraint-based approach to structure learning
  12. Bayesian network classifiers
  13. Bayesian network models for cluster analysis
  14. Latent structure discovery
  15. Application

Text book: n/a

Reference books/materials: Please refer to the course web site.

Grading Scheme:

  • Class participation 10% (Based on impression. So make yourself heard in class:-))
  • Unit summaries 35%
  • Oral presentation 10%
  • Project report 45% (35% content & depth, 5% organization and presentation, 5% English )

Background needed: Basic background in probability theory

Available for final year UG students to enroll: Yes.

Minimum CGA required for UG students: B+

Course Code: COMP573
Course Title: Computational Geometry

Instructor: Siu-Wing Cheng
Room: 3514
Telephone: 23586973
Email:
WWW page: http://cse.hkust.edu.hk/~scheng/

Area in which course can be counted: Foundations of Computer Science

Course description:
This is an introductory course in Computational Geometry. It deals with the design and analysis of algorithms for geometric problems. Examples of objects to be studied include Convex hulls, Voronoi diagrams, and Triangulations.

Course objective:
To give students the background for further research in geometric algorithms, modeling, and computation.

Course outline/content (by major topics):

  • Convex Hulls
  • Line Segment Intersection
  • Point Location
  • Voronoi Diagrams
  • Arrangements and Duality
  • Triangulations
  • Shortest paths
  • Curve reconstruction
  • Mesh generation

Text book:
M. de Berg, M. van Kreveld, M. Overmars and O. Schwarzkopf, Computational geometry---algorithms and applications, Springer-Verlag, 2000.

Reference books/materials: materials to be added by the instructor.

Grading Scheme:

  • Written assignments (30%)
  • Midterm (30%)
  • Final (40%)

Background needed: COMP271 (Background in algorithm design and analysis)

Available for final year UG students to enroll: Yes.

Minimum CGA required for UG students: B+

Course Code: COMP 610F
Course Title: Pervasive and Embedded Software Engineering

Instructor: S.C. Cheung
Room: 3543
Telephone: 23587016
Email:
WWW page: http://cse.hkust.edu.hk/~scc/hkust_only/comp610f/

Area in which course can be counted: software technology

Course description:
This is an advanced research-oriented course on the software design and development for pervasive and embedded software systems. The course overviews related research issues in software engineering, concurrency theory, object-oriented technologies and methodologies, software infrastructures, middleware, context management, experimentation and exception handling. The course consists of reading assignments, projects and presentations. Some parts of the course are theoretical.

Course objective:
To understand the underlying software engineering issues for the development of pervasive and embedded systems.

Course outline/content (by major topics):

  • Overview
  • Concurrency Theory
  • Unified Modeling Language
  • Experimentation
  • Software testing
  • Context-Aware Middleware
  • Wireless Sensor Networks
  • RFID Applications
  • Embedded Systems
  • Paper Presentation
  • Project Presentation

Text book: n/a

Reference books/materials:
Concurrency - State Models & Java Programs, J. Magee & J. Kramer, Wiley, 1999
Communication and Concurrency, R. Milner, Prentice-Hall, 1989
Java Concurrency in Practice, Brian Goetz et al., Addison-Wesley, 2006.

Grading Scheme:

  • Participation 10%
  • Class presentation of papers 20%
  • Assignment/Quiz 25%
  • Project proposal 5%
  • Project presentation and report 40%

Background needed: UML, Java programming, Operating systems, Automata theory

Available for final year UG students to enroll: Yes.

Minimum CGA required for UG students: permission of the instructor

Course Code: COMP641M
Course Title: Topics in Graphics: GPU Computation

Instructor: Pedro V. Sander
Room: 3535
Telephone: 23586983
Email:
WWW page: http://cse.hkust.edu.hk/~psander/

Area in which course can be counted: Vision & Graphics

Course description:
The Graphics Processing Unit (GPU) is particularly efficient for real-time rendering applications. Recently, it has also evolved into a highly parallel general purpose processor. In this course, we will cover recent research on GPU computation. In the first part, we present an in-depth analysis of the graphics hardware pipeline, including the most recent advances, such as geometry shaders. In the second part, we study recent, complex real-time rendering algorithms that take advantage of the added efficiency and functionality in order to render compelling 3D scenes in real time. Topics will include latest algorithms on lighting, shadowing, and shading. Finally, in the third part, we will study techniques that use the graphics pipeline for general purpose (non-rendering) computation. The research focus is on designing parallel algorithms that map efficiently to the GPU's graphics pipeline and are faster than their CPU counterparts. Applications include scientific algorithms, database query processing, and geometric optimization, among many others.

Course objective:
Students taking this course will gain an in-depth understanding of the GPU and learn to research and develop novel rendering algorithms and general purpose processing algorithms that run on the GPU.

Course outline/content (by major topics):

  • Overview of the Graphics Processing Unit (GPU)
  • Rendering algorithms
  • General purpose processing algorithms (GPGPU)

Text book: None.

Reference books/materials:
Research papers and course notes distributed by instructor.

Grading Scheme:

  • Lab assignments (35%)
  • Class presentation (15%)
  • Final project (50%)

Pre-requisites/Background needed:
Basic computer graphics background equivalent to COMP 341 is highly recommended, but not required for very strong PG students that are interested in GPGPU.

Available for final year UG students to enroll: Yes.

Minimum CGA required for UG students: Permission of the instructor.

Course Code: COMP 660K
Course Title: Peer-to-Peer Systems and Applications, Theory and Practice

Instructor: Bo Li
Room: 3524
Telephone: 23586976
Email:
WWW page: http://cse.hkust.edu.hk/~bli/

Area in which course can be counted: NE

Course description (can be more detailed than the one in the calendar):
The Peer-to-Peer (P2P) technologies have not only gained significant attentions in research community but also found its wide range of applications in practical systems. It is estimated that P2P traffic occupies 60-70% of the Internet Traffic today. The earlier driving force behind the P2P technology was to leverage the available resources at end systems such as bandwidth, storage space and computing capability. The P2P file sharing applications such as Napster, Gnutella and BitTorrent, Voice over IP applications such as Skype have gained explosive popularity in the past decade. There have been also significant interesting and development in P2P video streaming technologies.

This course discusses several fundamental issues in P2P systems and focuses on on the emerging P2P streaming system. Topics include P2P file distribution protocols, overlay multicast, incentive mechanism, structure P2P and unstructured P2P, and selected applications.

Course objective:
The objective of this course is to give students an overview of similarity search over database and let students get familiar with the basic techniques related to similarity search. Through the projects, students will learn how to start a research in this area.

Course outline/content (by major topics):

  1. Basic P2P technology
  2. P2P file distribution
  3. VoIP application
  4. Reputation and incentive mechanism
  5. Structure and unstructured P2P
  6. Overlay multicast
  7. Potpourri

Text book: N/A.

Reference books/materials: A list of technical papers

Grading Scheme:
This course will involve reading and presenting research papers, participating in class discussions, and completing a research project. Students are required to write a review for each paper presented in class. Students are also required to identify one particular problem for a research-oriented project, and carry out study on that topic.

  • Reviews: 40%
  • Presentations: 20%
  • Project: 40%

Pre-requisites/Background needed: Student enrollment needs the instructor's approval.

Available for final year UG students to enroll: No.

Course code: COMP 670P
Title: Topics in Theory: Metric Embeddings and Algorithms

Instructor: Mordecai Golin
Room: 3559
Telephone: 23586993
Email:
Web page: http://cse.hkust.edu.hk/~golin/

Area in which course can be counted: NO AREA

Course description:
The idea of metric embeddings (taking a problem in one space, projecting down to another space while preserving some properties, and then solving in the lower dimensional space) has become very popular in recent years. Applications include problems in machine learning, data mining and bioinformatics.
This course will provide a quick and dirty introduction to the basic concepts of metric embeddings followed by a survey of some recent applications in computer science.

Course objective:
To teach ourselves about a fast-growing research field in modern computer science

Course outline/content (by major topics):

The course will start with the instructor giving two or three introductory lessons on the basics. The remainder of the course will be participants
presenting papers. All students will be expected to

o read ALL of the papers assigned
o present two papers

For an example of the topics that might be covered please see these recent courses at CMU, MIT, Stanford, Toronto, Chicago and Caltech

http://www.cs.cmu.edu/~anupamg/metrics/
http://www-math.mit.edu/~goemans/18409.html
http://theory.stanford.edu/~tim/w06b/w06b.html
http://www.cs.toronto.edu/~avner/teaching/2414/index.html
http://ttic.uchicago.edu/~harry/teaching/teaching.html

Text book:
No textbook.
We will be reading recent papers

Grading Scheme: TBA

Background needed: COMP271 or equivalent and mathematical sophistication Enrollment is only with permission of the instructor

Available for final year UG students to enroll: No

Course Code: COMP 680K
Course Title: Topics in CE: Wireless and Mobile Computing: Wireless & Mobile Comp

Instructors:Yunhao Liu, Lionel M. Ni
Room: 3548, 3531
Telephone: 23587019, 23587009
Email: ,
Web page: http://cse.hkust.edu.hk/~ni/, http://cse.hkust.edu.hk/~ni/

Area in which course can be counted:Computer Engineering

Description: This is a seminar-style research-oriented course. The course will cover new advances in wireless and mobile computing networks and systems. Students should have sufficient knowledge in computer systems, operating systems, networking, and wireless communications. Students require the instructor's approval before taking the course.

Course objective: Research on wireless and mobile computing has recently received a great deal of attention world wide. This course will begin with the background and motivation of wireless communications. The course will cover from low-level sensor node design to high-level wireless and mobile applications. The focus of this course will be on new challenging research issues in this exciting research area.

Course outline/content(by major topics):
Lecture: Lecture material will be drawn from the readings and other sources. All lectures notes will be available in advance in PowerPoint format from the login page. Students are expected to read the material in advance, and participate in discussions, by offering their ideas and observations.
Class Attendance: Students are required to attend the class. To be excused from the class, students must provide the instructor with adequate advanced notice.

Text book: No text book is required.

Grading Scheme:

  • Class Procedure: All class materials will be available on this web site. All your final reports, project proposals, and other assignments should be submitted in electronic format (either pdf, ppt, or Word). Please read HKUST Conduct in Classroom too.
  • Plagiarism Policy: Students are expected to produce original research for their project, an original written project report and original written paper reviews.
  • Students may work together in teams to create/build their project, but the content of the collective project must be original.
  • The written project report must be original. If material produced elsewhere is included in the report, such as a graph or a written passage, then citations must be made within the report to the included material. Similarly, the slide presentation of the final project must include citations of any significant included material.
  • When presenting papers for discussion in class, students may use material without citation, such as slides produced by others on the Web.
  • Violations of this plagiarism policy will be grounds for grade reduction and/or potentially other punitive actions, in accordance with the University policy.

Prerequisite: COMP 680I or 680J and at least 1-year research experience on wireless sensor networks or p2p systems or permission of the instructor

Course code: COMP 680E
Title: High-Speed Internet Switches and Routers

Instructor: Mounir Hamdi
Room: 3506
Telephone: 23586984
Email:
Web page: http://cse.hkust.edu.hk/~hamdi/

Area in which course can be counted: Computer Engineering

Course description:
The focus of the course is on the design and analysis of high-performance electronic/optical switches/routers needed to support the development and delivery of advanced network services over high-speed Internet. Switches and routers and the KEY building blocks of the Internet, and as a result, the capability of the Internet in all its aspects depends on the capability of its switches and routers. The goal of the course is to provide a basis for understanding, appreciating, and performing research and development in networking with a special emphasis on switches and routers. The course begins with a survey of the state of the art in switching and routing. Then, it examines the issues involved in designing switches and routers for both the optical domain and the electronic domain. The issues include protocols, architectures, algorithms, and performance evaluation.

The course involves both a lecture component and project component. Projects will consist of practical designs of switches/routers and will typically be executed by a small team (2-3 people). During the first few weeks of the course we will suggest a number of possible areas and projects. Teams should submit formal project proposals. The projects will require a mid-semester status report and a demo and final report at the end of the semester. The course evaluation is based on a the project and a mid-term exam.

Course objective:
The Objective of this course is to provide the basis for understanding, appreciating, and performing research and development in advanced networking with a special emphasis on switches and routers.

Course outline/content (by major topics):

  • Introduction
    • General introduction about high-speed networking
    • Evolution of packet switches and routers, basic architectural components, some example architectures.
    • Architecture and operation of ¡°optical¡± circuit-switched switches/routers
    • Architecture and operation of ¡°optical¡± burst-switches switches/routers
  • High-Performance Packet Switches/Routers
    • Architectural alternatives
    • Virtual output queued (VOQ) switches
    • Design and analysis of unicast arbitration algorithms
    • Design and analysis of multicast scheduling algorithms
    • Providing quality-of-service guarantees on VOQ switches
  • Output-queued and Shared Memory Switches
    • Architectures, performance, and problems
    • Output scheduling: Motivation - providing bandwidth and delay guarantees, fairness - definitions and algorithms, practical considerations and practical algorithms, end-to-end delay guarantees
    • Differentiated Services
  • Network Processors: Table Lookup and Packet Classification
    • Table Lookup: Exact matches, longest prefix matches, performance metrics, hardware and software solutions.
    • Packet classifiers: For firewalls, QoS, and policy-based routing; graphical description and examples of 2-D classification, examples of classifiers, theoretical and practical considerations.
  • Congestion Control and Active Queue Management
    • Active queue management: Introduction and motivation, dropping packets to reduce congestion, dropping packets for QoS, packet dropping vs. packet scheduling, theory, practical algorithms.
  • Optical ¡°Circuit-Switched¡± Switches and Routers
    • Introduction and motivation
    • Optical Technology
    • Wavelength Division Multiplexing (WDM)
    • Architectural alternatives
    • Switch configuration and scheduling algorithms
  • Multiprotocol Label Switching (MPLS) and Qos for Internet (1 week)
    • Introduction and motivation for QoS
    • Traffic Engineering using MPLS
    • Implementation of MPLS and QoS on Switches/routers

Text book:
The course will rely on lecture notes, research papers, and book chapters to be provided to the students.

Grading Scheme:

  • Project: 60%
  • Exam: 20%
  • HW participation: 20%

Background needed: Introduction to Computer Networks

Available for final year UG students to enroll: Yes.

Minimum CGA required for UG students: Permission of the instructor

Course Code: COMP 696X
Title: Independent Studies: Mathematical Methods in Biomedical Image Analysis : Biomedical Image Analysis

Instructor: Albert C. S. Chung
Room: 3516
Telephone: 23588876
Email:
WWW page: http://cse.hkust.edu.hk/~achung/

Course description (can be more detailed than the one in the calendar):
This course gives an overview and focuses on new developments in computational techniques for the analysis of biomedical images.

Course outline/content (by major topics):
Biomedical Image Registration and Segmentation Scale Space and PDE based Methods of Image Analysis Surface and Volume Models of Anatomy

Text book: Nil.

Reference books/materials: Will be available on-line or distributed in class.

Grading Scheme:

Pre-requisites/Background needed: Permission of the instructor.

Available for final year UG students to enroll: Permission of the instructor.

Course code: COMP696Y
Title: Independent Studies: Advanced modeling from images

Instructor:Long QUAN
Room: 3506
Telephone: 23587018
Email:
WWW page: http://cse.hkust.edu.hk/~quan/

No. of Credits:3
Quota:5

Course description:
This course will review the fundamental topics in image-based modeling. It covers the fundamentals of three-dimensional reconstruction from multiple uncalibrated images, the computation of the camera geometry, and the representation of the objects and the scenes from the images. It also covers the development of graphics approach to modeling and introduces the interactive technology in the modeling loop using both graphics and vision based methods.

Course outline/content(by major topics):

  • Projective geometry,
  • Euclidean geometry,
  • single view geometry,
  • multiple view geometry,
  • optimal reconstruction of N views,
  • image-based rendering,
  • image-based modeling,
  • interactive methods of segmentation,
  • interaction in the modeling.

Text book:

Reference books/materials:
Hartley and Zisserman, Multiple View Geometry.
Research papers to be assigned.

Grading Scheme: project based.

Pre-requisites/Background needed: Some basic knowledge in computer vision and graphics. Permission of the instructor is required.

Available for final year UG students to enroll: No

Course code: COMP696Z
Title: Independent Studies: Semi-Supervised Learning

Instructor: Dit-Yan Yeung
Room: 3541
Telephone: 23586977
Email:
WWW page: cse.hkust.edu.hk/~dyyeung/

No. of Credits:3
Quota:3

Course description:
In the field of machine learning, semi-supervised learning (SSL) occupies the middle ground, between supervised learning (in which all training examples are labeled) and unsupervised learning (in which no label data are given). Interest in SSL has increased in recent years, particularly because of application domains in which unlabeled data are plentiful, such as images, text, and bioinformatics. The target audience of this course are advanced research students with strong background in machine learning to learn in depth recent advances in the emerging SSL paradigm. An expected outcome of the course is that students will be able to write up high-quality research papers on SSL that are of comparable quality to those in major machine learning conferences.

Course outline/content (by major topics):

  • Introduction
  • Taxonomy of semi-supervised learning methods
  • EM-based methods
  • Clustering with constraints
  • Transductive support vector machines
  • Semi-definite programming
  • Gaussian process models
  • Entropy regularization
  • Data-dependent regularization
  • Graph-based methods
  • Graph kernels
  • Spectral methods
  • Distance function learning
  • Applications

Text book:
Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien (eds.).
Semi-Supervised Learning. MIT Press, September 2006.

Reference books/materials: Research papers to be assigned

Grading Scheme:

  • Attendance: 10%
  • Class presentations and discussions: 40%
  • Term paper: 50%

Pre-requisites/Background needed: COMP621I, COMP621L or COMP621O. Permission of the instructor is required.

Available for final year UG students to enroll: No

Minimum CGA required for UG students: N/A

Course code: COMP 697B
Title: Independent Studies: Randomized & Probabilistic Algorithms

Instructor:Mordecai Golin
Room: 3559
Telephone: 23586993
Email:
Web page: http://cse.hkust.edu.hk/~golin/

No. of Credits:3
Quota: 1

Course description: To learn the basic techniques used in the

  1. the probabilistic analysis of algorithms
  2. the design and amalysis of ramdomized algorithms
  3. the probabilistic method

Course objective: To learn about the use of probability theory in the design and analysis of algorithms and discrete mathematics.

Course outline/content(by major topics):

  • Probabilistic Preliminaries
  • Derandomization
  • Chernoff Bounds
  • Hashing
  • Game Theoretic Techniques
  • Randomized Algorithms in Geometry
  • Online Algorithms
  • Number Theoretic Algorithms, e.g., Primality Testing
  • Graph Algorithms
  • Other topics depending upon time remaining

Text books: Randomized Algorithms, Jajeev Motwani & Prahakar Raghavan. The Probabilistic Method, Nog Alon & Joel Spencer. Introduction to Algorithms, Cormen, Leiserson, Rivest & and Stein.

Grading Scheme:Grades will be based on submitted assignments

Background needed: COMP271 or equivalent and mathematical sophistication. Enrollment is only with permission of the instructor

Available for final year UG students to enroll:Only with Permission of the Instructor

Please visit https://www.ab.ust.hk/wcr/cr_class_staf_main.htm for the timetable and quota.

Archive of past courses

This web page was created by Hong ZHOU on 08 December, 2006.

Last modified on 11 January, 2007.