DS 397, Spring 2021, Homework 5

due Thursday April 22, 11:59 PM

Material Covered

● Algorithmic Methods for Graphs and Networks

Submission:

●   The pdf file, a5.pdf, must include the following:

–   pseudocode, along with a brief explanation of each step

–   explanation of time complexity

–   the answers to the questions

Indicate clearly which answer belongs to which question. Marks will be deducted if these are not followed.

●   For the implementation in questions 1 and 4 submit a java file, a5q*.java, or a python file, a5q*.py, to Canvas. Your algorithms will be tested based on test cases. We expect you to follow a reasonable programming style. While we do not mandate a specific style, we require that your code to be neat, clear, documented/commented and above all consistent. Marks will be deducted if these are not followed.

Question 1: Finding Loyal Lions, Continued (30 points)

Thanks to your help in the previous homework, the instructor figured out the minimum amount of money and therefore won the game! While disappointed (since the lions have to wash the dishes), they must keep their promise and show us the jungles. The location of the jungles can be seen in a map, which is a m × n matrix. Each entry is either 0 or 1, where 0 represents desert and 1 forest. Here, a jungle is surrounded by deserts and comprised of adjacent forests connected horizontally or vertically. Examples of the jungles can be seen in Tests 1 and 2.

●   Design an algorithm that takes as input a matrix, and outputs the number of discon-nected jungles.

●   The time complexity of the algorithm should not be worse than O(m × n).

●   For this question, you should provide:

1.  The pseudocode, along with a brief explanation of each step

2.  The explanation of the time complexity

3.  The Java or Python implementation

●   The function is declared as follows.

//Java

public class Solution {

public int numOfJungles(int[][] matrix) {

//Implement me

}

}

#Python

class Solution(object):

def numOfJungles(self, matrix):

"""

:type matrix: List[List[int]]

:rtype: int

"""

# Implement me

Test 1:

Input:

1 1 1 1 0

1 0 0 1 0

1 1 0 1 0

0 0 0 0 0

Output: 1

Explanation: There is only one jungle, as shown by the red 1s.

Test 2:

Input:

1 1 1 1 0

1 0 0 0 0

1 1 0 1 0

0 0 0 0 0

Output: 2

Explanation: There are two disconnected jungles, as shown by the red 1s.

Question 2: Applied Algorithms (30 points)

Part I (15 points)

Consider Kruskal’s algorithm for finding a minimum spanning tree. Given the following undirected graph, apply Kruskal’s algorithm to find the minimum spanning tree:

●   You must show every step of applying the algorithm and intermediate steps.

●   You must also show the status of the union-find data structure at each step.

Note. Your work must clearly show steps of the algorithm including all the details.

Part II (15 points): A research question

The PageRank algorithm is a method for finding the most influential nodes in a graph network. It was the first algorithm developed and used by Google founders to rank web pages in their search engine results. It can also be used to rank influencers on social media platforms such as Tweeter and Instagram.

The algorithm outputs a probability distribution used to represent the likelihood that a person randomly clicking on links will arrive at any particular page.

In this question, you are asked to research the PageRank algorithm, learn how it works, and apply it to the given graph.

●   For this question, you can (and should) use any sources on the internet (including videos, papers, Wiki pages, etc.).

●   Focus only on the simplified version of PageRank.

●   Your work must clearly show steps of the algorithm including all the details.

●   You must show the state of the graph (and the values of nodes) in each iteration.

Question 3: Shortest Path (20 points)

Consider the following directed graph:

Part I

Show the adjacency matrix for this graph.

Part II

Given the graph above, illustrate the steps of running the Bellman-Ford algorithm for finding the shortest paths from vertex A to all other vertices in the graph.

Note. Your work must clearly show each iteration of the Bellman-Ford algorithm including all the details.

Question 4: Detecting Negative Cycles (20 points)

There is a weighted graph G with possibly negative weights on some edges. Describe an algorithm that takes the graph as input and detects whether the graph contains any negative cycle.

●   Design an algorithm that takes as input a matrix, and outputs true or false.

●   The time complexity of the algorithm should not be worse than O(m × n).

●   For this question, you should provide:

1.  The pseudocode, along with a brief explanation of each step

2.  The explanation of the time complexity

3.  The Java or Python implementation

●   The function is declared as follows.

//Java

public class Solution {

public boolean detectNegativeCycle(int[][] matrix) {

//Implement me

}

}

#Python

class Solution(object):

def detectNegativeCycle(self, matrix):

"""

:type matrix: List[List[int]]

:rtype: boolean

"""

# Implement me

Test 1:

Input:

0 5 3

1 0 0

0 0 0

Output: False

Explanation: There is no negative cycle.

Test 2:

Input:

0 -5 3

1 0 0

-1 2 0

Output: True