DAA_lab

KO | EN

gitlite — search

#typescript #llm #golang #go #android #linux #macos #java #windows #cli #kubernetes #awesome-list #security #pytorch

(★ 14)

Compilation of questions from DAA course - Design and Analysis of Algorithms

DAA_lab Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# DAA_lab

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.

---

## Repository Structure

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.`

---

## Weekly Topics Covered

Below are the topics as per the folder names in this repository:

### **Week 1: Quicksort**

- **Lab Exercise**: Implementation and analysis of Quicksort algorithm.
- **MCQ**: Conceptual and practical questions on Quicksort.
- **Practice At Home / Challenge Yourself**: Extra sorting problems.

### **Week 2: Mergesort and Binary Search**

- **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.

### **Week 3: Prim's and Kruskal's Algorithm**

- **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.

### **Week 4: Dijkstra's Algorithm**

- **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.

### **Week 5: Matrix Multiplication**

- **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.

### **Week 6: OBST (Optimal Binary Search Tree)**

- **Lab Exercise**: Construction and cost calculation of OBST.
- **MCQ**: Theory and application-based questions on OBST.
- **Practice At Home / Challenge Yourself**: Additional OBST problems.

### **Week 7: LCS, LPS, LIS (Dynamic Programming on Sequences)**

- **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.

### **Week 8: Digraph**

- **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%

### **Week 9: APSP (All-Pairs Shortest Paths)**

- **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%

### **Week 10: Maximum Flow**

- **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%

### **Week 11: nQueens**

- **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%

### **Week 12: 15-puzzle problem**

- **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.

---

## Contribution

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!**

DAA_lab

DAA_lab Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

DAA_lab

DAA_lab Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README