CIDA Lab @ UoS

Introduction to Algorithm Assignment 1

   

  • Submission Guideline: Upload your homework file (hw1_[your student id].doc or hw1_[your student id].hwp) to online Uclass classroom. You are allowed to write down your answers either in Korean or English at your convenience.
  • Deadline: 23:59 PM, Tuesday, October 15, 2024

       

Please feel free to leave your questions about homework problems in the online Ed Discussion platform.

   

  1. For each function $f(n)$ and time $t$ in the following table, determine the largest size n of a problem that can be solved in time $t$, assuming that the algorithm to solve the problem takes $f(n)$ microseconds.
  1 second 1 minute 1 hour 1 day 1 month 1 year 1 century
$lgn$ $2^{10^6}$ $2^{6 \times 10^{7}}$ $2^{3.6 \times 10^{9}}$ $2^{8.64 \times 10^{10}}$ $2^{2.59 \times 10^{12}}$ $2^{3.15 \times 10^{13}}$ $2^{3.15 \times 10^{15}}$
$\sqrt{n}$              
$n$              
$nlgn$              
$n^2$              
$n^3$              
$2^n$              
$n!$              

   

  1. Give asymptotic upper and lower bounds for $T(n)$ in each of the following recurrences. Assume that $T(n)$ is constant for $n \le 2$. Make your bounds as tight as possible, and justify your answers.

a. $T(n)=2T(n/2)+n^4$.

b. $T(n)=T(7n/10)+n$.

c. $T(n)=16T(n/4)+n^2$.

d. $T(n)=7T(n/3)+n^2$.

e. $T(n)=7T(n/2)+n^2$.

f. $T(n)=2T(n/4)+\sqrt{n}$.

g. $T(n)=T(n-2)+n^2$.

   

  1. Indicate, for each pair of expressions $(A,B)$ in the table below, whether $A$ is $O$, $o$, $\Omega$, $\omega$, or $\Theta$ of $B$. Assume that $k \le 1$, $\epsilon > 0$, and $c > 1$ are constants. Your answer should be in the form of the table with “yes” or “no” written in each box.
$A$ $B$ $O$ $o$ $\Omega$ $\omega$ $\Theta$
$\lg^kn$ $n^\epsilon$ yes yes no no no
$n^k$ $c^n$          
$\sqrt{n}$ $n^{\sin n}$          
$2^n$ $2^{n/2}$          
$n^{\lg c}$ $c^{\lg n}$          
$\lg(n!)$ $\lg(n^n)$          

   

  1. When RANDOMIZED-QUICKSORT runs, how many calls are made to the random-number generator RANDOM in the worst case? How about in the best case? Give your answer in terms of $\Theta$-notation.

   

  1. Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n)=2T(n-1)+1$. Use the substitution method to verify your answer.

   

  1. Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$? What about a fraction $1/2^n$?

   

  1. Suppose that the splits at every level of quicksort are in the proportion $1-\alpha$ to $\alpha$, where $0 < \alpha \le 1/2$ is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately $-\lg n / \lg \alpha$ and the maximum depth is approximately $-\lg n/\lg(1-\alpha)$. (Don’t worry about integer round-off.)

   

  1. Use Strassen’s algorithm to compute the matrix product

$\begin{pmatrix} 1 & 3 \\ 7 & 5 \end{pmatrix}\begin{pmatrix} 6 & 8 \\ 4 & 2 \end{pmatrix}$.

Show your work.

   

  1. Let $A[1..n]$ be an array of $n$ distinct numbers. If $i < j$ and $A[i] > A[j]$, then the pair $(i, j)$ is called an inversion of $A$.

a. List the five inversions of the array $\left \langle 2, 3, 8, 6, 1 \right \rangle$.

b. What array with elements from the set $\{1,2,\cdots,n\}$ has the most inversions? How many does it have?

c. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

d. Give an algorithm that determines the number of inversions in any permutation on $n$ elements in $\Theta(n \lg n)$ worst-case time. (Hint: Modify merge sort.)

def count_inversion_sub(arr, l, r):
    """
    Args:
      arr: The array to count the number of inversions.
      l: The left index of the array.
      r: The right index of the array.

    Returns:
      cnt: The number of inversions in the array.
    """
    
    # Implement the function here!!
    #
    #

    return cnt

def count_inversion(arr):
    return count_inversion_sub(arr, 0, len(arr) - 1)

   

  1. Answer the following questions and write the python programs to justify your answers.

a. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is $n$. Show how to sort the array in $O(n)$ time. (Hint: Use a counting sort.)

def n_digit_number_sort(arr):
    """
    Args:
      arr: The list of integers where the total number of digits over all the integers in the array is n.

    Returns:
      arr: The sorted array.
    """
    
    # Implement the function here!!
    #
    #

    return arr

b. You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is $n$. Show how to sort the strings in $O(n)$ time. (Note that the desired order here is the standard alphabetical order; for example, $a < ab < b$.)

def counting_sort_string(arr):
    """
    Args:
      arr: The list of strings where the total number of characters over all the strings is n.

    Returns:
      arr: The sorted array in the standard alphabetical order.
    """
    
    # Implement the function here!!
    #
    #

    return arr
Search