UNIT-V.pptx-big data notes-ccs334anna university syllabus

big data notes

1. UNIT-V NP-COMPLETE AND APPROXIMATION ALGORITHM

2. SYLLABUS Tractable and intractable problems: Polynomial time algorithms – Venn diagram representation - NP- algorithms - NP-hardness and NP-completeness – Bin Packing problem - Problem reduction: TSP – 3- CNF problem. Approximation Algorithms: TSP - Randomized Algorithms: concept and application - primality testing - randomized quick sort - Finding kth smallest number

3. Tractable and intractable problems Tractable problems: the class P The class of algorithms whose time-demand was described by a polynomial function. Such problems are said to be tractable and in the class PTIME. A problem is in P if it admits an algorithm with worst-case time-demand in O ( n^k ) for some integer k. However there are some problems for which it is known that there are no algorithms which can solve them in polynomial time, these are referred to as provably intractable and as being in the class EXPTIME (exponential time) or worse. For these problems, it has been shown that the lower bound on the time-demand of any possible algorithm to solve them is a function that grows unreasonably fast. Intractable problems: the class EXPTIME and beyond A problem is in the class EXPTIME if all algorithms to solve it have a worst-case time demand which is in O (2^p(n)) for some polynomial p(n)

4. Problems that can be solved in reasonable time called Tractable. OR  A problem that is solvable by a polynomial-time algorithm.  Here are examples of tractable problems (ones with known polynomial-time algorithms): 1 . Searching an unordered list 2 . Searching an ordered list 3 . Sorting a list 4 . Multiplication of integers 5 . Finding a minimum spanning tree in a graph

5. Problems that “can be” solved but the amount of time it takes to solve is too large. 2. A problem that cannot be solved by a polynomial-time algorithm. 3. Can be solved in reasonable time only for small inputs. Or, can not be solved at all. 4. As their input grows large, we are unable to solve them in reasonable time. o Eg : TSP Polynomial functions : Any function that is O(n k ), for some constant k.  E.g. O(1), O(log n), O(n), O(n × log n), O(n2 ), O(n3 ) Exponential functions : The remaining functions.  E.g. O(2n ), O(n!), O(n n ) It Can be classified in various categories based on their degree of difficulty, e.g.,  P  NP  NP-complete  NP-hard

6. polynomial time An algorithm is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is  for some nonnegative integer , where  is the complexity of the input. Polynomial-time algorithms are said to be "fast." Most familiar mathematical operations such as addition, subtraction, multiplication, and division, as well as computing square roots, powers, and logarithms, can be performed in polynomial time . Computing the digits of most interesting mathematical constants, including  and , can also be done in polynomial time . Venn Diagram Definition A Venn diagram is a graphical representation used to illustrate the relationships between different sets. It consists of overlapping circles, each representing a set. The points where the circles overlap indicate the elements that are common to the sets, while the areas of the circles that do not overlap represent elements that are unique to their respective sets.

7. Benefits of Venn Diagrams Venn diagram is used for the classification of data belonging to the same category but different sub-categories. The comparison of the different data becomes easier through the Venn diagram, as well as the relationship between the data. Grouping the information and finding similarities and differences among them becomes easy. The different unknown parameters can be easily understood and found with the help of Venn diagrams . Venn Diagram Examples Venn diagrams are highly useful in solving problems of sets and other problems. Venn diagrams are useful in representing the data in picture form. Let’s learn more about the Venn diagram through an example, Example: Take a set A representing even numbers up to 10 and another set B representing natural numbers less than 5 then their interaction is represented using the Venn diagram.

8. Terms Related to Venn Diagram The concept of the Venn diagram is very useful for solving a variety of problems in Mathematics and others. To understand more about it let’s learn some important terms related to it. Universal Set Universal Set  is a large set that contains all the sets which we are considering in a particular situation. For example, suppose we are considering the set of Honda cars in a society say set A, and let set B is the group of Red car in the same society then the set of all the cars in that society is the universal set as it contains the values of both the sets, set A and set B in consideration.

9. Subset Subset is actually a set of values that is contained inside another set i.e. we can say that set B is the subset of set A if all the values of set B are contained in set A. For example, if we take N as the set of all the  natural numbers  and W as the set of all  whole numbers  then, N = Set of all Natural Numbers W = set of all Whole Numbers We can say that N is a subset of W as all the values of set N are contained in set W i.e.,N ⊆ W We use Venn diagrams to easily represent a subset of a set. The images discussing the subset of a set are given below ,

10. Venn Diagram Symbols In order to draw a Venn diagram, first, understand the type of symbols used in sets. Sets can be easily represented on the Venn diagram and the parameters are easily taken out from the diagram itself. We use various types of symbols in drawing Venn diagrams, some of the most important types of symbols used in drawing Venn diagrams are, Venn Diagram Symbols Name of the Symbol Description ∪ Union Symbol The union symbol is used for taking the union of two or more sets. ∩ Intersection Symbol The intersection symbol is used for taking the intersection of two or more sets. A’ or A c Compliment Symbol The complement symbol is used for taking the complement of a set.

11. NP-algorithm NP (Nondeterministic Polynomial Time) Definition: NP is a class of decision problems for which a given solution can be verified as correct or incorrect in polynomial time. This means that if we are given a "certificate" or "proof" of a solution, we can check whether this solution is correct within polynomial time. NP-Complete Problems Definition: A problem is NP-complete if it is in NP and every other problem in NP can be reduced to it in polynomial time. If a polynomial-time algorithm exists for any NP-complete problem, then polynomial-time algorithms exist for all problems in NP (which would imply P = NP).

12. Bin Packing Problem In case of given m elements of different weights and bins each of capacity C, assign each element to a bin so that number of total implemented bins is minimized. Assumption should be that all elements have weights less than bin capacity . Applications Placing data on multiple disks. Loading of containers like trucks.

13. Input: weight[] = {4, 1, 8, 1, 4, 2} Bin Capacity c = 10 Output : 2 We require at least 2 bins to accommodate all elements First bin consists {4, 4, 2} and second bin {8, 2 } Lower Bound We can always calculate a lower bound on minimum number of bins required using ceil() function. The lower bound can be given below − Bins with minimum number >= ceil ((Total Weight) / (Bin Capacity)) In the above example, lower bound for first example is “ceil(4 + 1 + 8 + 2 + 4 + 1)/10” = 2 The following approximate algorithms are implemented for this problem.