CS 375 - Logic and Theory of Computing
Credits: 3
Course Description
Topics in logic and theory of computation aimed at applications in Computer Science. Logic, propositional calculus and predicate calculus, tautologies, soundness, proofs. Finite Automata, regular and non-regular languages. Regular expressions and their applications in programming languages, Turing machines, decidability, and complexity.
Prereqs: MA 113, CS 215, CS 275, and engineering standing
Needed Skills
Before taking this course, the student is expected to be mathematically mature and, in particular, familiar with: basic algebra and calculus, basic discrete mathematics, basic programming techniques in a general purpose programming language, data structures including lists, trees and graphs, elementary algorithms such as searching and various concepts of recursion.
Learning Outcomes
The student will develop knowledge of a variety of mathematical tools for the design and analysis of algorithms and computer programs. He or she will learn basic concepts of logic, proof construction, and reasoning with variables and quantifiers, and to model basic computation using logic circuits, finite automata, and Turing machines. Specific outcomes include:
1. an ability to write simple proofs using propositional logic
2. an ability to handle predicate logic syntax and semantics
3. fluency in the elements of automata theory
4. basic understanding of properties of formal languages and associated concepts including grammars and regular expressions
5. basic understanding of models of computation including Turing machines
Measures
These five specific outcomes will be evaluated on the basis of student work (homeworks and exams) that will contain problems specifically addressing these outcomes. An additional mechanism includes a questionnaire measuring student self-assessment of their mastery of these five specific outcomes, performed at the end of the semester.
CAC Categories
Topic
|
Core
|
Advanced
|
Math
Fundamentals
|
25
|
10
|
Data
Structures
|
2
|
0
|
Algorithms
& Software Design
|
1
|
0
|
Computer
Organization and Architecture
|
0
|
0
|
Concepts
of Programming Languages
|
6
|
0
|
Social
and ethical issues
|
1
|
0
|
Total
|
35
|
10
|
Math Fundamentals (35):
Core (25): Review of sets and combinatorics (2); Propositional logic (3); Circuits (1); Propositional Proofs (3); Predicate logic (9); Automata theory (7)
Advanced (10): Turing machines (5), measures of complexity (2), undecidability (halting problem) (3)
Data structures (2): Core (2): Data structures associated with formulas (trees)
Algorithms and Software (1): Core (1): algorithms for satisfiability testing
Concepts of Programming Languages (6): Core (6): Tools and languages based on regular expressions
Social and Ethical Issues (1): Discussion of professional and academic integrity
Oral Communication (presentations)
none
Written Communication
8-10 homeworks and projects
Coverage
Theoretical content: 80%
· Fundamentals of logic, propositional connectives, equivalence of formulas, semantics and truth tables, quantifiers, semantics of predicate logic, basic methods of proof in predicate logic.
· Finite automata and regular languages.
· Nonregular languages, pumping lemma.
· Turing machines, basic complexity classes, intractability, computability and undecidability of predicate calculus.
Problem analysis: 10%
· Describing various formal structures occurring in computer science as relational structures.
Solution design: 10%
· Using tools of automata theory for programming
Student evaluation and feedback
Students are evaluated on their work (homeworks, exams). Students receive back their homework and exams. These papers are marked to indicate problems and they point out correct or better solutions. Problems that turn out to be especially difficult are discussed in class during lectures. A self-assessment test will be instituted at the end of the course.
Course Evaluation Questions
The course has helped me:
37. To understand propositional proofs
38. To handle predicate calculus syntax and semantics
39. To understand automata theory
40. To use regular expressions in my future work
41. To understand the relationship between formal models of computation and modern computers
42. To understand the relevance of logic and theory of computation to the CS curriculum
Possible Textbook
R.P. Grimaldi
Discrete and Combinatorial Mathematics
Addison Wesley, 1994.