Differences

This shows you the differences between two versions of the page.

--- teaching:2024summer:karp [2024/03/11 16:13]
rwittler
+++ teaching:2024summer:karp [2024/04/23 11:28] (current)
rwittler
@@ Line 12: / Line 12: @@
 \\
-The overarching topic of this semester are "Karp's 21 NP-complete problems": [[https://pdfs.semanticscholar.org/a3c3/7657822859549cd6b12b0d1f76f8ee3680a0.pdf|Richard M. Karp. "Reducibility among combinatorial problems" (1972)]]
+The overarching topic of this semester are "Karp's 21 NP-complete problems": [[https://link.springer.com/content/pdf/10.1007/978-1-4684-2001-2_9.pdf|Richard M. Karp. "Reducibility among combinatorial problems" (1972)]]
 In this work, Karp shows NP-hardness of many classical, important formal problems, mainly by listing reductions/equivalence between them. The given reductions appear like brief cooking recipes, but no intuition or proof of equivalence is provided. The relations are not too obvious but also not too hard to see -- excellent exercises for understanding formal statements, logical thinking, formal writing etc.
 \\
 \\
-{{karp-fig1.png}}
+{{teaching:2024summer:karp:karp-fig1.png}}
@@ Line 28: / Line 28: @@
 Concrete tasks are:
+  * Carefully read the original publication of Karp until 17 April
   * Understand the two problems (A and B)
   * Understand  the reduction from B to A
@@ Line 42: / Line 43: @@
 \\
-| Clique (from Satisfiability)                      | as example by Kassian and Roland |
+  * Set Packing (from Clique)
-| Set Packing (from Clique)                         |  |
+  * Exact Cover (from Chromatic Number)
-| Feedback Arc Set (from Node Cover)     |  |
+  * Partition (from Knapsack)
-| Exact Cover (from Chromatic Number) |  |
+  * Steiner Tree (from Exact Cover)
-| Hitting Set (from Exact Cover)                |  |
+\\
-| Steiner Tree (from Exact Cover)              |  |
-| 3-dim. Matching (from Exact Cover)      |  |
+As backup, we could also do:
-| Knapsack (from Exact Cover)                  |  |
+  * Feedback Arc Set (from Node Cover)
-| Sequencing (from Knapsack)                  |  |
+  * Hitting Set (from Exact Cover)
-| Partition (from Knapsack)                       |  |
+  * Knapsack (from Exact Cover)
+  * Sequencing (from Knapsack)
+\\
+\\
+^ Day ^ Topic ^ Responsible person ^
+| 10.04. | Overview | all |
+| 17.04. | Discussion of Karp's Paper | all |
+|           | Repetition NP-completeness | Roland  ({{:teaching:2024summer:karp:np_completeness.pdf|slides}}) |
+|           | Example: Clique (from Satisfiability)  | Kassian |
+| 24.04. | [[:teaching:2024summer:karp:writing|Scientific writing]] & presentations | Roland {{:teaching:2022summer:algbioinf:howtoread.pdf|Slides: HowToRead}} [[https://chat.openai.com/share/b941110b-63ce-4355-8a7f-28fd6dcc8906
+|chatGPT: Beautifully phrased nonsense]] |
+| 01.05.  | -- (national holiday) ||
+| 08.05. | | |
+| 15.05. | | |
+| 22.05. |Set Packing |Olivia (Kassian)|
+| 29.05. | Exact Cover|Enna (Roland)|
+| 05.06. | | |
+| 12.06. | | |
+| 19.06. | Partition| Asal (Kassian)|
+| 26.06. | Steiner Tree| Franziska (Roland)|
+| 03.07. | Abgabe Implementierung | |
+| 10.07. | presentation of implementations | all |
+| 17.07. | | |

Genome Informatics

Differences