15-212 Section A Notes

April 22, 1998
Thomas Kang

1. Administrative Details

Many of you told me that you'd like to push the Gin project deadline back. I'm working on it, and I'll let you know as soon as we make a decision.

NEWS FLASH: I just got the OK from Ravi, so it's official -- the new Gin deadline is Friday, 5/1, at 11:59:59pm ET. You may continue working on your player algorithm for the tournament on 5/11, but that's for a free dinner, not for class credit.

2. Outline of Things To Study

Here is an outline of things that we've covered in class and is therefore fair game for the final exam. A quick disclaimer: This outline is not an official list of things to study; it's just here to guide you as you review for the exam. So this outline is not a list of things guaranteed to be on the exam; and if I left something out, that doesn't mean that it won't be on the exam.

  • Languages

    • general
    • regular (RL)
      • closure operations
      • regular expressions (regex)
      • pumping theorem
      • examples of RL
      • examples of non-RL
    • context-free (CFL)
      • closure operations
      • grammar
      • parse tree
      • ambiguity
      • terminal and nonterminal symbols
      • generation rules
      • examples of CFL
      • examples of non-CFL
    • recursive
      • closure operations
      • examples of recursive languages
      • examples of non-recursive languages

  • Models of Computation

    • determinism vs. nondeterminism
    • finite automata (DFA, NDFA)
    • push-down automata (DPDA, PDA)
    • Turing machines (DTM, TM)
    • NDFA -> DFA construction
    • DTM -> TM construction (dovetailing)
    • Church-Turing Thesis
    • undecidability

  • Complexity Theory

    • big-O notation
    • P
    • NP
    • NP-Complete (NPC)
      • why do we care about NPC?
      • criteria for NPC membership
      • reduction: why it works, how to do it
    • famous NPC problems
      • clique
      • Hamiltonian cycle (HC)
      • Hamiltonian path (HP)
      • traveling salesman problem (TSP)
      • vertex cover (VC)

  • Direct Applications of Theory

    • Cryptography
      • Why use it?
      • private-key cryptography
      • public-key cryptography (e.g., RSA)
    • Parsing
      • CYK algorithm
      • top-down parsing
      • bottom-up parsing

  • Object-Oriented Programming

    • encapsulation
    • inheritance
    • polymorphism

  • Concurrency

    • process
    • thread
    • race condition (and examples)
    • deadlock
    • mutex: why and how it is used
    • test-and-set
    • Programming With Threads by Andrew Birrell, a classic paper on concurrency; overkill for this class, but parts of it may be helpful

  • Java

    • mechanisms for encapsulation: levels of protection
      • public
      • protected
      • package (not a keyword)
      • private
    • mechanisms for inheritance: class hierarchies and interfaces
      • extends
      • implements
      • interface
    • mechanisms for polymorphism
      • abstract
      • overriding
      • overloading
    • exceptions
      • class Exception
      • try, catch, finally
      • why use exceptions?
    • Abstract Windowing Toolkit (AWT)

  • Simple Language (SL)

    • SL specifications
      • SL syntax
      • SL semantics
    • Lexer
      • stream
      • token
      • lexeme
    • Parser
      • things done at parse-time
        • syntax check
        • parse tree
    • Interpreter
      • things done at run-time
        • binding
        • semantic evaluation
      • scoping: how and why