Choose the best answer , Answer the following questions

Computer Science : Algorithmic Strategies

Evaluation

Part – I

Choose the best answer: (1 Marks)

1 .The word comes from the name of a Persian mathematician Abu Ja’far Mohammed ibn-i Musa al Khowarizmi is called?

(A) Flowchart

(B) Flow

(C) Algorithm

(D) Syntax

2. From the following sorting algorithms which algorithm needs the minimum number of swaps?

(A) Bubble sort

(B) Quick sort

(C) Merge sort

(D) Selection sort

3. Two main measures for the efficiency of an algorithm are

(A) Processor and memory

(B) Complexity and capacity

(C) Time and space

(D) Data and space

4. The complexity of linear search algorithm is

(A) O(n)

(B) O(log n)

(C) O(n2)

(D) O(n log n)

5. From the following sorting algorithms which has the lowest worst case complexity?

(A) Bubble sort

(B) Quick sort

(C) Merge sort

(D) Selection sort

6. Which of the following is not a stable sorting algorithm?

(A) Insertion sort

(B) Selection sort

(C) Bubble sort

(D) Merge sort

7. Time complexity of bubble sort in best case is

(A) θ (n)

(B) θ (nlogn)

(C) θ (n2)

(D) θ (n(logn) 2)

8. The Θ notation in asymptotic evaluation represents

(A) Base case

(B) Average case

(C) Worst case

(D) NULL case

9. If a problem can be broken into subproblems which are reused several times, the problem possesses which property?

(A) Overlapping subproblems

(B) Optimal substructure

(C) Memoization

(D) Greedy

10. In dynamic programming, the technique of storing the previously calculated values is called ?

(A) Saving value property

(B) Storing value property

(C) Memoization

(D) Mapping

**Part – II**

**Answer the following questions (2 Marks)**

**1. What is an Algorithm?**

**Ans.** An algorithm is a finite set of instructions to accomplish a
particular task. It is a step-by-step procedure for solving a given problem.

**2. Define Pseudo code.**

**Ans.** (i) Pseudo code is an informal high level description of the
operations principle of a computer program or other algorithm.

(ii) It uses the structural conventions of a normal programming
language, but is intended for human reading rather than machine reading.

**3. Who is an Algorist?**

**Ans.** (i) Algorism is the technique of performing basic arithmetic by
writing numbers in place value form and applying a set of memorized rules and
facts to the digits.

(ii) One who practices algorism is known as an algorist.

**4. What is Sorting?**

**Ans.** Sorting is any process of arranging information or data in an
ordered sequence either in ascending or descending order.

**5. What is searching? Write its types.**

**Ans.** Searching is designed to check for an element or retrieve an
element from any data structure where it is store(d)

**Types:**

(i) Linear Search

(ii) Binary Search.

**Part – III**

**Answer the following questions (3 Marks)**

**1. List the characteristics of an algorithm.**

**Ans.**

(i) Input

(ii) Output

(iii) Finiteness

(iv) Definiteness

(v) Effectiveness

(vi) Correctness

(vii) Simplicity

(viii) Unambiguous

(ix) Feasibility

(x) Portable

(xi) Independent

**2. Discuss about Algorithmic complexity and its types.**

**Ans. **The complexity of an algorithm f (n) gives the running time
and/or the storage space required by the algorithm in terms of n as the size of
input data.

**(i) Time Complexity:** The Time complexity of an algorithm is given by the number of
steps taken by the algorithm to complete the process.

**(ii) Space Complexity :** Space complexity of an algorithm is the amount of memory
required to run to its completion.

**3. What are the factors that influence time and space complexity.**

**Ans.** **(i) Time Factor**
-Time is measured by counting the number of key operations like comparisons in
the sorting algorithm.

**(ii) Space Factor **- Space is measured by the maximum memory space required by the
algorithm.

**4. Write a note on Asymptotic notation.**

**Ans.** Asymptotic Notations are languages that uses meaningful
statements about time and space complexity. Hie following three asymptotic
notations are mostly used to represent time complexity of algorithms:

**(i) Big O:** Big O is often used to describe the worst-case of an algorithm.

**(ii) Big Ω:** Big Omega is the reverse Big O, if Bi O is used to describe the
upper bound (worst - case) of a asymptotic function, Big Omega is used to
describe the lower bound (best-case).

**(iii) Big Θ:** When an algorithm has a complexity with lower bound = upper
bound, say that an algorithm has a complexity O (n log n) and Ω (n log n), its
actually has the complexity Θ (n log n), which means the running time of that
algorithm always falls in n log n in the best-case and worst-case.

**5. What do you understand by Dynamic programming?**

**Ans.** (i) Dynamic programming is an algorithmic design method that
can be used when the solution to a problem can be viewed as the result of a
sequence of decisions.

(ii) Dynamic programming approach is similar to divide and
conquer. The given problem is divided into smaller and yet smaller possible
sub-problems.

(iii) Dynamic programming is used whenever problems can be
divided into similar sub-problems. So that their results can be re-used to
complete the process.

(iv) Dynamic programming approaches are used to find the
solution in optimized way. For every inner sub problem, dynamic algorithm will
try to check the results of the previously solved sub-problems. The solutions
of overlapped sub-problems are combined in order to get the better solution.

**Part – IV**

**Answer the following questions (5 Marks)**

**1. Explain the characteristics of an algorithm.**

**Ans.**

**Input**: Zero or more quantities to be supplied.

**Output**: Al least one quantity is produced.

**Finiteness**: Algorithms must terminate after Unites number of steps.

**Definiteness: **all operations should be well defined. For example operations
involving division by zero or taking square root for negative number are
unacceptable.

**Effectiveness:** Every instruction must be carried out effectively.

**Correctness: **The algorithms should be error free.

**Simplicity: **East to implement.

**Unambiguous:** Algorithm should be clear and unambiguous. Each of its steps
and their inputs/outputs should be clear and must lead to only one meaning.

**Feasibility:** Should be feasible with the available resources.

**Portable:** An algorithm should be generic, independent of any programming
language or an operating system able to handle all range of inputs.

**Independent:** An algorithm should have step-by-step directions, which should
be independent of any programming code.

**2. Discuss about Linear search algorithm.**

**Ans. **(i) Linear search also called sequential search is a sequential
method for finding a particular value in a list.

(ii) This method checks the search element with each element in
sequence until the desired element is found or the list is exhausted. In this
searching algorithm, list need not be ordered.

**Pseudo code:**

(i) Traverse the array using for loop

(ii) In every iteration, compare the target search key value
with the current value of the list.

(iii) If the values match, display the current index and value
of the array.If the values do not match, move on to the next array element.

(iii) If no match is found, display the search element not
found.

To search the number 25 in the array given below, linear search
will go step by step in a sequential order starting from the first element in
the given array if the search element is found that index is returned otherwise
the search is continued till the last index of the array. In this example
number 25 is found at index number 3.

**Example 1:**

Input: values[] = {5, 34, 65, 12, 77, 35}

target = 77

**Output:** 4

**Example 2:**

Input: values[] = {101, 392, 1, 54, 32, 22, 90, 93}

target = 200

**Output:** -1 (not found)

**3. What is Binary search? Discuss with example.**

**Ans. Binary search:** Binary search also called half¬interval search algorithm. It
finds the position of a search element within a sorted array. The binary search
algorithm can be done as divide- and-conquer search algorithm and executes in
logarithmic time.

**Pseudo code for Binary search :**

**Start with the middle element:**

(i) If the search element is equal to the middle element of the
array i.e., the middle value = number of elements in array/2, then return the
index of the middle element.

(ii) If not, then compare the middle element with the search
value,

(iii) If the search element is greater than the number in the
middle index, then select the elements to the right side of the middle index,
and go to Step-1.

(iv) If the search element is less than the number in the middle
index, then select the elements to the left side of the middle index, and start
with Step-1.

(v) When a match is found, display success message with the
index of the element matched.

(vi) If no match is found Tor all comparisons, then display
unsuccessful message.

**Binary Search Working
principles:**

(i) List of elements in an array must be sorted first for Binary
search. The following example describes the step by step operation of binary
search.

(ii) Consider the following array of elements, the array is
being sorted so it enables to do the binary search algorithm. Let us assume
that the search element is 60 and we need to search the location or index of
search element 60 using binary search.

(iii) First, we find index of middle element of the array by
using this formula :

mid = low + (high - low) / 2

(iv) Here it is, 0 + (9 - 0 ) / 2 = 4 (fractional part ignored).
So, 4 is the mid value of the array.

(v) Now compare the search element with the value stored at mid
value location 4. The value stored at location or index 4 is 50, which is not
match with search element. As the search value 60 is greater than 50.

(vi) Now we change our low to mid + 1 and find the new mid value
again using the formula.

low to mid + 1

mid = low + (high - low) / 2

(vii) Our new mid is 7 now. We compare the value stored at
location 7 with our target value 31.

(viii) The value stored at location or index 7 is not a match
with search element, rather it is more than what we are looking for. So, the
search element must be in the lower part from the current mid value location

(ix) The search element still not found. Hence, we calculated
the mid again by using the formula.

high = mid -1

mid = low + (high - low)/2

Now the mid value is 5.

(x) Now we compare the value stored at location 5 with our
search element. We found that it is a match.

(xi) We can conclude that the search element 60 is found at
location or index 5. For example if we take the search element as 95, For this
value this binary search algorithm return unsuccessful result.

**4. Explain the Bubble sort algorithm with example.**

**Ans.** **Bubble sort algorithm:**

(i) Bubble sort is a
simple sorting algorithm. The algorithm starts at the beginning of the list of
values stored in an array. It compares each pair of adjacent elements and swaps
them if they are in the unsorted order.

(ii) This comparison and passed to be continued until no swaps
are needed, which indicates that the list of values stored in an array is
sorted. The algorithm is a comparison sort, is named for the way smaller
elements "bubble" to the top of the list.

(iii) Although the algorithm is simple, it is too slow and less
efficient when compared to insertion sort and other sorting methods.

(iv) Assume list is an
array of n elements. The swap function swaps the values of the given array
elements.

**Pseudo code:**

(i) Start with the first element i.e., index = 0, compare the
current element with the next element of the array.

(ii) If the current element is greater than the next element of
the array, swap them.

(iii) If the current element is less than the next or right side
of the element, move to the next element. Go to Step 1 and repeat until end of
the index is reached.

(iv) Let's consider an array with values {15, 11, 16, 12, 14,
13} Below, we have a pictorial representation of how bubble sort will sort the
given array.

(v) The above pictorial
example is for iteration-1. Similarly, remairfing iteration can be done. The
final iteration will give the sorted array. At the end of all the iterations we
will get the sorted values in an array as given below :

**5. Explain the concept of Dynamic programming with suitable example.**

(i) Dynamic programming is an algorithmic design method that can
be used when the solution to a problem can be viewed as the result of a
sequence of decisions.

(ii) Dynamic programming approach is similar to divide and
conquer. The given problem is divided into smaller and yet smaller possible
sub-problems.

(iii) Dynamic programming is used whenever problems can be
divided into similar sub¬problems. so that their results can be re¬used to
complete the process.

(iv) Dynamic programming approaches are used to find the
solution in optimized way. For every inner sub problem, dynamic algorithm will
try to check the results of the previously solved sub-problems.

(v) The solutions of overlapped sub-problems are combined in
order to get the better solution.

**Steps to do Dynamic programming
:**

(i) The given problem will be divided into smaller overlapping
sub-problems.

(ii) An optimum solution for the given problem can be achieved
by using result of smaller sub-problem.

(iii) Dynamic algorithms uses Memoization.

**Fibonacci Series - An example:**

(i) Fibonacci series generates the subsequent number by adding
two previous numbers. Fibonacci series starts from two numbers - Fib 0 &
Fib 1. The initial values of Fib 0 & Fib 1 can be taken as 0 and 1.

(ii) Fibonacci series satisfies the following conditions :

Fibn = Fib_{n-l} . + Fib_{n-2}

(iii) Hence, a Fibonacci series for the n value 8 can look like
this

Fib_{8} = 0 1 1 23 58 13

**Fibonacci Iterative Algorithm
with Dynamic programming approach : **The following
exam¬ple shows a simple Dynamic programming approach for the generation of
Fibonacci series.

Initialize f0=0, fl =1

**step-1:** Print the initial values of Fibonacci f0 and fl

**step-2:** Calculate fibanocci fib ← f0 + fl

**step-3:** Assign f0 ← fl, fl ← fib

**step-4:** Print the next consecutive value of fibanocci fib

**step-5:** Goto step-2 and repeat until the specified number of terms
generated

For example if we generate fibobnacci series upto 10 digits, the
algorithm will generate the series as shown below:

The Fibonacci series is : 0 1 1 2 3 5 8 13 21 34 55.

Tags : Computer Science , 12th Computer Science : Chapter 4 : Algorithmic Strategies

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

12th Computer Science : Chapter 4 : Algorithmic Strategies : Algorithmic Strategies: Book Back Questions and Answers | Computer Science

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.