This repository is a comprehensive compilation of questions, codes, and activities from the Design and Analysis of Algorithms (DAA) course. It is organized week-wise, using the folder names to reflect the topics covered each week. The structure is designed to help students prepare for lab FATs and reinforce their understanding of algorithmic concepts.
Each week's folder contains:
- Lab Exercise: Questions and solutions practiced during the lab session.
- MCQ: Multiple-choice questions discussed and solved in the week.
- Practice At Home: Additional problems for self-practice.
- Challenge Yourself: Advanced problems for deeper understanding.
All codes and questions are collected to aid in lab FAT preparation.
Below are the topics as per the folder names in this repository:
- Lab Exercise: Implementation and analysis of Quicksort algorithm.
- MCQ: Conceptual and practical questions on Quicksort.
- Practice At Home / Challenge Yourself: Extra sorting problems.
- Lab Exercise: Implementation of Mergesort and Binary Search algorithms.
- MCQ: Questions on divide and conquer, searching, and sorting.
- Practice At Home / Challenge Yourself: Additional problems on sorting and searching.
- Lab Exercise: Minimum Spanning Tree algorithms (Prim's and Kruskal's).
- MCQ: Theory and application-based questions on MST algorithms.
- Practice At Home / Challenge Yourself: More graph algorithm problems.
- Lab Exercise: Implementation and applications of Dijkstra's algorithm.
- MCQ: Conceptual and practical questions on shortest path algorithms.
- Practice At Home / Challenge Yourself: Extra problems on shortest path.
- Lab Exercise: Standard and Strassen’s matrix multiplication algorithms.
- MCQ: Questions on matrix operations and algorithm analysis.
- Practice At Home / Challenge Yourself: Matrix multiplication and related problems.
- Lab Exercise: Construction and cost calculation of OBST.
- MCQ: Theory and application-based questions on OBST.
- Practice At Home / Challenge Yourself: Additional OBST problems.
- Lab Exercise: Problems on Longest Common Subsequence (LCS), Longest Palindromic Subsequence (LPS), and Longest Increasing Subsequence (LIS).
- MCQ: Questions on dynamic programming techniques for sequences.
- Practice At Home / Challenge Yourself: More DP sequence problems.
- Lab Exercise: Directed graph representations, traversal (DFS/BFS), topological sort, strongly connected components.
- MCQ: Concepts and properties of digraphs, edge directions, and algorithmic implications.
- Practice At Home / Challenge Yourself: Problems on DAGs, cycle detection, and reachability.
- Lab completion: 100%
- Lab Exercise: Floyd–Warshall algorithm, repeated Dijkstra for dense/sparse graphs, negative weight handling.
- MCQ: Complexity comparisons, correctness, and use-cases for APSP algorithms.
- Practice At Home / Challenge Yourself: Variants and optimizations of APSP.
- Lab completion: 50%
- Lab Exercise: Ford–Fulkerson, Edmonds–Karp, residual networks, min-cut / max-flow theorem.
- MCQ: Flow conservation, augmenting paths, complexity trade-offs.
- Practice At Home / Challenge Yourself: Network flow problem modeling (bipartite matching, circulation with demands).
- Lab completion: 50%
- Lab Exercise: Backtracking solutions for n-Queens, pruning strategies, constraint propagation.
- MCQ: Symmetry reductions, complexity, and heuristics.
- Practice At Home / Challenge Yourself: Improve solver speed and count all solutions for given n.
- Lab completion: 0%
- Lab Exercise: Sliding puzzle representation, solvability test (inversions), A* search with heuristics (Manhattan distance).
- MCQ: State-space size, admissible heuristics, and performance trade-offs.
- Practice At Home / Challenge Yourself: Implement an efficient A* solver and experiment with heuristic combinations.
Pull Requests (PRs) are appreciated!
If you have additional questions, solutions, or improvements, feel free to contribute and help make this repository even more useful for everyone.
Happy Learning and All the Best for Your Lab FATs!