# CSE303 / DAA

## Syllabus

{% file src="<https://3148391480-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FoWho7cxjZIbvsuDwIAzB%2Fuploads%2F1uRTMNfwoTrQ20HtbWA4%2FY3S5-CSE303-SYLLABUS-BTECH-CSE-IT.pdf?alt=media&token=ddc125c6-7fd9-4e1e-92fb-c11d6f26f85e>" %}

## Resources

<details>

<summary>M1: Introduction</summary>

* **Algorithm Design Paradigms**
  * Motivation
  * Concept of algorithmic efficiency
  * Run time analysis of algorithms
  * Asymptotic notations
* **Recurrences**
  * Substitution Method
  * Recursion Tree Method
  * Master’s Method

***

<table><thead><tr><th width="81.0859375">[⤓]</th><th>Content Preview</th></tr></thead><tbody><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1X9aXWjQiRIk5j0JJ62FEWFpstIEertOd" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1X9aXWjQiRIk5j0JJ62FEWFpstIEertOd/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M1-L1-Introduction to Algorithm</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1l0ILBi7hei9QHle9LK0o4JrrlxsmX8FU" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1l0ILBi7hei9QHle9LK0o4JrrlxsmX8FU/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M1-L2-Algorithm Design Techniques</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=13x7YOi44yquPFdsZw5-mt6LZPS7Hvqto" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/13x7YOi44yquPFdsZw5-mt6LZPS7Hvqto/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M1-L3-Asymptotic Notations</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1Ekwy1eLY55YZ2b0KfAtyDEWrE0AvAEnB" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1Ekwy1eLY55YZ2b0KfAtyDEWrE0AvAEnB/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M1-L4-Recurrences</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=13D6--7bfrZRRx53o0saq8JlMen10r6U1" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/13D6--7bfrZRRx53o0saq8JlMen10r6U1/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M1-L5-Substitution Method</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=180Kw9isPu8CCqjUd0iCuZmc1H-DBlXOi" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/180Kw9isPu8CCqjUd0iCuZmc1H-DBlXOi/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M1-L6-Recursion Tree Method</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1RNuGUAQN0yYQUu6gjEOVmLbwD7eYzuR9" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1RNuGUAQN0yYQUu6gjEOVmLbwD7eYzuR9/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M1-L7-Master Method</a></td></tr></tbody></table>

</details>

<details>

<summary>M2: Divide &#x26; Conquer</summary>

* **Structure of divide-and-conquer algorithms**
  * Examples: Binary search, Quick sort, Merge sort, Strassen multiplication
  * Analysis of run time recurrence relations
* **Greedy Method**
  * Overview of greedy paradigm
  * Examples:
    * Exact optimization: Minimum Cost Spanning Tree
    * Approximate solution: Knapsack Problem
    * Single source shortest paths
    * Traveling Salesman

***

<table><thead><tr><th width="81.0859375">[⤓]</th><th>Content Preview</th></tr></thead><tbody><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1Bo0gjavO40O30kSvHi2log5vUI-vDipR" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1Bo0gjavO40O30kSvHi2log5vUI-vDipR/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M2-L1-Divide and Conquer Algorithm</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1ZQUlvOTog0ATQoAJPfbwwFvTW5rDKuE7" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1ZQUlvOTog0ATQoAJPfbwwFvTW5rDKuE7/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M2-L2-Quick Sort</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1xK1FWdm5ZHeOPh5nPbS31r8YHYxIMvUj" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1xK1FWdm5ZHeOPh5nPbS31r8YHYxIMvUj/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M2-L3-Merge Sort</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1cfWAPXvOCtLu_MkypzFaOW8MT-hFfCbT" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1cfWAPXvOCtLu_MkypzFaOW8MT-hFfCbT/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M2-L4-Strassen’s Matrix Multiplication</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1wODwQny-RO9OQFqjajMjuGbipKwC0Kb_" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1wODwQny-RO9OQFqjajMjuGbipKwC0Kb_/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M2-L5-Knapsack Problem</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1OzLSPW4r2TDXc-_aXjmhXZVwv5PxQ2Bp" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1OzLSPW4r2TDXc-_aXjmhXZVwv5PxQ2Bp/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M2-L6-MST-Prim’s Kruskal Algorithm</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1c5MCgZfWGH9S0iF307u3q3yEg0CN9HOD" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1c5MCgZfWGH9S0iF307u3q3yEg0CN9HOD/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M2-L7-Dijkstra Algorithm</a></td></tr></tbody></table>

</details>

<details>

<summary>M3: Dynamic Programming</summary>

* Overview
* Difference between dynamic programming and divide and conquer
* Applications:
  * Shortest path in a graph
  * Chain matrix multiplication
  * Traveling Salesman Problem
  * Longest common sequence
  * Knapsack Problem

***

<table><thead><tr><th width="81.0859375">[⤓]</th><th>Content Preview</th></tr></thead><tbody><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1RnFpQy-P1NIHbadAs09SGDf20EhVtdX9" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1RnFpQy-P1NIHbadAs09SGDf20EhVtdX9/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M3-L1-Divide-Conquer Method vs Dynamic-Programming-CSE303</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1USiF-wzSLhvd9ok6Kau3wGRAInG6EJ-R" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1USiF-wzSLhvd9ok6Kau3wGRAInG6EJ-R/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M3-L2-Knapsack problem-Dynamic Programming-CSE303</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=13RaMubo43Bu9dv4PbdcZuFpcLqPrIyf5" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/13RaMubo43Bu9dv4PbdcZuFpcLqPrIyf5/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M3-L3-Longest Common Subsequence-CSE303</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1GdmPYfUEBVFEDMegZgKWLkDu8blm8dyz" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1GdmPYfUEBVFEDMegZgKWLkDu8blm8dyz/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M3-L4-Matrix Chain Multiplication-CSE303</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1VgKWXYhD8lUwYkWO_WavIzefP0O9L2vT" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1VgKWXYhD8lUwYkWO_WavIzefP0O9L2vT/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M3-L5-All pair shortest path-CSE303</a></td></tr></tbody></table>

</details>

<details>

<summary>M4: Graph Search &#x26; Traversal</summary>

* Overview
* Representation of graphs
* Strongly connected components
* Traversal methods:
  * Depth-first search (DFS)
  * Breadth-first search (BFS)
* **Backtracking**
  * Overview
  * 8-queen problem
  * Knapsack Problem
* **Branch and Bound**
  * LC searching and bounding
  * FIFO branch and bound
  * LC branch and bound
  * Applications:
    * 0/1 Knapsack Problem
    * Traveling Salesman Problem

***

<table><thead><tr><th width="81.0859375">[⤓]</th><th>Content Preview</th></tr></thead><tbody><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1UGish3kes4Y6zPzh0tmGTwP956SKPsxw" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1UGish3kes4Y6zPzh0tmGTwP956SKPsxw/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M4-L1-Graph-Introduction-CSE303</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1_qbKkClkk-nGjco5vcRPLHbrioz7GKwV" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1_qbKkClkk-nGjco5vcRPLHbrioz7GKwV/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M4-L2-Representation of Graph-CSE303</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1dKFPaZlgTWipOmRqRTx33IDHPjzQ2s4h" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1dKFPaZlgTWipOmRqRTx33IDHPjzQ2s4h/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M4-L3-Traversal_BFS-CSE303</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1jfEZ4EuTgw3z6xi38-1PU24zKUEfIW0m" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1jfEZ4EuTgw3z6xi38-1PU24zKUEfIW0m/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M4-L4-DFS-CSE303</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1TS2DCFqshj_y-ic-ML4SqwB58ZTvNCox" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1TS2DCFqshj_y-ic-ML4SqwB58ZTvNCox/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M4-L5-Introduction of Backtracking-CSE303</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1DJruNmH86ogOzHOKEhka02-2bt_SSC1M" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1DJruNmH86ogOzHOKEhka02-2bt_SSC1M/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M4-L6-Queens problem-CSE303</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1fGIwie_y8AzDPBA0M6wv4VW4-bQe6WDI" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1fGIwie_y8AzDPBA0M6wv4VW4-bQe6WDI/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M4-L7-Branch and Bound-CSE303</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=12BkRQPcfnoMkHeFnomwhyoFaj4MaztYx" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/12BkRQPcfnoMkHeFnomwhyoFaj4MaztYx/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M4-L8- BB_Travelling Salesman Problem-2-CSE303</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1mSWv2nV7GTY4VBTBdnKHfewb4Zy-F6u_" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://docs.google.com/presentation/d/1mSWv2nV7GTY4VBTBdnKHfewb4Zy-F6u_/edit?usp=drive_link&#x26;ouid=114560226846413789967&#x26;rtpof=true&#x26;sd=true">M4-L9- Knapsack_BB-1-CSE303</a></td></tr></tbody></table>

</details>

<details>

<summary>M5: Computational Complexity</summary>

* Complexity measures
* Polynomial vs non-polynomial time complexity
* NP-hard and NP-complete classes with examples

***

<table><thead><tr><th width="81.0859375">[⤓]</th><th>Content Preview</th></tr></thead><tbody><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1IMHrS11BlkcgAxl2GysRoWVwXhsMLOX5" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://drive.google.com/file/d/1IMHrS11BlkcgAxl2GysRoWVwXhsMLOX5/view?usp=drive_link">M5-All-L-Computational-Complexity-CSE303</a></td></tr></tbody></table>

</details>

## Notes

### MidTerm

<a href="https://drive.google.com/uc?export=download&#x26;id=1kB7_2JnWBoIe--O8UiK4f-f1qlmfe_hl" class="button primary" data-icon="arrow-down-to-square"></a> [CSE303-M1+M2-MidTerm-Notes](https://drive.google.com/file/d/1kB7_2JnWBoIe--O8UiK4f-f1qlmfe_hl/view?usp=drive_link)

{% embed url="<https://drive.google.com/file/d/1kB7_2JnWBoIe--O8UiK4f-f1qlmfe_hl/view?usp=drive_link>" %}

### EndSem

\[⤓]

## Question Directory

### Previous Year Questions

#### Mid-Sem-PYQ

<table><thead><tr><th width="81.90771484375">[⤓]</th><th width="554.568115234375">Content Preview</th></tr></thead><tbody><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1unwQl1g4KLVXTD7QOyc8ihqJXcU8Sa3b" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://drive.google.com/file/d/1unwQl1g4KLVXTD7QOyc8ihqJXcU8Sa3b/view?usp=drive_link">Y3S5-CSE303-DAA-MidTerm-Set-A-PYQ-OCT25</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1Atf52gtlMCVjdqwgcwx0PYXzjCGBkdpM" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://drive.google.com/file/d/1Atf52gtlMCVjdqwgcwx0PYXzjCGBkdpM/view?usp=drive_link">Y3S5-CSE303-DAA-MidTerm-Set-B-PYQ-OCT25</a></td></tr></tbody></table>

#### End-Sem-PYQ

<table><thead><tr><th width="81.9005126953125">[⤓]</th><th width="547.80322265625">Content Preview</th></tr></thead><tbody><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1jJvWWuQ2-EB1--JDy8oBFq3mLDYpH56o" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://drive.google.com/file/d/1jJvWWuQ2-EB1--JDy8oBFq3mLDYpH56o/view?usp=drive_link">Y3S5-CSE303-DAA-EndSem-PYQ-DEC23</a></td></tr><tr><td><a href="https://drive.google.com/uc?export=download&#x26;id=1M2Yjn7ISdeJjF2pVOu7-0a1BdDrAq3zJ" class="button primary" data-icon="arrow-down-to-square"></a></td><td><a href="https://drive.google.com/file/d/1M2Yjn7ISdeJjF2pVOu7-0a1BdDrAq3zJ/view?usp=drive_link">Y3S5-CSE303-DAA-EndSem-PYQ-DEC24</a></td></tr></tbody></table>

## External Sources

{% embed url="<https://youtube.com/playlist?list=PLxCzCOWd7aiHcmS4i14bI0VrMbZTUvlTa&si=pN-Cs2wA2TUMGcyp>" %}

***

{% embed url="<https://discord.gg/6ywR3zbNfg>" %}

{% embed url="<https://mantavyam.notion.site/18152f7cde8880d699a5f2e65f87374e>" %}

{% embed url="<https://mantavyam.notion.site/17e52f7cde8880e0987fd06d33ef6019>" %}