Unit 1 Algorithms: Efficiency, Analysis, and Order

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.

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

🔹 ****Search problem

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$).

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$

Programming (Python) Sequential search: https://colab.research.google.com/drive/1h8773WRFhHTSIxCotcn5co-MhKigFymg?usp=sharing

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

▪️Search problem on sorted array

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$)

Algorithm: Binary Search Example. $n=8$, $x=5$, $S=[1,3,4,6,7,9,11,13]$. Initially low $=0$, high $=7$. The possible positions of $x$: low .. highstepmidcomparisonpossible positions of $x$initial$0..7$1$\lfloor\frac{0+7}{2}\rfloor=3$$S[3]=6>x$$0..2$ (high $=$ mid$-1$)2$\lfloor\frac{0+2}{2}\rfloor=1$$S[1]=3<x$$2..2$ (low $=$ mid$+1$)3$\lfloor\frac{2+2}{2}\rfloor=2$$S[2]=4<x$$3..2$ (low $=$ mid$+1$)4low $=3>$ high $=2$return “not found”

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

Iterative version (迭代版) https://colab.research.google.com/drive/1G7J_C0H91HhjXIKne5wwtLzp7U1joI2E?usp=sharing BinarySearch($S[0 .. n-1]$, value)

low = 0 high = n-1 while (low <= high) mid = ⌊(low + high)/2⌋ if (S[mid] > value) high = mid - 1 else if (S[mid] < value) low = mid + 1 else return mid return "not found"