Why? A central concept in Computer Science. Algorithms are ubiquitous.


 Abel Day
 6 years ago
 Views:
Transcription
1 Analysis of Algorithms: A Brief Introduction Why? A central concept in Computer Science. Algorithms are ubiquitous. Using the Internet (sending , transferring files, use of search engines, online shopping). Document preparation/processing. Scheduling flights. Manufacturing. Medicine. 1
2 Algorithm: A well defined computational procedure to solve a problem. Focus: Combinatorial problems (i.e., problems whose solution space is discrete). Problem Specification: Input to the problem. Output to be produced. Problem 1: Finding the maximum value. Input: An array A[1.. n] of n integers. Output: The maximum value in the input. 2
3 Problem 2: Sorting into nondecreasing order. Input: An array A[1.. n] of n integers. Output: A permutation of the array elements so that A[1] A[2]... A[n]. Problem 3: Zero Sum. Input: An array A[1.. n] of n integers. (The integer values may be positive, negative or zero.) Output: True if the array has two elements A[i] and A[j] (i j) such that the sum A[i] + A[j] is zero; False otherwise. Note: Zero Sum is a decision problem. 3
4 Definition: Given an array A[1.. n], a block is a subarray A[i.. j], where 1 i j n. Note: Each element A[i] is a block by itself. Problem 4: Maximum Block Sum. Input: An array A[1.. n] of n integers. (The integer values may be positive, negative or zero.) Output: The maximum value among the sums of all the blocks of A. Note: Maximum Block Sum is an optimization problem. 4
5 Problem 5: Shortest Path. Input: A network G consisting of nodes and edges, with each edge having a length (nonnegative number); two nodes u and v. Output: A shortest path between u and v in G. Example: a 4 b 5 7 c u 3 3 d 3 v e 2 f Note: Shortest Path is also an optimization problem. 5
6 Boolean Satisfiability Problem: Terminology and Notation: Boolean variable x: Takes on a value from {True, False}. Complement of x is denoted by x. (The symbols x and x are called literals.) Boolean operators (connectives): e.g. And (denoted by ), Or (denoted by ). A Boolean formula is constructed using literals, connectives and parentheses. 6
7 Example: The following formula F uses three Boolean variables x 1, x 2 and x 3. F = (x 1 x 2 x 3 ) (x 2 x 3 ) (x 1 x 3 ) (a) Let x 1 = True, x 2 = True and x 3 = True. assignment, F evaluates to False. For this (b) Let x 1 = True, x 2 = True and x 3 = False. For this assignment, F evaluates to True. Definition: A Boolean formula F is satisfiable if there is at least one assignment of values to the variables in F for which F evaluates to True. 7
8 Examples: Formula F = (x 1 x 2 x 3 ) (x 2 x 3 ) (x 1 x 3 ) is satisfiable. (One satisfying assignment for F is x 1 = True, x 2 = True and x 3 = False.) Formula F 1 defined by F 1 = (x 1 ) (x 2 ) (x 1 x 2 ) is not satisfiable. Problem 6: Boolean Satisfiability (SAT) Input: A formula F constructed using Boolean variables x 1, x 2,..., x n, their complements and Boolean operators. Output: True if F satisfiable and False otherwise. Note: SAT is also a decision problem. 8
9 Exercises: 1. Find the number of satisfying assignments for the formula F given on page Construct a formula F 2 using three variables x 1, x 2 and x 3 such that F 2 has exactly one satisfying assignment. Indicate the satisfying assignment. 3. Construct a Boolean formula F 3 using two variables x 1 and x 2 such that F 3 evaluates to True for every assignment. 9
10 An Algorithm for Finding the Maximum: Input: Array A[1.. n] of integers. Pseudocode: 1. Max = A[1] 2. for i = 2 to n do if (A[i] > 3. Print Max Max) then Max = A[i] Correctness of an Algorithm: Algorithm must halt for every input instance. Must produce the correct output for every input instance. 10
11 Analyzing an Algorithm: Estimating the resources (e.g. running time, memory) needed in a machine independent manner. Useful in comparing candidate algorithms for a problem. Computational Model: Each primitive operation (e.g. arithmetic operation, comparison, assignment) takes one unit of time. Running time for a specific input: Number of primitive operations executed by the algorithm for that input (expressed as a function of the input size ). 11
12 Running Time of an Algorithm: The longest running time for any input of a certain size. Also called worstcase time (or time complexity). Input Size: Depends on the problem. Examples: (a) Sorting: Number (n) of input values. (b) Graph problems: Number of nodes + Number of edges. (c) SAT problem: Number of literals + Number of operators + Number of parentheses. 12
13 Running Time Analysis Example I: Pseudocode: 1. Max = A[1] 2. for i = 2 to n do if (A[i] > Max) then Max = A[i] 3. Print Max Analysis: Input size = n. Step 1: No. of operations = 1. Step 2: The for loop executes n 1 times. Each time through the loop, we have: 13
14 (a) Two operations (comparison and increment) on i. (b) At most two operations (a comparison and an assignment) for the if statement. So, the total number of operations over all the iterations of the loop is at most 4(n 1). Step 3: No. of operations = 1. So, the total number of operations carried out by the algorithm is at most 1 + 4(n 1) + 1 = 4n 2. Running Time Analysis Example 2: Zero Sum: Input: Array A[1.. n] containing n integers. 14
15 Pseudocode: 1. for i = 1 to n 1 do 1.1 for j = i + 1 to n do if (A[i] + A[j] = 0) then Print True and stop. 2. Print False. Analysis: Step 1: The for loop runs n 1 times. For each iteration of this loop: (a) The for loop in Step 1.1 runs n i times. (b) During each iteration of this inner for loop, at most 6 operations are carried out: 15
16 Comparison and increment for j, the sum A[i] + A[j] and its comparison with 0 and print and stop operations. (c) So, the total number of operations carried out during all iterations of the inner for loop is at most 6(n i). So, the total number of operations carried out during all the iterations of the outer for loop is n 1 6(n i) = 3n(n 1). Step 2: No. of operations = 1. Conclusion: i=1 The total number of operations carried out by the algorithm is at most 3n(n 1)
17 Disadvantages: This type of detailed analysis is too tedious. The exact number of operations is not too insightful. Simplified Representation: Order or BigO Notation. Running time as the input size becomes large (also called asymptotic running time). Facilitates the comparison of algorithms for a problem. Basic Ideas: Use only the most dominant term in the expression for the number of operations. Suppress additive and multiplicative constants. 17
18 Examples: The number of steps used by the algorithm for finding the maximum is at most 4n 2. This is expressed as O(n). So, the running time of the maximum finding algorithm is O(n). The number of steps used by the algorithm for the Zero Sum problem is at most 3n(n 1) + 1. So, the running time of the algorithm for the Zero Sum problem is O(n 2 ). Additional Examples: (a) Let f(n) = n n Then, f(n) = O(n 3 ). (b) Let g(n) = 2n log 2 n + 31n Then, g(n) = O(n log 2 n). Note: O(1) denotes a constant. 18
19 Exercises: n 1. Find the bigo representation for i=1 (2i2 ). 2. Suppose f(n) = 8n 3 + 2n 2 17 and g(n) = n 5 + n Find the bigo representations for f(n) + g(n) and f(n) g(n). Algorithms for the Maximum Block Sum Problem: Input: An array A[1.. n] of integers. Idea behind Algorithm I: Consider each block of A and compute its sum. Output the largest sum found. 19
20 Pseudocode for Algorithm I: 1. MaxSum = A[1] 2. for i = 1 to n do 2.1 for j = i to n do temp = FindSum(A, i, j) if (temp > MaxSum) then MaxSum = temp 3. Print MaxSum function FindSum(A, i, j) 1. sum = 0 2. for k = i to j do sum = sum + A[k] 3. return sum 20
21 Analysis: Each call to FindSum takes O(n) time. Each iteration of the loop in Step 2.1 runs in O(n) time (since the dominant time is due to the call to FindSum). Since the loop itself runs at most n times, the running time of the loop in Step 2.1 is O(n 2 ). The loop in Step 2 runs n times. Each iteration of this loop executes the loop in Step 2.1. Since the latter takes O(n 2 ) time, the time to complete Step 2 is O(n n 2 ) = O(n 3 ). Steps 1 and 3 take O(1) time. So, the overall running time is O(n 3 ). 21
22 Algorithm II for Maximum Block Sum Idea: For each i, (1 i n), there are n i+1 blocks whose starting point is A[i]. For each such block, Algorithm I computes the sum in O(n) time (using the FindSum function). So, the time used to compute the sums for all the blocks with starting point A[i] is O(n 2 ). It is possible to compute the sums of all the blocks that start at A[i] in O(n) time as follows. Let S i,j denote the sum of the block A[i.. j]. S i,i = A[i] S i,i+1 = S i,i + A[i + 1] S i,i+2 = S i,i+1 + A[i + 2]. 22
23 S i,n = S i,n 1 + A[n] The resulting algorithm runs in time O(n 2 ). Exercise: Write pseudocode for Algorithm II using the above idea. Verify that the running time of the algorithm is O(n 2 ). Algorithm III for Maximum Block Sum Idea: (a) Observation: A block with the maximum sum ends at A[i] for some i, 1 i n. (b) For each i, compute and store the maximum sum among all blocks that end at A[i]. (c) The largest sum found in (b) is the solution. 23
24 How to carry out Step (b): Use an auxiliary array B[1.. n]; for each i, let B[i] store the maximum sum among the blocks that end at A[i]. Note that B[1] = A[1]. For any i 2, B[i] = B[i 1] + A[i] if B[i 1] > 0 = A[i] otherwise. Example: To be presented in class. 24
25 Pseudocode for Algorithm III: 1. B[1] = A[1] 2. for i = 2 to n do if (B[i 1] > 0) then B[i] = B[i 1] + A[i] else B[i] = A[i] 3. Find and print the maximum value in B[1.. n] Running time of Algorithm III: Step 1: O(1) time. Step 2: The loop executes at most n times and each iteration of the loop uses O(1) time. So, the total time for the loop is O(n). 25
26 Step 3: O(n) time. So, the overall running time is O(n). Conclusion: Algorithm III has the best running time for the Maximum Block Sum problem. Definition: An algorithm is efficient if its running time is a polynomial function of the input size. Note: Polynomial means that the running time can be expressed as O(n k ) where n is the problem size and k is a constant independent of n. 26
27 Examples: The algorithm for finding the maximum runs in O(n) time. The algorithm for the Zero Sum problem runs in O(n 2 ) time. All the three algorithms for the Maximum Block Sum problem are efficient algorithms. (Their respective running times are O(n 3 ), O(n 2 ) and O(n).) Problems such as Sorting and Shortest Path can also be solved efficiently. Exercise: Several algorithms with running times of O(n log 2 n) are known for the sorting problem. Also, given a sorted array A[1.. n] and a value q, binary search can be used to determine whether or not A contains the value q in O(log 2 n) time. Use these facts to devise an O(n log 2 n) algorithm for the Zero Sum problem. 27
28 NPComplete Problems: Terminology: The class P contains all the problems for which a solution can be found in polynomial time. The class NP contains all the problems for which a given solution can be verified in polynomial time. Notes: 1. NP denotes Nondeterministic Polynomial. 2. For mathematical convenience, the class NP is restricted to decision problems. 28
29 Example: SAT is in NP. Given an assignment of values to the Boolean variables of a formula F, we can evaluate F and thus determine whether the given assignment satisfies the formula in polynomial time. However, we don t know how to find a satisfying assignment in polynomial time. Note: Every problem in P is also in NP. (Thus, P NP.) Other Problems in NP: Problem 7: Clique Input: A set S of n people, a set P of pairs of people from S who know each other and an integer K n. Question: Is there a subset S of S containing at least K people such that each person in S knows every other person in S? 29
30 Problem 8: Subset Sum Input: A set S of n integers and another integer Q. Question: Is there a subset S of S such that the sum of the integers in S is equal to Q? Problem 9: Longest Path Input: A graph G with vertex set V, edge set E, two vertices u and v and an integer K V. Question: Is there a path of length at least K between u and v? NPComplete Problems: The hardest problems in NP. 30
31 These problems are equivalent in the following sense: (a) If any one of the NPcomplete problems can be solved in polynomial time, then all of them can be solved in polynomial time. (If this happens, then P = NP.) (b) If we can show that there is no polynomial algorithm for any one of the NPcomplete problems, then none of them can be solved in polynomial time. (If this happens, then P NP.) The problems SAT, Clique, Subset Sum and Longest Path defined above are known to be NPcomplete. Thousands of problems that arise in practical applications are known to be NPcomplete. P? = NP is a major open question. 31
Lecture 7: NPComplete Problems
IAS/PCMI Summer Session 2000 Clay Mathematics Undergraduate Program Basic Course on Computational Complexity Lecture 7: NPComplete Problems David Mix Barrington and Alexis Maciel July 25, 2000 1. Circuit
More informationNPCompleteness. CptS 223 Advanced Data Structures. Larry Holder School of Electrical Engineering and Computer Science Washington State University
NPCompleteness CptS 223 Advanced Data Structures Larry Holder School of Electrical Engineering and Computer Science Washington State University 1 Hard Graph Problems Hard means no known solutions with
More informationDiscuss the size of the instance for the minimum spanning tree problem.
3.1 Algorithm complexity The algorithms A, B are given. The former has complexity O(n 2 ), the latter O(2 n ), where n is the size of the instance. Let n A 0 be the size of the largest instance that can
More informationOutline. NPcompleteness. When is a problem easy? When is a problem hard? Today. Euler Circuits
Outline NPcompleteness Examples of Easy vs. Hard problems Euler circuit vs. Hamiltonian circuit Shortest Path vs. Longest Path 2pairs sum vs. general Subset Sum Reducing one problem to another Clique
More informationPage 1. CSCE 310J Data Structures & Algorithms. CSCE 310J Data Structures & Algorithms. P, NP, and NPComplete. PolynomialTime Algorithms
CSCE 310J Data Structures & Algorithms P, NP, and NPComplete Dr. Steve Goddard goddard@cse.unl.edu CSCE 310J Data Structures & Algorithms Giving credit where credit is due:» Most of the lecture notes
More informationIntroduction to Algorithms. Part 3: P, NP Hard Problems
Introduction to Algorithms Part 3: P, NP Hard Problems 1) Polynomial Time: P and NP 2) NPCompleteness 3) Dealing with Hard Problems 4) Lower Bounds 5) Books c Wayne Goddard, Clemson University, 2004 Chapter
More informationData Structures and Algorithms Written Examination
Data Structures and Algorithms Written Examination 22 February 2013 FIRST NAME STUDENT NUMBER LAST NAME SIGNATURE Instructions for students: Write First Name, Last Name, Student Number and Signature where
More informationReductions & NPcompleteness as part of Foundations of Computer Science undergraduate course
Reductions & NPcompleteness as part of Foundations of Computer Science undergraduate course Alex Angelopoulos, NTUA January 22, 2015 Outline Alex Angelopoulos (NTUA) FoCS: Reductions & NPcompleteness
More information1. Nondeterministically guess a solution (called a certificate) 2. Check whether the solution solves the problem (called verification)
Some N P problems Computer scientists have studied many N P problems, that is, problems that can be solved nondeterministically in polynomial time. Traditionally complexity question are studied as languages:
More informationAnalysis of Binary Search algorithm and Selection Sort algorithm
Analysis of Binary Search algorithm and Selection Sort algorithm In this section we shall take up two representative problems in computer science, work out the algorithms based on the best strategy to
More information2. (a) Explain the strassen s matrix multiplication. (b) Write deletion algorithm, of Binary search tree. [8+8]
Code No: R05220502 Set No. 1 1. (a) Describe the performance analysis in detail. (b) Show that f 1 (n)+f 2 (n) = 0(max(g 1 (n), g 2 (n)) where f 1 (n) = 0(g 1 (n)) and f 2 (n) = 0(g 2 (n)). [8+8] 2. (a)
More informationComplexity Theory. IE 661: Scheduling Theory Fall 2003 Satyaki Ghosh Dastidar
Complexity Theory IE 661: Scheduling Theory Fall 2003 Satyaki Ghosh Dastidar Outline Goals Computation of Problems Concepts and Definitions Complexity Classes and Problems Polynomial Time Reductions Examples
More informationCSC 373: Algorithm Design and Analysis Lecture 16
CSC 373: Algorithm Design and Analysis Lecture 16 Allan Borodin February 25, 2013 Some materials are from Stephen Cook s IIT talk and Keven Wayne s slides. 1 / 17 Announcements and Outline Announcements
More informationApproximation Algorithms
Approximation Algorithms or: How I Learned to Stop Worrying and Deal with NPCompleteness Ong Jit Sheng, Jonathan (A0073924B) March, 2012 Overview Key Results (I) General techniques: Greedy algorithms
More informationComputer Algorithms. NPComplete Problems. CISC 4080 Yanjun Li
Computer Algorithms NPComplete Problems NPcompleteness The quest for efficient algorithms is about finding clever ways to bypass the process of exhaustive search, using clues from the input in order
More informationEfficiency of algorithms. Algorithms. Efficiency of algorithms. Binary search and linear search. Best, worst and average case.
Algorithms Efficiency of algorithms Computational resources: time and space Best, worst and average case performance How to compare algorithms: machineindependent measure of efficiency Growth rate Complexity
More informationCost Model: Work, Span and Parallelism. 1 The RAM model for sequential computation:
CSE341T 08/31/2015 Lecture 3 Cost Model: Work, Span and Parallelism In this lecture, we will look at how one analyze a parallel program written using Cilk Plus. When we analyze the cost of an algorithm
More informationTutorial 8. NPComplete Problems
Tutorial 8 NPComplete Problems Decision Problem Statement of a decision problem Part 1: instance description defining the input Part 2: question stating the actual yesorno question A decision problem
More informationChapter 11. 11.1 Load Balancing. Approximation Algorithms. Load Balancing. Load Balancing on 2 Machines. Load Balancing: Greedy Scheduling
Approximation Algorithms Chapter Approximation Algorithms Q. Suppose I need to solve an NPhard problem. What should I do? A. Theory says you're unlikely to find a polytime algorithm. Must sacrifice one
More informationIntroduction to Logic in Computer Science: Autumn 2006
Introduction to Logic in Computer Science: Autumn 2006 Ulle Endriss Institute for Logic, Language and Computation University of Amsterdam Ulle Endriss 1 Plan for Today Now that we have a basic understanding
More informationSIMS 255 Foundations of Software Design. Complexity and NPcompleteness
SIMS 255 Foundations of Software Design Complexity and NPcompleteness Matt Welsh November 29, 2001 mdw@cs.berkeley.edu 1 Outline Complexity of algorithms Space and time complexity ``Big O'' notation Complexity
More informationIn mathematics, it is often important to get a handle on the error term of an approximation. For instance, people will write
Big O notation (with a capital letter O, not a zero), also called Landau's symbol, is a symbolism used in complexity theory, computer science, and mathematics to describe the asymptotic behavior of functions.
More informationTheoretical Computer Science (Bridging Course) Complexity
Theoretical Computer Science (Bridging Course) Complexity Gian Diego Tipaldi A scenario You are a programmer working for a logistics company Your boss asks you to implement a program that optimizes the
More informationChapter. NPCompleteness. Contents
Chapter 13 NPCompleteness Contents 13.1 P and NP......................... 593 13.1.1 Defining the Complexity Classes P and NP...594 13.1.2 Some Interesting Problems in NP.......... 597 13.2 NPCompleteness....................
More informationIntroduction to computer science
Introduction to computer science Michael A. Nielsen University of Queensland Goals: 1. Introduce the notion of the computational complexity of a problem, and define the major computational complexity classes.
More informationThe Classes P and NP
The Classes P and NP We now shift gears slightly and restrict our attention to the examination of two families of problems which are very important to computer scientists. These families constitute the
More information! Solve problem to optimality. ! Solve problem in polytime. ! Solve arbitrary instances of the problem. !approximation algorithm.
Approximation Algorithms Chapter Approximation Algorithms Q Suppose I need to solve an NPhard problem What should I do? A Theory says you're unlikely to find a polytime algorithm Must sacrifice one of
More informationP versus NP, and More
1 P versus NP, and More Great Ideas in Theoretical Computer Science Saarland University, Summer 2014 If you have tried to solve a crossword puzzle, you know that it is much harder to solve it than to verify
More informationCatalan Numbers. Thomas A. Dowling, Department of Mathematics, Ohio State Uni versity.
7 Catalan Numbers Thomas A. Dowling, Department of Mathematics, Ohio State Uni Author: versity. Prerequisites: The prerequisites for this chapter are recursive definitions, basic counting principles,
More informationWelcome to... Problem Analysis and Complexity Theory 716.054, 3 VU
Welcome to... Problem Analysis and Complexity Theory 716.054, 3 VU Birgit Vogtenhuber Institute for Software Technology email: bvogt@ist.tugraz.at office hour: Tuesday 10:30 11:30 slides: http://www.ist.tugraz.at/pact.html
More informationNear Optimal Solutions
Near Optimal Solutions Many important optimization problems are lacking efficient solutions. NPComplete problems unlikely to have polynomial time solutions. Good heuristics important for such problems.
More informationOn the Relationship between Classes P and NP
Journal of Computer Science 8 (7): 10361040, 2012 ISSN 15493636 2012 Science Publications On the Relationship between Classes P and NP Anatoly D. Plotnikov Department of Computer Systems and Networks,
More informationChapter 3. if 2 a i then location: = i. Page 40
Chapter 3 1. Describe an algorithm that takes a list of n integers a 1,a 2,,a n and finds the number of integers each greater than five in the list. Ans: procedure greaterthanfive(a 1,,a n : integers)
More informationMapReduce and Distributed Data Analysis. Sergei Vassilvitskii Google Research
MapReduce and Distributed Data Analysis Google Research 1 Dealing With Massive Data 2 2 Dealing With Massive Data Polynomial Memory Sublinear RAM Sketches External Memory Property Testing 3 3 Dealing With
More informationAlgorithm Design and Analysis
Algorithm Design and Analysis LECTURE 27 Approximation Algorithms Load Balancing Weighted Vertex Cover Reminder: Fill out SRTEs online Don t forget to click submit Sofya Raskhodnikova 12/6/2011 S. Raskhodnikova;
More informationNPcomplete? NPhard? Some Foundations of Complexity. Prof. Sven Hartmann Clausthal University of Technology Department of Informatics
NPcomplete? NPhard? Some Foundations of Complexity Prof. Sven Hartmann Clausthal University of Technology Department of Informatics Tractability of Problems Some problems are undecidable: no computer
More informationWarshall s Algorithm: Transitive Closure
CS 0 Theory of Algorithms / CS 68 Algorithms in Bioinformaticsi Dynamic Programming Part II. Warshall s Algorithm: Transitive Closure Computes the transitive closure of a relation (Alternatively: all paths
More informationA simple algorithm with no simple verication
A simple algorithm with no simple verication Laszlo Csirmaz Central European University Abstract The correctness of a simple sorting algorithm is resented, which algorithm is \evidently wrong" at the rst
More informationThe Traveling Beams Optical Solutions for Bounded NPComplete Problems
The Traveling Beams Optical Solutions for Bounded NPComplete Problems Shlomi Dolev, Hen Fitoussi Abstract Architectures for optical processors designed to solve bounded instances of NPComplete problems
More informationSolutions to Homework 6
Solutions to Homework 6 Debasish Das EECS Department, Northwestern University ddas@northwestern.edu 1 Problem 5.24 We want to find light spanning trees with certain special properties. Given is one example
More informationCSE373: Data Structures and Algorithms Lecture 3: Math Review; Algorithm Analysis. Linda Shapiro Winter 2015
CSE373: Data Structures and Algorithms Lecture 3: Math Review; Algorithm Analysis Linda Shapiro Today Registration should be done. Homework 1 due 11:59 pm next Wednesday, January 14 Review math essential
More informationAnalysis of Computer Algorithms. Algorithm. Algorithm, Data Structure, Program
Analysis of Computer Algorithms Hiroaki Kobayashi Input Algorithm Output 12/13/02 Algorithm Theory 1 Algorithm, Data Structure, Program Algorithm Welldefined, a finite stepbystep computational procedure
More informationApplied Algorithm Design Lecture 5
Applied Algorithm Design Lecture 5 Pietro Michiardi Eurecom Pietro Michiardi (Eurecom) Applied Algorithm Design Lecture 5 1 / 86 Approximation Algorithms Pietro Michiardi (Eurecom) Applied Algorithm Design
More informationWhy Study NP hardness. NP Hardness/Completeness Overview. P and NP. Scaling 9/3/13. Ron Parr CPS 570. NP hardness is not an AI topic
Why Study NP hardness NP Hardness/Completeness Overview Ron Parr CPS 570 NP hardness is not an AI topic It s important for all computer scienhsts Understanding it will deepen your understanding of AI
More informationCAD Algorithms. P and NP
CAD Algorithms The Classes P and NP Mohammad Tehranipoor ECE Department 6 September 2010 1 P and NP P and NP are two families of problems. P is a class which contains all of the problems we solve using
More informationOne last point: we started off this book by introducing another famously hard search problem:
S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani 261 Factoring One last point: we started off this book by introducing another famously hard search problem: FACTORING, the task of finding all prime factors
More information! Solve problem to optimality. ! Solve problem in polytime. ! Solve arbitrary instances of the problem. #approximation algorithm.
Approximation Algorithms 11 Approximation Algorithms Q Suppose I need to solve an NPhard problem What should I do? A Theory says you're unlikely to find a polytime algorithm Must sacrifice one of three
More informationSingle machine parallel batch scheduling with unbounded capacity
Workshop on Combinatorics and Graph Theory 21th, April, 2006 Nankai University Single machine parallel batch scheduling with unbounded capacity Yuan Jinjiang Department of mathematics, Zhengzhou University
More informationData Structures. Algorithm Performance and Big O Analysis
Data Structures Algorithm Performance and Big O Analysis What s an Algorithm? a clearly specified set of instructions to be followed to solve a problem. In essence: A computer program. In detail: Defined
More informationSYSM 6304: Risk and Decision Analysis Lecture 5: Methods of Risk Analysis
SYSM 6304: Risk and Decision Analysis Lecture 5: Methods of Risk Analysis M. Vidyasagar Cecil & Ida Green Chair The University of Texas at Dallas Email: M.Vidyasagar@utdallas.edu October 17, 2015 Outline
More informationSolution of Linear Systems
Chapter 3 Solution of Linear Systems In this chapter we study algorithms for possibly the most commonly occurring problem in scientific computing, the solution of linear systems of equations. We start
More informationCSC 180 H1F Algorithm Runtime Analysis Lecture Notes Fall 2015
1 Introduction These notes introduce basic runtime analysis of algorithms. We would like to be able to tell if a given algorithm is timeefficient, and to be able to compare different algorithms. 2 Linear
More informationBinary Heaps * * * * * * * / / \ / \ / \ / \ / \ * * * * * * * * * * * / / \ / \ / / \ / \ * * * * * * * * * *
Binary Heaps A binary heap is another data structure. It implements a priority queue. Priority Queue has the following operations: isempty add (with priority) remove (highest priority) peek (at highest
More informationReminder: Complexity (1) Parallel Complexity Theory. Reminder: Complexity (2) Complexitynew
Reminder: Complexity (1) Parallel Complexity Theory Lecture 6 Number of steps or memory units required to compute some result In terms of input size Using a single processor O(1) says that regardless of
More informationReminder: Complexity (1) Parallel Complexity Theory. Reminder: Complexity (2) Complexitynew GAP (2) Graph Accessibility Problem (GAP) (1)
Reminder: Complexity (1) Parallel Complexity Theory Lecture 6 Number of steps or memory units required to compute some result In terms of input size Using a single processor O(1) says that regardless of
More informationMathematics for Algorithm and System Analysis
Mathematics for Algorithm and System Analysis for students of computer and computational science Edward A. Bender S. Gill Williamson c Edward A. Bender & S. Gill Williamson 2005. All rights reserved. Preface
More informationInteger Factorization using the Quadratic Sieve
Integer Factorization using the Quadratic Sieve Chad Seibert* Division of Science and Mathematics University of Minnesota, Morris Morris, MN 56567 seib0060@morris.umn.edu March 16, 2011 Abstract We give
More informationMathematical Induction. Lecture 1011
Mathematical Induction Lecture 1011 Menu Mathematical Induction Strong Induction Recursive Definitions Structural Induction Climbing an Infinite Ladder Suppose we have an infinite ladder: 1. We can reach
More informationOHJ2306 Introduction to Theoretical Computer Science, Fall 2012 8.11.2012
276 The P vs. NP problem is a major unsolved problem in computer science It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute to carry a $ 1,000,000 prize for the
More informationProblem Set 7 Solutions
8 8 Introduction to Algorithms May 7, 2004 Massachusetts Institute of Technology 6.046J/18.410J Professors Erik Demaine and Shafi Goldwasser Handout 25 Problem Set 7 Solutions This problem set is due in
More informationBicolored Shortest Paths in Graphs with Applications to Network Overlay Design
Bicolored Shortest Paths in Graphs with Applications to Network Overlay Design Hongsik Choi and HyeongAh Choi Department of Electrical Engineering and Computer Science George Washington University Washington,
More informationNPcompleteness and the real world. NP completeness. NPcompleteness and the real world (2) NPcompleteness and the real world
completeness and the real world completeness Course Discrete Biological Models (Modelli Biologici Discreti) Zsuzsanna Lipták Imagine you are working for a biotech company. One day your boss calls you
More informationCloud Computing is NPComplete
Working Paper, February 2, 20 Joe Weinman Permalink: http://www.joeweinman.com/resources/joe_weinman_cloud_computing_is_npcomplete.pdf Abstract Cloud computing is a rapidly emerging paradigm for computing,
More informationCS/COE 1501 http://cs.pitt.edu/~bill/1501/
CS/COE 1501 http://cs.pitt.edu/~bill/1501/ Lecture 01 Course Introduction Metanotes These notes are intended for use by students in CS1501 at the University of Pittsburgh. They are provided free of charge
More informationSection IV.1: Recursive Algorithms and Recursion Trees
Section IV.1: Recursive Algorithms and Recursion Trees Definition IV.1.1: A recursive algorithm is an algorithm that solves a problem by (1) reducing it to an instance of the same problem with smaller
More informationIntroduction to NPCompleteness Written and copyright c by Jie Wang 1
91.502 Foundations of Comuter Science 1 Introduction to Written and coyright c by Jie Wang 1 We use timebounded (deterministic and nondeterministic) Turing machines to study comutational comlexity of
More informationNPCompleteness and Cook s Theorem
NPCompleteness and Cook s Theorem Lecture notes for COM3412 Logic and Computation 15th January 2002 1 NP decision problems The decision problem D L for a formal language L Σ is the computational task:
More informationThe UnionFind Problem Kruskal s algorithm for finding an MST presented us with a problem in datastructure design. As we looked at each edge,
The UnionFind Problem Kruskal s algorithm for finding an MST presented us with a problem in datastructure design. As we looked at each edge, cheapest first, we had to determine whether its two endpoints
More informationComplexity Classes P and NP
Complexity Classes P and NP MATH 3220 Supplemental Presentation by John Aleshunas The cure for boredom is curiosity. There is no cure for curiosity Dorothy Parker Computational Complexity Theory In computer
More informationScheduling Shop Scheduling. Tim Nieberg
Scheduling Shop Scheduling Tim Nieberg Shop models: General Introduction Remark: Consider non preemptive problems with regular objectives Notation Shop Problems: m machines, n jobs 1,..., n operations
More informationDeterminants can be used to solve a linear system of equations using Cramer s Rule.
2.6.2 Cramer s Rule Determinants can be used to solve a linear system of equations using Cramer s Rule. Cramer s Rule for Two Equations in Two Variables Given the system This system has the unique solution
More informationON THE COMPLEXITY OF THE GAME OF SET. {kamalika,pbg,dratajcz,hoeteck}@cs.berkeley.edu
ON THE COMPLEXITY OF THE GAME OF SET KAMALIKA CHAUDHURI, BRIGHTEN GODFREY, DAVID RATAJCZAK, AND HOETECK WEE {kamalika,pbg,dratajcz,hoeteck}@cs.berkeley.edu ABSTRACT. Set R is a card game played with a
More informationSocial Media Mining. Graph Essentials
Graph Essentials Graph Basics Measures Graph and Essentials Metrics 2 2 Nodes and Edges A network is a graph nodes, actors, or vertices (plural of vertex) Connections, edges or ties Edge Node Measures
More informationNotes on Complexity Theory Last updated: August, 2011. Lecture 1
Notes on Complexity Theory Last updated: August, 2011 Jonathan Katz Lecture 1 1 Turing Machines I assume that most students have encountered Turing machines before. (Students who have not may want to look
More informationLogic in Computer Science: Logic Gates
Logic in Computer Science: Logic Gates Lila Kari The University of Western Ontario Logic in Computer Science: Logic Gates CS2209, Applied Logic for Computer Science 1 / 49 Logic and bit operations Computers
More informationNotes on Complexity Theory Last updated: August, 2011. Lecture 1
Notes on Complexity Theory Last updated: August, 2011 Jonathan Katz Lecture 1 1 Turing Machines I assume that most students have encountered Turing machines before. (Students who have not may want to look
More informationARTICLE IN PRESS. European Journal of Operational Research xxx (2004) xxx xxx. Discrete Optimization. Nan Kong, Andrew J.
A factor 1 European Journal of Operational Research xxx (00) xxx xxx Discrete Optimization approximation algorithm for twostage stochastic matching problems Nan Kong, Andrew J. Schaefer * Department of
More informationTransportation Polytopes: a Twenty year Update
Transportation Polytopes: a Twenty year Update Jesús Antonio De Loera University of California, Davis Based on various papers joint with R. Hemmecke, E.Kim, F. Liu, U. Rothblum, F. Santos, S. Onn, R. Yoshida,
More informationEuler Paths and Euler Circuits
Euler Paths and Euler Circuits An Euler path is a path that uses every edge of a graph exactly once. An Euler circuit is a circuit that uses every edge of a graph exactly once. An Euler path starts and
More informationCPSC 211 Data Structures & Implementations (c) Texas A&M University [ 313]
CPSC 211 Data Structures & Implementations (c) Texas A&M University [ 313] File Structures A file is a collection of data stored on mass storage (e.g., disk or tape) Why on mass storage? too big to fit
More informationGuessing Game: NPComplete?
Guessing Game: NPComplete? 1. LONGESTPATH: Given a graph G = (V, E), does there exists a simple path of length at least k edges? YES 2. SHORTESTPATH: Given a graph G = (V, E), does there exists a simple
More informationEvery tree contains a large induced subgraph with all degrees odd
Every tree contains a large induced subgraph with all degrees odd A.J. Radcliffe Carnegie Mellon University, Pittsburgh, PA A.D. Scott Department of Pure Mathematics and Mathematical Statistics University
More informationChapter 1. Computation theory
Chapter 1. Computation theory In this chapter we will describe computation logic for the machines. This topic is a wide interdisciplinary field, so that the students can work in an interdisciplinary context.
More informationRecursive Algorithms. Recursion. Motivating Example Factorial Recall the factorial function. { 1 if n = 1 n! = n (n 1)! if n > 1
Recursion Slides by Christopher M Bourke Instructor: Berthe Y Choueiry Fall 007 Computer Science & Engineering 35 Introduction to Discrete Mathematics Sections 717 of Rosen cse35@cseunledu Recursive Algorithms
More informationDATA ANALYSIS II. Matrix Algorithms
DATA ANALYSIS II Matrix Algorithms Similarity Matrix Given a dataset D = {x i }, i=1,..,n consisting of n points in R d, let A denote the n n symmetric similarity matrix between the points, given as where
More informationSCORE SETS IN ORIENTED GRAPHS
Applicable Analysis and Discrete Mathematics, 2 (2008), 107 113. Available electronically at http://pefmath.etf.bg.ac.yu SCORE SETS IN ORIENTED GRAPHS S. Pirzada, T. A. Naikoo The score of a vertex v in
More informationCoNP and Function Problems
CoNP and Function Problems conp By definition, conp is the class of problems whose complement is in NP. NP is the class of problems that have succinct certificates. conp is therefore the class of problems
More informationClassification  Examples
Lecture 2 Scheduling 1 Classification  Examples 1 r j C max given: n jobs with processing times p 1,...,p n and release dates r 1,...,r n jobs have to be scheduled without preemption on one machine taking
More informationTHE PROBLEM WORMS (1) WORMS (2) THE PROBLEM OF WORM PROPAGATION/PREVENTION THE MINIMUM VERTEX COVER PROBLEM
1 THE PROBLEM OF WORM PROPAGATION/PREVENTION I.E. THE MINIMUM VERTEX COVER PROBLEM Prof. Tiziana Calamoneri Network Algorithms A.y. 2014/15 2 THE PROBLEM WORMS (1)! A computer worm is a standalone malware
More informationThe Goldberg Rao Algorithm for the Maximum Flow Problem
The Goldberg Rao Algorithm for the Maximum Flow Problem COS 528 class notes October 18, 2006 Scribe: Dávid Papp Main idea: use of the blocking flow paradigm to achieve essentially O(min{m 2/3, n 1/2 }
More informationSouth Carolina College and CareerReady (SCCCR) Algebra 1
South Carolina College and CareerReady (SCCCR) Algebra 1 South Carolina College and CareerReady Mathematical Process Standards The South Carolina College and CareerReady (SCCCR) Mathematical Process
More informationDiscrete Mathematics Problems
Discrete Mathematics Problems William F. Klostermeyer School of Computing University of North Florida Jacksonville, FL 32224 Email: wkloster@unf.edu Contents 0 Preface 3 1 Logic 5 1.1 Basics...............................
More informationChapter 1. NP Completeness I. 1.1. Introduction. By Sariel HarPeled, December 30, 2014 1 Version: 1.05
Chapter 1 NP Completeness I By Sariel HarPeled, December 30, 2014 1 Version: 1.05 "Then you must begin a reading program immediately so that you man understand the crises of our age," Ignatius said solemnly.
More informationTetris is Hard: An Introduction to P vs NP
Tetris is Hard: An Introduction to P vs NP Based on Tetris is Hard, Even to Approximate in COCOON 2003 by Erik D. Demaine (MIT) Susan Hohenberger (JHU) David LibenNowell (Carleton) What s Your Problem?
More informationA Working Knowledge of Computational Complexity for an Optimizer
A Working Knowledge of Computational Complexity for an Optimizer ORF 363/COS 323 Instructor: Amir Ali Ahmadi TAs: Y. Chen, G. Hall, J. Ye Fall 2014 1 Why computational complexity? What is computational
More informationDATA STRUCTURES USING C
DATA STRUCTURES USING C QUESTION BANK UNIT I 1. Define data. 2. Define Entity. 3. Define information. 4. Define Array. 5. Define data structure. 6. Give any two applications of data structures. 7. Give
More information136 CHAPTER 4. INDUCTION, GRAPHS AND TREES
136 TER 4. INDUCTION, GRHS ND TREES 4.3 Graphs In this chapter we introduce a fundamental structural idea of discrete mathematics, that of a graph. Many situations in the applications of discrete mathematics
More informationWOLLONGONG COLLEGE AUSTRALIA. Diploma in Information Technology
First Name: Family Name: Student Number: Class/Tutorial: WOLLONGONG COLLEGE AUSTRALIA A College of the University of Wollongong Diploma in Information Technology Final Examination Spring Session 2008 WUCT121
More information