CSC 200  Undergraduate Problem Seminar, Spring 2002

• General course information
• Reading List (last updated on April 4)
• Project assignments
• Project 3.  Software Adaptive Cache (SAC),
• Phase II current best results
• Phase I is due midnight Wednesday, April 17.  Phase II is due midnight Sunday, April 28.
• Project Three groups.
• Project 2.  Hyper Min-Cut
• Description
• Phase II is due midnight Sunday, April 7.  The design review should be done by Wednesday, March 27 to leave enough time for implementation.  There will be no extension since we need to have a third project before the semester ends.
• Phase I demonstration.
• Phase I projects' performance on standard test cases.
• Phase I starts on Wednesday, Feb. 19.  Min-cut graph package is due Saturday, March 2.  The written part is due Friday,  March 8.
• Project 2 groups
• Project 1.  XML Parser Generator.  See lecture notes for a basic description.  It is intentional that the description is very high-level so that you can approach a solution with the full freedom in design.  The Phase I of your design and implementation will be judged not only by our graders but also by your classmates.
• Current project groups with links to Phase I presentation files
• Phase I group presentation:
• 4:40pm-7:30pm, Feb. 5, CSB 209
• Session I
• Session II  (immediately following Session I)
• Phase II
• See lecture notes for a high-level description of interface
• Due midnight Friday, February 15.
• Phase II group presentation

General Information

• 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.)
• Programming Languages Pragmatics, by Michael Scott, Morgan Kaufmann, 2000.  (Sections on scanning and recursive-descent parsing.)
• Grading
• 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 self-contained
• 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.
• Additional reading
• Lecture notes on object orientation, which explains the concept of type, polymorphism, interface, class, and inheritance.  Course webpage of CS 254, Fall 2001.

Reading List

• Cache Optimization
• Adaptive cache optimization
• "Improving Cache Performance in Dynamic Applications through Data and Computation Reorganization at Run Time" , Chen Ding and Ken Kennedy, PLDI '99.
• Classical material
• Algorithm view

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.
• Compiler view

Chapter 8 and 9, "Optimizing Compilers for Modern Architectures" by Allen and Kennedy, Morgan Kaufmann Publishers.  (available at Carlson library)
• Architecture view

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 too)
• Software engineering
• "No 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.)
• Graph algorithms
• "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 is fine.
• "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.)
• An interactive web applet for maximum/minimum cut is available from Remote Interactive Optimization Testbed (RIOT).
• Language design
• "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 article on the expressive power of programming languages by Matthias Felleisen in 1991.
• Interoperability.  Chapters 12 to 15, Szyperski book (see list of textbooks, on reserve in Calson).
• Programming tools
• "Efficient Path Profiling", Thomas Ball and James Larus, MICRO-29, December 1996.
• "Catching Bugs in the Web of Program Invariants" , Cormac Flanagan, Matthew Flatt, Shriram Krishnamurthi, Stephanie Weirich, Matthias Felleisen, PLDI '96.
• "Improving Cache Performance in Dynamic Applications through Data and Computation Reorganization at Run Time" , Chen Ding and Ken Kennedy, PLDI '99.
• Data modeling
• Entity-Relationship model
• "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)