Welcome to the repository for the Laboratory Practice III (410246) course, focusing on Design and Analysis of Algorithms, part of the Fourth Year Computer Engineering curriculum (2019 Course) at Savitribai Phule Pune University. This repository provides practical implementations and resources to help you explore fundamental algorithm design techniques, analyze their performance, and implement solutions for various computational problems.
🏛️ Course Information:
| Feature | Description |
|---|---|
| University | Savitribai Phule Pune University |
| Course Name | Laboratory Practice III (410246) |
| Companion Course | Design and Analysis of Algorithms (410241) |
| Credit | 02 |
| Practical Sessions | 04 Hours/Week |
| Examination Scheme | Term Work: 50 Marks Practical Exam: 50 Marks |
🎯 Learning Objectives:
- Develop strong problem-solving skills using mathematical and algorithmic principles.
- Learn to apply appropriate algorithmic strategies to solve different types of problems.
- Analyze the time and space complexity of algorithms to understand their efficiency.
- Design and implement time and space-efficient algorithms.
- Study and understand algorithms used in distributed and concurrent environments.
- Gain insights into multithreaded and distributed algorithms.
💡 Course Outcomes:
Upon successful completion of this laboratory course, students will be able to:
- CO1: Formulate computational problems effectively and define their requirements.
- CO2: Analyze the asymptotic performance (time and space complexity) of algorithms using Big O notation.
- CO3: Select and apply appropriate algorithmic strategies (e.g., greedy, dynamic programming, divide and conquer) to solve given problems.
- CO4: Find optimal or near-optimal solutions to problems using various algorithmic methods.
- CO5: Analyze and implement common scheduling and sorting algorithms.
- CO6: Design and implement basic algorithms suitable for multi-core, distributed, or concurrent environments.
📂 Practical Implementations:
| Practical No. | Description |
|---|---|
| 1 | Fibonacci Numbers (Recursive & Non-Recursive): 1. Write both recursive and non-recursive programs to calculate Fibonacci numbers. 2. Analyze the time and space complexity of each approach. |
| 2 | Huffman Encoding: Implement Huffman Encoding, a lossless data compression algorithm, using a greedy approach. |
| 3 | Fractional Knapsack Problem: Implement a solution to the Fractional Knapsack problem using a greedy strategy. |
| 4 | 0-1 Knapsack Problem: Implement a solution to the 0-1 Knapsack problem using either dynamic programming or a branch and bound strategy. |
| 5 | N-Queens Problem (Backtracking): 1. Design an N-Queens matrix with the first queen placed in a specific position. 2. Use backtracking to place the remaining queens so that no two queens threaten each other. |
Mini Project - String Matching Algorithms:
Implement the Naive string matching algorithm and the Rabin-Karp algorithm for string matching. Compare and contrast the performance of these algorithms using the same input string and pattern.
🚀 Getting Started:
Navigate to the specific practical implementation directory for instructions, code examples, and further details.
🙌 Contributions:
Contributions, improvements, and feedback are welcome! If you have any enhancements, bug fixes, or additional examples to share, please open a pull request. Refer to the CONTRIBUTING.md file for guidelines.
📄 License:
This repository is distributed under the MIT License. You are free to use, modify, and distribute the code for educational and personal projects.
Let's dive into the fascinating world of algorithms and enhance our problem-solving skills!