Games, graphs, and machines

Semester 2, 2023, Australian National University

This is the public webpage for the course Games, Graphs, and Machines (MATH2301) taught by Asilata Bapat at the Australian National University in Semester 2, 2023. Here are the ongoing typed course notes. Please get in touch if you have any comments.

Notes from lectures

These are the handwritten notes from our lectures. They have not been proofread and may contain some inaccuracies.

  1. Monday 24 Jul 2023 — sets, properties of sets [screen version] [print version]
  2. Wednesday 26 Jul 2023 — relations, functions [screen version] [print version]
  3. Friday 28 Jul 2023 — equivalence relations, equivalence classes [screen version] [print version]
  4. Monday 31 Jul 2023 — equivalence classes, modular arithmetic [screen version] [print version]
  5. Wednesday 2 Aug 2023 — modular arithmetic [screen version] [print version]
  6. Friday 4 Aug 2023 — directed graphs, adjacency matrices [screen version] [print version]
  7. Monday 7 Aug 2023 — paths in directed graphs [screen version] [print version]
  8. Wednesday 9 Aug 2023 — powers of adjacency matrix, transitive closure [screen version] [print version]
  9. Friday 11 Aug 2023 — boolean operations, weighted graphs [screen version] [print version]
  10. Monday 14 Aug 2023 — minimum cost paths, partial orders [screen version] [print version]
  11. Wednesday 16 Aug 2023 — total and partial orders, Hasse diagrams [screen version] [print version]
  12. Friday 18 Aug 2023 — max and min elements, topological sorts [screen version] [print version]
  13. Monday 21 Aug 2023 — incidence algebra [screen version] [print version]
  14. Wednesday 23 Aug 2023 — edge functions, operations in incidence algebra [screen version] [print version]
  15. Friday 25 Aug 2023 — calculations in incidence algebra [screen version] [print version]
  16. Monday 28 Aug 2023 — invertibility, Moebius function, one sided convolutions [screen version] [print version]
  17. Wednesday 30 Aug 2023 — one sided convolutions, inclusion exclusion principle [screen version] [print version]
  18. Friday 1 Sep 2023 — inclusion exclusion calculation, formulas for Moebius function [screen version] [print version]
  19. Monday 18 Sep 2023 — recap of Moebius inversion, alphabets, languages [screen version] [print version]
  20. Wednesday 20 Sep 2023 — language operations, regular expressions [screen version] [print version]
  21. Friday 22 Sep 2023 — regex constructors, matching, language of a regex [screen version] [print version]
  22. Monday 25 Sep 2023 — regex example continued, deterministic finite automata [screen version] [print version]
  23. Wednesday 27 Sep 2023 — attempt to convert regex to DFA [screen version] [print version]
  24. Friday 29 Sep 2023 — product automaton, nondeterministic finite automata [screen version] [print version]
  25. Tuesday 3 Oct 2023 — NFA calculation tree, regex constructors to NFAs [screen version] [print version]
  26. Wednesday 4 Oct 2023 — NFA to DFA via power set automaton [screen version] [print version]
  27. Friday 6 Oct 2023 — NFA to regex [screen version] [print version]
  28. Monday 9 Oct 2023 — NFA to regex, regular and nonregular languages [screen version] [print version]
  29. Wednesday 11 Oct 2023 — pumping lemma argument, intro to games [screen version] [print version]
  30. Friday 13 Oct 2023 — N and P labelling, hackenbush, chomp [screen version] [print version]
  31. Monday 16 Oct 2023 — nim [screen version] [print version]
  32. Wednesday 18 Oct 2023 — nim sum, winning strategy for nim [screen version] [print version]
  33. Friday 20 Oct 2023 — sum of games, equivalence of games [screen version] [print version]
  34. Monday 23 Oct 2023 — equivalence of games, criterion to check equivalence [screen version] [print version]
  35. Wednesday 25 Oct 2023 — Grundy labelling [screen version] [print version]
  36. Friday 27 Oct 2023 — Sprague Grundy theorem [screen version] [print version]