ADA USING C

Design and Analysis of Algorithm.

Introduction: What is an Algorithm? Fundamentals of Algorithmic problem solving. Fundamentals of the Analysis of Algorithm Efficiency. Analysis Framework. Measuring the input size, Units for measuring Running time, Orders of Growth, Worst-case, Best-case and Average-case efficiencies.

Asymptotic Notations and Basic Efficiency classes, Informal Introduction, O-notation,Ω-notation, θ-notation, mathematical analysis of non-recursive algorithms, mathematical analysis of recursive algorithms.

Brute Force & Exhaustive Search: Introduction to Brute Force approach, Selection Sort and Bubble Sort, Sequential search, Exhaustive Search Travelling Salesman Problem and Knapsack Problem, Depth First Search, Breadth First Search.

Decrease-and-Conquer: Introduction, Insertion Sort, Topological Sorting.

Divide-and-Conquer: Introduction, Merge Sort, Quick Sort. Binary Search, Binary Tree traversals and related properties.

Greedy Technique: Introduction. Prim's Algorithm, Kruskal's Algorithm. Dijkstra's Algorithm. Lower-Bound Arguments, Decision Trees, P Problems, NP Problems, NP- Complete Problems. Challenges of Numerical Algorithms.

Practical Content

1.Write a program to sort a list of N elements using Selection Sort Technique

2.Write a program to perform Travelling Salesman Problem

3. Write program to implement Dynamic Programming algorithm for the 0/1 Knapsack problem.

4. Write a program to perform Knapsack Problem using Greedy Solution

5. Write program to implement the DFS and BFS algorithm for a graph.

6. Write a program to find minimum and maximum value in an array using divide and conquer.

7. Write a test program to implement Divide and Conquer Strategy.

Eg: Quick sort algorithm for sorting list of integers in ascending order.

8. Write a program to implement Merge sort algorithm for sorting a list of integers in ascending order

9. Sort a given set of n integer elements using Merge Sort method and compute its time complexity Run the program for varied values of n 5000, and record the time taken to sort

10. Sort a given set of n integer elements using Quick Sort method and compute its time complexity Run the program for varied values of n> 5000 and record the time taken to sort

11. Write C program that accepts the vertices and edges for a graph and stores it as an adjacency matrix.

12. Implement function to print In-Degree, Out-Degree and to display that adjacency matrix

13. Write program to implement backtracking algorithm for solving problems like N queens

14. Write a program to implement the backtracking algorithm for the sum of subsets problem

15. Write program to implement greedy algorithm for job sequencing with deadlines.

16. Write program to implement Dynamic Programming algorithm for the Optimal Binary Search Tree Problem.

17. Write a program that implements Prim's algorithm to generate minimum cost spanning Tree.

18. Write a program that implements Kruskal's algorithm to generate minimum cost spanning tree.