### Obsah

# Algorithms and Data Structures II 2022/23 -- Lecture

I teach Algorithms and Data Structures II (NTIN061) every Wednesday at 10:40 at S5 (Malá strana).

If you want to talk to me, you're welcome in my office S326 at Malá Strana, but agree with me on a time to meet first.
You can also e-mail me at `koutecky+ads2@iuuk.mff.cuni.cz`

and/or include the text `[ADS2]`

in the email subject.

data | what was taught [resources] |
---|---|

5. 10. | String searching: Knuth-Morris-Pratt algorithm. JeffE's notes, 7.1, 7.4-7.6 |

12. 10. | String searching: Aho-Corasick, Rabin-Karp JeffE's notes, 7.2-7.3, reference for AC: slides |

19. 10. | Finished Rabin-Karp analysis. Network flows intro, Ford-Fulkerson's algorithm. JeffE's notes, 10.1-10.4, recording |

26. 10. | Finished Ford-Fulkerson, Dinic's algorithm slides of Honza Hubička, CP-algorithms, NetworkX notebook, recording |

2. 11. | Goldberg's push-relabel algorithm recording, slides, notes |

9. 11. | Dean's sport day – no class |

16. 11. | Parallel algorithms: fast addition, fast sorting. slides: 1, 2, recording; more slides for sorting; notes for addition (6.1) |

23. 11. | Design of a comparator (see slides above). Geometric algorithms: convex hull, line segment intersections slides; sorry, no recording. [CLRS 33.1-33.3] |

30. 11. | Multiplying polynomials quickly: FFT (Fast Fourier Transform). slides 1 2, JeffE's notes, recording |

7. 12. | Finish FFT, begin reductions. recording |

14. 12. | Reductions: SAT, 3-SAT, IndSet, Clique, 3DM. recording, slides, JeffE (more than you asked for) |

21. 12. | 3,3-SAT reduces to 3DM. Classes P, NP; Cook's theorem. slides, JeffE, recording |

4. 1. | Dealing with NP-hardness. IndSet is solvable on trees; coloring is solvable on interval graphs; Knapsack is solvable in pseudopolynomial time (=when input values are polynomially bounded). Approximation: 2-approximation algorithm for $\Delta$-TSP (on a complete graph and with $\Delta$-inequality). No $\alpha$-approximation for general TSP. Fully polynomial time approximation scheme (FPTAS) for Knapsack (downscaling values). slides 1, slides 2, recording |

## Useful Resources

**[A]**Algorithms by Dasgupta, Papadimitriou, and Vazirani**[JE]**Algorithms by Jeff Erickson (the page contains various PDFs suitable for screen, printing etc.)

- Notes from Andrej Perković (
**100MB file**) (no guarantee of correctness, email him if you find bugs: arachneen_octogone.0c@icloud.com)

# ADS2 Exam / 2023

The exam will consist of:

- Two questions about an algorithm or a data structure from the lecture – describing the algorithm or data structure, proving they are correct, giving the complexity analysis. (With „big“ topics I will ask about a specific part of an algorithm, or for an overview of the algorithm. No need to reproduce 2 lectures worth of material as your first answer.)
- Two tasks similar to those from the tutorial – either apply an algorithm / data structure from the lecture to some problem (need to model the problem appropriately) OR adapt the algorithm / data structure to solve some problem (need to understand how it works internally to be able to adapt it appropriately)

The form of the exam is that you will come, get the question sheet, and work on the answers. Once you are finished with one of the answers, you hand it in, I will read it, point out anything which is missing / incorrect, give you hints if needed, and you can revise it. At some point either you will reach a correct solution, or you won’t want to try to improve it again, or I will feel like I can’t give you any more hints, and then we’ll reach some grade.

### Grading

**To get a 3** it suffices to know definitions and algorithms / data structures and (with hints) finish at least one of the “type 2” tasks (perhaps suboptimally).

**To get a 2** you need to be able to solve the tasks with some hints, or find a suboptimal (complexity) algorithm. If we proved some intermediate claims during the lecture, and these are used in the proofs of correctness/complexity, you need to at least know the statements of these claims.

**To get a 1** you need to analyze the algorithms (correctness and complexity) including the proofs, and you need to be able to solve the “type 2” tasks mostly independently. (Advice like “try dynamic programming” and similar is still fine though.)

## Topics

**Disclaimer:** the topics below are NOT specific instances of “type 1” questions. It is clear that some topics are wider and some narrower. However, if you have a good understanding of all the topics below, you should not be surprised by anything during the lecture.

- String searching – problem definition, basic notions and lemmas
- Knuth-Morris-Pratt Algorithm
- Aho-Corasick Algorithm
- Rabin-Karp Algorithm

- Network Flows – problem definition, notions, lemmas
- Ford-Fulkerson
- Dinitz
- Goldberg

- Parallel Algorithms / Circuits
- Fast Addition
- Fast Sorting

- Geometric Algorithms
- Convex Hull
- Line Segment Intersections

- FFT: definitions, algorithm, how to multiply polynomials quickly
- Reductions
- Definitions of most important NP-hard problems: SAT, IS, VC, Clique, 3DM, SubsetSum
- P, NP, NP-complete, NP-hard
- Cook's theorem

- Dealing with NP-hardness
- IndSet on Trees
- Coloring of Interval Graphs
- Approximation algorithms (definition)
- $2$-approximation of $\Delta$-TSP
- Non-existence of an $O(1)$-approximation for (unrestricted) TSP
- Pseudopolynomial algorithm for Knapsack; FPTAS for Knapsack.