Logic and Theory of ComputingRequired/Elective: requiredPrerequisites: MA113, CS215, CS275, and engineering standingGENERAL INFORMATION
- Wearing a mask is optional for this class
- LOCATION: Mandrell Hall, Rm 143
- TIME: MWF 2:00pm - 3:15pm
- INSTRUCTOR: Dr. Fuhua (Frank) Cheng
- OFFICE: Davis Marksbury Building, Rm 303
- OFFICE HOURS: TR 3:30pm - 5:30pm, and by appointment
- PHONE: (859) 257-6760
- E-MAIL: cheng@cs.uky.edu
- Class website: http://www.cs.uky.edu/~cheng/cs375/
- TEXTBOOK: Discrete Structures, Logic, andComputability (4th Edition)
Author: James L. Hein
Publisher: Jones & Bartlett Learning
ISBN-13: 978-1284070408
ISBN-10: 1284070409
and my notes (may be downloaded from the class website) - GRADERS:
Knox Garland (email: knox.garland@uky.edu)
Aaron Hall (email: awha239@uky.edu)
- Week 1 : Preliminaries: set algebra, relations, functions - read Chapters 1-4
- Weeks 2 - 5: Regular languages, finite automata- Chapter 11
- Weeks 6 - 8: Context-free languages, pushdownautomata - Chapter 12
- Weeks 9 - 11: Turing Machines - Chapter13
- Week 12: Propositional logic and predicate logic - Chapters6 & 7
- Week 13: Computing with logic and algebraic structures - Chapters9 & 10
There will be 8-10 homework assignments.Homework assignments will be posted on the
class website, due dates are printed on the assignments.
Not all the homework grades are used in the computation of your final grade.The worst
homework grade will be dropped, only the remaining better ones will be usedto compute
your final grade.
Homework assignments should be submitted to Canvas both as a pdf file and a
doc file on the date due. Submission deadlines will be strictly enforced.NO LATE HOMEWORKS WILL BE ACCEPTED.
You may use ChatGPT or any GAI to help with yourHW assignments.
All course materials will be available on theclass website.
I will use e-mail as means of communication. SEND MEAN E-MAIL ON FRIDAY
(1/12/2024) if you have not received any e-mails from me by then yet.
There will be a midterm exam and a final exam.Final exam is not comprehensive.
The exams are closed notes/books exams.
Final grade will be based on homeworks, class attendancerecord and exams, weighted as
follows:
- homeworks - 40%
- class attendance (extra credit) - 5%
- Exams - 60% (30 each)
The way attendance is checked will be announced both in class and by an email. You must
provide documentation from your health provider for any execused absence due to illness.To compute your final grade, I use the following scale (after rounding):
- A = 90 - 105
- B = 80 - 89
- C = 70 - 79
- D = 60 - 69
- E = 0 - 59
The students will develop knowledge of a variety of mathematical toolsfor the design
and analysis of algorithms and computer programs. They will learn basicmodels of
computation based on finite automata, grammars and Turing machines.Basic concepts of
logic, proof construction, and reasoning with variables and quantifierswill be reviewed
if time permits. Specific skills as outcomes of the course include:
- A fluency in the elements of automata theory, regular grammars and regular expressions,
and their uses - An understanding of the relationship between formal models of computation and
modern computers - An understanding of the relevance of logic and theory of computation to the computer
science curriculum - An ability to apply knowledge of computing and mathematicsappropriate to the discipline
- An ability to apply mathematical foundations, algorithmicprinciples, and computer
science theory in the modeling and design of computer-based systemsin a way that
demonstrates comprehension of the tradeoffs involved in design choices
These course learning outcomes support the following program outcomes:
- Outcome (a): An ability to apply knowledge of computing and mathematics appropriate
to the discipline; - Outcome (b): An ability to analyze a problem, and identify and define thecomputing
requirements appropriate to its solution; - Outcome (c): An ability to design, implement and evaluate a computer-basedsystem,
process, component, or program to meet desired needs; - Outcome (j): An ability to apply mathematical foundations, algorithmic principles, and
computer science theory in the modeling and design of computer-based systemsin a way
that demonstrates comprehension of the tradeoffs involved in design choices;
PLAGIARISM and CHEATING are serious academicoffenses. Consult the following links
for more information on what constitutes an academic offense and on
applicable penalties:cs375-syl-2022f.html
I want to emphasize that in this class studentsare allowed to discuss ideas and are
allowed to help others by explaininig concepts and possible solutions.
However, all the work that is submitted must be performed by studentsindividually.
Any sharing of electronic files, printouts and other materials developed
by the students is not allowed. If any fragments of text appearing inbooks,
journals, conference proceedings, web pages, etc. are used, students must
provide appropriate citations.Any help from others must also be acknowledged.
You are not allowed to use your cell phone any time during the exams(midterm/final).
- Important Links:
- Important Dates:
- First day of class - 8/27/2024 (Tuesday)
- Last day to withdraw without a W or change grading option - 9/15/2024 (Sunday)
- Midterm - 10/15/2024 (Tuesday)
- Fall break - 10/28/2024-10/29/2024 (Monday and Tuesday)
- Thanksgiving break - 11/27/2024-11/30/2024 (Wednesday - Sunday)
- Last day of class - 12/10/2024 (Tuesday)
- Final Exam - 12/19/2024 (Thursday 1:00-3:00p)
