CPSC 229 Foundations of Computation Spring 2024

CPSC 229 Schedule

Reading is to be done for the class period where it is listed; unless stated otherwise, sections refer to the textbook.

Dates for things in light gray are for planning purposes and may be adjusted slightly. Homework will typically be assigned and due on Wednesdays, except when there is an exam.

 Assignments

Week 1: 1/22-1/26

Topics: course introduction; propositional logic, boolean algebra
Mon Slides and Examples: introductory survey
(on Canvas, under "Quizzes")
Wed Reading:
  • chapter 1 introduction (logic and proof)
  • section 1.1 (propositional logic)
Slides and Examples: 		homework 1
due Wed 1/31
Fri Reading:
  • section 1.2 (boolean algebra)
Slides and Examples:

Week 2: 1/29-2/2

Topics: logic circuits, predicates and quantifiers, deduction
Mon Reading:
  • section 1.3 (logic circuits)
Slides and Examples:
Wed Reading:
  • section 1.4 (predicates and quantifiers)
Slides and Examples: 		homework 2
due Wed 2/7
Fri Reading:
  • section 1.5 (deduction)
Slides and Examples:

Week 3: 2/5-2/9

Topics: proof, proof by contradiction, mathematical induction
Mon Reading:
  • section 1.6 (proof)
Slides and Examples:
Wed Reading:
  • section 1.7 (proof by contradiction)
Slides and Examples: 		homework 3
due Wed 2/14
Fri Reading:
  • section 1.8 (mathematical induction)
Slides and Examples:

Week 4: 2/12-2/16

Topics: applications of proof by induction; sets
Mon Reading:
  • sections 1.9-1.10 (recursion and induction)
    If you haven't taken CPSC 225 (which introduces recursion and linked structures), you may not be able to follow all the details in these sections — that's OK, just try to get what you can.
Slides and Examples:
Wed Reading:
  • section 2.1 (sets)
Slides and Examples:
  • slides: sets (concepts and definitions)
homework 4
due Wed 2/21
Fri Reading:
  • section 2.2 (boolean algebra of sets)
Slides and Examples:

Week 5: 2/19-2/23

Topics: bitwise operators, flags, and masks; functions; counting past infinity
Mon Reading:
  • section 2.3 (programming with sets)
Slides and Examples:
Wed Reading:
  • section 2.4 (functions)
  • section 2.5 (programming with functions)
Slides and Examples: 		homework 5 (corrected!)
due Wed 2/28
Fri Reading:
  • section 2.6 (counting past infinity)
Slides and Examples:

Week 6: 2/26-3/1

Topics: languages and regular expressions
Mon Reading:
  • section 3.1 (languages)
Slides and Examples:
Wed Reading:
  • section 3.2 (regular expressions)
  • section 3.3 (using regular expressions)
Slides and Examples:
Fri Slides and Examples: exam 1 review survey
(on Canvas, under "Quizzes")

due Thu 2/29 10pm

Week 7: 3/4-3/8

Topics: regular expressions, finite state automata
Mon
exam 1
Wed Slides and Examples: homework 6
due Wed 3/13

(data.txt)
Fri Reading:
  • section 3.4 (finite-state automata)
Slides and Examples:

Week 8: 3/11-3/15

Topics: nondeterministic finite-state automata
Mon Reading:
  • section 3.5 (nondeterministic finite-state automata)
Slides and Examples:
Wed *** meet in Rosenberg 009 (make sure you remember your Linux username and password - let me know by Tuesday night if you need a password reset) homework 7
and
regex lab
due Wed 3/27
Fri *** meet in Rosenberg 009

Spring Break: 3/16-3/24

Week 9: 3/25-3/29

Topics: nondeterministic finite-state automata; finite-state automata and regular languages; non-regular languages
Mon Slides and Examples:
Wed Reading:
  • section 3.6 (finite-state automata and regular languages)
Slides and Examples: 		homework 8
due Wed 4/3
Fri Reading:
  • section 3.7 (non-regular languages)
Slides and Examples:

Week 10: 4/1-4/5

Topics: context-free grammars; application: BNF; parsing and parse trees
Mon Reading:
  • section 4.1 (context-free grammars)
Slides and Examples:
Wed Reading:
  • section 4.2 (application: BNF)
Slides and Examples: 		homework 9
due Wed 4/10
Fri Reading:
  • section 4.3 (parsing and parse trees)
Slides and Examples:

Week 11: 4/8-4/12

Topics: parsing and parse trees; pushdown automata
Mon Slides and Examples:
Wed Reading:
  • section 4.4 (pushdown automata)
Slides and Examples:
Fri Slides and Examples: exam 1 redo
due Fri 4/12

(corrections and redo information)

Week 12: 4/15-4/19

Topics: general grammars
Mon
exam 2
Wed Reading:
  • section 4.6 (general grammars)
Slides and Examples: 		homework 10
due Fri 4/26
Fri Slides and Examples:

Week 13: 4/22-4/26

Topics: Turing machines
Mon Reading:
  • section 5.1 (Turing machines)
Slides and Examples:
Wed HWS Day (no class)
Fri Slides and Examples: homework 11
due Fri 5/3

Week 14: 4/29-5/3

Topics: computability and the limits of computation
Mon Reading:
  • section 5.2 (computability)
Slides and Examples:
Wed Reading:
  • section 5.3 (the limits of computation)
Slides and Examples:
Fri Slides and Examples:

Reading Period: 5/4-5/6
Sat
Sun
Mon office hours 10am-1pm

Examples:

Final Exams: 5/7-5/10

 exam 2 redo
due Tue 5/7

(redo information and comments)
Tue office hours 10am-1pm

final exam
5/7 1:30-4:30pm
 end-of-semester deadline
no work accepted after 5/7 4:30pm
Wed
Thu
Fri

last updated: --Mon May 6 05:34:30 EDT 2024--
page owned by: bridgeman@hws.edu