Theory of Computation (Logic and Computation)

CSCI 440, Spring Semester, 2014

 

Instructor: Dr. Shieu-Hong Lin

Course Website:         csci.biola.edu/csci440TC/

Class:                        M W 1:30-2:45am

 

Course objectives:

¡P       Learn the syntax and semantics of Eclipse, a powerful programming language for constraint logic programming, to develop an in-depth understanding of the roles of constraint processing and search in problem solving.

¡P       Establish the problem solving capability using Eclipse and concepts from stochastic local search to cope with hard real-world combinatorial optimization and constraint satisfaction problems. 

¡P       Cultivate the foundational understanding of formal logic and its important applications in artificial intelligence, formal software/hardware verification, and problem solving.

¡P       Gain a solid understanding of computational complexity such as the concepts of complexity classes P, NP, NP-hard, and NP-complete and the implications of whether P=NP in computation.

 

Textbooks and References:

¡P       Krzysztof R. Apt and Mark, Constraint Logic Programming using Eclipse, Cambridge University Press, 2007. (Required)

¡P       Holger H. Hoos, Stochastic Local Search - Methods, Models, Applications, PhD thesis, TU Darmstadt, 1998.

¡P       Holger H. Hoos & Thomas Stützle, Stochastic Local Search Foundations and Applications, Morgan Kaufmann, 2004.

 

Components of the Final Grade

1. Class Presentation   and Discussion                                              15%

2. Reading and Participation                                                               15%

3. Homework& Programming Assignments                                       30%

4. Midterm                                                                                           20%

5. Final                                                                                                 20%

 

 

Weekly Progress Report for the Reading and Participation Credit:

Download the template of cumulative weekly 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, 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.

 

Submission of the Weekly Progress Report: By the end of every Wednesday, you should email the cumulative progress report as an attachment to Dr. Lin.

 

Course Website and Online Course Information: Check the course website (http://csci.biola.edu/csci440TC/index.htm) regularly for course announcements. The class web page will contain the most up-to-date information on class assignments, things to do, and due dates.  Records of the points you got from the assignments, test, and exams will be posted online on the Biola Blackboard system.

 

 

Tentative Schedule

¡P       Week 1          Logic programming and pure Prolog   

¡P       Week 2          A reconstruction of pure Prolog

¡P       Week 3          Arithmetic in Prolog

¡P       Week 4          Control and meta-programming

¡P       Week 5          Manipulating structures

¡P       Week 6          Constraint programming: a primer

¡P       Week 7          Iteration in ECLiPSe

¡P       Week 8          Top-down search with passive constraints

¡P       Week 9          The suspend library

¡P       Week 10        Constraint propagation in ECLiPSe

¡P       Week 11                Top-down search with active constraints

¡P       Week 12        Optimization with active constraints

¡P       Week 13        Constraints on reals

¡P       Week 14        Linear constraints over continuous and integer variables

¡P       Week 15        Applications

¡P       Final

 

 

ACADEMIC HONESTY POLICY: We are committed at Biola University to ethical practice in teaching, scholarship, and service.  As such, plagiarism and other forms of academic dishonesty will not be tolerated.  Please see the undergraduate/graduate student handbook and/or the departmental/program/school policy on academic honesty.  It is imperative that you present all written, oral, and/or performed work with a clear indication of the source of that work.  If it is completely your own, you are encouraged to present it as such, taking pleasure in ownership of your own created work.  However, it is also imperative that you give full credit to any and all others whose work you have included in your presentation via paraphrase, direct quotation, and/or performance, citing the name(s) or the author(s)/creator(s) and the source of the work with appropriate bibliographic information. To do otherwise is to put oneself in jeopardy of being sanctioned for an act or acts of plagiarism that can carry serious consequences up to and including expulsion from the university.

 

Students desiring accommodations on the basis of physical, learning, or psychological disability are to contact the Learning Center (x4542) located in room U137, on the upper level of the library.