DAA_Assignments

This repository contains Design and Analysis of Algorithms (DAA) assignments implemented in C++. The assignments cover various algorithmic problems and techniques, including graph traversal, dynamic programming, sorting algorithms, and time analysis of recursive and iterative approaches.

📂 Project Structure

Each algorithm is implemented as a separate C++ file with detailed comments explaining the logic. Below is a list of the included assignments:

1. Depth First Search (DFS)

• Description: Implements DFS to traverse a graph using recursion.
• Input: Adjacency list or matrix.
• Output: Traversal order of nodes.

2. Breadth First Search (BFS)

• Description: Implements BFS to traverse a graph level by level using a queue.
• Input: Adjacency list or matrix.
• Output: Traversal order of nodes.

3. Chain Matrix Multiplication

• Description: Solves the matrix chain multiplication problem using dynamic programming to find the minimum number of scalar multiplications.
• Input: Dimensions of matrices.
• Output: Minimum number of multiplications required.

4. Coin Change Problem

• Description: Solves the coin change problem using dynamic programming.
• Input: Array of coin denominations and the target amount.
• Output: Number of ways to make the target amount.

5. Diamond Problem (0/1 Knapsack)

• Description: Solves the 0/1 knapsack problem using dynamic programming to maximize the value of items that can be included in the knapsack.
• Input: Weights, values of items, and knapsack capacity.
• Output: Maximum value that can be obtained.

6. Factorial

• Description: Compares the time complexity of factorial calculation using both iterative and recursive methods.
• Output: Execution time of each approach.
• Time Analysis of Iterative and Recursive Approaches

7. Fibonacci

• Description: Compares the time complexity of Fibonacci number calculation using both iterative and recursive methods.
• Output: Execution time of each approach.
• Time Analysis of Iterative and Recursive Approaches

8. Longest Common Subsequence (LCS)

• Description: Finds the longest subsequence common to two sequences using dynamic programming.
• Input: Two sequences.
• Output: Length and elements of the longest common subsequence.

9. Kruskal's Algorithm

• Description: Finds the minimum spanning tree of a graph using Kruskal's algorithm.
• Input: Graph with weighted edges.
• Output: Edges in the minimum spanning tree and its total weight.

10. Prim's Algorithm

• Description: Finds the minimum spanning tree of a graph using Prim's algorithm.
• Input: Graph with weighted edges.
• Output: Edges in the minimum spanning tree and its total weight.

11. Sorting Algorithms

• This section includes implementations and time complexity analysis for:

  • SimpleSort
  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort
  • Heap Sort
  • Counting Sort
  • Radix Sort

• Each sorting algorithm includes:

  • Best Case: Time complexity analysis.
  • Average Case: Time complexity analysis.
  • Worst Case: Time complexity analysis.

🧪 Time Complexity Analysis

For algorithms involving iterative and recursive approaches, detailed time complexity analysis is provided to compare their efficiency.

Algorithm	Best Case	Average Case	Worst Case
Bubble Sort	O(n)	O(n^2)	O(n^2)
Selection Sort	O(n^2)	O(n^2)	O(n^2)
Insertion Sort	O(n)	O(n^2)	O(n^2)
Merge Sort	O(n log n)	O(n log n)	O(n log n)
Quick Sort	O(n log n)	O(n log n)	O(n^2)
Heap Sort	O(n log n)	O(n log n)	O(n log n)
Counting Sort	O(n + k)	O(n + k)	O(n + k)
Radix Sort	O(nk)	O(nk)	O(nk)

📊 Tools and Libraries Used

• C++ Standard Library

• g++ Compiler

• Time Library (for time analysis)