Some work on structure

1 files changed, 29 insertions, 0 deletions

diff --git a/ss2017/stable_marriage_problem/structure.md b/ss2017/stable_marriage_problem/structure.md
new file mode 100644
index 0000000..89f467c
--- /dev/null
+++ b/ss2017/stable_marriage_problem/structure.md
@@ -0,0 +1,29 @@
+  - Implement algorithm in haskell, split over single steps
+  - During presentation show steps working on examples of the problem (one solves during step 1, one fails during step 1, one that requires multiple rotations to be eliminated), within `ghci`
+  - For most important proofs (tbd) show applicable step in haskell code with sketch of proof
+  
+  
+# Tables
+  - Definition: Tables, embedded tables, embedded pairs, embedded matchings
+  - Definition: stable tables
+  - Matchings embedded in stable tables are stable (4.2.4 ii)
+  - (Stable tables are determined by all first OR all last entries (4.2.4 iii))
+  - No pair absent from a stable table can block any of it's embedded matchings (4.2.4 i)
+  
+# Phase 1
+  - Present algorithm and demonstrate
+  - Phase 1 has no effect on the embeddedness of stable pairs (4.2.3 i)
+  - Phase 1 stabilizes a table, when it doesn't fail (4.2.2 + 4.2.3 ii)
+  - Phase 1 results in the largest stable table (4.2.4 iv)
+  
+# Rotations
+  - Definition: rotation, exposure of rotations in stable tables
+  - Rotations exposed in a stable T are either identical or disjunct (4.2.5)
+  
+# Phase 2
+  - Stable tables that are not already matchings expose at least one rotation and how to find it (4.2.6)
+  - Elimination of rotations from stable tables
+      - ignores non-elements of rotation (4.2.7 iii)
+      - results in table consistent with rotation (4.2.7 i, ii)
+      - Thus: produce stable subtables (4.2.8)
+  - Present derived algorithm and demonstrate