Contents

## 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**

- When there are two nodes, then Hamiltonian path exists.
- 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 2*6*\frac{n}{2}^2 + 3*6*\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=Fn−1+Fn−2, 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 Fi−1Fi−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:

InShuffle(A♠2♠3♠4♠5♥6♥7♥8♥) = 5♥A♠6♥2♠7♥3♠8♥4♠

(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):**

- Prove that a binomial tree Bk has precisely \(\left( \begin{array}{c} k \\ d \\ \end{array} \right)\) nodes at depth d.
- Recalling the relationship between merging two binomial heaps and adding two binary numbers, describe an \(O(log n)\) algorithm for directly inserting a node.
- Find inputs that cause ExtractMin and DecreaseKey to run in time \(\Omega(log n)\).
- Argue that the running time of a sequence of n calls to InsertKey is \(O(n)\), not \(\Omega(n log n)\).
- 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.

- Analyze the amortized cost of any mixed sequence of n binary increment and decrement operations, where decrementing 0 results in 0.
- 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. - 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.- Use it to count from 0 to 32, writing down all intermediate results.
- How can this be turned into an algorithm with constant worst-case complexity?
- What remains to prove in order to assert its correctness?
- Implement and run it to try to find a counterexample.

- 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**

- 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)\).
- 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$$ -
- 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 - 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. - ????
- 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)

- Counting from zero to 32.
- 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.