Code Examples from Class

• Enumerator Examples
  • Enumerator Construction
  • Countability Example
• Halting Problem
  • Example of the Halting Problem
  • Example of a reduction from ATM to HALT-TM
  • Example of ATM from Sipser
• Polynomial-Time Reductions
  • Examples of Mapping Reductions (5.3)
  • Vertex Cover reduces to Subset Sum
    • vc.java
    • vc.in
  • Example of a mapping reduction of both Partition to Subset-Sum and Subset-Sum to Partition
  • 3-SAT to CLIQUE, 3-SAT to Vertex Cover Reduction
    • SAT_to_CLIQUE.java
    • SAT_to_VC.java
    • graphk.java
    • sat.java
    • graph.in
    • 3sat.txt
    • vc.txt
• Efficiency Examples
  • Standard Deviation Calculation
    • stddev.c (constant extra storage)
    • stddev2.c (O(n) extra storage)