<aside>
Topic 01: Algorithms: Efficiency, Analysis, and Order.
Deadline: Oct. 16, 2024.
Team members:
</aside>
- Use Binary Search, Recursive (Algorithm 2.1) to search for the integer 15 in the following list(array) $S$ of integers. Show the actions step by step. $S=[3, 5, 8, 10, 13, 16, 18, 20]$.
Solution: (紙本)
-
Implement Binary Search on your computer. (recursive and iterative)
Solution:
-
Show that $W_B(n) = \lfloor \log n\rfloor + 1$. Prove it by induction on $n$.
Solution:(紙本)
- Let $p=1$ and $n= 2^m$. Assume that $x$ is any of $S[0],\cdots, S[n-1]$ with probability $\dfrac 1 n$.
Find the average-case time complexity of Binary Search $A_B(n)$.
Solution:(紙本)
- Show that $\lg(n!)= \theta(n\lg n)$.
Solution:(紙本)
- Consider a list of functions:
$n\ln(n), (\lg n)^2, 5n^2+7n, n^{5/ 2}, (\lg n)^{\lg n}, 10^n+n^{20}, n!, 2^{n!}, 4^n$, $n^n, n^n+\ln(n), 5^{\lg n}, \lg(n!), (\lg n)!, \sqrt{n}, e^n, 8n+12$
Order them to $g_1, g_2, \cdots, g_{17}$ s.t. $g_i=O(g_{i+1})$ and use $g_i<<g_{i+1}$ if $g_i=o(g_{i+1})$.
Please show all your work for full credit.
Solution:(紙本)