-
© Universität Bielefeld
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
teaching:2026summer:karp [2026/04/08 12:06] rwittler |
teaching:2026summer:karp [2026/05/20 13:26] (current) rwittler |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ===== Karp's 21 Problems (S) ===== | ===== Karp's 21 Problems (S) ===== | ||
| - | | [[https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=659870819|392219]] | Wittler, Parmigiani | Summer 2026 | Wednesday 10:15-11:45 | U10-146 |\\ | + | | [[https://ekvv.uni-bielefeld.de/kvv_publ/publ/vd?id=659870819|392219]] | Wittler, Parmigiani | Summer 2026 | Wednesday 10:15-11:45 | U2-232 |\\ |
| \\ | \\ | ||
| Line 38: | Line 38: | ||
| * A (naive) implementation including a stress test (How far can we get with this?) | * A (naive) implementation including a stress test (How far can we get with this?) | ||
| \\ | \\ | ||
| - | |||
| - | The following problems will be covered: | ||
| \\ | \\ | ||
| - | * Set Packing (from Clique) | ||
| - | * Exact Cover (from Chromatic Number) | ||
| - | * Partition (from Knapsack) | ||
| - | * Steiner Tree (from Exact Cover) | ||
| - | \\ | ||
| - | |||
| - | As backup, we could also do: | ||
| - | * Feedback Arc Set (from Node Cover) | ||
| - | * Hitting Set (from Exact Cover) | ||
| - | * Knapsack (from Exact Cover) | ||
| - | * Sequencing (from Knapsack) | ||
| - | \\ | ||
| - | \\ | ||
| ^ Day ^ Topic ^ Responsible person ^ | ^ Day ^ Topic ^ Responsible person ^ | ||
| | 15.04. | Overview | all | | | 15.04. | Overview | all | | ||
| | 22.04. | Discussion of Karp's Paper | all | | | 22.04. | Discussion of Karp's Paper | all | | ||
| - | | | Repetition NP-completeness | Roland ({{:teaching:2024summer:karp:np_completeness.pdf|slides}}) | | + | | | Repetition NP-completeness | Roland ({{:teaching:2026summer:karp:np_completeness.pdf|slides}}) | |
| | | Example: Clique (from Satisfiability) | Luca | | | | Example: Clique (from Satisfiability) | Luca | | ||
| - | | 29.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 | + | | 29.04. | [[:teaching:2024summer:karp:writing|Scientific writing]] & presentations | Roland {{:teaching:2022summer:algbioinf:howtoread.pdf|Slides: HowToRead}} | |
| - | |chatGPT: Beautifully phrased nonsense]] | | + | |
| | 06.05. | | | | | 06.05. | | | | ||
| - | | 13.05. | | | | + | | 13.05. | Knapsack (from Exact Cover) | Sophie (Luca) | |
| - | | 20.05. | | | | + | | 20.05. | Set Packing (from Clique) | Sebastian (Roland) | |
| - | | 27.05. | | | | + | | 27.05. | Feedback Arc Set (from Node Cover) | Stina (Roland) | |
| - | | 03.06. | | | | + | | 03.06. | Steiner Tree (from Exact Cover) | Alena (Luca) | |
| - | | 10.06. | | | | + | | 10.06. | Hitting Set (from Exact Cover) | Anna (Luca) | |
| - | | 17.06. | | | | + | | 17.06. | Exact Cover (from Chromatic Number) | Philipp (Roland) | |
| - | | 24.06. | | | | + | | 24.06. | Sequencing (from Knapsack) | Alexander (Luca) | |
| - | | 01.07. | | | | + | | 01.07. | Partition (from Knapsack) | Nikita (Roland) | |
| | 08.07. | | | | | 08.07. | | | | ||
| | 15.07. | hand in implementations | | | | 15.07. | hand in implementations | | | ||
teaching/2026summer/karp.1775642814.txt.gz · Last modified: 2026/04/08 12:06 by rwittler
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International