Tutorial-1

Question1

Given the problem: “For the given positive integer, justify if it is a prime.”

1. Formally define the problem

2. Give some instances and corresponding outputs

3. Construct an algorithm and describe it with/without using pseudo code

• Input: a positive integer n
• Output: Yes, if n is a prime; No, Otherwise

begin
	for a =2 to |n^0.5| do
		\if {$n%a=0} then
			return No
		end if
	end for
	return Yes
end

Algorithm 2 Quicksort

1:procedure Quicksort($A, p, r$)

2:if $p < r$ then

3:$q =$ Partition($A, p, r$)

4:Quicksort($A, p, q - 1$)

5:Quicksort($A, q + 1, r$)

6:end if

7:end procedure

8:procedure Partition($A, p, r$)

9:$x = A[r]$

10:$i = p - 1$

11:for $j = p$ to $r - 1$ do

12:if $A[j] < x$ then

13:$i = i + 1$

14:exchange $A[i]$ with $A[j]$

15:end if

16:exchange $A[i]$ with $A[r]$

17:end for

18:end procedure