---
# System prepended metadata

title: Revision of DSA Topics

---

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

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

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





### Pseudo Code

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

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

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

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

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

```cpp
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;
        }
      }
    }
}
```  

    