- Question 6 2 Marks Insert The Following List Of Integers Following Order Of Insertion From Left To Right Of The List 1 (23.27 KiB) Viewed 86 times
Question 7 (2 marks) Consider the following algorithm: Input: Two matrices A and B both of size n x n 1. Initialize C to be a matrix of size n x n whose entries are all 0 2. For i from 1 to n: 3. 4. For j from 1 to n: If Ai,j # Bij: Ci,j = 5. 6. Output C Ai,j x Bij Determine the time function of this algorithm. To explain, state number of time units or iterations in each line. You only need to solve one of the two options of Question 8. Please choose one.
Question 8 Option 1 (2 + 1 marks) 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: Mij = 1 if vertices i and j are adjacent, and Mij = 0 if vertex i and j are not adjacent. Let S CV = {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. Note:
1. In a programming language, the matrix M can be represented as 2-dimentional array. In some languages, Mij can be called as M[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