Algorithm

Algorithm

AVL tree

AVL tree of height h has at most (n = 2^h – 1) and at least (n = F_{h+2}\geq \Omega(\Phi^h)) where (F_i) is (i)-th Fibonacci number and (\Phi = \frac{1 + \sqrt{5}}{2}). Note that ((T_{h+1} + 1) = (T_{h} + 1) + (T_{h-1} + 1) = F_{h+3}).

Algorithm

Definition of algorithm: A finite sequence of primitive instructions that, executed according to their well-specified semantics, provide a mechanical solution to the infinitely many instances of a possible complex mathematical problem.

  • Input/output
  • Complete in finite time

Examples

  • Powering: For \(x^n\) calculation, do binary expansion for n instead of doing \(n-1\) multiplication.

Stable matching

Stable solution: no unstable tuples: both professor and student do not prefer each other.

Running time optimality: (2n) people have own preference list of (n) people. No way to optimize it.

Binomial Trees / binomial heap

A binomial tree is an ordered tree defined recursively.

(B_k) has (n = 2^k) nodes and height (k)

Amortized Analysis

Definition

Let (\alpha.Method_1), …, (\alpha.Method_k) denote an implementation of an abstract data type. Let (T(n)) denote the worst-case cost of any sequence of (n) calls of (\alpha)’s methods. Then amortized cost of (\alpha) is (T(n)/n).

Note that amortized cost is different from average cost and expected cost. Amortized cost is about the cost of a sequence of operations, while average cost is a mean cost of all possible inputs, and expected cost considers not only random input but also internal randomness inside the algorithm.

Motivating example: binary counter

Value Binary representation Changed bits Potential
0 0000 - 0
1 0001 1 1
2 0010 2 1
3 0011 1 2
4 0100 3 1
5 0101 1 2
6 0110 2 2
7 0111 1 3
8 1000 4 1

If we increase a binary counter, then (\Theta(log N)) times single bit update need to be done. However, if we repeat this for M time then the total number of single-bit updates is (\Theta(M)) not (\Theta(M logN)).

We can represent a (N)-bit counter as (b_N…b_2b_1b_0). Then (b_n) is flipped for every (2^n) operations. After M operations, the total number of flip is (\sum\limits_{n = 0}^{log_2M} 2^n \leq 2M)

Potential method

https://en.wikipedia.org/wiki/Potential_method#Binary_counter

Virtues of TCS

Clearly describing what you want to say is important. Try to look for what is missing.

Input: n real numbers (x_j)
Output: YES if pairwise distinct, NO otherwise

Algorithm:

Let there be an input array A[n] = {(x_1, x_2, …, x_j, …, x_n) <span style="color: #ff0000;">}</span> Initialize empty hashmap(H)
FOR j := 1 to n: IF H contains(x_j) THEN RETURN NO ELSE insert(x_j) to H RETURN YES

Analysis: O(n)

Fast & Slowly growing functions

Slow Fast
\(2^n\) \(log N = min \{ n : 2^n \ge N \}\)
\(2^{2^{.^{.^2}}}\) \(log^*(N) = \#iterations \; of \; log \; before \; argument \le 1 \\= 1 + log^*(log N), \; N>1\)
For example, \(log(2^{64}) = 64, \; log log(2^{128}) = 7, \)

Akermann function

$$A_0(n) = n + 2, \quad A_{k+1}(0) = A_k(1), \quad A_{k+1}(n+1) = A_k(A_{k+1}(n))$$

$$A_1(n) = 2n + 3, \quad A_2(n) = s^{n+3} – 3, \quad A_3(n) = 2{\uparrow\uparrow}(n+3)-3$$

Disjoint-set data structure

Represents a set of vertices with a representative vertex called “handle”.

Operation Description
MARKDOWN_HASHb55b4a25ccb4c5592dfd802752ffabfcMARKDOWN_HASH
MARKDOWN_HASH30a0307673a6788ae8ad8afd87a0258bMARKDOWN_HASH
MARKDOWN_HASH3aa4adbb6beadcd5352d4d782bd17cc2MARKDOWN_HASH Weighted union heuristic: attach smaller to larger tree
MARKDOWN_HASH0c12b7c394a46a1ff0691bf03e05f25fMARKDOWN_HASH return MARKDOWN_HASH5b775e4252fada5e86ba18e59c397744MARKDOWN_HASH = MARKDOWN_HASH1f87fa08464489c75da30c19a99d096fMARKDOWN_HASH
MARKDOWN_HASH1a350b46effe67dbf1a109d9c7e2021aMARKDOWN_HASH MARKDOWN_HASH70f88d162c485c401bbc95340d5b115dMARKDOWN_HASH

Midterm hints

  • Binomial Heap: Merge, Remember how Binomial heap is implemented
    • Here is a sequence of operations, Please draw a binomial tree after these operations
  • Remember potential method work and how it is applied to binary counters
  • Fibonacci heap improve amortized cost of binomial heap
    • How it defined , what are its operations, amortized cost
  • After a sequence of Fib. heap operations how they result
  • Which of these three trees are relaxed binomial tree
  • How to evaluate Ackermann function, inverse Ackermann function
  • How union asdfasdf results asdfasdf
  • Analysis will not be a part of midterm

P/NP

Reduction \(3 SAT \le_p IS\)

$$N SAT \le_p 4 SAT \le_p 3 SAT \le_p IS \equiv_p CLIQUE \le_p SAT$$

Reduction \(IS \le_p SAT\)

Goal: Upon input of (the encoding of) a graph (G) and (k \in \mathbb{N}), produce in polynomial time a CNF formula (\Phi) such that: (\Phi) satisfiable iff (G) contains (\ge k) independent vertices.

Randomization: Motivation

$$ det\left(\begin{array} \
0 & x_{12} & x_{13} \
-x_{12} & 0 & x_{23} \
-x_{13} & -x_{23} & 0 \end{array} \right) = 0 – x_{12} x_{23} x_{13} + x_{13} x_{12} x_{23} = 0$$

 


Assignment 0

Online from February 29 (Monday); solution due by March 7 (Monday) 9am; feedback on March 8 (Tuesday) 4pm. Late submissions cannot be accepted!

This self-assessment is to be solved individually. (Homework assignments #1 and following are to be solved in groups…)

Problem 1 (10P)

A tournament is a directed graph with exactly one edge between every pair of vertices. (So for each pair (u,v)(u,v) of vertices, either the edge from uu to vv or from vv to uu exists, but not both.) You can think of the nodes as players in a tournament, where each player has to play against every other player. The edge points from the winner to the loser of a game.
A Hamiltonian path (not cycle) is a sequence of consecutive directed edges that visits every vertex exactly once.

Prove that every tournament contains at least one Hamiltonian path.

Solution

  1. When there are two nodes, then Hamiltonian path exists.
  2. If there is a Hamiltonian path, then the path still exists even after adding one more node.
    • If the new node has edges from the node, then it is new start point of Hamiltonian path.
    • If the new node has edges to the node, then it is new end point of Hamiltonian path.
    • If the new node has both edges from the node and edges to the node, then Hamiltonian path can detour the node.

 

Problem 2 (10P)

Professor Hastings has constructed a 23-node binary tree in which each node is labeled with a unique letter of the alphabet.

Preorder and postorder traversals of the tree visit the nodes in the following order:

  • Preorder: B K X E H L Z J W R C Y T S Q A P D F M N U G
  • Postorder: H J W Z R L E C X S Q T A Y K D M U G N F P B

Draw Professor Hastings’ tree and list the nodes in the order visited by an inorder traversal. Explain how you arrived at the answer!

 

 

Problem 3 (10P)

Solve the following recurrences. State tight asymptotic bounds for each function in the form Θ(f(n)) for some elementary function f(n). Assume reasonable but nontrivial base cases.

  • \(A(n)=4A(n−1)+1\)
  • \(B(n)=B(n−3)+n^2\)
  • \(C(n)=2C(n/2)+3C(n/3)+n^2\)
  • \(D(n)=2D(n/3)+\sqrt{n}\)

Advice: Don’t cheat on yourself by just applying the ‘Master Theorem’!

Solution

(A(n) = 4A(n-1) + 1 \= 4^2A(n-2)+4+1 \= 4^3A(n-3)+16+4+1 \= 4^{n-1}A(1) + 4^{n-1} + … + 4 + 1)
(\Theta(4^n))

(B(n) =)

(C(n): \Theta(n^2))
(C(n) \leq 6n^2 \leq 26\frac{n}{2}^2 + 36\frac{n}{3}^2 + n^2 = 6n^2)

(D(n) = 4D(\frac{n}{3}) + 2\sqrt{\frac{n}{3}} + \sqrt{n} \= 2^{log n}D() + \sqrt{n} + 2\sqrt{\frac{n}{3}} + 4\sqrt{\frac{n}{9}} + … \= 2^{log n}D() + \sqrt{n}(1 + \frac{2}{\sqrt{3}} +(\frac{2}{\sqrt{3}})^2 +(\frac{2}{\sqrt{3}})^3 + …))
(\Theta(n^{log_32}) <= \Theta(n^{0.62}))

 

Problem 4 (10P)

The Fibonacci numbers Fn are defined by the recurrence Fn=Fn1+Fn2, with base cases F0=0 and F1=1.

Prove that any non-negative integer can be written as the sum of distinct and non-consecutive Fibonacci numbers. That is, if FiFi appears in the sum, then Fi1Fi−1 and Fi+1Fi+1 do not appear in the sum. For example:

  • 17=F7+F4+F2
  • 42=F9+F6
  • 54=F9+F7+F5+F3+F1

 

Problem 5 (10P)

A perfect riffle shuffle, also known as a Faro shuffle, is performed by cutting a deck of cards exactly in half and then perfectly interleaving the two halves. There are two different types of perfect shuffles, depending on whether the top card of the resulting deck comes from the top half or the bottom half of the original deck.

An out-shuffle leaves the top card of the deck unchanged. After an in-shuffle, the original top card becomes the second card from the top. For example:

OutShuffle(A♠2♠3♠4♠5678) = A♠52♠63♠74♠8
InShuffle(A♠2♠3♠4♠5678) = 5A♠62♠73♠84♠

(If you are unfamiliar with playing cards, please refer to the Wikipedia article.)

Consider a deck of 2n2n distinct cards, for some non-negative integer nn. What is the effect of performing exactly nn perfect in-shuffles on this deck? Prove your answer!

Solution

Initial in-shuffle
(RSR and invert MSB)
out-shuffle
(RSR)
000 100 000
001 000 100
010 101 001
011 001 101
100 110 010
101 010 110
110 111 011
111 011 111

After n inversion, all bits will be inverted (2’s compliment).

Assignment 2

PROBLEM 7 (2+2+2+2+2P):
We have seen that a stable matching need not be unique.
(a) Specify, (b) describe, (c) analyze, and (d) justify the correctness of an (e) quadratic-time algorithm that verifies whether a given matching between n ‘men’ and n ‘women’ is stable.

 

PROBLEM 8 (2+2+2+2+2P):

  1. Prove that a binomial tree Bk has precisely \(\left( \begin{array}{c} k \\ d \\ \end{array} \right)\) nodes at depth d.
  2. Recalling the relationship between merging two binomial heaps and adding two binary numbers, describe an \(O(log n)\) algorithm for directly inserting a node.
  3. Find inputs that cause ExtractMin and DecreaseKey to run in time \(\Omega(log n)\).
  4. Argue that the running time of a sequence of n calls to InsertKey is \(O(n)\), not \(\Omega(n log n)\).
  5. Construct a sequence of n calls that produce a degenerate Fibonacci Heap of height \( \Omega(n)\).

 

PROBLEM 9 (1+3+3+3P):

Recall that counting from 1 to n in binary takes (\Theta(n)) steps; i.e., the increment operation has constant amortized cost as opposed to (\Theta(log n)) in the worst-case.

  1. Analyze the amortized cost of any mixed sequence of n binary increment and decrement operations, where decrementing 0 results in 0.
  2. The signed binary expansion represents \(N \in \mathbb{N}\) as \(\sum\nolimits_{j = 0}^{J – 1} b_j2^j\) for \(b_j \in \{ 0, 1, \bar{1} \} \), where \(\bar{1} = -1\); e.g., \(5_{10} = 0101 = 011\bar{1} = 10\bar{1}\bar{1} = 1\bar{1}01\).
    Describe an algorithm for both incrementing and decrementing; generalize the potential function \(\Phi\) from the lecture to show them to have constant amortized cost.
  3. Redundant arithmetic represents \(N \in \mathbb{N}\) as \(\sum\nolimits_{j = 0}^{J – 1} b_j2^j\) for \(b_j \in \{ 0, 1, 2 \} \); e.g. \(10_{10} = 1010 = 0202 = 0210 = 1002\)
    Consider the following algorithm for incrementing a number in this representation:

    Replace the rightmost occurrence of x2 with (x+1)0;
    If the rightmost digit is 0, change it to 1; otherwise to 2.

    1. Use it to count from 0 to 32, writing down all intermediate results.
    2. How can this be turned into an algorithm with constant worst-case complexity?
    3. What remains to prove in order to assert its correctness?
    4. Implement and run it to try to find a counterexample.
  4. Combine (b) and (c) to devise an algorithm for both incrementing and decrementing at constant worst-case cost. (You do not need to prove its correctness — as long as it is correct.)

Solution

  1. Let’s think about a repeated increment and decrement operations. For the best case, if the initial value of \(N\)-bit binary counter is zero, then each of increment operation and following decrement operation will flip only one bit, thus amortized cost for \(N\) operations will be \(N\). For the worst case, if the initial value is \(2^{N-1}-1\), then each of increment operation and decrement operation will flip \(N\) bits, thus amortized cost for \(N\) operations will be \(N^2\). As a result, mixed sequence of \(N\) binary increment and decrement operations have cost of \(\Omega(N)\) and \(O(N^2)\).
  2. Algorithm in pseudocode.
    Increment Decrement
    for (\(j\) = 0; \(j\) < \(J\); \(j\)++) {
        if (\(b_j\) == \(1\))
            \(b_j\) = 0;
        else {
            if (\(b_j\) == 0)
                \(b_j\) = 1;
            else
                \(b_j\) = 0;
            break;
        }
    }
    for (\(j\) = 0; \(j\) < \(J\); \(j\)++) {
        if (\(b_j\) == \(\bar{1}\))
            \(b_j\) = 0;
        else {
            if (\(b_j\) == 0)
                \(b_j\) = \(\bar{1}\);
            else
                \(b_j\) = 0;
            break;
        }
    }

    Let a potential \(\Phi = \sum\limits_{j = 0}^{J} b_j\). For example, \(\Phi(10\bar{1}1) = 1 + 0 + (-1) + 1 = 1\).
    For increment operation, let’s suppose \(i\)-th operation changes \(t_i\) bits from 1 to 0. Cost for the operation,
    $$c_i \leq t_i + 1$$
    If \(\Phi_i = 0\), then the \(i\)-th operation resets all \(J\) bits, so \(\Phi_{i-1} = t_i = J, \Phi_i = \Phi_{i – 1} – t_i\). If \(\Phi_i \lt 0\), the \(i\)-th operation resets \t(t_i\) bits, increment one bit, so \(\Phi_i = \Phi_{i-1} – t_i + 1\). Either way,
    $$\Phi_i \leq \Phi_{i – 1} – t_i + 1$$
    Therefore,
    $$\Phi_i – \Phi_{i – 1} \leq \Phi_{i-1} – t_i + 1 – \Phi_{i – 1} = 1 – t_i$$
    As a result, amortized cost
    $$c_i^\prime = c_i + \Phi_i – \Phi_{i – 1} \leq (t_i + 1) + (1 – t_i) = 2$$
    1. Counting from zero to 32.
      1
      2
      10 -> 11
      12
      20 -> 21
      101 -> 102
      110 -> 111
      112
      120 -> 121
      201 -> 202
      210 -> 211
      1011 -> 1012
      1020 -> 1021
      1101 -> 1102
      1110 -> 1111
      1112
      1120 -> 1121
      1201 -> 1202
      1210 -> 1211
      2011 -> 2012
      2020 -> 2021
      2101 -> 2102
      2110 -> 2111
      10111 -> 10112
      10120 -> 10121
      10201 -> 10202
      10210 -> 10211
      11011 -> 11012
      11020 -> 11021
      11101 -> 11102
      11110 -> 11111
      11112
    2. Constant worst-case complexity algorithm.
      Push \(j\) to a stack when \(b_j\) becomes 2. To find the rightmost occurrence of 2, just pop from the stack.
    3. ????
    4. Counting from 990 to 1024
      1110211102(= 990)
      1110211111(= 991)
      1111011112(= 992)
      1111011121(= 993)
      1111011202(= 994)
      1111011211(= 995)
      1111012012(= 996)
      1111012021(= 997)
      1111012102(= 998)
      1111012111(= 999)
      1111020112(= 1000)
      1111020121(= 1001)
      1111020202(= 1002)
      1111020211(= 1003)
      1111021012(= 1004)
      1111021021(= 1005)
      1111021102(= 1006)
      1111021111(= 1007)
      1111101112(= 1008)
      1111101121(= 1009)
      1111101202(= 1010)
      1111101211(= 1011)
      1111102012(= 1012)
      1111102021(= 1013)
      1111102102(= 1014)
      1111102111(= 1015)
      1111110112(= 1016)
      1111110121(= 1017)
      1111110202(= 1018)
      1111110211(= 1019)
      1111111012(= 1020)
      1111111021(= 1021)
      1111111102(= 1022)
      1111111111(= 1023)
      1111111112(= 1024)
  3. Represent \(N \in \mathbb{N}\) as \(\sum\nolimits_{j = 0}^{J – 1} b_j2^j\) for \(b_j \in \{ \bar{2}, \bar{1}, 0, 1, 2 \} \) where \(\bar{1}\) and \(\bar{2}\) are -1 and -2, respectively.
    Let there be two stacks, \(S_2\) and \(S_\bar{2}\).
    Increment operation:
    If \(S_2\) is not empty, then pop an integer \(i\) from \(S_2\), set \(b_i\) as \(0\),  increment \(b_{i+1}\), and push \(i + 1\) to \(S_2\) if \(b_{i + 1}\) is \(2\).
    Increment \(b_0\) and push \(0\) to \(S_2\) if \(b_0\) is \(2\) after the increment.
    Decrement operation:
    If \(S_\bar{2}\) is not empty, then pop an integer \(i\) from \(S_\bar{2}\), set \(b_i\) as \(0\),  decrement \(b_{i+1}\), and push \(i + 1\) to \(S_\bar{2}\) if \(b_{i + 1}\) is \(\bar{2}\).
    Decrement \(b_0\) and push \(0\) to \(S_\bar{2}\) if \(b_0\) is \(\bar{2}\) after the decrement.

Leave a Reply