Design and Analysis of Algorithms B.C.A 17-20 SEM 4, Sec Internal March 2019

Name   …………………………… Roll No ……………………….

SAINTGITS COLLEGE OF APPLIED SCIENCES

SECOND INTERNAL ASSESSMENT EXAMINATION, MARCH 2019

Department of B.C.A, Semester 4

DESIGN AND ANALYSIS OF ALGORITHM – ANSWER SCHEME

Total   : 80 marks                                                                        Time: 3 Hours

Section A

Answer any 10 questions. Each question carries 2 marks.

1.      What is an algorithm design technique?

Algorithm design technique determines the style and approach  of designing an algorithm Various style involves divide and conquer, dynamic programming, greedy approach and backtracking.

2.      What is worst case efficiency of an algorithm?

The worst-case complexity of an algorithm should be contrasted with its average-case complexity, which is an average measure of the amount of resources the algorithm uses on a random input.

3.      Define Omega notation.

Omega Notation, Ω The notation Ω(n) is the formal way to express the lower bound of an algorithm's running time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete.

4.      Define the general concept of Divide and Conquer method.

In computer science, divide and conquer is an algorithm design paradigm based on multi-branched recursion. A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.

5.      Write any two characteristics of greedy algorithm.

Greedy algorithms produce good solutions on some mathematical problems, but not on others. Most problems for which they work will have two properties: Greedy choice property. ... "A problem exhibits optimal substructure if an optimal solution to the problem contains optimal solutions to the sub-problems."

6.      What is the use of Dijkstra’s algorithm?

Dijkstra's algorithm is an algorithm that is used to solve the shortest distance problem. That is, we use it to find the shortest distance between two vertices on a graph. Depending on what the graph represents, we can find shortest routes, minimum costs, etc. all using this algorithm.

7.      What is meant by n-queen problem?

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For example, following is a solution for 4 Queen problem. The expected output is a binary matrix which has 1s for the blocks where queens are placed.

8.      Define Travelling salesman problem.

The Traveling Salesman Problem (often called TSP) is a classic algorithmic problem in the field of computer science and operations research[1]. It is focused on optimization. In this context, better solution often means a solution that is cheaper, shorter, or faster. TSP is a mathematical problem. It is most easily expressed as a graph describing the locations of a set of nodes.

9.      Define Hamiltonian circuit.

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

10.  What are a feasible solution and an optimal solution?

An optimal solution is a feasible solution where the objective function reaches its maximum (or minimum) value – for example, the most profit or the least cost. A globally optimal solution is one where there are no other feasible solutions with better objective function values.

11.  What is knapsack problem?

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

12.  Define an algorithm.            

An algorithm (pronounced AL-go-rith-um) is a procedure or formula for solving a problem, based on conducting a sequence of specified actions. ... In mathematics and computer science, an algorithm usually means a small procedure that solves a recurrent problem.                                              10 x 2 = 20

Section B

Answer any six of the following. Each question carries 5 marks.

13.  Write the algorithm of binary search.

Binary search algorithm – 5  marks

14.  Briefly explain Strassen’s matrix multiplication method with an example.

Write all the equation and an example – 5 marks

15.  Explain graph coloring in detail.

Graph coloring is nothing but a simple way of labelling graph components such as vertices, edges, and regions under some constraints. In a graph, no two adjacent vertices, adjacent edges, or adjacent regions are colored with minimum number of colors

Also write the algorithm – 5 marks

16.  Explain asymptotic notations in detail.

Asymptotic Notations are languages that allow us to analyze an algorithm's running time by identifying its behavior as the input size for the algorithm increases. This is also known as an algorithm's growth rate.

Write big oh , Omega and theta notation  - 5 marks

17.  Explain the properties of an algorithm with an example each.

An algorithm must satisfy the following properties: Input: The algorithm must have input values from a specified set. Output: The algorithm must produce the output valuesfrom a specified set of input values. ... Finiteness: For any input, the algorithm must terminate after a finite number of steps.

18.  What is backtracking? Write any one algorithm which follows backtracking.

Backtracking is a general algorithm for finding all solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate as soon as it determines that the candidate cannot possibly be completed to a valid solution

Write the algorithm of 8 queens or sum of subsets or graph colouring or Hamiltonian

19. State the Greedy Knapsack? Find an optimal solution to the Knapsack instance

n=3, m=20, (P1, P2, P3) = (25, 24, 15) and (W1, W2, W3) = (18, 15, 10).

Definition – 2 marks

Problem solving – 3 marks

20. What is a Hamiltonian Cycle? Explain how to find Hamiltonian path and cycle

using backtracking algorithm.

Definition – 2 marks

Explanation – 3 marks

21. Write the algorithm of Kruskal.

Algorithm – 5 marks(No tracing required for 5 marks)

                                                             (6x5=30)

Section C.

Answer any two of the following.

Each question carries 15 marks

       22. Explain Prim’s algorithm in detail.

            Definition – 3 marks

            Algorithm – 7 marks

            Tracing  - 5 marks

23. Apply merge sort algorithm to the list {14, 33, 27, 10, 35, 19, 42, and 44}.

            Solving the list – 15 marks

24.  Write and explain the algorithm of Sum of Subsets.

            Definition – 3 marks

            Algorithm – 7 marks

            Tracing – 5 marks

25.  What is dynamic programming? Write any algorithm which uses dynamic programming concept.

Definition – 3 marks

Algorithm – 7 marks

Tracing – 5 marks

                                                                  (2x15=30)

[Scan QR code for answer key]

_____________________