ROUGH DRAFT authorea.com/5039
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • Algo HW #1

    Problem 1

    1. \(f(n)=\sqrt{2^{7n}}, g(n)=lg(7^{2n})\)

      \(f(n)=2^{7n/2}, g(n)=2nlg(7)\)

      \(f(n)=lg(2^{7n/2}), g(n)=lg(2nlg(7))\)

      \(f(n)=lg(2^{7n/2}), g(n)=lg(2nlg(7))\)

      \(f(n)=7n/2, g(n)=lg(2n) + lg(lg(7))\)

      \(f(n)=7n/2, g(n)=lg(2n)\)

      \(f=\Omega(g)\)

    2. \(f(n)=2^{nln(n)}, g(n)=n!\)

      \(f(n)=ln(2^{nln(n)}), g(n) = ln(n!)\)

      \(f(n)=nln(n), g(n) = nlg(n)\) (via previously proved identity)

      \(f=\theta(g)\)

    3. \(f(n)=lg(lg^*n), g(n)=lg^*(lgn)\)

      \(f=O(g)\)

    4. \(f(n)=\frac{lgn^2}{n},g(n)=lg^*n\)

      \(f=O(g)\) via limits. f approaches 0.

    5. \(f(n)=2^n, g(n)=n^{lgn}\)

      \(f(n)=n, g(n)=(lgn)^2\)

      \(f=\Omega(g)\)

    6. \(f(n)=2^{\sqrt{lgn}}, g(n)=n(lgn)^3\)

      \(f(n)=(lgn)^{1/2} , g(n)=lg(n)+lg((lg(n))^3)\)

      \(f=O(g)\)

    7. \(f(n)=e^{cos(n)}, g(n)=lgn\)

      \(f(n)=cos(n), g(n) = ln(lg(n))\)

      \(f= O(g)\)

    8. \(f(n)=lgn^2,g(n)=(lgn)^2\)

      \(f(n)=2lg(n), g(n)=(lgn)^2\)

      \(f=O(g)\)

    9. \(f(n)=\sqrt{4n^2-12n+9}, g(n)=n^(\frac{3}{2})\)

      \(f(n)=2n, g(n)=n^(\frac{3}{2})\)

      \(f(n) = O(g)\)

    10. \(f(n)=\sum_{k=1}^{n} k, g(n)=(n+2)^2\)

      \(f(n) = \frac{k(k+1)}{2}\) via summation formula \(g(n)=(n+2)^2\)

      \(f=\theta(g)\)

    Problem 2

    • Line 1: 1 - Constant

    • Line 2: 1 (bitshifting)

    • Line 3: 1

    • Line 4: \(n^2\) (modular arithmetic)

    • Line 5: \(m\) (loop)

    • Line 6: \(n^3\) (finding GCD)

    • Line 8:lg(N)

    • Line 9: \(n^3\) (exponential modular arithmetic)

    • Line 10: \(m\) (loop)

    • Line 11: \(n^3\) (exponential modular arithmetic)

    • Line 12: \(n^2\) (modular arithmetic)

    • Line 13: \(n^3\) (primality test)

    Total:

    \([(2n^3+n^2)m + n^3 + log(N) + n^3]m + n^2\)

    \(m^2(n^3)\)

    Problem 3

    • The lower bound for the height of the tree is 0, because the tree can consist of only the root node.

    • The asymptopic behavior of \(h_{m}\) relative to \(h_{m'}\) depends on the relationship between m and m’ (whether one is larger than the other, or is equal).

      \(N = \frac{1-m^{h+1}}{1-m}\) via geometric sum

      \(N(1-m) = 1-m^{h+1}\)

      \(1 - N{1-m} = m^{h+1}\)

      \(lg_{m}(Nm - N + 1) -1 = h\)

      So looking at large values of N and M, this formula is basically

      \(lg_{m}(Nm) = h\) because \(Nm\) is the dominating term. So if \(n=m^2\), then the height of \(n\) is double \(M\).

      \(lg(Nm) = h\)

      Now if use \(n\),

      \(lg(Nn) = h\)

      \(lg(N(m^2)) = h\)

      \(lg(Nm) = \frac{h}{2}\)

      So this shows, if you square m, it divides the height by 2.

    • Using Master Thoerem, we will be able to write the recursive cost of this function as:

      \[T(n) = aT(\frac{n}{b}) + O(n^d)\]

      The branching factor \(a\) is 1 because we are only left with one subproblem at each iteration. Also doing \(\frac{y}{2}\) takes constant time because \(y\) is in the order of \(2^n\), so dividing by 2 is just a simple bitshift. The subproblem is \(n/2\) because you only have to deal with a number with half the bitsize. THe cost of combining the subproblems back to the larger problem is the cost of squaring a number and then take mod on a number order \(2^0\).

      Squaring a number is like multiplying two \(n\) bit numbers and using Gauss’ observation, it takes \(O(n^{1.59})\) time. Taking mod on the order of \(2^o\) is simple because you do a shift that takes constant time and the answer is the bits you were shifting. So the cost of recombining is \(O(n^{1.59})\). So using Master Theorem:

      \[T(n) = 1*T(\frac{n}{2}) + O(n^{1.59})\]

      Using the theorem, lg(1) < 1.59 so cost of recursion is \(n^{1.59}\), and we need to do recursion \(n\) times. Since \(y=2^n\), we need y = 1 until we can stop. So total time is:

      \[O(n^{2.59})\]

    Problem 4

    • Compute \(2^{902} mod 7\)

      The stategy here is to look for a pattern for mod 7.

      \(2^0 = 1 mod 7\)

      \(2^1 = 2 mod 7\)

      \(2^2 = 4 mod 7\)

      \(2^3 = 1 mod 7\)

      \(2^4 = 2 mod 7\)

      \(2^5 = 4 mod 7\)

      \(2^6 = 1 mod 7\)

      \(2^7 = 2 mod 7\)

      \(2^8 = 4 mod 7\)

      We notice the pattern that every third power of 2 is congruet to \(1mod7\), so we continued the pattern from \(2^{900}\).

      \(2^{900} = 1 mod 7\)

      \(2^{901} = 2 mod 7\)

      \(2^{902} = 4 mod 7\)

      Now we know that \(2^{902} mod 7 = 4\)

    • Multiplicative Inverse of:

      \(11 mod 120: 11\)

      \(13 mod 45: 7\)

      \(35 mod 77: None\)

      \(9 mod 11: 5\)

      \(11 mod 1111: None\)

    • The running time of an efficient algorithm for finding the inverses modulo \(x^m\) is \(n^3\) via the Extended Euclidean Algorithm.