# Revision of DSA Topics

---
title: DSA 4.2 Module Description
description:
duration: 600
card_type: cue_card
---

> ### Note to Instructor: Please keep the below content pre-written on your iPad.

* Revision of DSA Topics
* Maths: Inverse Mod & Problems
* Backtracking: Famous Problems
* Tries 1: Trie of Character
* Tries 2: Trie of Bits + Problems on Trees
* Strings Pattern Matching
* DP 1: DP on Strings
* DP 2: Famous Problems
* Graphs 1: DSU, Kruskal Algorithm & Bipartite Graph
* Graphs 2: Bellman Ford & Floyd Warshall Algorithm
* Advanced Interview Problems

---
title: Agenda
description:
duration: 600
card_type: cue_card
---

Topics:
* Recursion
* DP
* Graphs => BFS and DFS

---
title: Problem 1 Scaler Adventure Park
description:
duration: 600
card_type: cue_card
---

### Problem Statement

Scaler has opened an Adventure Park and there is a staircase. Every staircase has a cost associated that you need to pay when you claims it.

You can either start from the 0th staircase or the 1st staircase.

**Goal:** What is the least amount of money you can spend to reach the top.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/874/original/a.png?1725808889" width=500px/>

**Example 1:**

A = [9, 12, 22]
Cost = 12

**Example 2:**
A = [10, 20, 5, 8, 15, 25, 10, 12]

Cost = 10+5+15+10 = 40

### Approach

Whenever we have Notation of choices, we always go for Recursion as the solution initiallly.

Recursion gives the flexibility to make the choices.

**Notation of choice => Recursion**

**4 Step to solve any Recursion Problems:**
1. Elements of choice => Jump of 1 stair or Jump of 2 stairs.
2. What does a recursive state calculates.
Cost(2) => Minimum cost to reach the ith staircase.
3. Reccurance relationship
<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/875/original/a.png?1725808923" width=500px/>
The last state is dependent on the Penultimate states,
`Cost(i) = min(Cost(i-1), Cost(i-2)+A[i])`
<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/908/original/a.png?1725816267" width=500px/>

**Base Case**
Before moving to 4th step, Lets discuss the base case part

Values of i for which transition goes out of sounds
<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/909/original/a.png?1725816314" width=500px/>

So here we cant make use of the recurrence relation.

Here we will directly declare the base cases.

Cost(0) = A[0]
Cost(1) = A[1]

4. Which reccursive state is your answer?
`min(cost(N - 1), cost(N - 2))`

### Pseudo Code

int cost (i) {
    if(i == 0 || i == 1){
        return A[i];
  }
  return min(cost(i - 1),cost(i - 2)) + A[i];
}
Ans = min(cost(N - 1), cost(N - 2));

### Complexity

**Time complexity**: O(2$^N$)
**Space Complexity**: O(Height of rear tree) = O(N)

---
title: Scaler Adventure Park Optimisation
description:
duration: 600
card_type: cue_card
---

### Possiblity of DP

1. Optimal Substructure
2. Overlapping Subproblems

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/910/original/a.png?1725816355" width=500px />

Lets look into both the approaches one by one!

**1. Top Down DP**

Recursion + Memoization.

Lets modify the recursion code

### Pseudo Code

DP[N] = {-1}
int cost(i){
   if(i == 0 || i == 1){
      return A[i];
   }
   if(DP[i] != -1){
      return DP[i];
   }
   DP[i] = min(cost(i - 1),cost(i - 2)) + A[i];
   return DP[i];
}
Ans = min(DP[N - 1], DP[N - 2]);

### Dry Run

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/911/original/a.png?1725816393" width=500px/>

### Complexity

**Time complexity**: O(N)

**Space Complexity**: N + N

Time complexity of rear solution = (# recursive cells) * (Time per recursive cell)

**2. Bottom Up DP**

We will move from Left to Right,
<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/913/original/a.png?1725816461" width=500px/>

### Pseudo Code

DP[N]

DP[0] = A[0]
DP[1] = A[1]

for(i = 2; i < N; i++){
   DP[i] = min(DP[i - 1], DP[i - 2]) + A[i];
}
 return min(DP[N - 1], DP[N - 2]);

### Complexity

**Time complexity**: O(N)
**Space Complexity**: N

# Top Down v/s Bottom Up.

1. No stack space in Bottom Up.
2. Top Down is more in
3. Bottom Up gives more control.

### Optimised Version on Space

costi2 = A[0]

costi1 = A[1]

for(i = 2; i < 2; i++){
    temp = min(costi1, costi2) + A[i];
    costi2 = costi1;
    costi1 = temp;
}

return min(costi1, costi2);

### Complexity

**Time complexity**: O(N)

**Space Complexity**: O(1)

---
title: Graphs
description:
duration: 600
card_type: cue_card
---

### Definition
Nodes connected via edges

What is the other data structure, which as the similar definition?
> Tree

### Main Difference Between Trees and Graphs

1. Trees are hierarchical unlike graphs.
2. Number of edges in a tree with N nodes is N - 1

### Classification of Graphs

**1. Facebook => Undefined Graph**

In Facebook, Lets say, If A is a Friend of B, then it implies, B is a Friend of A.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/070/352/original/graph.png?1712261639" width=200 />

**2. Instagram => Directed Graph**

Lets say, If A is following B, does it implies, that B is following A ? No!

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/070/353/original/graph.png?1712262966" width=300 />

Examples:
<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/878/original/a.png?1725809817" width = 500px />

**3. Weighted and Unweighted Graph**

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/876/original/a.png?1725809534" width=500px/>

**4. Cyclic Undirected and Acyclic Undirected graph**

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/877/original/a.png?1725809682" width=500px/>

**4. Cyclic directed and Acyclic directed graph**

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/879/original/a.png?1725809980" width=500px/>

> NOTE: Type of graph will be given in question.

---
title: Graph Inputs
description:
duration: 600
card_type: cue_card
---

### How graph is given as I/P ?

<img src = "https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/880/original/a.png?1725810098" width = 500px />

Example:

10 14 (N = 10, E = 14)
2 3 (These next 10 lines are the edges)
4 7
8 9
2 7
7 8
10 1
4 6
5 8
2 6
10 9
7 10
3 5
7 1
1 1

In Questions, it is given as follows:

1. Undirected or Directed
2. Weighted or Unweighted

>Note that Cyclic or Acyclic is not given in the Question.

---
title: Store a Graph
description:
duration: 600
card_type: cue_card
---

### Store A Graph

Lets Consider this graph, and will see, how to store this.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/881/original/a.png?1725810341" width=500px/>

There are two famous Representation,

**1. Adjacency Matrix**

Lets have an 2-D array, M[N][N].

* M[i][j] = 1/Weight => Edge from i to j
* M[i][j] = 0 => No edge from i to j

The adjancy matrix for the above exmaple.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/882/original/a.png?1725810471" width=500px/>

### Complexity

**Space Complexity**: O(N$^2$)

**Time Complexity**: O(E)

**2. Adjacency List**

Just store the neighbour nodes alone for a particular node.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/883/original/a.png?1725810540" width=500px/>

For a weighted graph, we use

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/884/original/a.png?1725810687" width=500px/>

---
title: Traversals of Graphs
description:
duration: 600
card_type: cue_card
---

### Traversals

* Depth First Search (DFS)
* Breadth First Search (BFS)

**1. DFS**

Starting with Source as 2.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/886/original/a.png?1725810794" width=500px/>

### Pseudo Code

visited [N] = {False}

void dfs (source){
   visited [source] = True;
   for(all u connected to source){
        if(visited[u] == false){
            dfs(u);
        }
   }
}

**2. BFS**

Starting with Source as 2.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/088/887/original/a.png?1725810848" width=500px/>

### Pseudo Code

void bfs (source){
     visited(N) = {false}
     Queue<int> q;
     q.enqueue(source);
     visited[source] = True;
     while(! q.isEmpty()){
         int u = q.dequeue();
         for(all v converted to a){
             if(visited[v] == false){
                 q.enqueue(v);
                 visited[v] = True;
        }
      }
    }
}