Clique problem
The Clique Problem is a classic problem in the field of computer science, specifically in the areas of algorithm design and analysis, as well as graph theory.
Clique Problem Definition:
In graph theory, a clique in an undirected graph is a subset of vertices such that every two distinct vertices in the subset are connected by an edge. In other words, it is a complete subgraph where each pair of vertices is adjacent.
The Clique Problem can be formally defined as follows:
Input: An undirected graph \( G = (V, ______ ________ ____ ____ _________ ________ _______ ______ _________ _____ ___.
___ ____ __________ ______ __________ _____ ___.
_____ ____ ________ ________ ________ __________ _________ __________ __________ ________ _________.
__________ ________ _______ __________ ____ __________ __________ __________ _____.
___ ________ _____ _____ ___ ____ ____ _____ _____.
________ _________ ____ ____ ___ ________ ________ ________ __________ ______ _____.
______ ____ ___ _______ ______ _____ __________ ___ ________ _________.
__________ __________ ______ _________ ________ ______ _____ ______.
____ _________ ____ ________ ____ ____ __________ ____ ___ ___.
______ ______ ________ _________ ____ __________ ______ _____.
___ __________ ________ _______ _______ ___ ______ ___ __________.
___ ____ ________ _________ __________ _____.
_____ ___ _____ ___ ___ ___ ________ ___ ____ _____ ________ ________.
______ _______ _____ _________ _____.
________ ____ ______ ____ ______ ____ ________ _______ __________ _________ _____.
________ _____ ________ _________ _________ ___ __________ ______.
______ _________ ______ _____ _______.
__________ _______ _______ ____ ___ _________ __________ ______ _________.
____ _______ ____ _____ _______ ______ _____ ___ _________ ___ ____ ___.
__________ _______ ____ ___ _______ __________ ___ ____ ____ _____.
__________ ___ _______ ________ _________ _______ ____ _____.
________ ________ _______ _______ __________ _____ _________ ___ ______.
___ ____ _______ _________ ________ ______ _______ _________ _______.
_________ ______ _____ ___ ____ _______ __________ ____.
_________ ___ _________ ___ ______ _______ __________ __________ ________.
______ _________ ______ __________ _____ _______ ________.
________ ____ __________ _____ ____ ________ _________.
____ __________ ______ ___ ___.
________ ____ __________ ____ _______ ________ ____ __________.
__________ _______ __________ ___ _____ ________.
________ ________ ________ ______ __________ _________ _________.
_____ _____ _____ __________ _______ __________.
________ ____ ___ _________ ________ _______.
______ _______ ___ ___ __________ ____ _______ _______ ___ _______.
___ ____ ____ _________ ____ ________ ____ ______ ________ __________ ________ ___.
________ ____ _______ ______ _______ ________ _________ __________ ___ ______ ____ ____.
__________ ___ ___ _______ __________ ___.
___ _______ _____ __________ __________ _________ ___.
________ __________ _____ ____ ___ ________ __________ ____ _________ _____ __________.
__________ ________ ____ ________ ____ ______ ______ ___ ______ _________ _____.
________ __________ _____ __________ _____ ________.
________ ________ ___ ___ ___ ________.
____ ___ _______ ___.
Get Full Answer on WhatsApp
Graph Colouring Problem
Consider the following Graph:
Figure 1: Graph for Problem 3(a) and 3(b)
a) Write the Kruskal’s algorithm and Prim’s algorithm to find the minimum cost
spanning tree of the graph given in Figure 1. Show all the steps of computation.
Also, compute the time complexity of both the algorithms.
b) In the Figure 1, find the shortest path from the vertex ‘a’ using Dijkstra’s shortest
path algorithm. Show all the steps of computation. Also, find the time complexity
of the algorithm.
c) What is dynamic programming? What is the principle of Optimality? Use the
dynamic programming approach to find the optimal sequence of chain
multiplication of the following matrices:
| Matrix | Dimension |
| A1 | 5 × 10 |
| A2 | 10 × 20 |
| A3 | 20 × 15 |
| A4 | 15 × 8 |
| A5 | 8 × 10 |
Explain binary exponentiation for computing the value Write the right-to left binary exponentiation algorithm and show its working for the exponentiation
Also, find the worst-case complexity of this algorithm.
Differentiate between Polynomial-time and exponential-time algorithms. Give an example of one problem each for these two running times.
State and explain the theorems for computing the bounds O, Ω and Θ. Apply these theorem to find the O-notation, Ω-notation and Θ-notation for the function:
Expalin the Partition procedure of the Quick Sort algorithm. Use this procedure and quick sort algorithm to sort the following array of size 8: [12, 9, 17, 15, 23, 19, 16, 24]. Compute the worst case and best case complexity of Quick sort algorithm
Write and explain the linear search algorithm and discuss its best and worstcase time complexity. Show the working of the linear search algorithm for the data: 12, 11, 3, 9, 15, 20, 18, 19, 13, 8, 2, 1, 16.