[ General Information
| Lectures
| Handouts
| Other Pointers
| Requirements
]
[ Announcements
]
Course description: This course is officially an advanced graduate topics course, but the materials are for anyone who likes or dislikes algorithms/programming/problem-solving, for good reasons, but who would like to (1) get better at them, by learning a systematic method, (2) see applications in security policy frameworks, database applications, web applications, program analysis, and many more, and (3) be exposed to cool languages, such as Python. Each student will do a project that involves designing and implementing an advanced database application, specifying and checking an existing computer program, developing and implementing a general optimization method, or other tasks that exploit or support the methods studied. Good projects can also lead to research projects and publications. | Prerequisites: a programming language or compiler course, an algorithm course, a database course, and skills for programming in a high-level language such as Java; or permission of the instructor. | Credits: 3.
Instructor: Annie Liu | Email: liu@cs.sunysb.edu | Office: Computer Science 1433 | Phone: 632-8463.
Hours: Mon 11:30AM-2:00PM, in Computer Science 2129 | Office hours: after class or by appointment.
Textbook: There is no textbook for the course; relevant materials 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. Homework is always due in class the following Monday. Reduced credit for late submissions, 20% per day.
Course homepage: http://www.cs.sunysb.edu/~liu/cse690/, containing all course-related information.
1. Overview: problems, application domains, challenges, outline of methods and languages.
2. A language: Python.
3. An application: role-based access control (RBAC, an ANSI standard).
4. Computing polynomials, etc. --- the basic idea: incrementalize.
5. Set expressions --- incrementalize and implement.
6. An "application": relational calculus implementation.
7. Recursive functions --- iterate and incrementalize.
8. Logic rules --- iterate, incrementalize, and implement.
9. Object abstraction --- incrementalize across object abstraction.
10. An "application": querying complex graphs.
11. Summary: iterate, incrementalize, implement.
12. Elaboration and project discussion.
13. More on applications and implementations.
14. Project presentations: individual or team or whole class.
Handouts
Handout Q: Questionnaire
ANSI Standard for Role-Based Acces Control, ANSI INCITS 359-2004, 2004.
Role-Based Access Control: A Simplified Specification, SB TR DAR 05-24, 2005.
Slides for optimizing arithmetic and array operations by incrementalization.
Finite differencing of computable expressions, by Robert Paige and
Shaye Koenig. ACM TOPLAS 1982.
Core role-based access control: Efficient implementations by transformations, ACM SIGPLAN PEPM 2006.
Lecture notes for efficiently implementing join queries.
Slides for optimizing recursive functions by incrementalization.
Slides for generating efficient implementations from rules by incrementalization.
Slides for incrementalization across object abstraction.
Slides for parametric regular path queries and querying complex graphs.
Slides and a paper for an overview/summary: iterate, incrementalize, and implement.
Viewing a program transformation system at work, by Robert Paige. Joint 6th PLILP and 4th ALP, 1994.
Handout P: Presentation evaluation
Other Pointers
Python Tutorial
(Section on Data Types
)
| Reference Manual
| Library Reference
Python
| Python Documentation (v2.4.2)
Core RBAC executable specification in Python
Old APTS: old version of the Automatic Program Transformation System developed by Paige (guide to local installation, usage, examples)
InvTS: currently under development at Stony Brook, based on the
incrementalization rule language in LSGRL-OOPSLA05
(demo given in class)
Requirements
This course is officially an advanced graduate topics course, but you do not need to have taken 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 basic concepts and methods covered in the class.
Homeworks and projects must be done individually, unless specified otherwise; you may discuss with others and look up references, but you must write up your 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.