This repository contains implementations of various algorithms completed as part of our lab exercises. Each lab focuses on a different algorithmic concept, including recursive and iterative approaches, divide and conquer, and greedy strategies. Below is a brief description of each lab:
Topic: Implement the insertion inside iterative and recursive Binary Search Tree (BST) and compare their performance.
Description: This lab demonstrates the implementation of both iterative and recursive approaches to inserting elements into a Binary Search Tree. The performance comparison highlights the differences between these two methods.
Topic: Implement divide and conquer-based Merge Sort and Quick Sort algorithms and compare their performance for the same set of elements.
Description: This lab focuses on two important sorting algorithms: Merge Sort and Quick Sort. By implementing both, we compare their performance when applied to the same dataset.
Topic: Compare the performance of Strassen's method of matrix multiplication with the traditional way of matrix multiplication.
Description: In this lab, we explore matrix multiplication using Strassen's method and the traditional method, comparing their efficiency for different matrix sizes.
Topic: Implement the activity selection problem to get a clear understanding of the greedy approach.
Description: The activity selection problem is implemented to showcase the greedy algorithm approach, which helps in selecting the maximum number of activities without overlapping.
Topic: Matrix Chain Multiplication with Dynamic Programming to analyze the impact of parenthesis positioning on computation time.
Description: This lab demonstrates the dynamic programming approach to the Matrix Chain Multiplication problem. By optimizing parenthesis placement, we aim to minimize the number of scalar multiplications required, highlighting how dynamic programming can significantly improve efficiency.
Topic: Performance comparison between Dijkstra’s and Bellman-Ford algorithms for single-source shortest path.
Description: This lab implements both Dijkstra and Bellman-Ford algorithms, which are used for finding the shortest path from a single source. We compare their performance, considering both time complexity and their effectiveness in handling graphs with and without negative weights.
Topic: Analyzing the greedy and dynamic programming approaches for the 0/1 Knapsack problem.
Description: This lab explores the 0/1 Knapsack problem using two approaches: greedy and dynamic programming. We analyze their effectiveness on the same dataset, emphasizing the differences in solutions and efficiency between greedy heuristics and the dynamic programming method.
Topic: Implementation of the Sum of Subset problem.
Description: In this lab, we tackle the Sum of Subset problem, which finds all subsets of a set that sum up to a particular target value. The implementation showcases recursive and/or backtracking methods to explore possible subset combinations efficiently.
Topic: Comparing Backtracking and Branch & Bound approaches in the 0/1 Knapsack problem, including performance analysis against dynamic programming.
Description: This lab demonstrates the use of Backtracking and Branch & Bound approaches in the 0/1 Knapsack problem. By comparing these methods with dynamic programming, we gain insights into their performance differences in terms of time complexity and memory usage.
Topic: Performance comparison among Rabin-Karp, Knuth-Morris-Pratt, and naive string matching algorithms.
Description: In this lab, we implement and compare three string matching algorithms: Rabin-Karp, Knuth-Morris-Pratt, and the naive approach. Through performance analysis, we assess their efficiency on different types of strings and highlight the advantages of each algorithm in various scenarios.