Design and Analysis of Algorithms, Semester 4(2020), Model examination, July 2022

 

SAINTGITS COLLEGE OF APPLIED SCIENCES

          PATHAMUTTOM, KOTTAYAM

 

Model Examination, JULY 2022

P.G Department of Computer Applications & Artificial Intelligence, Semester 4

Design & Analysis of Algorithms

Total : 80 marks                                                                    Time: 3 hours

Section A

Answer any 6questions.Each question carries 3 marks.

(Write in not less than a paragraph)

1. What is space complexity of an algorithm?

The space complexity of an algorithm or a computer program is the amount of memory space required to solve an instance of the computational problem as a function of characteristics of the input. It is the memory required by an algorithm until it executes completely.

 

2. Define algorithm.

An algorithm is a procedure used for solving a problem or performing a computation. Algorithms act as an exact list of instructions that conduct specified actions step by step in either hardware- or software-based routines. Algorithms are widely used throughout all areas of IT.

3. State principle of optimality.

Principle of Optimality. Definition: A problem is said to satisfy the Principle of Optimality if the subsolutions of an optimal solution of the problem are themesleves optimal solutions for their subproblems. Examples: The shortest path problem satisfies the Principle of Optimality.

 

4. Define Kruskal algorithm?

Kruskal's algorithm is the concept that is introduced in the graph theory of discrete mathematics. It is used to discover the shortest path between two points in a connected weighted graph. This algorithm converts a given graph into the forest, considering each node as a separate tree

5. Give the definition of the minimum spanning trees.

A minimum spanning tree or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible

6. Define Big Omega notation.

Similar to big O notation, big Omega(Ω) function is used in computer science to describe the performance or complexity of an algorithm. If a running time is Ω(f(n)), then for large enough n, the running time is at least k⋅f(n) for some constant k.

7. List the advantages of Greedy algorithm.

·         Greedy approach is easy to implement.

·         Typically have less time complexities.

·         Greedy algorithms can be used for optimization purposes or finding close to optimization in case of NP Hard problems.

 

8. Define Prims algorithm.

In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized

 

9.  Define Best, Average and Worst case.

Best case is the function which performs the minimum number of steps on input data of n elements. Worst case is the function which performs the maximum number of steps on input data of size n. Average case is the function which performs an average number of steps on input data of n elements.

 

10. What is ordering paradigm?

For the problems that make decisions by considering the inputs in some order, each decision is made using an optimization criterion that can be computed using decisions already made. This version of greedy method is ordering paradigm.

 

11. What is travelling salesman problem?

The traveling salesman problem (TSP) is an algorithmic problem tasked with finding the shortest route between a set of points and locations that must be visited.

 

12. Define biconnected component.

In graph theory, a biconnected component is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or separating vertices or articulation points.

 

                                                                                                            (6 x 3 = 18 Marks)

Section B

Answer any 4 questions. Each question carries 8 marks.

(Write in not less than 2 pages)

 

13. Write the characteristics of Divide and Conquer algorithm.

·         Divide the problem into a number of subproblems that are smaller instances of the same problem.

·         Conquer the subproblems by solving them recursively. ...

·         Combine the solutions to the subproblems into the solution for the original problem

 

14. Explain all pairs shortest path with algorithm.

Write the algorithm.

Definition

 

15. Explain in detail algorithm analysis.

In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them

 

16. Write the algorithm of merge sort.

Write the algorithm of merge sort

 

17. Write a note on Performance Analysis.

Performance analysis of an algorithm is done to understand how efficient that algorithm is compared to another algorithm that solves the same computational problem. Choosing efficient algorithms means computer programmers can write better and efficient programs.

 

18.  Discuss the forward approach in multistage graph with an example.

Dynamic programming uses either forward recursion or backward recursion to solve a management problem. Forward recursion involves moving in a direction from the first stage to the last stage. Backward recursion is the opposite, where the problem is solved from the last stage backward to the first stage.

 

19. Explain in detail any 2 algorithm design strategies.

Design strategies are

Divide and conquer

Greedy method

Dynamic programming

Backtracking

 

20. Find an optimal solution to the knapsack instance n=4 objects and the capacity of 

      knapsack m=15, Profits (10,5,7,11) and weights are (3,4,3,5)

 

 21.  Write the algorithm of 8 Queens problem.

Write the algorithm

            (4 x 8 = 32 Marks)

 

Section C

Answer up to 3 questions carrying 15 marks each. However, total marks for this section should not exceed 30 marks. Marks scored over 30 will be ignored

 

22. Explain in detail binary search algorithm with an example.

23. What is an algorithm? Explain its different properties. Also explain different areas of an algorithm.

24. Discuss in detail about the procedure for Strassen's Matrix Multiplication. Illustrate with an example.

25. Explain Kruskal algorithm with an example.

 

                                                                                                

            (Maximum 30 Marks)

 

 

 

 

[Scan QR code for Answer Key]