3-CNF SAT
In the context of the Design and Analysis of Algorithms, 3-CNF SAT refers to a specific case of the Boolean Satisfiability Problem (SAT) known as the 3-SAT problem, where each clause in the Boolean formula is restricted to exactly three literals. Here's a detailed definition:
### 3-CNF SAT Definition
3-CNF SAT (3-Conjunctive Normal Form Satisfiability):
- Problem Statement: Given a Boolean formula _______ _______ ________ ______ ______ ________ _______ _______ _________ __________ ______ _________.
_______ __________ _______ ____ ____ ____.
__________ ____ ________ ____ ________ ____ ____ _________ _____ __________ ________.
________ _____ ______ ________ ______ ___ _________ ______ ________.
_____ _______ ___ _________ __________ _________ ________ ___ __________ ____ ___ ______.
_______ _______ ________ __________ ___ ______ ___ ____.
___ ______ ________ _________ _______ ______ _____ __________ __________ _______ ________.
______ _____ ________ ___ _________ _________ _____ ______ ___ ________ ____.
____ ____ ________ _______ __________ _____ _____ _________ _________.
______ _____ _______ ______ ___ ________ _______ ____ ________ _____ _______ _______.
______ __________ _______ _________ ________ ______ ____ _______ _____ _____.
__________ ____ ______ ______ _____ _________ _____.
_______ __________ _________ ____ __________ _________ ____.
__________ _______ _________ ____ _______ ______ ____ ________.
___ _______ ____ ____ _________.
___ _______ _____ ___ _________ ____ ____ ___ ______.
________ _____ ________ ____ _________ _________ ______ ___ ________ _______ ____ ___.
_________ _________ ________ _______ _______ ____ ____ ___ ________ ______ ______ _____.
_________ _________ _____ ______ _____ ________ _____ ___.
____ ____ ___ ____ ___ _______ _____.
____ _____ __________ __________ ____ _________ ________ ___ _______ ____ ______.
____ ___ _______ __________ _______.
____ ______ ______ _________ ____ _________ _________ ____ ____ _____ _____.
____ ______ ___ __________ ____.
________ ____ _____ ___ _______ ________ _______ __________.
______ ________ _____ ____ ___.
__________ ______ ______ ___ __________ _______ ____ __________ ____.
______ ___ _________ ___ ______ _________ ____ __________ _______.
___ ________.
Get Full Answer on WhatsApp
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.
3-CNF SAT
Define P and NP class of Problems with the help of examples. How are P class of problem different from NP class of Problems.
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 |
What is a recurrence relation? Solve the following recurrence relations using the Master’s method
a.
b.
Using Horner's rule, evaluate the polynomial p(x)= 2x5 -5x4 -3x2+15 at x=2. Analyse the computation time required for polynomial evaluation using Horner’s rule against the Brute force method.