manisha-nair28/Analysis-and-Design-of-Algorithms

This repository contains a collection of programming exercises focused on implementing and analyzing the efficiency of algorithms.

Analysis and Design of Algorithms(ADA) Assignment

This repository contains my college assignments for the subject of Analysis and Design of Algorithms (ADA) in the 6th semester of my 3rd year. Collection of programming assignments that I completed as part of the ADA course are contained in this repository. These assignments cover a range of topics, including flowcharts, algorithm design paradigms, complexity analysis, and more. Each assignment comes with a detailed problem statement and my implementation of the solution.

Unit-1: Introduction to Algorithms:

Programming Exercises:

1. Implement a binary search algorithm for an array of integers.

2. Implement a bubble sort algorithm for an array of integers.

3. Implement a selection sort algorithm for an array of integers.

4. Implement an insertion sort algorithm for an array of integers.

5. Implement a merge sort algorithm for an array of integers.

6. Implement a quick sort algorithm for an array of integers.

7. Implement a linear search algorithm for an array of integers.

8. Implement a hash table data structure using separate chaining collision resolution.

9. Implement a hash table data structure using linear probing collision resolution.

10. Implement a heap data structure and use it to sort an array of integers.

Unit-2: Divide and Conquer:

Programming Exercises:

1. Implement a recursive algorithm for computing the factorial of a given positive integer using divide-and-conquer.

2. Implement a recursive algorithm for computing the Fibonacci sequence using divide-and-conquer.

3. Implement a recursive algorithm for computing the greatest common divisor of two integers using divide-and-conquer.

4. Implement a recursive algorithm for computing the Euclidean distance between two points in 2D space using divide-and-conquer.

5. Implement a divide-and-conquer algorithm for finding the maximum subarray sum of a given array of integers.

6. Implement a divide-and-conquer algorithm for merging two sorted arrays.

7. Implement a divide-and-conquer algorithm for finding the kth largest element in an unsorted array of integers.

8. Implement a divide-and-conquer algorithm for multiplying two large integers.

9. Implement a divide-and-conquer algorithm for finding the closest pair of points in 2D space.

10. Implement a divide-and-conquer algorithm for sorting a linked list.

Unit-3: Dynamic Programming:

Programming Exercises:

1. Implement the Fibonacci sequence using dynamic programming. Analyze the time complexity of your implementation and compare it with the time complexity of a recursive implementation.

2. Implement the longest common subsequence problem using dynamic programming. Analyze the time and space complexity of your implementation and compare it with the time and space complexity of a naive recursive implementation.

3. Implement the knapsack problem using dynamic programming. Analyze the time and space complexity of your implementation and compare it with the time and space complexity of a greedy algorithm.

4. Implement the rod-cutting problem using dynamic programming. Analyze the time and space complexity of your implementation and compare it with the time and space complexity of a naive recursive implementation.

5. Implement the matrix chain multiplication problem using dynamic programming. Analyze the time and space complexity of your implementation and compare it with the time and space complexity of a naive recursive implementation.

6. Develop a dynamic programming algorithm for the edit distance problem. Analyze the time and space complexity of your implementation and compare it with the time and space complexity of a naive recursive implementation.

7. Develop a dynamic programming algorithm for the coin change problem. Analyze the time and space complexity of your implementation and compare it with the time and space complexity of a greedy algorithm.

8. Implement a dynamic programming algorithm to find the maximum sum subarray. Analyze the time and space complexity of your implementation and compare it with the time and space complexity of a naive brute-force approach.

9. Develop a dynamic programming algorithm to find the longest increasing subsequence. Analyze the time and space complexity of your implementation and compare it with the time and space complexity of a brute-force approach.

10. Create a flowchart for a dynamic programming algorithm that solves the longest common substring problem. Analyze the time and space complexity of the algorithm and compare it with the time and space complexity of a brute-force approach.