Table of Contents
Pseudocode
Simplified tradeoff between natural and programming language. Pseudocode is not unique. That is to say that it does not have rigid rules. Different people may have different pseudocode syntax.
Design
- Step 1: Do something
- Step 2: Do something
- Step 3: Do something
- … : …
Sequential steps
A sequential step is a single task; for example a 1 to x
.
Conditional steps
Ask a question that is answered with a logic answer. The answer can be true
/false
.
For example:
if (x > 0) add 1 to x else substract 1 from x
Loops
Iterative steps.
add 1/2 cup to mixture while mixture is dry
Recursion
(This will be filled at a later point.)
Case study: addition
Example:
472 +593
Conceptualise:
Let m => 1 be number of digits a<sub>m-1</sub> a<sub>3</sub> a<sub>2</sub> a<sub>1</sub> === Algorithm === <code> Step 1: get m (user provides m) Step 2: get a<sub>m-1</sub>・・・a<sub>1</sub> a<sub>0</sub>, b<sub>m-1</sub>・・・b<sub>1</sub>b<sub>0</sub> Step 3: set i=0, set carry=0 Step 4: while(i ≤ m-1) do Step 5 to 7 Step 5: set c<sub>i</sub> = a<sub>i</sub> + b<sub>i</sub> + carry Step 6: if(c<sub>i</sub> ≥ 10) then set c<sub>i</sub> = c<sub>i</sub> - 10 set carry = 1 else set carry = 0 Step 7: set i = i + 1 Step 8: set c<sub>m</sub> = carry step 9: print c<sub>m</sub> c<sub>m-1</sub> ... c<sub>2</sub> c<sub>1</sub> c<sub>1</sub> step 10: stop
Squential statements
- Inputs: Get “variable”
- Ex: get m, get radius
- Computation: set “variable” = expression
- Ex: set area = π*radius2
- Output: print “variable”
- Ex: print area
Conditional statements
Loop
do op1 op2 op3 while(condition)
* Do while
loops will execute at least once, online while
loops
Sequential Search
Data set of N elements: 13
4
-20
45
112
・・・ N=10¹³ / 38944
Therefore the list will be L1, L2, L3… LN
Target: 45 〇 130 ×
This is easy for the brain because the brain is made pattern matching.
Step 1 get L1, L2, LN, N, Target Step 2 Set Found = No Step 3 Set i = 1 Step 4 while (Foundo = No AND i ≤ N) do Step 5 to Step 6 Step 5 if (Li = Target) then set Found = Yes Step 6 else set i = i + 1 Step 7 if (Found = Yes) then print "Target found" Step 8 else print "Target not found" Step 9 stop
The Swap
x y 5 3 Swap the content of both variable so that X=3 and Y=5
Step 1 get x, y Step 2 set temp = x Step 3 x = y Step 4 y = temp Stop 5 Stop
* For swapping in other algorithm swap(x,y)
can be used instead.
Gauss Sum
n ≥ 1 1+2+3+4+…+n
Formula: $\frac{(n+1)*n}{2}$ $\Theta$
(double check this information)
When talking about efficiency we say that the efficiency of n is $\Theta(n^2)$