ADA_lab_jssstu

Design and Analysis of Algorithm Lab @SJCE

List of Programs

1. GCD Algorithms:

   • Implement Euclid’s, Consecutive integer checking, and Modified Euclid’s algorithms to find GCD of two nonnegative integers.
   • Perform comparative analysis by generating best case and worst case data.

2. Searching Algorithms:

   • Implement the following searching algorithms and perform their analysis by generating best case and worst case data. a) Sequential Search b) Binary Search(Recursive)

3. Elementary Sorting Algorithms:

   • Implement the following elementary sorting algorithms and perform their analysis by generating best case and worst case data. a) Selection Sort b) Bubble Sort c) Insertion Sort (Note: Any two may be asked in the test/exam)

4. Brute Force String Matching:

   • Implement Brute force string matching algorithm to search for a pattern of length ‘M’ in a text of length ‘N’ (M<=N).
   • Perform its analysis by generating best case and worst case data.

5. Merge Sort:

   • Implement Merge Sort algorithm and perform its analysis by generating best case and worst case data.

6. Quick Sort:

   • Implement Quick Sort algorithm and perform its analysis by generating best case and worst case data.

7. DFS Algorithm:

   • Implement DFS algorithm to check for connectivity and acyclicity of a graph.
   • If not connected, display the connected components.
   • Perform its analysis by generating best case and worst case data. (Note: While showing correctness, input should be given for both connected/disconnected and cyclic/acyclic graphs.)

8. BFS Algorithm:

   • Implement BFS algorithm to check for connectivity and acyclicity of a graph.
   • If not connected, display the connected components.
   • Perform its analysis by generating best case and worst case data. (Note: While showing correctness, Input should be given for both connected/disconnected and cyclic/acyclic graphs.)

9. Topological Ordering:

   • Implement DFS based algorithm to list the vertices of a directed graph in Topological ordering.
   • Perform its analysis giving a minimum of 5 graphs with a different number of vertices and edges. (starting with 4 vertices). (Note: While showing correctness, input should be given for with and without a solution.)

10. Source Removal Algorithm:

    • Implement source removal algorithm to list the vertices of a directed graph in Topological ordering.
    • Perform its analysis giving a minimum of 5 graphs with a different number of vertices and edges. (starting with 4 vertices). (Note: Use an efficient method to identify the source vertex. While showing correctness, Input should be given for with and without a solution.)

11. Heap Sort:

    • Implement heap sort algorithm with bottom-up heap construction.
    • Perform its analysis by generating best case and worst case data.

12. Graph Algorithms: a) Implement Warshall’s Algorithm to find the transitive closure of a directed graph. b) Implement Floyd’s Algorithm to find All-pair shortest paths for a graph.

    • Perform analysis giving a minimum of 5 graphs with a different number of vertices and edges (starting with 4 vertices).

13. Dynamic Programming - Knapsack Problem: a) Implement bottom up Dynamic Programming algorithm to solve the Knapsack problem. b) Implement a Dynamic Programming algorithm with a Memory function to solve the Knapsack problem.

    • Perform analysis with different instances (different numbers of items and Capacity, starting with 4 items).

14. Prim’s Algorithm:

    • Implement Prim’s algorithm to find the Minimum Spanning Tree of a graph.
    • Perform its analysis giving a minimum of 5 graphs with a different number of vertices and edges (starting with 4 vertices).

15. Dijkstra's Algorithm:

    • Implement Dijkstra's algorithm to find the shortest path from a given source to all other vertices.
    • Perform its analysis giving a minimum of 5 graphs with a different number of vertices and edges (starting with 4 vertices).