CPSC 229 Course Information

From the course catalog:

This course introduces students to some of the mathematical and theoretical foundations of computer science, and to their practical applications to computing. Topics include propositional and predicate logic, sets and functions, formal languages, finite automata, regular expressions, grammars, and Turing machines. This course is required for the major in computer science.

By the end of the course, the successful student should be able to:

• explain the terminology and concepts of propositional and predicate logic
• explain the terminology and concepts of formal languages, including methods of specifying, producing, and recognizing those languages (regular expressions and finite-state automata, context-free grammars and pushdown automata, general grammars)
• explain aspects of computability theory, including the Church-Turing thesis, decidability, the halting problem, and the limits of computation
• explain the relevance and some applications of the "foundations of computation" studied to computer science and computing
• recognize and write rigorous proofs, applying formal proof techniques (including induction and contradiction) to establish and clearly convey the validity of a statement
• understand and use regular expressions
• understand syntax expressed as a grammar using BNF or similar notation
• use, write, and analyze context-free grammars, and design and analyze finite-state automata, pushdown automata, and Turing machines
• model and reason about computational systems, including their limitations and capabilities

CPSC 124 is required.
Java will be used in some examples, and a few homework assignments may require writing small programs in Java.

Textbook

Foundations of Computation, 2nd ed.
Carol Critchlow and David Eck

The book is freely available at https://math.hws.edu/FoundationsOfComputation. You can download a PDF version from the website, or order a printed copy if you'd like a physical copy. If you want to print the text for yourself, please do not use the Math/CS department printers.

Additional material will be handed out or posted on the course webpage.

Software

Some homework assignments may involve programming in Java. The tools that you need (Java 17, Eclipse or Visual Studio Code) are available on the lab computers in Rosenberg 009 (reboot them to Linux) and Lansing 310, or you can install them on your own computer.

Readings: Readings are an important first introduction to material that will be discussed in class. Reading should be completed for the class where it is listed.

Homework: Hands-on practice is essential for learning and mastery. Weekly problem sets will be assigned and graded; while most problems will be more mathematical in nature, some may involve writing small programs. In addition, you are encouraged to try the end-of-section exercises in the textbook for additional practice. These will not be graded, but I am happy to discuss them with you in office hours.

Exams: Exams assess what you, individually, have mastered. There will be two in-class midterm exams and a final exam. The dates of the exams are on the schedule page. More details about each exam will be announced prior to the exam.

Grades: Final grades in this course will be computed as follows:

• Homework: 45%
• Midterm exams: 30% (15% each)
• Final exam: 20%
• Engagement: 5%

Engagement: Learning isn't a passive activity where you simply read about something or sit back and watch someone else do things; you need to work with the material by thinking about it, trying to apply it, asking questions about it, and so forth and you will get more out of the course and will be more successful if you are engaged in the course. "Engagement" covers aspects of participation in the course other than completing graded assignments and exams: attendance, contributing to class, and asking questions (in class, at office hours). The minimum expectations for a passing engagement grade are that you satisfy the attendance policy. For full credit (and your own learning), you should demonstrate greater engagement through some of the following: missing fewer classes, participating in class, coming to office hours, etc.

Extra Credit: There may be some opportunities to earn extra credit on homeworks and exams, such as by tackling some harder problems. You are encouraged to take advantage of these opportunities to challenge yourself!

If you are concerned about your grade, come to office hours to get help. Staying on top of things and seeking help as soon as possible when you need it is the best route to success.

The expectations for this course are that you attend all scheduled class meetings (3 hours per week), spend approximately 8 hours per week (*) on average on additional work (reading, homework, studying) outside of class, and attend at least 5 hours of problem sessions over the course of the semester. If you can't make it to the scheduled problem sessions, this expectation can also be satisfied by coming to office hours. (5 hours = e.g. one problem session every three weeks or a 20-minute office hours visit every week)

(*) The assigned work is intended to take about this much time, though your experience may vary. However, if you routinely spend much less time, you may not be successfully mastering the material, and if you routinely spend substantially more time, especially if you feel like you are spinning your wheels and not making progress, you should come to office hours for help.

last updated: --Tue May 7 07:10:19 EDT 2024--
page owned by: bridgeman@hws.edu