Algorithms: Design and Analysis, Part 1 - Problem Set 3 - Question 5

Problem:

The minimum s-t cut problem is the following. The input is an undirected graph, and two distinct vertices of the graph are labelled "s" and "t". The goal is to compute the minimum cut (i.e., fewest number of crossing edges) that satisfies the property that s and t are on different sides of the cut.
Suppose someone gives you a subroutine for this s-t minimum cut problem via an API. Your job is to solve the original minimum cut problem (the one discussed in the lectures), when all you can do is invoke the given min s-t cut subroutine. (That is, the goal is to reduce the min cut problem to the min s-t cut problem.)

Now suppose you are given an instance of the minimum cut problem -- that is, you are given an undirected graph (with no specially labelled vertices) and need to compute the minimum cut. What is the minimum number of times that you need to call the given min s-t cut subroutine to guarantee that you'll find a min cut of the given graph?

Solution:

Wow - that's a mouthful, but the solution is simple. Fix $ s $ to be one of the vertex and $ t $ varies across all others, then we are done by picking the smallest one, therefore we need at most $ n - 1 $ call.

If I add two vertices $ s $ and $ t $ connected to every other nodes, then wouldn't I find the right min cut with just one call, the answer is no because that min cut will necessary be of size $ n $, and after removing the added edges the 'min' cut might not be minimal.

Algorithms: Design and Analysis, Part 1 - Problem Set 3 - Question 4

Problem:

Let $ 0 < \alpha < 1 $ be a constant, independent of $ n $. Consider an execution of RSelect in which you always manage to throw out at least a $ 1 - \alpha $ fraction of the remaining elements before you recurse. What is the maximum number of recursive calls you'll make before terminating?

Solution:

In the initial call, we have $ n $ elements.
In the first recursive call, we have at most $ \alpha n $ elements.
...
In the d^th recursive call, we have at most $ \alpha^d n $ elements.

If the recursion has to stops at the d^th recursive call, then $ \alpha^d n \le 1 $, that log on both side we get

$ d = -\frac{\log n}{\log \alpha} $.

Algorithms: Design and Analysis, Part 1 - Problem Set 3 - Question 3

Problem:

Let $ .5 < \alpha <1 $ be some constant. Suppose you are looking for the median element in an array using RANDOMIZED SELECT (as explained in lectures). What is the probability that after the first iteration the size of the subarray in which the element you are looking for lies is $ \le \alpha $ times the size of the original array?

Solution:

Let the size of the array be $ N $. The pivot is the x^th number in the sorted array.

Then as long as $ (1-\alpha) N < x < \alpha N $, then the median will be in the array smaller than of equals to $ \alpha N $.

If this is a little abstract, see this, suppose $ \alpha = 0.7 $ and the array has 10 elements, then as long as the pivot is the 4th, 5th, 6th, 7th element (array index start with 1), we should be fine as the array containing the median has length at most 6.

Now the question becomes what is the probability of the pivot lying in that range, the answer is simply $ p = 1 - (1 - \alpha) - (1 - \alpha) $ (i.e. the whole range minus the forbidden ones), simplifying, we get $ p = 2 \alpha - 1 $, and that is the answer.

Algorithms: Design and Analysis, Part 1 - Problem Set 3 - Question 2

Problem:

Let "output" denote the cut output by Karger's min cut algorithm on a given connected graph with $ n $ vertices, and let $ p=\frac{1}{\left(\begin{array}{c}n \\ 2\end{array}\right)} $. Which of the following statements are true?

[Choices elided]

Solution:

We know that the probability of finding any fixed minimum cut is lower bounded $ p $, so these two options is automatically true.

For every graph G with n nodes, there exists a min cut (A,B) such that
$ Pr[out=(A,B)] \ge  p $

For every graph G with n nodes and every min cut (A,B) of G,
$ Pr[out=(A,B)] \ge  p $

What is non-trivial is that whether or not there exists a graph and a min-cut such that the probability of finding it is at most $ p $. This is possible, for example, a graph with only two nodes and one edge, the probability of finding the min cut is 1 and that is also the same value for $ p $. Therefore this is also a correct option.

There exists a graph G with n nodes and a min cut (A,B) of G,
$ Pr[out=(A,B)] \le  p $

This is a tricky question and I screwed this one the first time.

Algorithms: Design and Analysis, Part 1 - Problem Set 3 - Question 1

Problem:

How many different minimum cuts are there in a tree with $ n $ nodes (ie. $ n - 1 $ edges) ?

Solution:

Any edge is a minimum cut, so there are n - 1 minimum cuts.

UTM Ideals Varieties and Algorithm - Chapter 1 Section 2 Exercise 3

Problem:

Solution:

It is the intersection of a circle with a hyperbola, so there are only four points, there is no point 'drawing' the points.

To solve the intersection points, note that $ x^2 + y^2 = 4 $ and $ x^2y^2 = 1 $.
That gives

$ \begin{eqnarray*} x^2(4 - x^2) &=& 1 \\ x^4 - 4x^2 + 1 &=& 0 \\ x^2 &=& 2 \pm \sqrt{3} \\ x &=& \pm \sqrt{2 \pm \sqrt{3}} \\ \end{eqnarray*} $

We could have solve $ y $ by back substituting, but here we can simply use a symmetric argument to conclude the four points must be:

$ (\sqrt{2 + \sqrt{3}}, \sqrt{2 - \sqrt{3}}) $
$ (\sqrt{2 - \sqrt{3}}, \sqrt{2 + \sqrt{3}}) $
$ (-\sqrt{2 + \sqrt{3}}, -\sqrt{2 - \sqrt{3}}) $
$ (-\sqrt{2 - \sqrt{3}}, -\sqrt{2 + \sqrt{3}}) $

UTM Ideals Varieties and Algorithm - Chapter 1 Section 2 Exercise 2

Problem:

Solution:

Note that $ y^2 $ is non-negative, therefore we only need to focus on range of $ x $ such that $ x(x - 1)(x - 2) $ is non-negative.

The only two such ranges is $ [0, 1] $ and $ [2, +\infty) $.

Next, we look at the range $ [0, 1] $, the curve start from 0 and go back to 0, therefore it must has a turning point, taking the first derivative we get

$ \begin{eqnarray*} f(x) &=& x(x - 1)(x - 2) \\ f'(x) &=& (x - 1)(x - 2) + x(x - 1) + x(x - 2) \\ &=& (x^2 - 3x + 2) + (x^2 - x) + (x^2 - 2x) \\ &=& 3x^2 - 6x + 2 \\ &=& 3(x^2 - 2x + 1) - 1 \end{eqnarray*} $

Therefore the curve turn at $ x = -\sqrt{\frac{1}{3}} + 1 = 0.42... $.

Last but not least, the curve is growing cubic fast in $ [2, +\infty) $, it is easy to sketch there.

It looks like a fish, isn't it?

UTM Ideals Varieties and Algorithm - Chapter 1 Section 2 Exercise 1

Problem:

Solution:

(Part a)

It is an ellipse, let me put it in a standard form.

$ \begin{eqnarray*} x^2 + 4y^2 + 2x - 16y + 1 &=& 0 \\ x^2 + 2x + 4y^2 - 16y &=& -1 \\ x^2 + 2x + 1 + 4y^2 - 16y + 16 &=& -1 + 1 + 16 \\ x^2 + 2x + 1 + 4(y^2 - 4y + 4) &=& 16 \\ (x + 1)^2 + 4(y - 2)^2 &=& 16 \\ \frac{(x + 1)^2}{4^2} + \frac{(y - 2)^2}{2^2} &=& 1 \\ \end{eqnarray*} $.

Therefore it is an ellipse with center $ (-1, 2) $ and radii on x-axis being 4, radii on y-axis being 2, it looks like this:

It can be parameterized with one parameter, so it should be 1 dimensional.

As an aside, if I add a 'curve' on this plot on excel, it looks like an lemon :(

(Part b)

This is really just $ x = \pm y $, therefore, it is the pair of straight line $ x = y $ and $ x = -y $.

I am not sure about the dimension of this one, but look like we cannot do that in one parameter, so at least two.

(Part c)

Let's solve the pair of equations

$ 2x + y - 1 = 0 $
$ 3x - y + 2 = 0 $.

The second equation shows $ y = 3x + 2 $, so just substitute that back to equation 1 to get

$ 2x + 3x + 2  - 1 = 0 $, solving get $x = -\frac{1}{5} $, $ y = \frac{7}{5} $

So this is simply the point $ (\frac{-1}{5}, \frac{7}{5}) $.

Just a point has dimension 0.

UTM Ideals Varieties and Algorithm - Chapter 1 Section 1 Exercise 6

Problem:

Solution:

Step 0: Induction hypothesis

Let $ S(n) $ be the statement that if $ f \in \mathbf{C}^n $ vanishes on every point of $ \mathbf{Z}^n $, then $ f $ is the zero polynomial.

Step 1: Induction basis

Suppose $ n = 1 $, then it is well known that if a polynomial has infinite number of zeroes, then it must be the zero polynomial.

Step 2: Induction

Suppose the statement $ S(n) $ is true for all $ n < k $, then when $ n = k $. For any fixed integers $ x_2 \cdots x_n $, $ f $ becomes a polynomial of 1 variable that vanish on all integers, so it must be a zero polynomial.

The coefficients of f (when interpreted as a polynomial in $ K[x_2, \cdots, x_n] $) must then be vanishing on all integers as well. Therefore, by the induction hypothesis, they must be zero polynomial as well.

Last but not least, a polynomial with all coefficients being zero polynomial is a zero polynomial itself, therefore we concluded $ S(k) $ is also true.

The presentation above is a little abstract, let show it in concrete terms.

Suppose we wanted to prove $ f(x, y) = axy + bx + cy $ is a constant polynomial, given this polynomial vanishes on all integers.

We write this polynomial in this form $ f(x, y) = (ax + c)y + bx $.

For any fixed x, say x = 2, we have $ g(y) = f(2, y) = (2a + c)y + 2b $, now this must be the zero polynomial because it vanishes on all integers, which means $ 2a + c $ and $ 2b $ are both 0.

But that must be true for all $ x $, not just $ x = 2 $, therefore we have
$ ax + c = 0 $ and $ bx = 0 $.

We can now show $ a, b, c $ must all be zero using the induction hypothesis now.

For part b, we replace the argument 'vanish on all integers' by 'vanish on more than $ M $ points and the proof proceed just like this above.

The key property is that, throughout the proof above, there will be no polynomial with degree larger than $ M $, therefore vanishing on a large enough grid is sufficient.

UTM Ideals Varieties and Algorithm - Chapter 1 Section 1 Exercise 5

Problem:

Solution:

a) $ (y^2z)x^5 + (-y^3)x^4 + (z)x^2 + (y + 2)x + (y^5 - y^3z - 5z + 3) $
b) $ y^5 + (-x^4 - z)y^3 + (x^5z + x)y + (x^2z + 2x - 5z + 3) $
c) $ (x^5y^2 + x^2 -y^3 - 5)z + (x^4y^3 + y^5 + xy + 2x + 3)$

A rather straightforward problem, terms in the brackets are the coefficients.

Algorithms: Design and Analysis, Part 1 - Programming Question 2

Problem:

Compute the number of comparison in QuickSort with different partitioning strategies

Solution: 

I don't really like this programming assignment, it is really just implement exactly as what the lecture slide said.

Algorithms: Design and Analysis, Part 1 - Problem Set 2 - Question 5

Problem:

Define the recursion depth of QuickSort to be the maximum number of successive recursive calls before it hits the base case --- equivalently, the number of the last level of the corresponding recursion tree. Note that the recursion depth is a random variable, which depends on which pivots get chosen. What is the minimum-possible and maximum-possible recursion depth of QuickSort, respectively?

Solution:

The minimum possible depth occurs when we pick median all the time, and the minimum depth would be $ \lg n = \theta(\log n) $.

The maximu mpossible depth occurs when we pick the smallest element all the time, and the maximum depth would be $ n = \theta(n) $.

Algorithms: Design and Analysis, Part 1 - Problem Set 2 - Question 4

Problem:

Now assume that you achieve the approximately balanced splits above in every recursive call --- that is, assume that whenever a recursive call is given an array of length k, then each of its two recursive calls is passed a subarray with length between $ \alpha k $ and $ (1 - \alpha) k$ (where $ 0 < \alpha < .5 $). How many recursive calls can occur before you hit the base case, as a function of $ \alpha $ and the length n of the original input? Equivalently, which levels of the recursion tree can contain leaves? Express your answer as a range of possible numbers $ d $, from the minimum to the maximum number of recursive calls that might be needed. [The minimum occurs when you always recurse on the smaller side; the maximum when you always recurse on the bigger side.]

Solution:

The smallest $ d $ occurs when we always recurse on the smaller side, therefore $ \alpha^d n = 1 $, or in other words,

$ \begin{eqnarray*} \log(\alpha^d n) = 0 \\ d\log(\alpha) +\log(n) = 0 \\ d = -\frac{\log n}{\log \alpha} \end{eqnarray*} $

Similarly, the largest $ d $ occurs when we always recurse on the larger side, therefore $ (1 - \alpha)^dn = 1 $, we get a similar upper bound.

The answer is now $ -\frac{\log n}{\log \alpha} \le d \le -\frac{\log n}{\log (1 - \alpha)} $

Algorithms: Design and Analysis, Part 1 - Problem Set 2 - Question 3

Problem:

Let $ 0 < \alpha < 0.5 $ be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in lecture. What is the probability that, with a randomly chosen pivot element, the Partition subroutine produces a split in which the size of the smaller of the two subarrays is $ \ge \alpha $ times the size of the original array?

Solution:

It is easy to think in terms of actual value for $ \alpha $ and $ n $, for example, $ n = 40 $ and $ \alpha = 0.25 $, then we need to make sure the pivot is chosen so that it is either larger than (or equal to) the 10^th element or smaller than (or equal to) the 30^th element, so we are clear in general how to reason about this.

Therefore, the answer is $ 1 - 2 \alpha $.

Algorithms: Design and Analysis, Part 1 - Problem Set 2 - Question 2

Problem:

Consider the following pseudocode for calculating ab (where a and b are positive integers)

      FastPower(a,b) : 

              if b = 1 

                   return a 

              otherwise 

                   c := a*a 

                   ans := FastPower(c,[b/2]) 

               if b is odd 

                   return a*ans 

               otherwise return ans 

end

Here [x] denotes the floor function, that is, the largest integer less than or equal to x.
Now assuming that you use a calculator that supports multiplication and division (i.e., you can do multiplications and divisions in constant time), what would be the overall asymptotic running time of the above algorithm (as a function of b)?

Solution:

Denote the time to run this algorithm $ T(n) $, (we use $ n $ here instead of $ b $ to avoid name clash with the master method variables), so we have:

$ T(n) = T([n/2]) + O(1) $.

Using the master method terminologies, we have

$ a = 1 $, $ b = 2 $, $ d = 0 $.

Notice we have $ 1 = a = b^d = 1 $, therefore, the answer is $ O(\log n) $.

Algorithms: Design and Analysis, Part 1 - Problem Set 2 - Question 1

Problem:

This question will give you further practice with the Master Method. Suppose the running time of an algorithm is governed by the recurrence $ T(n)=5∗T(n/3) + 4n $. What's the overall asymptotic running time (i.e., the value of $T(n) $)?

Solution:

Using the master theorem terminologies, $ a = 5 $, $ b = 3 $, $ d = 1 $.

Notice $ 5 = a > b^d = 3 $, therefore, the answer is $ \Theta (n^{\log_3 5}) $.

Bitcoin and Cryptocurrency Technologies - Quiz 11 Problem 4

According to the lecture, what are some issues with using cryptography to enforce contracts? (check all that apply)

Losing a device containing your private keys could result in the inability to use your smart property	Correct
It is problematic if the state does not recognize a block chain based notion of property because the state will always be the final arbiter	Correct
Cryptographic security lacks the corrective controls of real-world security such as prosecution of criminals	Correct
The technology behind smart contracts is not powerful enough to express the logic needed for real-world contracts like derivatives	Wrong

Bitcoin and Cryptocurrency Technologies - Quiz 11 Problem 3

Data feeds.... (check all that apply)

can be decentralized to a degree using multisignatures	Correct
are useful for implementing decentralized prediction markets	Correct
allow arbiters to assert facts about the world into the block chain	Correct

Bitcoin and Cryptocurrency Technologies - Quiz 11 Problem 2

Which of these are potential ways to improve security when using Bitcoin as a platform for decentralized commerce? (check all that apply)

Escrow and dispute mediation	Correct
Warranties	Wrong
Atomic exchange	Correct
Reputation	Correct

Bitcoin and Cryptocurrency Technologies - Quiz 11 Problem 1

In the smart property scenario presented, where Alice sells her car to Bob via an atomic transaction:

Requires modifications to Bitcoin because there is no way for two different people who don't trust each other to securely sign the same transaction	Wrong
Alice and Bob must be physically near the car for the transfer of control to take effect	Wrong
Bob must make sure that Alice deletes her private key so that she does not retain the ability to activate the car	Wrong
The protocol doesn't prove to Bob, before the sale, that the transaction output that Alice wants to sell him actually corresponds to the car he wants to buy	Correct

Bitcoin and Cryptocurrency Technologies - Quiz 10 Problem 3

Here are several ways in which new coins in an altcoin can be allocated to users. Which of these require changes to Bitcoin?

Altcoin allocation is "grandfathered" from Bitcoin - every owner of bitcoins becomes the owner of a certain number of altcoins (in a fixed proportion of bitcoins to altcoins)	Wrong
All coins in the altcoin are generated through (merge) mining and are allocated to miners	Wrong
Bitcoin is used as a "reserve currency" for the altcoin - a unit of the altcoin can be created by putting 1 BTC into escrow; the bitcoin can be released by provably destroying one altcoin unit	Correct
A unit of the altcoin is created by provably destroying one bitcoin	Wrong

Bitcoin and Cryptocurrency Technologies - Quiz 10 Problem 2

In a merge-mined altcoin scenario:

Bitcoin blocks include transactions from the altcoin	Wrong
Bitcoin block headers include the merkle root of transactions for an altcoin block	Correct
Altcoin block headers include a hash pointer to a Bitcoin block	Wrong
The altcoin has the same hash target as Bitcoin at all times	Wrong

Bitcoin and Cryptocurrency Technologies - Quiz 10 Problem 1

Which of these statements about altcoins are true? (check all that apply)

Bitcoin is the most widely forked cryptocurrency	Wrong
Bitcoin has a higher "market capitalization" than all altcoins combined	Correct
Namecoin supports additional functionality such as domain-name registration that is not found in Bitcoin	Correct

Bitcoin and Cryptocurrency Technologies - Quiz 9 Problem 5

In a prediction market where shares pay out if and only if a potential future event happens: (check all that apply)

The average price of all shares traded as a fraction of the payout is an estimate of the event's likelihood	Wrong
A trader who is able to control or influence the outcome of the event will likely be able to make a profit	Correct
The current price of shares as a fraction of the payout is an estimate of the event's likelihood	Correct

Bitcoin and Cryptocurrency Technologies - Quiz 9 Problem 4

Which of these are advantages of using the Bitcoin blockchain to generate a cryptographic beacon? (check all that apply)

The beacon outputs random bits at frequent intervals	Correct
No central authority is needed	Correct
Fresh random bits can be obtained at any desired future time	Wrong
The cost to an attacker to manipulate the beacon's output is quantifiable	Correct
Manipulating the beacon output requires 51% mining power	Wrong

Bitcoin and Cryptocurrency Technologies - Quiz 9 Problem 3

Which of the following features does the Bitcoin secure multi-party lottery system presented depend on? (check all that apply)

Multisignatures	Correct
Colored coins	Wrong
Time-locked transactions	Correct
Hash commitments	Correct
Micropayments	Wrong

Bitcoin and Cryptocurrency Technologies - Quiz 9 Problem 2

The OpenAssets protocol works by

Forking Bitcoin to allow many different types of "colored" coins	Wrong
Enabling conversion between Bitcoin and a new type of coin	Wrong
Associating extra metadata with bitcoins	Correct
Exploiting non-fungibility of bitcoins to impose a blacklist	Wrong

Bitcoin and Cryptocurrency Technologies - Quiz 9 Problem 1

In which of these situations could secure timestamping be useful? Assume that there is no way to prove that you didn’t timestamp multiple values

Proving possession of a document at a specific time	Correct
Proving that you can predict the winner of the 2016 US presidential election	Wrong
Securely saving a document at a specific time	Wrong
Proving that you don't know something at a specific time	Wrong

UTM Ideals Varieties and Algorithm - Chapter 1 Section 1 Exercise 4

Problem:

Solution:

Step 1: The set $ \mathbf{F} - \{0\} $ together with multiplication is a group - all axioms can be trivially verified by virtue that $ \mathbf{F} $ is a finite field.

Step 2: The set $ a^p $, $ \forall p \in \mathbf{Z} $, $ a \neq 0 \in \mathbf F $ is the cyclic subgroup generated by $ a $. As such, the subgroup has an order $ r \mid q-1 $. Therefore $ a^{q-1} = (a^r)^k = 1^k = 1 $. $a^r = 1 $ is because it is a cyclic subgroup.

Step 3: For $ a \ne 0 $, the above show that $ a^{q} = a(a^{q-1}) = a $, therefore $ a^q - a = 0$. It is obvious that $ a^q - a = 0 $ for $ a = 0 $ as well.

Therefore we have just proved that $ a^q - a = 0 $ for all $ a \in \mathbf{F} $.

MIT 6.002 poster

Problem:

Saw this poster in MIT building 38 for their course 6 (i.e. EECS) - Note the @mit email address.

Solution:

The potential at the positive terminal of the power supply is -3.001V

The potential at the negative input terminal of the operational amplifier is 0 volt because it is a differential amplifier and negative feedback will drive it to 0V

The ideal operational amplifier characteristic ensure no current will flow into the amplifier, so current flows from Vout will flow all the way back to ground at the negative terminal of the power supply, this make the two resistors simply a potential divider.

Therefore $ V_{out} $ is 6.002, that is the course number of Circuits and Electronics in MIT!

Last I learnt the operational amplifier back in my high school days at around 1999, it has been 15 years since then.

Some trigonometry formula (IV)

Last time we proved $ \sin 3x = \frac{1}{4}(3\sin x - \sin 3x) $ and we promised to go for the $ \sin^n x $, so here we are, using recurrences.

We start with:

$ \sin^{n - 2} x = \sum a_j \sin jx $

Next we multiply $ \sin^2 x $ on both side and get

$ \begin{eqnarray*} \sin^{n - 2} x &=& \sum a_j \sin jx \\ \sin^n x &=& \sum a_j \sin^2 x \sin jx \\ &=& \frac{1}{2}\sum a_j (\sin x (\cos (x - jx)) - \cos (x + jx))) \\ &=& \frac{1}{2}\sum a_j (\sin x \cos (x - jx)) - \sin x \cos (x + jx)) \\ &=& \frac{1}{4}\sum a_j (\sin (x + x - jx) + \sin (x - (x - jx)) - \sin (x + x + jx) - \sin (x - (x + jx))) \\ &=& \frac{1}{4}\sum a_j (\sin (2 - j)x + \sin (jx) - \sin (j + 2)x - \sin (-jx)) \\ &=& \frac{1}{4}\sum a_j (-\sin (j - 2)x + \sin (jx) - \sin (j + 2)x + \sin (jx)) \\ &=& \frac{1}{4}\sum a_j (-\sin (j - 2)x + 2\sin (jx) - \sin (j + 2)x) \\ \end{eqnarray*} $

So that's the theory. Imagine this, take every term in the sine series, push a negative value to your neighbors, and double itself. Sum these little pieces together

$ \begin{eqnarray*} \sin^3 x &=& \frac{1}{4}(-\sin 3x + 2\sin x - \sin (-x)) \\ \end{eqnarray*} $

We apply the principle once again, we get

1 -2 1
  -2 4 -2
     1 -2 1

$ \sin^5 x = \frac{1}{16}(\sin 5x - 4\sin(3x) + 6\sin x - 4 \sin(-x) + \sin(-3x)) $

Note the beautiful symmetry and binomial coefficients!

UTM Ideals Varieties and Algorithm - Chapter 1 Section 1 Exercise 3

Problem:

Solution:

(Part a)

The closure, associativity, identity properties are obvious. The only thing unclear is why such an operation has multiplicative inverse.

Note that for a fixed $ a \neq 0 $, if $ x \neq y $, then $ ax \neq ay $ because otherwise $ a(x - y) = 0 $ and that is impossible if both of them are non-zero.

When $ x $ varies from 1 to $ p $, there are $ p $ different $ ax $ values ranging from 1 to $  p $. By the pigeonhole principle one of them must be 1.

(Part b)

Thanks for the hint for using the Lagrange's theorem, we know that the subgroup generated by $ a $ have an order $ s $ which is a factor of $ p - 1 $. Now we can write $ a^{p-1} = a^{ks} = (a^s)^k = 1^k = 1 $.

For myself in the future, I need to explain more why $ a^s = 1 $. Consider the following sequence that represent the cyclic subgroup.

$ a^0, a^1 \cdots a^{s-1} $.

Now it is obvious why $ a^s = 1 $

(Part c)

Again, thanks for the hint. It is obvious now if $ a = 0, a^p = 0 = a $. If $ a \neq 0 $, part b applies and just multiply both side by $ a $.

(Part d)

What else would that be? $ a^p - a $, that has to be 0.

Algorithms: Design and Analysis, Part 1 - Programming Question 1

Problem:

Compute the number of inversion in a text file containing integers 1 - 100,000

Solution:

The key idea is to count the number of inversions during mergesort.

Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 5

Problem:

Arrange the following functions in increasing order of growth rate (with g(n) following f(n) in your list if and only if f(n)=O(g(n))).

a) $ \sqrt{n} $
b) $ 10^n $
c) $ n^{1.5} $
d) $ 2^{\sqrt{\log n}} $
e) $ n^{\frac{5}{3}} $

Solution:

The simplest approach I can think of is to compute a bunch of values:

	$ \sqrt{n} $	$ 10^n $	$ n^{1.5} $	$ 2^{\sqrt{\log n}} $	$ n^{\frac{5}{3}} $
1	1	10	1	1	1
2	1.4142	100	2.8284	1.4627	3.1748
3	1.7321	1000	5.1962	1.6141	6.2403
4	2	10000	8	1.7123	10.079
5	2.2361	100000	11.18	1.7851	14.62
6	2.4495	1E+06	14.697	1.8431	19.812
7	2.6458	1E+07	18.52	1.8912	25.615
8	2.8284	1E+08	22.627	1.9323	32
9	3	1E+09	27	1.9682	38.941
10	3.1623	1E+10	31.623	2	46.416
11	3.3166	1E+11	36.483	2.0286	54.407
12	3.4641	1E+12	41.569	2.0546	62.898
13	3.6056	1E+13	46.872	2.0783	71.874
14	3.7417	1E+14	52.383	2.1003	81.323
15	3.873	1E+15	58.095	2.1206	91.233
16	4	1E+16	64	2.1396	101.59
17	4.1231	1E+17	70.093	2.1573	112.4
18	4.2426	1E+18	76.368	2.1741	123.63
19	4.3589	1E+19	82.819	2.1898	135.29
20	4.4721	1E+20	89.443	2.2048	147.36

Now it is totally obvious the order should be

$ 2^{\sqrt{\log n}} < \sqrt{n} < n^{1.5} < n^{\frac{5}{3}} < 10^n $

In fact, looking it in retrospective, after taking log (and remember in asymptotics base does not matter), the solution is very obvious.

In the sublinear range, we have $ \sqrt{\log n} < \frac{1}{2}\log{n} $ 

In the polynomial range, we have $ 1.5 < \frac{5}{3} $

Exponential grow fastest $  10^n $

Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 4

Problem:

k-way-Merge Sort. Suppose you are given k sorted arrays, each with n elements, and you want to combine them into a single array of kn elements. Consider the following approach. Using the merge subroutine taught in lecture, you merge the first 2 arrays, then merge the 3rd given array with this merged version of the first two arrays, then merge the 4th given array with the merged version of the first three arrays, and so on until you merge in the final (kth) input array. What is the running time taken by this successive merging algorithm, as a function of k and n? (Optional: can you think of a faster way to do the k-way merge procedure ?)

Solution:

For simplicity, we say the time required for a merge is simply equal to the sum of the list lengths.

So for the first merge, we have $ T(1) = n + n $
For the second merge, we have $ T(2) = n + 2n $.
...

The overall sum of these numbers would be $ \frac{n\sum\limits_{i = 2}^{k}}{k} = \frac{n(k(k+1) - 1)} = O(nk^2) $.

The last equality in some sense is trivial. In some sense, it is totally non-obvious what do we actually mean when we put two variables in the Big Oh notation. Let's clarify what is going on there.

The faster way to do k-way-Merge sort is to use a priority queue, see the implementation at my other blog: LeetCode OJ - Merge k Sorted Lists

Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 3

Problem:

Assume again two (positive) nondecreasing functions $ f $ and $ g $ such that $ f(n)=O(g(n)) $. Is $ 2^{f(n)}=O(2^{g(n)}) $ ?

Solution:

Not really, let us check some simple special case.

Case 1: $ f(n) = g(n) = n $. In this case, it $2^n = O(2^n) $ is certainly true.
Case 2: $ f(n) = 10n, g(n) = n $. In this case, we have $ 2^{10n} \neq O(2^n) $.

To understand case 2, suppose the contrary, there would exists integers $ c $ and $ n_0 $ such that $ 2^{10n} \leq c2^n $, but then $2^{9n} \leq c $ which is absurd.

With that, we can be sure that:

The statement is not always true.
The statement is not always false.

What is the necessary condition for the statement to be true?

Consider the very same proof above, what we really want is that instead of the statement being absurd, we want it to be true for sure, so we have

$ 2^{f(n)} \leq c2^{g(n)} $, leading to $ 2^{f(n) - g(n)} \leq c $. We can be sure that will be true if $ f(n) - g(n) \leq 0 $, or in other words, $ f(n) \leq g(n) $.

Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 2

Problem:

You are given functions f and g such that $ f(n)=O(g(n)) $. Is $ f(n)∗\log_2(f(n)c)=O(g(n)∗\log_2(g(n))) $ ? (Here c is some positive constant.) You should assume that $ f $ and $ g $ are nondecreasing and always bigger than 1.

Solution:

Using the definition of the Big-Oh notation, we are given:

$ f(n) < c_1 g(n) $ for $ n > n_0 $.

Let's try to derive a bound for the left hand side, we have

$ \begin{eqnarray*} f(n) & < & c_1 g(n) \\ f(n)^c & < & (c_1 g(n))^c \\ \log_2(f(n)^c) & < & \log_2((c_1 g(n))^c) \\ \log_2(f(n)^c) & < & c\log_2(c_1) + c\log_2(g(n)) \\ f(n)\log_2(f(n)^c) & < & cc_1 g(n)\log_2(c_1) + cc_1 g(n)\log_2(g(n)) \\ \end{eqnarray*} $

So far, the proof is obvious:
The second line comes from the assumption that the values are bigger than 1
The third line comes from logarithm is monotonic.
The rest is just simplification of properties of log.

To simplify things further, we get $ d = cc_1 \log_2(c_1) $ and $ e = cc_1 $, so we have

$ \begin{eqnarray*} & & f(n)\log_2(f(n)^c) \\ & < & dg(n) + eg(n)\log_2(g(n)) \\ & = & g(n)(d + e\log_2(g(n)) \\ & = & g(n)(d\frac{\log_2(g(0))}{\log_2(g(0))} + e\log_2(g(n)) \\ & \le & g(n)(\frac{d}{\log_2(g(0))}\log_2(g(n)) + e\log_2(g(n)) \\ & = & (\frac{d}{\log_2(g(0))} + e)g(n)\log_2(g(n) \\ \end{eqnarray*} $

The critical line above is line 4, where we use the fact that g(n) is non-decreasing. Together we proved $ f(n)∗\log_2(f(n)c)=O(g(n)∗\log_2(g(n))) $

Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 1

Problem:

3-way-Merge Sort : Suppose that instead of dividing in half at each step of Merge Sort, you divide into thirds, sort each third, and finally combine all of them using a three-way merge subroutine. What is the overall asymptotic running time of this algorithm? (Hint: Note that the merge step can still be implemented in $ O(n) $ time.)

Solution:

Step 1: Write down the recurrence

$ T(1) = O(1) $
$ T(n) = 3T(\frac{n}{3}) + O(n) $

Step 2: Assuming $ n = 3^k $, simplify the recurrence

Let $ S(k) = T(3^k) $, therefore, we have

$ S(0) = O(1) $
$ S(k) = 3S(k - 1) + O(3^k) $

Step 3: We solve the recurrence

$ \begin{eqnarray*} & & S(k) \\ &=& 3S(k - 1) + O(3^k) \\ &=& 3(3(S(k - 2) + O(3^{k - 1})) + O(3^k) \\ &=& 3^2S(k - 2) + O(3^k) + O(3^k) \\ &=& 3^2S(k - 2) + 2O(3^k) \\ &=& 3^kS(k - k) + kO(3^k) \\ &=& 3^kO(1) + kO(3^k) \\ &=& O(k3^k) \\ &=& O(n \log n) \\ \end{eqnarray*} $

UTM Ideals Varieties and Algorithm - Chapter 1 Section 1 Exercise 2

Problem:



Solution:

It is interesting to look at the finite field as boolean values and think of operators as logic gates. Multiply is AND and Addition is XOR, then this problem is really easy.

a) We have XOR(AND(x, x, y), AND(x, y, y)), there are two cases:

x and y are both 1, in this case, we got XOR(1, 1) = 0
otherwise, we get XOR(0, 0) = 0

Proposition 5 states that the only function that have every point in it zero set is the zero function if the field is infinite. In this case, the field is finite, that simply does not apply.

b) Using the same logic gate trick, we do this

$ g(x, y, z) = xyz + xyz^2 $

c) Using the very same trick, we also have

$ g(x_1, x_2, ... x_n) = x_1 x_2 ... x_n + x_1 x_2 ... x_n^2 $.

As a note, for any polynomial, we can add that polynomial to it to form another polynomial that yield exactly the same zero set!

Some trigonometry formula (III)

Now we are starting to do something fun out of what we derived. The goal is to find out an expression for $ \sin^n x $ for odd $ n $ in terms of $ \sin k x $ only.

Obviously, we have a base case for $ n = 1 $, that give $ \sin x = \sin x $, not very interesting, I know.

How about $ \sin^3 x $? We can start using the product to sum formula we derived.


$ \begin{eqnarray*} & & \sin^3 x \\ &=& \sin x (\sin x (\sin x)) \\ &=& \sin x (\frac{1}{2}(\cos(x - x) - \cos(x + x))) \\ &=& \sin x (\frac{1}{2}(\cos(0x) - \cos(2x))) \\ &=& \frac{1}{2}(\sin x \cos(0x) - \sin x \cos(2x)) \\ &=& \frac{1}{2}(\frac{1}{2}(\sin(x + 0x) + \sin(x - 0x)) - \frac{1}{2}(\sin(x + 2x) + \sin(x - 2x))) \\ &=& \frac{1}{4}(\sin(x + 0x) + \sin(x - 0x) - \sin(x + 2x) - \sin(x - 2x)) \\ &=& \frac{1}{4}(\sin(x) + \sin(x) - \sin(3x) - \sin(-x)) \\ &=& \frac{1}{4}(\sin(x) + \sin(x) - \sin(3x) + \sin(x)) \\ &=& \frac{1}{4}(3\sin(x) - \sin(3x)) \\ \end{eqnarray*} $

You probably wondered, why do I keep all those $ \cos 0x $ around. That is done to show that exactly the same trick can be applied to general $ n $.

Let's do that in the next post!

Bitcoin and Cryptocurrency Technologies - Quiz 8 Problem 4

Which of these is true of virtual mining? (check all that apply)

Virtual mining does away with most of the power requirements of proof-of-work systems	Correct
Several variations of virtual mining have been proposed	Correct
A proof-of-stake system makes 51% attacks impossible	Wrong

Bitcoin and Cryptocurrency Technologies - Quiz 8 Problem 3

In a vigilante attack against a mining pool, the attacker...

discards both shares and blocks that he finds	Wrong
submits shares but discards blocks	Correct
discards shares while submitting blocks to a different mining pool	Wrong

Bitcoin and Cryptocurrency Technologies - Quiz 8 Problem 2

Proof-of-useful-work cryptocurrency designs... (check all that apply)

differ from traditional volunteer distributed computing projects because cryptocurrencies cannot rely on a trusted administrator to select and distribute the problems to be solved	Correct
should preferably be based on problems whose solution benefits the public, rather than the solver, to avoid skewing the incentives of miners	Correct
have been successfully used to solve computational problems such as protein folding	Wrong

Bitcoin and Cryptocurrency Technologies - Quiz 8 Problem 1

ASIC resistance... (check all that apply)

is a response to the centralization of Bitcoin mining	Correct
has been successfully achieved in practice using the scrypt memory-hard hash function	Wrong
seeks to make it more appealing to mine with regular consumer devices than it is today	Correct

Bitcoin and Cryptocurrency Technologies - Quiz 7 Problem 6

Which of these are signs that there might be a market failure? (check all that apply)

Customers are unable to tell the difference between high-quality and low-quality products	Correct
Sellers agree with each other to raise prices	Correct
The market is completely unregulated	Wrong
Sellers agree not to compete with each other and offer a reduced selection of products	Correct

In fact, unregulated market means market success, it can manage itself!

Bitcoin and Cryptocurrency Technologies - Quiz 7 Problem 5

A reputation-based approach to fixing a lemons market might not work: (check all that apply)

When consumers don't do repeat business with the same entity	Correct
When sellers don't provide warranties for products	Wrong
At the end of a sellers presence in the market	Correct
At the beginning of a sellers presence in the market	Correct

Bitcoin and Cryptocurrency Technologies - Quiz 7 Problem 4

According to the lecture, what steps do governments take to prevent money laundering? (check all that apply)

Require a variety of companies to file reports describing any large transactions they are a party to	Correct
Constantly monitor the Bitcoin network and block chain	Wrong
Limit the maximum size of financial transactions	Wrong
Require some businesses that handle money to know their customers identities	Correct

Bitcoin and Cryptocurrency Technologies - Quiz 7 Problem 3

According to the lecture, whats one way that governments have tried to enforce capital controls in a world with Bitcoin?

Disconnecting Bitcoin from the local fiat currency	Correct
Purchasing mining hardware and attempting a Goldfinger attack	Wrong
Blocking the Bitcoin protocol	Wrong
Shutting down Bitcoin-based markets for illegal items such as Silk Road	Wrong

The last one is incident that actually happened, it is just that it has nothing to do with capital control.

Bitcoin and Cryptocurrency Technologies - Quiz 7 Problem 2

Which participants in the Bitcoin ecosystem have some amount of power in a negotiation about rule-setting? (check all that apply)

Payment services	Correct
Miners	Correct
Investors	Correct
Merchants	Correct
Bitcoin Core developers	Correct

Everyone can decide whether or not to adopt the rule or not, so all of them is correct.

Bitcoin and Cryptocurrency Technologies - Quiz 7 Problem 1

Which of the following is true about a fork of Bitcoins rules which results in a fork of the block chain into two branches?

The fork doubles the total value of the currency	Wrong
The fork will eventually be resolved due to the longest valid branch rule	Wrong
A transaction can be valid in both forks	Correct
Anyone who owned bitcoins before the fork can choose which branch to transfer their coins to	Wrong

The value is determine by the market, which would unlikely be doubled just because of rule split.

The fork is due to rule difference and therefore will not converge.

The fork can choose to accept the previous BitCoin or not.

UTM Ideals Varieties and Algorithm - Chapter 1 Section 1 Exercise 1

Problem:



Solution:

Instead of exhausting the formula, it is easier to describe and prove by defining those operation as mod 2 operations.

Now addition mod 2 is closed, associative, commutative, has identity 0 and inverse well defined.

Multiplication is closed, associative, commutative and distributive under addition.
The only non trivial thing is multiplicative inverse, but that is trivial for mod 2 because the only element need a multiplicative is 1, which is simply itself.

Some trigonometry formula (II)

Following the last post, we now introduce the interesting consequences for the formula we derived. Remember we have these


$ \begin{eqnarray*} \sin(\alpha + \beta) &=& \sin \alpha \cos \beta + \sin \beta \cos \alpha \\ \sin(\alpha - \beta) &=& \sin \alpha \cos \beta - \sin \beta \cos \alpha \\ \cos(\alpha + \beta) &=& \cos \alpha \cos \beta - \sin \beta \sin \alpha \\ \cos(\alpha - \beta) &=& \cos \alpha \cos \beta + \sin \beta \sin \alpha \end{eqnarray*} $

There are a few things we could do, for example, we could substitute $ \beta = \alpha $ and get

$ \begin{eqnarray*} & & \sin(2\alpha) \\ &=& \sin(\alpha + \alpha) \\ &=& \sin \alpha \cos \alpha + \sin \alpha \cos \alpha \\ &=& 2 \sin \alpha \cos \alpha \\ \end{eqnarray*} $

$ \begin{eqnarray*} & & \cos(2\alpha) \\ &=& \cos(\alpha + \alpha) \\ &=& \cos \alpha \cos \alpha - \sin \alpha \sin \alpha \\ &=& \cos^2 \alpha - \sin^2 \alpha \end{eqnarray*} $

More interestingly, we can add and subtract these formula together to do something, for example

$ \begin{eqnarray*} & & \sin(\alpha + \beta) + \sin(\alpha - \beta) \\ &=& \sin \alpha \cos \beta + \sin \beta \cos \alpha + \sin \alpha \cos \beta - \sin \beta \cos \alpha \\ &=& \sin \alpha \cos \beta + \sin \alpha \cos \beta \\ &=& 2 \sin \alpha \cos \beta \\ \end{eqnarray*} $

$ \begin{eqnarray*} & & \sin(\alpha + \beta) - \sin(\alpha - \beta) \\ &=& \sin \alpha \cos \beta + \sin \beta \cos \alpha - \sin \alpha \cos \beta + \sin \beta \cos \alpha \\ &=& \sin \beta \cos \alpha + \sin \beta \cos \alpha \\ &=& 2 \sin \beta \cos \alpha \\ \end{eqnarray*} $

$ \begin{eqnarray*} & & \cos(\alpha + \beta) + \cos(\alpha - \beta) \\ &=& \cos \alpha \cos \beta - \sin \beta \sin \alpha + \cos \alpha \cos \beta + \sin \beta \sin \alpha \\ &=& \cos \alpha \cos \beta + \cos \alpha \cos \beta \\ &=& 2 \cos \alpha \cos \beta \\ \end{eqnarray*} $

$ \begin{eqnarray*} & & \cos(\alpha - \beta) - \cos(\alpha + \beta) \\ &=& \cos \alpha \cos \beta + \sin \beta \sin \alpha - \cos \alpha \cos \beta + \sin \beta \sin \alpha \\ &=& \sin \beta \sin \alpha + \sin \beta \sin \alpha \\ &=& 2 \sin \beta \sin \alpha \end{eqnarray*} $

If you look at these equation closely, you notice we converted a sum to a product, this can be very useful. To summarize, in this post, we have derived

$ \begin{eqnarray*} \sin(2\alpha) &=& 2 \sin \alpha \cos \beta \\ \cos(2\alpha) &=& \cos^2 \alpha - \sin^2 \alpha \\ \end{eqnarray*} $

$ \begin{eqnarray*} \sin(\alpha + \beta) + \sin(\alpha - \beta) &=& 2 \sin \alpha \cos \beta \\ \sin(\alpha + \beta) - \sin(\alpha - \beta) &=& 2 \sin \beta \cos \alpha \\ \cos(\alpha + \beta) + \cos(\alpha - \beta) &=& 2 \cos \alpha \cos \beta \\ \cos(\alpha - \beta) - \cos(\alpha + \beta) &=& 2 \sin \beta \sin \alpha \\ \end{eqnarray*} $