Theory of Computation: Logic and Programming

CSCI 440, Spring 2012

 

To the Bottom of the Page

 

Instructor:     Dr. Shieu-Hong Lin

Email:              Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: LinEmail

Class:             MW 10:30-11:45 am at BUSN 209 PC Lab

Office hours:   MW 1:30-3:00pm.

 

Course Syllabus

 

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 + Arithmetic in Prolog.  Progress report and the following assignments due: Wednesday, Feb. 22.

 

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 and Arithmetic in Prolog.  Progress report and the following assignments due: Wednesday, Feb. 29.

 

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.

 

 

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.

 

 

 

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.

 

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.

 

 

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.

 

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.

 

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.

 

 

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.

 

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.

 

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. 11:30pm

 

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