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
Next revision Both sides next revision
teaching:2024summer:karp [2024/03/15 08:35]
rwittler 		teaching:2024summer:karp [2024/04/23 11:28]
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. | presentation of implementations | all | | 10.07. | presentation of implementations | all |
-| 17.07. | | (Roland away) |+| 17.07. | | |