CPSC 203: Mathematical Foundations of Computer Science
Fall 1998

Class Time: MWF, 11:00-11:50am
Location: MCEC 220

Chuck C. Liang
Office: MCEC 343
Office Phone: (860 297) 5395
Designated Office Hours: Monday-Thursday 3-4pm, or by appointment
Email: chuck.liang@mail.trincoll.edu

Teaching Assistant: Jamie Mazur

Course Description:

An introduction to the principles of logic and discrete mathematics required in the study of computer science. Topics covered may include propositional and predicate logic and their relationship to general proof techniques used in computing and correctness proofs of programs; mathematical induction applied to recursion and recurrence relations; set theory with an emphasis on infinite sets used in computing; counting principles useful in analyzing graphs and trees; relations and functions and their relationship to databases and functional programming languages; Computer programs may be used to explore concepts examined in the course.
Prerequisites: CPSC 115L and Math 131.

Required Textbook: ``Logic and Discrete Mathematics: A Computer Science Perspective'' by W. K. Grassman and J-P Tremblay.

Reference Material:

  1. ``Discrete Mathematics'' By K. Ross and C. Wright
  2. ``Logic for Computer Science'' By S. Reeves and M. Clarke


Class Web Page: http://www2.trincoll.edu/~cliang/c203/


Tentative List of Topics:

  1. Overview and examples of discrete math in computer science
  2. Propositional logic (Chap. 1)
    1. Syntax: symbols and connectives
    2. Semantics: truth tables
    3. Natural Deduction
  3. Predicate logic (Chap. 2)
    1. Terms, variables and quantifiers
    2. Basic model theory
    3. Axiomatizations
    4. Soundness and completeness; Goedel's theorem
  4. Induction and recursion (Chap. 3)
    1. Inductions on natural numbers
    2. Inductive definitions
    3. Recursive programs and induction
    4. Inductive proofs of correctness of programs.
  5. Programming with Logic (Chap. 4)
    1. Automated Proof search and unification
    2. The Prolog programming language
    3. Implementation of Axioms and Theories.
    4. Negation and Closed World Assumption.
  6. Sets, Relations and Functions(Chaps. 5,6)
    1. Basic Set Theory
    2. Representing sequences and functions
    3. Equivalence relations and partial orders
    4. Uncountable sets
    5. Introduction to Abstract Algebra
  7. Graphs and trees (Chap. 7)
    1. Definitions and properties
    2. Graph algorithms
    3. Trees
  8. Counting Principles (supplementary handout)
  9. Advanced topics (if time allow)

Exams, Assignments and Grading

There will be approximately one homework assignment per week. There will be ~3 in-class exams and a final. The final exam will be cumulative (the scheduled time for the final is December 15th at noon in the regular classroom). The grade distribution will be roughly as follows: exams 40%, final 20%, and homeworks 40%.

All material handed in must be in hard copy, and be well organized and legible. Unreadable material will not be graded. Consultation of outside material for completion of assignments must be pre-approved. Late assignments will not be accepted.

Attendance

Regular attendence is expected. Students are responsible for all material, in all forms, presented during scheduled class times.

Final Note: The contents of the this syllabus may be modified according to the progress of the course