date: 2024-03-04
title: DAA-Assignment-0
author:
  - AllenYGY
status: DONE
tags:
  - DAA
  - Assignment
created: 2024-03-09
updated: 2024-05-31T00:44
publish: True

DAA-Assignment-0

Question-1

For Euclidean Algorithm to find GCD

Define the problem solved by the algorithm (6pt)
- Input: 2 positive integer A,B
- Output: A positive integer that is Greatest Common Divisor of A and B
Give a high-level presentation of the algorithm (6pt)
- Divide the larger number by the smaller number, then remove the divisor by the remainder that occurs (the first remainder), then remove the first remainder by the remainder that occurs (the second remainder), and so on until the final remainder is zero. If you are finding the greatest common divisor of two numbers, then the final divisor is the greatest common divisor of those two numbers.
Write the pseudo code (8pt)

Algorithm Euclidean Algorithm

while $B \neq 0$ do

$temp \gets B$

$B \gets a \bmod b$

$A \gets temp$

end while

return $A$

Question-2

Input: A task t
Output: "Yes" or "No"

Algorithm Task Work Procedure

if atomic( $t$ ) then

return accomplishable( $t$ )

end if

$subtasks \gets$ destruct( $t$ )

for each $subtask$ in $subtasks$ do

if work( $subtask$ ) == ‘‘No'' then

return ‘‘No''

end if

end for

return ‘‘Yes''

Question-3

Verification:
The array A is known to be in ascending order and the length of the array is n. When we search for the target number x, we compare it with the middle element of the array.
- If , the target number is found;
- if , the search needs to be narrowed down, the search needs to be done in the array containing elements from to ;
- if , the search needs to be done in the array containing elements from to .

Question-4

...

Question-5

The main goal of algorithm analysis is to understand the rate at which an algorithm's running time or space requirement grows with input size. Although multiplication has a slower running time than addition, it does not affect the overall time complexity in general.