###### tags: `learning` `algorithm` `neopolitan`
# 演算法作業02
## ch 2 - 1 Recursive Binary Search
用遞迴的二元搜尋法找出120
```python=
def RecursiveBinarySearch(S, target):
def location(low, high): # python style indexing
if low > high:
return None # target is not in S
else:
mid = math.floor((low + high) / 2)
# ceiling works as well
if S[mid] == target:
return mid
else:
if S[mid] > target: # go to small side
return location(0, mid - 1)
else: # go to large side
return location(mid + 1, high)
# Python uses 0 ~ (n-1) for 1-st ~ n-th
return location(0, len(S) - 1)
```
```python
S = [12, 34, 45, 57, 82, 99, 120, 134]
print(RecursiveBinarySearch(S, 120))
```
## ch 2 - 7 D&C Find The Max
Use the divide-and-conquer approach to write an algorithm that finds the largest item in a list of n items. Analyze your algorithm, and show the results in order notation.
### Ans:
```python=
def mymax(S):
# Conquer the trivial case
if len(S) == 1:
return S[0]
# Divide the combinational case
else:
SS = []
for i in range(len(S) // 2): # === floor(len(S)/2)
# Pick up the winners
if S[2 * i] > S[2 * i + 1]:
SS.append(S[2 * i])
else:
SS.append(S[2 * i + 1])
# Let the lone remainder join the winners
if len(S) % 2:
SS.append(S[-1])
return mymax(SS)
```
Test the answer.
```python=
check_sum = 0
for _ in range(100):
S_len = random.randint(0, 100)
S = [random.randint(0, 10000) for _ in range(S_len)]
if mymax(S) != max(S):
check_sum += 1
print("Fail!")
print(check_sum)
```
Beware of a stack overflow.
```
RecursionError: maximum recursion depth exceeded in comparison
```
## ch 2 - 8 Mergesort / merge sort
Use Mergesort (Algorithms 2.2 and 2.4) to sort the following list. Show the
actions step by step.
> 123, 34, 189, 56, 150, 12, 9, 240
### Ans:
We will use the style of Algorithm 2.4, which saves the extra usage of memory.
**Beware of the pass-by-reference nature of Python.**
**We shall use `U = S[:]` instead of `U = S`.**
```python=
def merge2(low, mid, high):
i = low # for the left/small
j = mid + 1 # for the right/large
k = low # the index for U[]
U = S[:] # the temp list to hold the merged result
# Beware of the pass-by-reference nature of Python
while i <= mid and j <= high:
if S[i] < S[j]:
U[k] = S[i]
i += 1
else:
U[k] = S[j]
j += 1
k += 1
# If one of the U[] or K[] is used up, we don't compare anymore.
# Merge the residual to the sorted part directly
if i > mid: # the left part is used up
U[k:high+1] = S[j:high+1] # Connect the right part onto the tail of U[]
else: # the right part is used up
U[k:high+1] = S[i:mid+1] # Connect the left part onto the tail of U[]
S[low:high+1] = U[low:high+1] # overwirte the yet-merged S[] with the merged U[]
```
```python=
def mergesort2(low, high):
if high > low:
mid = (low + high) // 2 # ===floor( (low + high) // 2 )
mergesort2(low, mid)
mergesort2(mid + 1, high)
merge2(low, mid, high)
```
```python
global S
S = [123, 34, 189, 56, 150, 12, 9, 240]
mergesort2(0,len(S)-1)
```
### step-by-step analysis
Please read https://hackmd.io/s/HJilnclFE
## ch 2 - 19 Quicksort
```cpp=
#include <iostream>
void partition(int S[], int low, int high, int pivotpoint)
{
int i, j, pivotitem, temp;
j = low;
pivotitem = S[low];
for (i = low + 1; i <= high; i++)
{
if (S[i] < pivotitem)
{
j++;
temp = S[i]; S[i] = S[j]; S[j] = temp;
}
}
pivotpoint = j;
temp = S[low]; S[low] = S[pivotpoint]; S[pivotpoint] = temp;
}
void quicksort(int S[], int low, int high)
{
int pivotpoint = low;
if (high > low)
{
partition(S, low, high, pivotpoint);
quicksort(S, low, pivotpoint - 1);
quicksort(S, pivotpoint + 1, high);
}
}
int main()
{
int S[] = {123, 34, 189, 56, 150, 12, 9, 240};
int size = sizeof(S) / sizeof(S[0]);
printf("\nThe size is %d\n\n", size);
int i; for (i = 0; i < size; i++)
printf("%d, ",S[i]);
printf("\n\n");
quicksort(S, 0, size-1);
for (i = 0; i < size; i++)
printf("%d, ",S[i]);
printf("\n");
}
```
## ch 2 - 45
```python=
import random
# Generate a list
S = []
for i in range(4, 100): # set the size of input as N
S.append(random.random())
# Sum the sublists of length-3
S3 = []
initial_index_list = []
for i in range(0,len(S) - 2):
S3.append(S[i] + S[i + 1] + S[i + 2]) # adding for 2N times (for two add symbols)
initial_index_list.append(i)
# find my max
def mymax(S3, index_list): # being called lg(N) times
print(index_list)
if len(index_list) > 1: ## judging for 1 time in each call
new_index_list = []
for i in range(0, len(index_list) - 1, 2):
print(i)
if S3[index_list[i]] > S3[index_list[i+1]]: ## judging for len/2 times in each call
new_index_list.append(index_list[i])
else:
new_index_list.append(index_list[i + 1]) ## judging for 1 time in each call
# collect the unpaired
if len(index_list) % 2:
new_index_list.append(index_list[-1])
return mymax(S3, new_index_list)
else:
return S3[index_list[0]]
# compare with Python's max
print(mymax(S3, initial_index_list) - max(S3))
```
### time complexity
\begin{aligned}
&f(N) = 2N+\lg N (1+\frac{\bf{len}}{2}+1)\\
&\lg N \; \frac{\bf{len}}{2} = 1.5 N
\end{aligned}
So the time complexity fumction is in $\Theta(N)$.
## Appendix B - 8
```python=
def t(n):
if n == 1:
return 1
else:
return t(n-1) + 2 * n - 1
for i in range(1, 11):
print(t(i))
```
The result is `
1,
4,
9,
16,
25,
36,
49,
64,
81,
100`.
Guess the solution is $t(n)=n^2$.
### Induction
* Check $n=1$
Valid.
* Assume valid when $n=k$
$t(k)=k^2$
* Try for the case of $n=k+1$
That is, we want to prove $t(k+1)=(k+1)^2$ from the definition $t(k+1)=t(k)+2k+1$ and the assumption $t(k)=k^2$.
$t(k+1)=k^2+2k+1$
Valid.
Based on Mathematical Induction, we have $t(n)=n^2$ for $n\geq 1$.
## Appendix B - 12
### (a)
\begin{aligned}
&r^2 - 4r + 3 =0 \\
&r=1, 3 \\
&t_n = c_1 + c_2 3^n \\
&t_n = -0.5 + 0.5 \times 3^n
\end{aligned}
### (b)
\begin{aligned}
&(r-1)^4 (r-2) =0 \\
&t_n = c_1 2^n + c_2 1^n + c_3 n 1^n + c_4 n^2 1^n + c_5 n^3 1^n\\
&t_n = 12\times 2^n - 12 - \frac{49}{6}n - \frac{5}{2} n^2 -\frac{1}{3}n^3
\end{aligned}
### \(c\)
\begin{aligned}
&(r-2) (r-3)(r-4) =0 \\
&t_n = c_1 2^n + c_2 3^n + c_3 4^n\\
&t_n = \frac{22}{3}\times 2^n - \frac{23}{2}\times 3^n + \frac{25}{6} 5^n
\end{aligned}
### (d)
\begin{aligned}
t_n = c_1 2^n + c_2 3^n + c_3 7^n + c_4 + c_5 n + c_6 n^2
\end{aligned}
We will use `numpy.linalg.solve(a,b)` to solve the above system of linear equations.
```python=
import numpy as np
# the recursion relationship
def t(n):
if n == 1: return 1
elif n == 0: return 0
else: return (
5*t(n-1) - 6*t(n-2) + n**2-5*n+7**n )
# the function to generate const
def coeff_list(n):
return [2**n,3**n,7**n,1,n,n**2] # return a list
# the coeff to solve C1~C6
coeff_list_list = []
for i in range(0, 6):
print(t(i))
coeff_list_list.append(t(i))
# the const of the six equation
const_list = []
for i in range(0, 6):
print(t(i))
const.append(t(i))
# matrix of coeff
a = np.array(
[ coeff(0),
coeff(1),
coeff(2),
coeff(3),
coeff(4),
coeff(5) ])
# column vector of const
b = np.array(const)
# solve the system of linear equations
c_n = np.linalg.solve(a,b)
print(c_n)
```
The fisrt 6 terms are:
```python
t(0) = 0
t(1) = 1
t(2) = 48
t(3) = 571
t(4) = 4964
t(5) = 38201
```
The coefficients are:
```python
c_1 c_2 c_3 c_4 c_5 c_6
[ 12.8 -14. 2.45 -1.25 1. 0.5 ]
```
Sign in with Wallet
Connect another wallet