Algorithm Design And Analysis Assignment.
ADA-Assignment-Programs This repo contains all the programs which i have done as a part of ADA assignment
Unit-1: Introduction to Algorithms: Implement a binary search algorithm for an array of integers. Implement a selection sort algorithm for an array of integers. Implement an insertion sort algorithm for an array of integers. Implement a merge sort algorithm for an array of integers. Implement a quick sort algorithm for an array of integers. Implement a linear search algorithm for an array of integers. Implement a hash table data structure using separate chaining collision resolution Implement a hash table data structure using linear probing collision resolution. Unit-2: Divide and Conquer: Implement a recursive algorithm for computing the factorial of a given positive integer using divide-and-conquer. Implement a recursive algorithm for computing the Fibonacci sequence using divide-and-conquer. Implement a recursive algorithm for computing the greatest common divisor of two integers using divide-and-conquer. Implement a recursive algorithm for computing the Euclidean distance between two points in 2D space using divide-and-conquer. Implement a divide-and-conquer algorithm for merging two sorted arrays. Implement a divide-and-conquer algorithm for sorting a linked list. Unit-3: Dynamic Programming: Implement the Fibonacci sequence using dynamic programming in C or Python. Implement the longest common subsequence problem using dynamic programming in C or Python. Analyze the time and space complexity of your implementation and compare it with the time and space complexity of a naive recursive implementation. Implement the knapsack problem using dynamic programming in C or Python. Analyze the time and space complexity of your implementation and compare it with the time and space complexity of a greedy algorithm. Implement the rod-cutting problem using dynamic programming in C or Python. Analyze the time and space complexity of your implementation and compare it with the time and space complexity of a naive recursive implementation Implement the matrix chain multiplication problem using dynamic programming in C or Python. Analyze the time and space complexity of your implementation and compare it with the time and space complexity of a naive recursive implementation. Develop a dynamic programming algorithm for the edit distance problem in C or Python. Analyze the time and space complexity of your implementation and compare it with the time and space complexity of a naive recursive implementation. Develop a dynamic programming algorithm for the coin change problem in C or Python. Analyze the time and space complexity of your implementation and compare it with the time and space complexity of a greedy algorithm. Develop a dynamic programming algorithm to find the longest increasing subsequence in C or Python. Analyze the time and space complexity of your implementation and compare it with the time and space complexity of a brute-force approach. Unit-4: Greedy Algorithms: Implement Kruskal's algorithm to find the minimum spanning tree of a given graph in C or Python. Implement the Dijkstra algorithm to find the shortest path between two vertices in a graph in C or Python. Implement Prim's algorithm to find the minimum spanning tree of a given graph in flowchart. Unit-5: Graph Algorithms: Implement Breadth First Search (BFS) algorithm to find the shortest path between two nodes in a graph in C or Python. Implement Depth First Search (DFS) algorithm to traverse a graph and find connected components in C or Python. Implement Dijkstra's algorithm to find the shortest path between two nodes in a weighted graph in C or Python. Implement the Prim's algorithm to find the minimum spanning tree of a given graph in C or Python.