Lectures for Mathematics 121, Fall 2006-07

  • Monday, 8/28: Introduction: Finite machines, regular expressions and languages
  • Tuesday, 8/29: Lab: Eclipse and Karel
  • Wednesday, 8/30: Karel and Java miscellany, logical operators
  • Friday, 9/1: Examples of simple Java, browsing online JavaDoc, concepts of object-oriented programming (OOP)

  • Monday, 9/4: Labor Day Holiday
  • Tuesday, 9/5: Lab: Study Simple Java demos
  • Wednesday, 9/6: Formal definition of FA, regular language. Examples of regular expressions
  • Friday, 9/8: [Add/section-change deadline]Review, begin NFA's

  • Monday, 9/11: More NFA's, NFA-to-DFA algorithm by examples
  • Tuesday, 9/12: Lab: Karel Addendum, comment Simple Java demos, work on Simple Java
  • Wednesday, 9/13: Formal definition of NFA, NFA=>DFA in symbols, closure properties of regular languages
  • Friday, 9/15: Regular expressions, RE=>NFA algorithm, DFA=>RE example

  • Monday, 9/18: Programming Q&A in connection with assignment 2
  • Tuesday, 9/19: Lab: Study Breakout demos, work on Breakout
  • Wednesday, 9/20: The Pumping Lemma for regular languages
  • Friday, 9/22: Q&A on Java to-date and for Breakout

  • Monday, 9/25: Discussion of Roberts chapters 3, 4, 5
  • Tuesday, 9/26: Lab: Work on Breakout, go over Assignment 2
  • Wednesday, 9/27: Using the Eclipse debugger
  • Friday, 9/29: (No meeting)

  • Monday, 10/2: [No-W drop deadline] Algorithms: equal languages, nonempty language, infinite language, congruent number
  • Tuesday, 10/3: Lab: Study Hangman demos, work on Hangman
  • Wednesday, 10/4: Context-free grammars and languages
  • Friday, 10/6: Pushdown automata

  • Monday, 10/9: CFG=>PDA
  • Tuesday, 10/10: Lab: Work on Sipser problems or Hangman
  • Wednesday, 10/11: PDA=>CFG
  • Friday, 10/13: CFL pumping lemma

  • Fall break week

  • Monday, 10/23: Preview Sipser hw 1b, start object memory model
  • Tuesday, 10/24: Lab: Work on Hangman
  • Wednesday, 10/25: (Sipser hw 1b triage)
  • Friday, 10/27: Object memory model

  • Monday, 10/30: MiniSim
  • Tuesday, 10/31: Lab: Yahtzee demos; finish Hangman or work on Yahtzee
  • Wednesday, 11/1: Pre-discuss Sipser hw2
  • Friday, 11/3: Pre-discuss Sipser hw2

  • Monday, 11/6: [Withdraw/leave deadline] Discuss 2.43; TM and PM for {a^nb^nc^n}
  • Tuesday, 11/7: Lab: Yahtzee demos; work on Yahtzee
  • Wednesday, 11/8: 2-bit memory, bidirectional PM, TM=kTM=NTM
  • Friday, 11/10: TM, kTM, NTM, kNTM, kPDA, PM all equivalent; universal TM

  • Monday, 11/13: Recognizable and decidable languages
  • Tuesday, 11/14: Lab: Work on Yahtzee
  • Wednesday, 11/15: Hilbert's program; the halting problem; a non-recognizable language
  • Friday, 11/17: MiniSim and memory review; TM's can add and multiply; raise-to-power algorithm; searching

  • Monday, 11/20: More languages than Turing machines; sort and convex hull demo
  • Tuesday, 11/21: Lab: Work on Yahtzee or play with convex hull
  • Wednesday, 11/22: (Eric Roberts lecture) The Busy Beaver function and the halting problem
  • Friday, 11/24: Thanksgiving Holiday

  • Monday, 11/27: TM for Collatz sequence; public key cryptology
  • Tuesday, 11/28: Lab: Miscellany
  • Wednesday, 11/29: Preview Sipser ch3 set; finding large primes
  • Friday, 12/1:

  • Monday, 12/4:
  • Tuesday, 12/5: No meeting (college on Thursday schedule)
  • Wednesday, 12/6:

Back to my home page | Assignments | Materials, Links, and Handouts