This shows you the differences between two versions of the page.
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/05/22 10:20] kkobert |
||
---|---|---|---|
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. | | | | ||
- | | 05.06. | | (Roland away) | | + | | 05.06. | | | |
- | | 12.06. | | (Roland away) | | + | | 12.06. |Exact Cover |Enna (Roland) | |
- | | 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. | | | |