2002-09-16

This course will focus on how to prepare a CS major student as a skilled computer programmer. There will be three major themes in this course -- computer algorithm designs, data structure, and computer program implementation techniques.

The computer algorithm design will focus on various methodologies, including divide-and-conquer, dynamic programming, combinatorial optimization, graph theory and its applications, randomized and amortized algorithm analysis. These methodologies will be illustrated by examples from ACM on-line problem archive, so that the student can learn to solve real-world problem.

 This course will also focus on advanced data structures. Several self-adjusting data structures, including splay trees and pointer-jumping trees for union-and-find operation will be introduced. The introduction of these advanced data structures will facilitate the efficiency of computer programs, and provide useful tools for other related applications.

The computer implementation techniques will cover various disciplines in computer programming, including structure programming, programming style, debugging techniques, system tools utilization, and object-oriented programming. The goal of this training is that the students will be able to establish a solid foundation in expression what they want to implement, so that they could write code to realize the algorithms they learn from the first part of the course.

This course will be accompanied by weekly homework assignments, mainly from the ACM on-line problem archive, to give the students a hand-on experience on how to solve difficult problems with computers. Therefore, extensive understanding of C/C++ programming environment is required. The students will need to understand how to write program, so that they can combine the idea of algorithm design with solid implementation techniques to solve real problem correctly.