CSE221 Task 01 Solution

You are given a piece of python code and a txt file named graph.txt. The input file contains the number of vertices in the first line, n, followed by the number of connections, c. Then there are c numbers of lines mentioning the connection between a pair of vertices in the form a,b – a is connected to b. The graph given is a directed graph.
If you look at the python file you will see that the methods readFile() and buildGraphUsingDictionary() have been done for you. Not only that, comments have been added for you to understand how each line is working and why it has been used.
Read the comments very carefully and study the code and of course run the code to match your input with the output. Your job is to complete the buildGraphUsingListofLists() method and the printGraph() method. Google “list of lists in python” to aid you complete the tasks.
Task 02 [10 Points]:
Alice and you are playing with a list of N non negative integers. Today you will try to find out the maximum number of the list. Alice writes the following code to find the maximum number.
maxValue = arr[0] for i in range(1,N): if maxValue < arr[i]: maxValue = arr[i]
Recently you have learned merge sort. Now, you are thinking if you can use the divide and conquer approach to find out the maximum from the given list.
Input
The first line contains an integer N ( 1 <= N <= 105), denoting the length of Alice’s sorted list. In the next line, there will be N integers separated by space.
Output:
You have to find out the maximum value from the list using the divide and conquer approach. Sample Input/Output:
Sample Input 1 Sample Output 1
8
1 7 13 4 5 7 13 12 13
Sample Input 2 Sample Output 2
7
5 15 2 3 10 1 9 15
Sample Input 3 Sample Output 3
1
9 9
Sample Input 4 Sample Output 4
6
5 2 3 10 1 9 10
Task 03 [10 Points]:
Somewhere in the universe, the Biannual Regional Alien Competition is taking place.
There are N aliens standing in a line. You will be given a permutation of N, which denotes the height of each alien. A sequence of N numbers is called permutation if it contains all integers from 1 to N exactly once. For example, the sequences [3,1,4,2], [1] and [2,1] are permutations, but [1,2,1], [0,1] and [1,3,4] — are not.
In the competition, for each alien, the judge wants to count how many aliens are standing on its right side with a strictly smaller height. The judge writes the following code to solve the problem.
count = 0 for i in range(n):
for j in range(i+1,n): if H[i] > H[j]:
count+=1
However, their algorithm wasn’t efficient at all. Hence, the alien calls you to write a better solution for the program.
More formally, you have to count how many pairs of aliens are standing in the line such that H[i] > H[j] and i<j. Here, A is the permutations of Alience’s height. And i,j denotes the Alience’s position.
Input
The first line contains a single integer 1 <= N <= 106 - the number of total aliens.
The next line contains N integers H1,H2,…………,Hn(1 ≤ Hi ≤ N)- the height of the i-th alien. It is guaranteed that the given heights will be the permutation of N.
Output
Print a single integer, which denotes the total number of inversions of the given permutation of alien’s heights as described in the problem statement.
Sample Input/Output:
Sample Input 1 Sample Output 1
5
1 2 3 4 5 0
Sample Input 2 Sample Output 2
5
5 4 3 2 1 10
Sample Input 3 Sample Output 3
8
2 7 4 1 5 6 8 3 11
Sample Input 3 Explanation:
In the sample input 3, the following pairs on alien’s heights satisfy the condition: (2,1), (7,4), (7,1), (7,5), (7,6), (7,3),
(4,1), (4,3), (5,3), (6,3), (8,3)