You need to register on Neptun for the exam day.

For the exam, only the knowledge necessary to answer the following questions is required.

1. • Explain the greedy algorithm design principle. Provide an example: Describe an optimization problem (what is the input, what needs to be calculated) and its greedy solution. [You can choose from the algorithms presented in the lecture.] Does the algorithm guarantee the optimality of the output? If not, what guarantee can be given for the quality of the output? Substantiate your claims about the guarantee.
   • Define the concept of (Karp-)reduction. Define the definition of NP-completeness. Define the concept of a Boolean network. Define the NETWORK-SAT language. Define the SAT language. Prove that NETWORK-SAT < SAT. If A is known to be NP-complete and A < B, what can be concluded?
2. • Describe the salami tactics algorithm design principle. Describe the basic question of binary search (what is the input, what needs to be calculated). What is the binary search algorithm? Analyze the algorithm.
   • Define the PALINDROME language. What is the decision problem described by this language? Outline a Turing machine solving it. Specify the model it uses.
3. • Describe the salami tactics algorithm design principle. Describe the basic question of median search (what is the input, what needs to be calculated). How was this task generalized? Provide an algorithm for it. Analyze the algorithm.
   • Define the concept of (Karp-)reduction. Define the definition of NP-completeness. Define two languages: A, B. Write a non-trivial reduction between them: A < B. We know that A is NP-complete. What can be inferred?
4. • Describe the divide and conquer algorithm design principle. Describe the basic question of sorting (what is the input, what needs to be calculated). Provide an algorithm for it. Analyze the algorithm.
   • What do we mean by the time complexity of a non-deterministic Turing machine for a given input? What do we mean by the space complexity of a non-deterministic Turing machine for a given input? How do these lead to complexity classes? Define the classes NL, NP, NPSPACE, NEXP, coNL, coNP, coNPSPACE, coNEXP.
5. • Describe the divide and conquer algorithm design principle. Describe the basic question of multiplication (what is the input, what needs to be calculated). Describe Karatsuba's algorithm. Analyze the algorithm.
   • Define the concept of Karp-reduction. Define the definition of NP-completeness. Define the concept of a Boolean network. Define the NETWORK-SAT language. Prove that NETWORK-SAT is NP-complete.
6. • Describe the dynamic programming algorithm design principle. Describe a problem where this principle can be applied (what is the input, what needs to be calculated). Describe a dynamic programming algorithm for this problem. Analyze the algorithm.
   • Define the concept of (Karp-)reduction. Define the definition of P-completeness. Define the concept of a Boolean network. Define the NETWORK-EVALUATION language. Prove that NETWORK-EVALUATION is P-complete.
7. • Define the flow problem (what is the input, what needs to be calculated). Define the concept of an augmenting path. Describe the schema of an improvement algorithm based on this. How did Ford and Fulkerson search for an augmenting path?
   • Define the concept of (Karp-)reduction. Define the definition of NL-completeness. Prove that DIRECTED-REACHABILITY is NL-complete. What follows from this?
8. • Define the flow problem (what is the input, what needs to be calculated). Define the concept of an augmenting path. Describe the schema of an improvement algorithm based on this. How did Edmonds and Karp search for an augmenting path? State the relevant theorem.
   • Define the concept of (Karp-)reduction. Provide simple examples. Define the concept of completeness. Define the concepts of NL-completeness, P-completeness, and NP-completeness.
9. • Can the Ford-Fulkerson algorithm cycle if the input numbers are rational? Can the Ford-Fulkerson algorithm cycle if the input numbers are handled with exact real arithmetic? What can we say about the flow problem if the input numbers are integers? Justify your answers.
   • Define the DIRECTED-REACHABILITY language/problem. Say something about its complexity. Provide multiple answers. Outline Savitch's algorithm.
10. • In what problems can we talk about amortized analysis? What do we mean by it? Describe the binary counter problem. Analyze it with amortized analysis. What do we mean by the banker's perspective? What do we mean by the physicist's perspective?
    • Define the concept of a universal Turing machine. Define the language of HALT. Define the class of decidable languages. Define the class of enumerable languages. Prove that HALT is undecidable.
11. • Define the concept of min-heap and max-heap. How can we represent this if the underlying rooted tree is binary? How can we represent this if the degrees of the underlying rooted tree are unbounded? Define the concept of a Fibonacci heap. What "services" does a Fibonacci heap provide?
    • Define the concept of (Karp-)reduction. Prove that polynomial and logarithmic space reducibility are transitive concepts.
12. • Define the concept of a Fibonacci heap. What "services" does a Fibonacci heap provide? How did we implement the Decrease-Key(v, delta) service?
    • Describe the concept of a Turing machine (work alphabet, state set, transition function, configuration, configuration update, run). When do we say that Turing machine T computes a computational problem f? How does the concept change when dealing with decision problems?
13. • Define the concept of a Fibonacci heap. What "services" does a Fibonacci heap provide? How did we implement the Min-Delete service?
    • What do we mean by the time complexity of a Turing machine for a given input? What do we mean by the space complexity of a Turing machine for a given input? How do these lead to complexity classes? Define the classes L, P, PSPACE, EXP.
14. • Text = sequence of characters. What do we mean by character-based encoding? Do you remember the parameters of ASCII encoding? How long (in bits) is the ASCII code of an n-character text? What do we mean by prefix coding? Describe the Huffman algorithm. What algorithm design principle does the algorithm follow?
    • What are the containment relationships between L, NL, P, NP, PSPACE, NPSPACE, EXP, NEXP classes? Substantiate your answers.
15. • Text = sequence of characters. What do we mean by character-based encoding? Do you remember the parameters of ASCII encoding? How long (in bits) is the ASCII code of an n-character text? What do we mean by dictionary-based encoding? Describe the Lempel-Ziv-Welsh algorithm.
    • Describe the concept of a non-deterministic Turing machine. Describe both variations presented in the lecture.