math.ucsb.edu/~padraic/

Things:

• Home
• Research
• Lecture Notes

Math/CCS: Problem-Solving

Course Information:

• Professor: Padraic Bartlett.
• Email: padraic at math dot ucsb dot edu.
• Syllabus: linked here.

Projects:

• Project 1: Latin squares.
• Project 2: Strongly regular graphs.
• Project 3: Sequential dynamical systems.
• Project 4: NP-Completeness.
• Project 5: Galois theory.
• Project 6: Knot theory.

Presentations:

• Week 2:
  • Knot theory,
  • Latin squares,
  • Sequential/simultaneous dynamical systems,
  • P and NP.
• Week 3:
  • Tricolorability of knots,
  • Latin squares and codes,
  • Cellular automata,
  • NP-completeness.
• Week 4:
  • Games on knots,
  • Complete Latin squares,
  • The Game of Life,
  • NP-completeness and Minesweeper.
• Week 5:
  • Games on braid knots,
  • Latin cubes and more complete Latin squares,
  • Turing machines,
  • Vertex coverings and NP-completeness.
• Week 6:
  • The link-smoothing game,
  • Concepts of completeness for Latin cubes.
• Week 7:
  • The Garden of Eden theorem,
  • The World's Hardest Game is NP-hard,
  • More link-smoothing game results,
  • The N-Queens problem.
• Week 8:
  • Finding Hamiltionian circuits is NP-complete,
  • Counting fixed points on SDS,
  • Transversals and Latin rectangles,
  • Yet more link-smoothing game results.
• Week 9:
  • Completeness and sequencable groups,
  • Crossing game strategies,
  • The Game of Life, interpreted sequentially,
  • Metatheorems about games.
• Week 10:
  • Speed limits in sLife,
  • More metatheorems about games.

email: padraic at math dot ucsb dot edu | mailing address: south hall, room 6516, ucsb