Theory of Computation: Logic and Programming
CSCI 440, Spring 2012
To the Bottom
of the Page
Instructor: Dr. Shieu-Hong Lin
Email: 
Class: MW 10:30-11:45 am at BUSN 209 PC Lab
Office hours: MW 1:30-3:00pm.
About the cumulative progress report:
¡P Download this template of cumulative progress report. Keep updating this cumulative weekly progress report as a file throughout the semester. By the end of every Wednesday, you should incorporate information of what you have done and the amount of time you spent for the reading assignment, the lab assignment, the programming assignment, or other written assignments since last Wednesday into the cumulative progress report. This file serves as the basis for you to gain the credit of ¡§Reading/Participation¡¨, which accounts for 15% of the total grade weight..
¡P Submission of the cumulative progress report (every Wednesday): By the end of every Wednesday (starting from Feb. 8), you should email the cumulative progress report as an attachment to Dr. Lin.
*************************************************************************************************
Week 1: Logic Programming and Pure Prolog. Progress
report and Homework#1 below due: Wednesday, Feb.
8.
Reading#1 (3 points, Reading + Participation):
due: Wednesday, Feb. 8.
¡P
Read Chapter 1 of Constraint Logic Programming using Eclipse.
¡P
Read Chapter 1 of A
Quick and Gentle Guide to Constraint Logic Programming via ECLiPSe.
(Download the book as a rar file and unzip it using 7-zip or others.).
¡P
Use Eclipse to play with the following sample
logic programming programs about family relationship 1, 2 and natural numbers 3 and 4.
Homework#1 (4 points): Do all Exercises 1.1~1.5 of Constraint Logic Programming using Eclipse and report
your findings in your progress report. due: Wednesday,
Feb. 8.
Class Presentation and Discussion: Benjamin and Leah on Reading #1 of Constraint Logic Programming using Eclipse (Feb 8 and/or 13)
Quiz#1: in class, open-book test Wednesday,
Feb. 8.
*************************************************************************************************
Week 2: Basics of Combinatorial
Optimization, Search, and Complexity. Progress report and Homework#2 below due: Wednesday, Feb. 15.
Reading#2 (3 points, Reading + Participation):
due: Wednesday, Feb. 15.
¡P
Review Chapter 1 of Constraint Logic Programming using Eclipse.
¡P Read Combinatorial Optimization, Search, and Complexity from Stochastic Local Search Foundations and Applications.
Homework#2 (12 points) programming the symbolic support of integers and arithmetic operations
on them: due: Wednesday, Feb. 15.
*************************************************************************************************
Weeks 3: A reconstruction of Pure
Prolog
- Reading#3: Chapter 2
and Chapter 3.
Class Presentation and Discussion: David and Bryan regarding Reading#2 on Combinatorial Optimization, Search, and Complexity and Homework#2 (Feb 22)
Quiz#2: Allocate one hour for this quiz (no Prolog
interpreter allowed, open-book test) and email your solutions back to me by Monday, Feb. 27.
*************************************************************************************************
Weeks 4: More on Pure Prolog
- Reading#4: Review Chapter
1, Chapter 2, and Chapter 3.
Homework#3 (8 points): All the end-of-chapter exercises of Chapter
2 and Chapter 3.
Class Presentation and Discussion: Matthew and Brandon on Reading#3 and Homework#3 (Feb 27 and/or 29)
*************************************************************************************************
Week 5: Control and
meta-programming. Progress report and the following
assignments due: Wednesday, March. 7.
- Reading#5: Chapter 4.
- Homework#4 (12 points): Write a prolog
program for doing merge sort. The quick sort
program in Chapter 3 can serve as a helpful example about how this may be
implemented. Here is the basic framework
of how the program may look like.
Class Presentation and Discussion: Samuel and Steven on Reading#5 and Homework#4 (Monday, March 12)
*************************************************************************************************
Weeks 6-7: More on meta-programming / Manipulating structures +
Mission Conference. due: Wednesday, March. 21.
- Reading#6-7: Chapter 5.
- Homework#5
(8 points): All the end-of-chapter exercises of Chapter
4 and Chapter 5.
- Homework#6
(12 points): Write a prolog sorting program
that implements selection
sort. The quick sort
program in Chapter 3 can serve as a helpful example about how this may be
implemented. Try to work it out on your own. If you have tried but still
feel need some more hints, see this basic
framework of how the program may look like.
Class Presentation and Discussion: Benjamin and Leah on Reading#6 and Homework#5, #6 (Monday, March 12 and/or 19)
Quiz#3
(Solution) : (No prolog interpreter allowed for
the first three problems) Wednesday, March. 21.
*************************************************************************************************
Week 8: Introduction
to Constraint Programming. due:
Wednesday, March. 28.
- Reading#8: Chapter 6.
Class Presentation and Discussion: David and Bryan on Reading#8 (Monday, March 26 and/or 28)
*************************************************************************************************
Week 9: Iteration
in Eclipse due: Wednesday,
April 4.
- Reading#9: Chapter 7.
- Homework#7
(8 points): All the end-of-chapter exercises of Chapter
6 and Chapter 7.
Class Presentation and Discussion: Matthew and Brandon on Reading#9 (Monday, April 2 and/or 4)
*************************************************************************************************
Weeks 10-11: Top-down
Search with Passive Constraints due:
Wednesday, April 18.
- Reading#10-11: Chapter 8.
Class Presentation and Discussion: Samuel and Steven on Reading#10 (Monday, April 16 and/or 18)
*************************************************************************************************
Week 12: The suspend
library due: Wednesday,
April 25.
- Reading#12: Chapter 9.
Class Presentation and Discussion: Benjamin and Leah on Reading#12 (Monday, April 23 and/or 25)
Quiz#4: Write your
own brute-force Prolog search program like the N-Queen program in chapter 7 to search for magic squares of any given order n. Here is a possible framework to do it. due: Wednesday, April 25.
*************************************************************************************************
Weeks 13: Constraint Propagation in
Eclipse. Progress report and the following
assignments due: Wednesday, May 2.
- Reading#13: Chapter
10.
- Homework#8
(15 points): Rewrite your magic squares program to improve the efficiency using the suspend library. You program
should describe the constraints in terms of the suspend library first and
search for the solutions with the delayed goals handled by the suspend
library.
Class Presentation and Discussion: David and Bryan regarding Reading#13 on and Homework#8 (Monday April 30 and/or May 2)
*************************************************************************************************
Weeks 14: Top-down Search with Active
Constraints in Eclipse. Progress report and the following
assignments due: Wednesday, May 9.
- Reading#14: Chapter
11.
Class Presentation and Discussion: Matthew and Brandon regarding Reading#14 (Monday May 7 and May 14)
Quiz#5
on Chapters 9, 10, and 11 (in-class open-book test, no Prolog interpreter allowed,):
Wednesday, May 9.
*************************************************************************************************
Weeks 15: Optimization with Active
Constraints in Eclipse. Progress report and the following
assignments due: Wednesday, May 16.
- Reading#14: Chapter
12.
Class Presentation and Discussion: Samuel and Steven on Reading#15 (Monday May 14 and 16)
*************************************************************************************************
Final exam (Take-home open-book test during Final Exam
Week) Monday May 21 10:30am ~ Thursday May 23.
External resources:
¡P
Holger
H. Hoos & Thomas Stützle, Stochastic
Local Search Foundations and
Applications, Morgan Kaufmann, 2004.
¡P List all source code of sample programs in Constraint Logic Programming using Eclipse.
¡P
Eclipse Constraint Logic Programming: (i)
homepage, (ii) online user manual,
(iii) online reference
manual.
To the Top of the Page