You are here: home » teaching » 2024summer » karp

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision 		Previous revision
teaching:2024summer:karp [2024/03/14 11:32]
rwittler 		teaching:2024summer:karp [2024/04/23 11:28] (current)
rwittler
Line 16: Line 16:
 \\ \\
 \\ \\
-{{karp-fig1.png}}+{{teaching:​2024summer:​karp:​karp-fig1.png}}
  
  
Line 28: Line 28:
  
 Concrete tasks are: Concrete tasks are:
 +  * Carefully read the original publication of Karp until 17 April
   * Understand the two problems (A and B)   * Understand the two problems (A and B)
   * Understand ​ the reduction from B to A   * Understand ​ the reduction from B to A
Line 44: Line 45:
   * Set Packing (from Clique) ​         ​   * Set Packing (from Clique) ​         ​
   * Exact Cover (from Chromatic Number)   * Exact Cover (from Chromatic Number)
-  * Steiner Tree (from Exact Cover) ​   ​ 
   * Partition (from Knapsack) ​         ​   * Partition (from Knapsack) ​         ​
 +  * Steiner Tree (from Exact Cover) ​   ​
 +\\
 +
 +As backup, we could also do:
   * Feedback Arc Set (from Node Cover) ​   * Feedback Arc Set (from Node Cover) ​
   * Hitting Set (from Exact Cover) ​       * Hitting Set (from Exact Cover) ​    
Line 56: Line 60:
 | 10.04. | Overview | all | | 10.04. | Overview | all |
 | 17.04. | Discussion of Karp's Paper | all | | 17.04. | Discussion of Karp's Paper | all |
-|           | Repetition NP-completeness | Roland ​ |+|           | Repetition NP-completeness | Roland  ​({{:​teaching:​2024summer:​karp:​np_completeness.pdf|slides}}) ​|
 |           | Example: Clique (from Satisfiability) ​ | Kassian | |           | Example: Clique (from Satisfiability) ​ | Kassian |
-| 24.04. | Scientific writing & presentations | Roland |+| 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) ||  ​ | 01.05. ​ | -- (national holiday) ||  ​
-| 08.05. | | (Roland away) | +| 08.05. | | | 
-| 15.05. | | (Roland away) | +| 15.05. | | | 
-| 22.05. | | | +| 22.05. |Set Packing ​|Olivia (Kassian)| 
-| 29.05. | | | +| 29.05. | Exact Cover|Enna (Roland)| 
-| 05.06. | | (Roland away) | +| 05.06. | | | 
-| 12.06. | | (Roland away) | +| 12.06. | | | 
-| 19.06. | | | +| 19.06. | Partition| Asal (Kassian)| 
-| 26.06. | | | +| 26.06. | Steiner Tree| Franziska (Roland)| 
-| 03.07. | | (Roland away) | +| 03.07. | Abgabe Implementierung ​| | 
-| 10.07. | | | +| 10.07. | presentation of implementations ​| all | 
-| 17.07. | | (Roland away) |+| 17.07. | | |