What are the algorithm analysis projects

Algorithms & Complexity

Back to overview


Logbook Efficient Algorithms - Summer 2019


  • 18.07.2019:
    Calculation of a maximum matching in general graph G with n nodes and m edges, matching M maximum ⇔ M has no augmenting path, augmenting paths and odd circles, contraction of odd circles (blossom), completion of augmenting paths, Edmonds Blossom algorithm , Correctness, running time O (n2(n + m)).

    Material and literature:

  • 16.07.2019:
    Example of the preflow push algorithm. Matching: perfect, maximum, maximum. Calculation of a maximum matching in bipartite graphs G = (A ∪ B, E) with n nodes and m edges, flow network, equivalence of integral flows to matchings, calculation with Ford-Fulkerson algorithm in time O (nm). Characterization of graphs with perfect matchings (Hall, König, Egervary, ...), either perfect matching or a set of X & subseteq; A with | X | > | Γ (X) |.

    Material and literature:

  • 11.07.2019:
    Preflows, excess, labeling, compatibility (relegation condition in the residual network). Flow with compatible labeling is maximum. Preflow push algorithm, manages compatible preflows and labels, reduces surpluses. Correctness, duration: number of relabels at most 2n2 (maximum height of a node), number of saturating pushes at most 2nm (height change by at least 2 before the next saturating push on the same edge), number of non-saturating pushes at most 4n2m (potential analysis).

    Material and literature:

  • 09.07.2019:
    Maximum flows, definitions of flow network, flow, value of flow, s-t-cut, capacity of cut, residual network, augmenting paths. Ford-Fulkerson algorithm, correctness, Max-Flow-Min-Cut theorem, running time, strongly polynomial running time with Edmonds-Karp variant.

    Material and literature:

  • 04.07.2019:
    Generation of random and pseudo-random bit sequences, statistical tests, generators, existence of an efficient pseudo-random generator independent of the stretching, connection to P-NP, Blum-Micali generator, multiplicative group modulo n, generators

    Material and literature:

  • 02.07.2019:
    Random sampling, example: closest pair, grid division, estimation μ of the smallest distance: random selection of a point, reduction of the number of points; Use of a grid with an estimate of μ. Yao principle, intuition with a 2-player model (algorithm designer vs. instance choice opponent), application to the paging problem, every randomized paging algorithm with cache size k has a competition factor of at least H.k.

    Material and literature:

  • 27.06.2019:
    Probabilistic method, for which numbers n and k there is a graph with n nodes, without K.k and without Kk as a subgraph? Probabilistic method shows existence for k ≥ 2log2 n. Byzantine Agreement, randomized algorithm for t < n/8="" illoyale="" generäle,="" erwartete="" laufzeit="">

    Material and literature:

  • 25.06.2019:
    Splay trees, Operation Splay (x) always rotates the largest element ≤ x to the root, Splay (x) as the basis for Insert (x), Lookup (x) and Remove (x), right and left rotations and application in the Splay operation, definition of the potential function, amortized costs for a zig-zig operation (zig-zag analog) and a zig operation, amortized costs of a splay operation in O (log n), dynamic optimality configuration, probabilistic method.

    Material and literature:

  • 18.06.2019:
    Fibonacci heaps, repetition of insert (in O (1)) and DeleteMin with cleanup (in O (log m)), DecreaseKey with cascading cuts, amortized runtime O (1), Fibonacci property of the remaining trees, Dijkstra's algorithm, runtime with binary and fibonacci heaps. Splay trees, Operation Splay (x) always rotates the largest element ≤ x to the root, Splay (x) as the basis for Insert (x), Lookup (x) and Remove (x), right and left rotations and application in the Splay operation, definition of the potential function.

    Material and literature:

  • 13.06.2019:
    Binomial trees, binomial heaps, operations with amortized runtimes: Insert by merging trees (in O (1)), DeleteMin by separating the roots and merging trees (in O (log m)), DecreaseKey by repair_up as with binary heaps ( in O (log m)), Delete = DecreaseKey + DeleteMin. Fibonacci trees, Fibonacci heaps, trivial insert (in O (1)), DeleteMin with cleanup (in O (log m)), DecreaseKey with cascading cuts.

    Material and literature:

  • 11.06.2019:
    Amortized runtime analysis, accountant argument and potential function, examples: paging with flush-when-full, bit counter, hash table with dynamic size adjustment. Repeat heaps, binomial trees.

    Material and literature:

  • 06.06.2019:
    Selection of experts, n experts, YES / NO decisions, each expert makes a recommendation, minimizes wrong decisions, optimum is the number of mistakes made by the best expert. The deterministic weighted majority algorithm is (log4/3 2) -competitive (plus additive costs log4/3 n). Online learning with costs, costs cit ∈ [0,1] for experts i in round t = 1, ..., T. Randomized Weighted Majority Algorithm generates expected total costs K ≤ (1 + ε) Kopt + ln (n) / ε.

    Material and literature:

  • 04.06.2019:
    Ski rental, deterministic strategy with a competition factor of 2-1 / K, lower limit for deterministic strategies. Randomized strategy with competition factor e / (e-1). k-server problem, generalizes the paging problem, simple algorithms: greedy, balance, randomized greedy. Work-Function, Definition, Work-Function Algorithm is 2k competitive (without proof).

    Material and literature:

  • 28.05.2019:
    Paging problem with cache size k, FIFO and LRU are k-competitive, proof of decomposition into partial sequences depends on page faults of FIFO / LRU. Every deterministic algorithm has competition factor at least k. The randomized marking algorithm is 2Hk-competitive, proof of decomposition into partial sequences independent of the algorithm, analysis of the probability of the removal of old elements.

    Material and literature:

  • 23.05.2019:
    Load balancing with random walks, H (G) maximum hitting time in G, after expected O (H (G) log Φ (& ell;0)) Laps a balanced state is achieved. Online algorithms, competition factor, Makespan scheduling on m identical machines, LIST algorithm is (2-1 / m) competitive, every deterministic algorithm is at least 3/2 competitive, paging problem, LFD is offline optimum.

    Material and literature:

  • 21.05.2019:
    Random walks in undirected graph G, associated Markoff chain irreducible ⇔ G connected, chain ergodic ⇔ G connected and not bipartite. Limit distribution is πv = deg (v) / 2 | E |. Hitting time H (u, v) definition, H (u, u) = 1 / πu, H (u, v) < 2|e|="" wenn="" {u,v}="" ∈="" e,="" h(u,v)="">< 2|e|(n-1)="" für="" beliebige="" knoten="" u,v="" ∈="" v.="" lastbalancierung="" mit="" random="" walks,="" h(g)="" maximale="" hitting-time="" in="" g,="" nach="" erwartet="" o(h(g)="" log="">0)) Laps a balanced state is achieved.

    Material and literature:

  • 16.05.2019:
    Repetition of Markoff chains, definitions: irreducible and reducible chains, period of a state, periodic and aperiodic chains. Stationary distributions, limit distribution, definition of ergodic chain, in ergodic chains the limit distribution is the only stationary distribution, ergodic ⇔ aperiodic and irreducible.

    Ergodic chains assume that limt → ∞ P.ti, k = limt → ∞ P.tj, k> 0 for all states i, j, k.
    Therefore applies ergodic ⇔ (aperiodic & wedge; irreducible).

    Material and literature:

  • 14.05.2019:
    2-SAT problem, random walk algorithm for 2-SAT, Markoff chain for runtime analysis, expected runtime to find a satisfactory occupancy at most n2, after running time k⋅2n2 error probability is at most (1/2)k. 3-SAT problem, same approach bad bounds in the order of 2n + 2, Random walk algorithm with restart, after runtime k⋅ (4/3)n⋅poly (n) is error probability at most (1 / e)k.

    Material and literature:
    • Notes Markoff chains, pages MK8-MK14, MK56-MK62
    • Foil Markoff chains, pages 3, 4
    • Script, section 3.1 the definitions and basic terms of Markoff chains.
    • Section 3.3 in the script deals with a different algorithm for 2-SAT and 3-SAT (and k-SAT with any k ≥ 2)

  • 09.05.2019:
    Distributed algorithm for non-expandable independent set, definition of good knots and edges, in each round every good knot is removed from V with a constant probability, at least half of the edges are good edges, in each round a constant proportion of all is expected Edges removed, running time O (log n) whp Markoff chains, 2-SAT problem, randomized 2-SAT algorithm, Markoff chain for runtime analysis.

    Material and literature:
    • Script, section 2.5.2.
    • Slides Randomized Algorithms 1, page 27
    • Notes Markoff chains, pages MK1-MK11
    • Foil Markoff chains, pages 1-3
    • Script, section 3.1 the definitions and basic terms of Markoff chains.
    • Section 3.3 in the script deals with a different algorithm for 2-SAT and 3-SAT (and k-SAT with any k ≥ 2)

  • 07.05.2019:
    Hashing with chaining, c-universal hashing, expected number of collisions, expected runtime for n operations in a hash table with m entries is at most n (1 + cn / (2m)). Symmetry breaking, connected components, randomized parallel algorithm, running time O (log n) expected and w.h.p.

    Material and literature:

  • 02.05.2019:
    Skip lists, definition "with high probability (whp)", logarithmically many layers whp, expected run time of lookup O (log n) (= expected length of the search path), expected run time of insert and delete also O (log n), there dominated by the corresponding search path. Fingerprinting, n-bit key x, fingerprint h (x) with modulo mapping according to a random prime number from the interval [2, nd], for fixed keys x ≠ y we have h (x) ≠ h (y) w.h.p.

    Material and literature:

  • 30.04.2018:
    Monte Carlo algorithms, RSA cryptosystem, prime number test, Fermat's small theorem, Fermat test, extended Fermat test, Miller-Rabin test, incorrect classification of composite numbers with a probability of 1/4 or less. Min-cut problem, randomized min-cut algorithm, error probability at most 1 - 2 / n2, Error probability at most (1 / e)r according to rn2/ 2 independent repetitions

    Material and literature:

  • 25.04.2019:
    Game trees, evaluation with deterministic algorithms, lower limit to the running time, improvement through randomized selection of the evaluated children. Decision problems, Monte Carlo algorithms with one-sided bounded error.

    Material and literature:

  • 23.04.2019:
    Secretary problem, algorithm with waiting time n / e, analysis of the probability of hiring the optimal applicant, optimality of the algorithm

    Material and literature:

  • 18.04.2019:
    Probability distributions, events, independence, conditional probability, formula for total probability, random variables, expected value, linearity of the expected value, conditional expected value, Markoff inequality, variance, Chebyshev inequality, Chernoff inequalities

    The presented basics of stochastics can be found in a large number of books and scripts.

    Material and literature:

  • 16.04.2019:
    Organizational, randomized algorithms, expected runtime, randomized quick sort, randomized average salary. Online algorithms, examples of online problems: bin packing, ski rental, secretary problem.

    Material and literature: