i will be giving you some question, i want you to solve them that is 
first give me the intuition of the pseudocode in detail then give me the actual pseudocode then prove the pseudocode that why does it work in detail and finally give detailed runtime analysis of the pseudocode
1. You are given an array of intervals, where each interval is defined as [starti
, endi
]. Your task
is to find the minimum number of intervals that need to be removed so that the remaining
intervals do not overlap.
Example 1:
Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1
Explanation: By removing the interval [1, 3], the rest of the intervals no longer overlap.
Example 2:
Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2
Explanation: Two of the intervals [1, 2] must be removed to eliminate all overlapping intervals.
Design an alogithhm for the same and mention its proof of correctness.
2. A message is made up entirely of characters from the set X = {P, Q, R, S, T}. The table of
probabilities for each of the characters is shown below:
Character Probability
P 0.22
Q 0.34
R 0.17
S 0.19
T 0.08
Total 1.00

If a message of 100 characters over X is encoded using Huffman coding, then the expected
length of the encoded message in bits is .
3. A Huffman tree is constructed for the following data: {A, B, C, D, E} with frequencies {0.17,
0.11, 0.24, 0.33, 0.15} respectively. The binary sequence 100 00 01101 is decoded as ?
4. Consider the following message:

BCCABBDDAECCBBAEDDCC

Determine the number of bits required for Huffman encoding of the above message.

1

5. You are given an algorithm and your task is to determine the objective of the same (usability).
Starting with intervals, your first sort them by their start times, breaking ties arbitrarily. Let
I1, I2, . . . , In denote the intervals in sorted order. For j = 1, 2, 3, . . . , n
• For each interval Ii that precedes Ij in sorted order and overlaps it:
– Exclude the label of Ii from consideration for Ij .
• If there is any label from {1, 2, . . . , d} that has not been excluded:
– Assign a nonexcluded label to Ij .
• Else
– Leave Ij unlabeled.
Endfor
Here d is the maximum number of overlapping intervals at a particular timestamp.
6. The city has n lakes, numbered from 1 to n. Whenever it rains over a lake, that lake becomes
full. The problem is represented by an array called rains where rains[i] means it rains over
the rains[i]

th lake on i

th day. If it rains on a lake that is already full, it results in a flood. To
prevent flooding, you have the option to dry one lake on days when it does not rain.
• rains[i] > 0 means there will be rains over the lake indexed by rains[i].
• rains[i] == 0 means there are no rains this day and you can choose one lake this day
and dry it.
Objective:
Determine whether it is possible to prevent flooding. If flooding can be avoided, return an
array where:
• The elements corresponding to rainy days are set to 1.
• On non-rainy days, return a positive integer representing the lake that is dried.
If it is impossible to prevent flooding, return an empty array.
Design an algorithm for the same and give its proof of correctness.
Example 1:
Input: rains = [1, 2, 3, 4]
Output: [-1, -1, -1, -1]
Explanation: No lakes are full, so no drying is needed.
Example 2:
Input: rains = [1, 2, 0, 0, 2, 1]
Output: [-1, -1, 2, 1, -1, -1]
Explanation: Dry lake 2 on day 3, and dry lake 1 on day 4 to avoid flooding.
7. You are given an array costs where costs[i] is the price of the i-th ice cream bar, and an
integer coins representing the total number of coins you have. You need to purchase the
maximum number of ice cream bars with your coins.
You can buy the ice cream bars in any order, and you may decide not to buy any ice cream
bars at all. Return the maximum number of ice cream bars you can purchase.

Solve it using Dynamic Programming. Also, give proof of correctness.
Example 1:
Input: costs = [1, 3, 2, 4, 1], coins = 7
Output: 4
Explanation: You can buy the ice creams priced at 1, 1, 2, and 3.
Example 2:
Input: costs = [10, 6, 8, 7, 7, 8], coins = 5
Output: 0
Explanation: You do not have enough coins to buy any ice cream.
Example 3:
Input: costs = [1, 6, 3, 1, 2, 5], coins = 20
Output: 6
Explanation: You can buy all the ice creams.
8. Prove the correctness of Prim’s and Kruskal’s algorithm to find a Minimum Cost Spanning
Tree of a graph.