CSC 200 Undergraduate Problem Seminar, Spring 2002
Chen Ding, CSB 710, ext. 51373
TAs: Yutao (Julie) Zhong (firstname.lastname@example.org) and
Andrew Kwon (email@example.com)
Lectures: 4:50 to 6:05pm, Tuesdays and Thursdays, CSB 601
Office hours: Ding, by appointments; Julie Zhong, 2pm-3pm Wednesdays
and 11am-12pm Fridays.
Description In this course, students will develop large and
sophisticated programs and in the process study problems and solution approaches
in software specification, design, implementation, testing, and maintenance.
The emphasis will be on object-oriented and component-based software construction.
Projects will be completed through team work, including working with team
members on assigned problems and selecting and using tools developed previously
developed by other teams. Students will spend significant amounts
of time outside class. Programs will be written in Java and C/C++.
The course will also cover applied algorithms in program syntax analysis,
graph theory, pattern matching, program data optimization, and artificial
intelligence. The technical topics will be organized around two themes---programming
automation and program optimization. Through course projects, students
will use and improve these algorithms to produce software tools of
non-trivial practical or research value.
Finally, the course will use a third of its class time in invited lectures
from other faculty members in the department. They will introduce
students to current research in artificial intelligence, computer vision,
theory, and other areas of computer systems.
Textbooks. There is no single textbook for this course.
Selected chapters of the following books will be covered. They are
all on-reserve at Carlson Library.
Introduction to Algorithms, 1st or 2nd Edition, by T.H. Cormen, C.E. Leiserson,
R.L. Rivest, and C. Stein, MIT Press and McGrew Hill Press. (Chapters
on graph/flow algorithms.)
Component software - beyond Object-Oriented programming, by C. Szyperski,
ACM Press and Addision-Wesley 1997. (Chapter 4 through 7.)
Design Patterns: Elements of Reusable Object-Oriented Software,
Gamma, Helm, Johnson, and Vlissides, Addision-Wesley, 1995. (Will
cover selected patterns.)
Languages Pragmatics, by Michael Scott, Morgan Kaufmann, 2000.
(Sections on scanning and recursive-descent parsing.)
80% for four projects, each project is 20% and consists of two phases
for each phase of a project: 2% design, 6% implementation, 2% testing
Phase II will use the tools produced in phase I, but otherwise they are
10% mid-term (March 5, in class)
10% final exam. Students who score near perfect in projects and in
mid-term will get A grade and do not need to take the final.
Adaptive cache optimization
The chapter on "Hash Tables" in book Introduction to Algorithms, 1st
or 2nd Edition, by T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein,
MIT Press and McGrew Hill Press.
Chapter 8 and 9, "Optimizing Compilers for Modern Architectures" by
Allen and Kennedy, Morgan Kaufmann Publishers. (available at Carlson
Chapter 5, "Computer Architecture: A Quantative Approach" by Henessey
& Patterson, Morgan Kaufmann Publishers. (available
at Carlson library)
Operating system view (virtual memory)
Section 12.3, "Operating Systems: A Modern Perspective", Second Edition,
by Gary Nutt, Addison Wesley Publisher. (available at Carlson
under reserve for CS 256, any other OS textbook should cover this topic
Silver Bullet: Essence and Accidents of Software Engineering", Fred
Brooks, IEEE Computer, April 1987.
Software Engineering, Stephen R. Schach, published by Aksen Associates,
1990, donated to Calson Library by Professor Charles Merriam. You should
read at least the following sections: Scope of SE (Chapter 1). Difficulties
(Chapter 2). Software life-cycle models (Chapter 3). Walkthroughs
and inspections (Sections 6.6, 6.7, and 6.11.3. (The book is on course
reserve in Calson.)
"Maximum Flow", Chapter 26, Introduction to Algorithms, 2nd Edition, by
T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, MIT Press and McGrew
Hill Press. The corresponding chapter in the first edition
"The Complexity of Multiterminal Cuts", E. Dahlhaus, D.S. Johnson, C.H.
Papadimitrious, P.D. Seymour and M. Yannakakis, SIAM Journal on Computing,
Volume 23, Number 4, pp. 864-894. (It is part of the course reserve
in Calson library by Monday. Only the sections related to multi-way cut
on normal graphs are scanned. The library has the journal if you
want to read the rest of paper, which is about multi-way cut on planar
graphs and trees.)
interactive web applet for maximum/minimum cut is available from Remote
Interactive Optimization Testbed (RIOT).
"The Next 700 Programming Languages", Peter J. Landin, Communications of
ACM, Volume 9 (3), 1966. (Available at ACM
Digital Library through a university subscription). Interested
students may want to take a look at a latter, more comprehensive and theoretical
on the expressive power of programming languages by Matthias Felleisen
Interoperability. Chapters 12 to 15, Szyperski book (see list of
textbooks, on reserve in Calson).
"Efficient Path Profiling",
Thomas Ball and James Larus, MICRO-29, December 1996.
Bugs in the Web of Program Invariants" , Cormac Flanagan, Matthew Flatt,
Shriram Krishnamurthi, Stephanie Weirich, Matthias Felleisen, PLDI '96.
Cache Performance in Dynamic Applications through Data and Computation
Reorganization at Run Time" , Chen Ding and Ken Kennedy, PLDI '99.
"The entity-relationship model: toward a unified view of data", Peter Pin-Shan
Chen, ACM Transactions on Database Systems (TODS), Volume 1 (1), 1976.
(Available at ACM Digital Library
through a university subscription)