Class Code: AMC621 Instructor: Huilan Chang

◼️ Algorithm

Goal: learn techniques for solving problems using a computer.

• Techniques:
  • not programming style or programming language (e.g. C, Java, Python...)
  • but the approach or methodology
• Example: Find "prompt" in a dictionary (in lexicographical order).
  • Sequential search 循序搜尋法: starting with the first letter, until “prompt” is located.
    • computational complexity: $O(n)$ if $n$ is the number of pages.
  • Modified binary search 二元搜尋法: Open the dictionary to where the p's could be located. It go too far, thumb back a little. Continue thumbing back or forth until we locate the page containing the word.
    • computational complexity: $O(\lg n)$. 注意: $\lg=\log_2$
• An algorithm is a step-by-step procedure for solving a problem.
• Goal:
  • Learn various problem-solving techniques: Divide-and-conquer 分而治之法, Dynamic programming 動態規劃, Greedy approaches 貪婪演算法, ...
  • Analyze algorithm in terms of time and storage.
• Terminologies:

  • problem: (Determine whether the number $x$ is in the list $S$ of $n$ numbers.)

  • parameters: variables. ($S$, $n$ and $x$)

  • instance實例: each specific assignment of values to the parameters. ($S=[10, 7, 11, 5, 13, 8]$, $n=6$ and $x=5$)

  • solution: the answer to the question asked by the problem in that instance. (yes)

  • algorithm: sequential search

  • pseudocode: informal high-level description of the operating principle of an algorithm.

    <aside> 💡

    To present algorithms clearly so they can be readily understood and analyzed.

    </aside>

🔹 ****Search problem

<aside>

Problem: Is the key $x$ in the array $S$ of $n$ keys?

Inputs (parameters): array of keys $S$ indexed from 0 to $n-1$, and a key $x$.

Output: a location of $x$ in $S$ (-1 if $x$ is not in $S$).

</aside>

<aside>

Pseudocode for sequential search

Search (list $S$, key $x$)

$l=0$;

while ( $l≤n-1$ and $S[l]≠x$)

$l++$;

if ($l\geq n$)

$l=-1$;

return $l$

</aside>

<aside>

Programming (Python) Sequential search:

https://colab.research.google.com/drive/1h8773WRFhHTSIxCotcn5co-MhKigFymg?usp=sharing

</aside>

Note. In Pseudocode, we can write “exchange $x$ and $y$” rather than “temp$=x$; $x=y$; $y=$ temp”.

▪️Search problem on sorted array

<aside>

Problem: Is the key $x$ in the sorted arrays of $n$ keys Inputs (parameters): sorted array $S[0 .. n-1]$ and a key $x$. Outputs: a location of $x$ in $S$ ( "not found" if $x$ is not in $S$)

</aside>

<aside>

Algorithm: Binary Search

Example.

</aside>

▪️Two versions of pseudocode for binary search (兩種寫法):

<aside>

Iterative version (迭代版) https://colab.research.google.com/drive/1G7J_C0H91HhjXIKne5wwtLzp7U1joI2E?usp=sharing

BinarySearch($S[0 .. n-1]$, value)

1

2

3

4

5

7

8

9

10

11

</aside>

<aside>

Recursive version (遞迴版）https://colab.research.google.com/drive/1bYQEshfeKq1qpoFLX-7viv0CEx9uLWN-?usp=sharing //initial low=$0$, high=$n-1$

BinarySearch($S$, value, low, high)

1

2

3

4

5

6

7

8

9

</aside>

🔹 ****Compute Fibonacci sequence

Fibonacci sequence $\{f_n\}_{n\geq 0}=\{0, 1, 1, 2, 3, 5, 8, 13, \cdots\}$

$f_0=0$, $f_1=1$, and $f_n=f_{n-1}+f_{n-2}$ for $n\geq 2$.

▪️Problem: Compute the $n$th term of the Fibonacci sequence 以下提供兩個不同的演算法，分別是recursive 和iterative:

▪️Analysis:

<aside>

</aside>

<aside>

</aside>

▪️Conclusion: Algorithm 1 computes more than $2^{n/2}$ terms to obtain $f_n$. Not efficient! Algorithm 2 computes $n+1$ terms ($f_0, \cdots, f_n$ ) to obtain $f_n$.

| --- | --- | --- | --- | --- |

These execution times are based on the simplifying assumption that one term can be computed in $10^{-9}$ second.

• 1 ns = $10^{-9}$ second. † 1 μs = $10^{-6}$ second.

◼️ Efficiency and Analysis