CS 375, Logic and Theory of Computation

Class page

Time and Place: 3--3:50 MWF, 255 FPAT (Anderson Tower)

Professor: Dr. J. Goldsmith
Office: 763E Anderson Hall, Phone: 257-4245
Dr. Goldsmith's Office Hours: Mondays 10 AM, Wednesdays 11 AM, and by appointment. Email questions encouraged and answered.

Course Description:

The topics covered in this course will be:

• Predicate Logic
  
• Propositional Logic
  
• Turing machines
  
• Computability
  
• Computational complexity
  
• Finite Automata and Regular Languages

Prereqs: MA 114, CS 215 and CS 275.

The textbook:

Grading:

There will be biweekly homeworks due Mondays at the beginning of class except those weeks when there is an exam; assignments will be posted by the previous Thursday on the web. The lowest homework grade will be dropped. Illegible work will not be graded. Plagiarized work will be penalized for all parties, according to University regulations. There will be two midterm exams and one final.

Homework will be 50% of your grade, each midterm will be 15% and the final 20%.

READ THIS:

Attendance in class and section is very strongly encouraged.

Copying of homework from other students or from other sources is strictly prohibited. Obtaining a solution from another source without citing the source is plagiarism. You are encouraged to visit Dr. Goldsmith in her office hours or to send her email if you are stuck on homework problems. You do not need an appointment for regularly scheduled hours.

Outcomes and assessments

The student will develop a 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.

Week by week course outline:

Date	Topic	Chapter	Assignment
Aug. 26--8	Sets, relations, graphs	1	problems
Aug. 31--Sept. 4	Functions, sizes of infinity, induction	2,3,4
Sept 9--11	Proofs and inference	3,6	problems
Sept. 14--18	Predicate logic	7
Sept. 21--25	SAT and DPLL, quantifiers	6	problems
	No class on Monday, Sept. 28: Jewish High Holy Day
Sept. 30--Oct. 2	Propositional logic	?
Oct. 5	Review		Practice problems
Oct. 7th	MIDTERM I
Oct. 9th	Languages
Oct. 12--16	Turing machines	13	problems
Oct. 19--23	Computability and enumerability	14.1
Oct. 26--30	Uncomputable languages	14.1	problems
Nov. 2--6	Computational complexity	14.3
Nov. 9--16	NP-completeness	14.3	problems
Nov. 18	Regular expressions	11.1
Nov. 20	Review		Practice problems
Nov. 23	MIDTERM II
Nov. 23	DFAs and NFAs	11.2	problems
Nov. 25--27	THANKSGIVING BREAK (Class does not meet)
Nov. 30--Dec. 4	Nonregular languages, equivalence of NFAs and DFAs	?
Dec. 7--11	Equivalence of FAs, regular expressions	11.2
Dec. 18	FINAL: 1:00 PM