Johns Hopkins Computer Science Home
Johns Hopkins University The Whiting School of Engineering

Declarative Methods
Prof. Jason Eisner
Course # 600.325/425 - Spring 2017

search tree

Announcements


Basic Course Information

Lectures:MWF 3-4 or sometimes 3-4:15, Shaffer 304.
Prof: Jason Eisner - (image of email address) ((image of email address))
TA: Patrick Xia - (image of email address)
CA: Xiaochen Li - (image of email address)
Weekly discussion session: TA-led session for solving problems together:
Mondays 6pm, Maryland 30
Discussion site: https://piazza.com/class/iyjuapy8tnz4zl
Office hrs: For Prof: MW 4pm after class; or by appt in Hackerman 324C
For TA: Tue 7:30-9pm, Hackerman 306; or by appt
Web page:http://cs.jhu.edu/~jason/325
Textbook: None, as I don't know of any other courses like this one. Suggestions welcome. I may assign some readings.
Computer accounts: You will need an account on the CS undergrad machines (ugrad1-ugrad18, etc.). That is where the software will be installed, and where your work will be tested.
It's okay to work on some other machine where you have installed the software yourself -- but you must make sure your code runs on the ugrad machines before you hand it in.
Policies: Academic integrity: read this! It says your work must be your own, etc.
Homework submission procedure: Announced on Piazza
Lateness: floating late days policy
Announcements: Read mailing list and this page!
Requirements and grading:

For 600.325 students: 5% class participation (this makes a difference!), 50% assignments, 15% midterm, 30% final.

For 600.425 students: 25% (TBA) for term project, with the rest partitioned as for the 325 students. You might also be assigned extra reading, extra questions, or a class presentation.

Course catalog entry

600.325/425. Declarative Methods (3 credits). Suppose you could simply write down a description of your problem, and let the computer figure out how to solve it. What notation could you use? What strategy should the computer then use? In this survey class, you'll learn to recognize when your problem is an instance of satisfiability, constraint programming, logic programming, dynamic programming, or mathematical programming (e.g., integer linear programming). For each of these related paradigms, you'll learn to reformulate hard problems in the required notation and apply off-the-shelf software that can solve any problem in that notation -- including NP-complete problems and many of the problems you'll see in other courses and in the real world. You'll also gain some understanding of the general-purpose algorithms that power the software. [Analysis]

Prereq: 600.226, Calc II. Students can only receive credit for 600.325 or 600.425, not both.

Another perspective on what this course is about

You could regard this as an alternative programming course. A programming course teaches you how to use a programming language to solve problems. It also outlines how your computer will actually execute the code you write in that programming language.

The languages we'll be using aren't conventional programming languages. They are powerful problem description languages that focus on special-purpose computation. These languages are declarative. That is, you use them to specify a problem, not a solution. But they are backed up by solvers that do a good job of finding the solution efficiently in most cases. This course will survey some declarative languages and examine the kinds of solvers that people have written for them.

How do these languages relate to conventional ones? Conventional languages help you build arbitrary large systems in a modular way. You can think of a solver as a particular powerful module that handles many problems of a particular sort. To explain your particular problem to the solver, you use a declarative language.


Schedule

This class is in the "flexible time slot" MWF 3-4:30. Please keep the entire slot open. Class will usually run 3-4, followed by office hours in the classroom from 4-4:30 (stick around to get your money's worth). However, class will sometimes run till 4:15 in order to keep up with the syllabus. I'll try to give advance notice of these "long classes," which among other things make up for no-class days when I'm out of town.

We'll also schedule a once-per-week discussion session led by your TA. This optional session will focus on solving problems together. That's meant as an efficient and cooperative way to study for an hour: it reinforces the past week's class material without adding to your homework load. Also, if you come to discussion session as recommended, you won't be startled by the exam style — the discussion problems are taken from past exams and are generally interesting.

Format: A typical unit will last two weeks. The first week will cover a particular declarative language. The second week will look at strategies used by modern solvers for that language. Your homework (assigned at the end of the first week) will ask you to program in the language, using specific solver software.

Warning: The schedule may change. Future lectures and assignments may also change—if we haven't gotten to something yet, you are looking at last year's version.

Warning: I sometimes turn off the PDF links when they are not up to date with the PPT links. If they don't work, just click on "ppt" instead.

Week 1: Introduction  (Jan 30, Feb 1, 3)

Weeks 2-3: Satisfiability  (Feb 6, 8, 10; Feb 13, 15, 17)

Weeks 4-5: Constraint Programming  (Feb 20, 22, 24; Feb 27, Mar 1, 3)

Project proposals for 600.425 due on Mar 6

Weeks 6-7: Logic Programming  (Mar 6, 8, 10; Mar 13, 15)

Midterm Exam  (Mar 17)

Spring Break  (Mar 20-26)

Week 8: Soft Constraints (Mar 27, 29, 31)

Weeks 9-10: Mathematical Programming  (Apr 3, 5, 7; Apr 10, 12, 14)

Weeks 11-12: Dynamic Programming  (Apr 17, 19, 21; Apr 24, 26, 28)

Week 13: Catch-up, Review, or Guest Lectures (May 1, 3, 5)

Final Exam  (Sat, May 13, 2-5pm)

Term Project  (for 600.425)


Old Materials

Here are some materials that we covered in past years but will probably omit this year.

Linear Classifiers

(This topic is now covered well in 600.475 Machine Learning.)

Satisfiability Modulo Theories

(Ken Roe gave a guest lecture on this topic in 2013.)