Answers For Algorithms
Uploaded by
Mark DjentAnswers For Algorithms
Uploaded by
Mark DjentTheory of Computer Science
group classes
Algorithms
Alina Momot
2020/21
Task 1
Give a flowchart and pseudocode for an algorithm which finds the indices of the largest and the
smallest elements in the given array int a[n] of size n>=2.
Task 1
Give a flowchart and pseudocode for an algorithm which finds the indices of the largest and the
smallest elements in the given array int a[n] of size n>=2.
void f(){
int i = 1, min_i = 0, max_i = 0;
while (i < N){
if (tab[i] > tab[max_i])
max_i = i;
else
if (tab[i] < tab[min_i])
min_i = i;
i++;
}
cout << “index of min is” << min_i;
cout << “index of max is” << max_i;
}
What is the efficiency of the algorithm?
Let’s analyze the time (computational) efficiency of the algorithm.
The dominant operation is comparison of array elements
1. The algorithm without else
𝑻(𝑵) = 𝑶(𝑵)
𝑻𝒐𝒑𝒕 (𝑵) = 𝟐 ∗ (𝑵 − 𝟏)
𝑻𝒑𝒆𝒔 (𝑵) = 𝟐 ∗ (𝑵 − 𝟏)
𝑻𝒂𝒗𝒆 (𝑵) = 𝟐 ∗ (𝑵 − 𝟏)
2. The algorithm with else
𝑻(𝑵) = 𝑶(𝑵)
𝑻𝒐𝒑𝒕 (𝑵) = 𝑵 − 𝟏 //increasing sequence (each next is greater than previous one)
𝑻𝒑𝒆𝒔 (𝑵) = 𝟐 ∗ (𝑵 − 𝟏) // the first one is the greatest
𝑻𝒂𝒗𝒆 (𝑵) = 𝟐 ∗ (𝑵 − 𝟏) − 𝒍𝒏 𝑵 + 𝑪
Task 2
Write a function for searching the first position of the pattern in the text.
We assume that the following has been declared: char text [n]; char pattern [m];
Example:
text = B A B D E F A B C D n = 10
pattern = ABC m=3 result = 6
text = B A B D E F A B C D n = 10
pattern = ABC m=3 result = 6
int n = …; int m = …;
char text [n] = …; char pattern [m] = …;
int f ( ){
int i =0;
int j =0;
do{
if (text[i] = = pattern[j])
{ i++; j++; }
else
{ i = i – j + 1; j = 0; }
}
while((i < n)&& (j < m))
if (j == m)
return i – j;
else
return -1;
}
Task 3
Write a function that counts (returns) the number of rows in the given array int A [m, n]
consistent with the pattern given in array int B [n].
Example:
A B
11 23 21 6 3 32 4 65 1 12
8 7 0 21 4
32 4 65 1 12
5 13 4 12 1 result = 2
32 4 65 1 12
int n = …;
int m = …;
int A[m, n] = …;
int B[n] = …;
int f ( ){
int counter = 0, i = 0, j = 0;
for (i = 0; i < m; i++){
for (j = 0; j < n; j++)
if (A[i ,j] != B[j])
break;
if (j == n)
counter++;
}
return counter;
}
Task 4
Give an algorithm for calculating the factorial of a non-negative integer n (a recursive and non-
recursive version).
a non-recursive and recursive version
int fac ( int n ){ int fac ( int n ){
int f = 1; if ( n <= 1)
return 1;
for (int i = n; i > 0; i--) else
f *= i; return n * fac(n-1);
}
return f;
}