Question 8

A. Let M be the adjacency matrix (size n x n) of a graph G =(V, E) of n vertices (V ={ 0,1,2,…,n−1} ) in which:

Mi, j =1 if vertices i and j are adjacent, and

Mi, j =0 if vertex i and j are not adjacent.

Let S ⊂ V={ 0,1,2,…,n−1} be a set of some vertices of G.

(a) Design an algorithm to verify if every pair of vertices in S are adjacent.

Input: An adjacency matrix M and a subset S of vertices of the graph

Output: Boolean value True if every pair of vertices in S are adjacent and False otherwise

Represent your algorithm in a pseudocode. Do not use any programming language for the solution. The purpose of this question is for you to learn writing pseudocode.

(b) What is the time function and big O complexity of your algorithm? In this question, mark is given only when time function is correct.

1. In a programming language, the matrix M can be represented as 2-dimentional array. In some languages, Mi,j can be called as M[i][j]. You are free to use any option that you are confident with.

2. You can assume that the set S is already a subset of V. You do not have to verify this condition.

B. a) Write an algorithm to solve the problem as discussed below.

b) What is time function of this algorithm? What is the big O complexity of your algorithm? In this question, mark is given only when time function is correct.

In week 1, we learn how to verify if a set is a relation from a set A to a set A. We also tried a question in Assessment 1 on this where we manually check elements one by one.

In this question, you are asked to write an algorithm that reads in three sets A, B, and X and output a Boolean value True if X is a relation from set A to set B and False otherwise.

Assumption:

1. Sets A and B are sets of objects and they have operator “in”. The call “x in A” will output True if x is an element in A and False otherwise. The same is true for set B.

2. The set X is iterable in the sense that you can iterate elements in X using the format “For each element e in X”.

3. Each element of X is a list of two objects. This means you can access the first and second elements of any element e of X by calling e[0] and e[1]. Our indices and list notation here are like our discussion in lectures and handout of week 9 materials.

Example:

A = {“Banana”, “Potato”, “Pumpkin”} and B = {“Fruit”, “Vegetable”} X = {[“Banana”, “Banana”],[“Banana”, “Fruit”]}

Your algorithm should output False because e[1] is not in B where e is the first element of X.

Your algorithm should work in the way that it can deal with any sets A, B, and X rather than only the above example input. Please think that X may have one million elements.