[ General Information
| Course Outline
| Other Pointers
[ Announcements ]
Course description: This course is for students interested in optimization of programs that are written in very high-level languages. We will look particularly at database languages (including XML query languages) and collection classes in object-oriented languages (such as Java collection classes). The course will mainly discuss general and systematic methods for developing correct and efficient algorithms and programs starting from specifications or queries written in these very high-level languages. Each student will do a project that involves designing and implementing an advanced database application, evaluating and improving an XML implementation, developing and implementing a general optimization method, finding and fixing performance bugs in an existing application, or other tasks that exploit or support the methods studied. | Prerequisites: a programming language or compiler course, an algorithm course, a database course, and skills for programming in a high-level language like Java; or permission of the instructor. | Credits: 3.
Instructor: Annie Liu | Email: liuATcsDOTsunysbDOTedu | Office: Computer Science 1433 | Phone: 632-8463.
Hours: Wed 10:00AM-12:30PM, in Computer Science 1211. | Office hours: after class or by appointment.
Textbook: There is no textbook for the course; relevant papers and additional references will be given as the course proceeds. Taking good lecture notes is an important part of the course.
Grading: Weekly homework and a course project, each worth 50% of the grade; no exams. No credit for late submissions.
Course homepage: http://www.cs.sunysb.edu/~liu/cse626/, containing all course-related information.
We will first overview the core of database languages (including relational, object, and XML query languages) and collection classes in object-oriented languages, and discuss the problem of developing correct and efficient algorithms and programs starting from specifications or queries written in these very high-level languages.
We will then focus on the main part of the course: a systematic method for optimization of programs and for design of algorithms and data structures starting with very high-level problem specifications. The method has three important components: the central component embodies the core idea, which is to replace repeated expensive computations with efficient incremental operations; a higher-level component determines how computation proceeds iteratively, and a lower-level component determines appropriate data-structure support.
The method will be discussed for our favorite language X, yet to be defined:-). In particular, we will first concentrate on operations involving sets and maps, the most important high-level constructs for data manipulation. We will then discuss the same method for optimizing the likely more familiar constructs, loops and arrays, and perhaps less familiar constructs, recursive functions and structures. We will finally discuss the method applied to rules and objects in general.
We will use nontrivial problems (taken from many applications in computer science) as examples throughout the course, and we will add more such problems as time permits. We will also motivate many program (i.e., sophisticated data) analysis problems as we proceed.
Course work: The course project will be determined based on the interests of both you and me and will be due on the last day of class. The weekly homework will mainly be to complete and organize the lecture notes you take in each class, and to answer some questions given in class, and will be due on the following Tuesday before 11am; it will be partly graded, possibly with suggestions for improvement, and returned to you before the next class; finally, your entire notes will be completely graded near the end of the class. You will get full credit if you take perfect notes, but since one can not generally do so, you may still get full credit by adding your own examples or explanations, asking good questions, etc.
Handout Q: Questionnaire
Papers and slides are handed out in class.
SETL2: A set-based
programming language. Version 2.3 (under directories binaries-2.3
and ide-2.3) supports major Unix platforms and Windows; version is 2.2
(under directory binaries-2.3) supports more older platforms.
SETL2 is documented in The SETL2 Programming Language by W. Kirk Snyder. An introduction by Robert Dewar and a description of developments including object-oriented features by Kirk Synder also come with the distribution.
Some sample programs and inputs are provided by Bob Paige (you could follow the installation instructions there, but you need to use the new ftp site ftp://cs.nyu.edu/pub/languages/setl2 and you can get the newer version 2.3).
Finite differencing of computable
expressions, by Robert Paige and Shaye Koenig.
ACM Transactions on Programming Languages and Systems, 4(3):402-454, 1982.
Program Derivation By Fixed Point
Computation, by Jiazhen Cai and Robert Paige.
Science of Computer Programming, 11:197-261, 1989. (ps)
Real-time simulation of a set machine on a
RAM, by Robert Paige.
Computing and Information, Vol. II, pages 69-73, 1989. (ps | notes by Paige)
Viewing a program transformation system at
work, by Robert Paige.
Proceedings of the Joint 6th Intl. Conf. on Programming Language Implementation and Logic Programming (PLILP) and 4th Intl. Conf. on Algebraic and Logic Programming (ALP), pages 5-24, 1994. (ps)
Old APTS: old version of the Automatic
Program Transformation System developed by Paige (guide
to local installation, usage, examples). Development of old APTS
stopped around 1993 when Paige took on an effort to develop new APTS,
aiming for a more general automatic program transformation system.
Most unfortunately, Paige passed away in 1999, and new APTS was not
completed and could not run the transformations developed by
Papers for the handout slides on optimizing loops [Liu-IFIP 97] and arrays [LS-ICCL 98 / LSLT-TR 02 (under minor revisions to be accepted by TOPLAS)], recursive functions and recursive data structures [LS-ESOP 99 / HOSC 03, LS-PEPM 00, LS-PEPM 02], and rules [LS-TR 02/03] can be found following links under Selected Publications on Annie's homepage
Ghostscript, Ghostview and GSview: Ghostview and GSview are for viewing and printing Postscript documents (some of the handouts for this course will be in this format). If you use Linux, then this software is already installed on your machine. On Windows, you need to download both Ghostview and Ghostscript (and also some fonts). Unzip Ghostview and run setup.exe. It will unpack and install the rest.
The gzip homepage: GNU zip for compression.
The official title of the course is Advanced Programming Languages, but you do not need to have taken CSE526 (or other graduate-level courses); the most important prerequisites are programming skills, knowledge of algorithms and data structures, and motivation for studying a systematic method for developing correct and efficient algorithms and programs.
You should learn all information on the course homepage. Check the homepage periodically for Announcements.
Do all course work. The homeworks and projects are integral parts of the course as they provide concrete experiences with the abstract ideas covered in the class.You are strongly encouraged to discuss with others and look up references, but you should write up your own solutions independently and credit all sources that you used. Any plagiarism or other forms of cheating will result in an F or worse.
Disability: If you have a physical, psychological, medical or learning disability that may have an impact on your ability to carry out assigned course work, please contact the staff in the Disabled Student Services office (DSS), Room 133 Humanities, 632-6748/TDD. DSS will review your concerns and determine with you what accommodations are necessary and appropriate. All information and documentation of disability are confidential.