Largest Contiguous Sum

Largest Contiguous Sum

CSC 172 P, NP, Etc Computer Science is a science of abstraction creating the right model for thinking about a problem and devising the appropriate mechanizable technique to solve it. Aho & Ullman (1995)

The process of abstraction You can solve problems by wiring up special purpose hardware (hand calculator) Turing showed that you could abstract hardware configurations Von Neumann showed that you could abstract away from the hardware (machine languages) High level languages are an abstraction of low level languages (JAVA/C++ rather

than SML) The process of abstraction Data structures are an abstractions in high level languages (mystack.push(myobject)) So, now we can talk about solutions to whole problems Similar problems with similar solutions constitute the next level of abstraction

Hard, Harder, Impossible Some well-formed computational problems don't have computational solution. They are undecidable. Trick: liar's paradox: This sentence is false. Halts?(x) is a subroutine that is T or F if x (a program) halts or loops. Oops(x) is

if Halts?(x) then loop-forever() else halt. Oops(Oops) ?? Some Definitions Exponential time: you have to test every possibility O(kn) Polynomial

time: you have some clever algorithm O(nk) Note even n100 is better than exponential P: A problem that can be solved quickly (in polynomial time) O(nc)

NP: A problem whose solution can be checked for correctness in polynomial time. NP-hard: A problem such that every problem in NP reduces to it. (Not in NP) NP-complete (NPC): A problem that is both NP hard and in NP P: A problem that can be solved quickly (in polynomial time) O(nc)

NP: A problem whose solution can be checked for correctness in polynomial time. NP-hard: A problem such that every problem in NP reduces to it. (Not in NP) NP-complete (NPC): A problem that is both NP hard and in NP The class of problems P P stands for Polynomial The class P is the set of problems that have polynomial time solutions

Some problems have solutions that run in O(nc) time testing for cycles, MWST, Conn. Comps, shortest path, simple sorting,.... Not in the class of problems P? On the other hand, some problems seem to take time that is exponential O(2n) or worse TSP, satisfiability, graph coloring

Famous Examples Travelling Salesman Prob: In undirected weighted graph find path starting and ending at specified vertex, visiting each vertex once, costing <= K. Satisfiability: e.g. what a, b, c, d, e values make (a v b v ~c)^(d v ~a ve)^(~c v b v d)^(c v ~d v e) true? (3-SAT) How many colors needed to color graph vertices so no nbrs have same color? How color (= sudoku)?

Same problem if polynomially reducible Assume I have boolean fn satisfiable(String expression) How do I write tautology(String expression) Easy Conversion tautology(exp) = no var. assts such that

satisfiable(exp) is false. The class NP NP stands for Nondeterministic Polynomial Nondeterministic computation: guess or parallelize A problem can be solved in nondeterministic polynomial time if: given a guess at a solution for some instance of size n we can check that the guess is correct in

polynomial time (i.e. the check runs O(n c)) NP takes P time to Check TSP: does path hit all vertices, cost <= K? linear. SAT: evaluate the boolean expression with constant (0,1) values: linear. Colorability: check all edges for diff. colored ends. linear. Hamiltonian Path: path hits all vertices? linear.

P NP NP P P NP NPC NPC stands for NP-complete Some problems in NP are also in P -they can be solved as well as checked in O(nc) time

Others, appear not to be solvable in polynomial time There is no proof that they cannot be solved in polynomial time But, we have the next best thing to such proof A theory that says many of these problems are as hard as any in NP We call these NP-complete problems Not sure? We work to prove equivalence of NPC problems

If we could solve one of them in O(n c) time then all would be solvable in polynomial time (P == NP) What do we have? Since the NP-complete problems include many that have been worked on for centuries, there is strong evidence that all NP-complete problems really require exponential time to solve. Reductions The way a problem is proved NP-complete is to

reduce a known NP-complete problem to it We reduce a problem A to a problem B by devising a solution that uses only a polynomial amount of time (to convert the data, make the correspondence) plus a call to a method that solves B Easiest NPC Problem? Partition problem: partition list of integers into 2

parts such that sum(part1) = sum(part2) (3,1,1,2,2,1) -> (1,1,1,2) and (2,3). Version of subset-sum problem (is there a subset of a list of ints that sums to zero?), Also NPC. Very good dynamic program and not bad greedy approaches. hence easy. Back to Graphs By way of example of a class of problems consider Cliques & Independent Sets in graphs

Cliques A complete sub-graph of an undirected graph A set of nodes of some graph that has every possible edge The clique problem: Given a graph G and an integer k, is there a clique of at least k nodes? Example Example

A B C D E

F G H Example A B

C D E F G

H Example K == 4 ABEF CGHD A B

C D E F G H

Independent Set Subset S of the nodes of an undirected graph such that there is no edge between any two members of S The independent set problem given a graph G and an integer k, is there an independent set with at least k nodes (Application: scheduling final exams) nodes == courses, edges mean that courses have one student in common. Any guesses on how large the graph would be for

UR? Example independent set K == 2 AC AD AG AH B(D,G,H) Etc..

A B C D E F

G H Checking Solutions Clique, IS, colorability are examples of hard to find solutions find a clique of n nodes But, its easy (polynomial time) to check a proposed solution.

Checking Check a proposed clique by checking for the existence of the edges between the k nodes Check for an IS by checking for the nonexistence of an edge between any two nodes in the proposed set Check a proposed coloring by examining the ends of all the edges in the graph Checking Check a proposed clique by checking for the existence of the edges between the k nodes

Check for an IS by checking for the nonexistence of an edge between any two nodes in the proposed set Check a proposed coloring by examining the ends of all the edges in the graph Same Problem Reductions Clique to IS Given a graph G and an integer k we want to know if there is a clique of size k in G 1. Construct a graph H with the same set of nodes as G and an edge wherever G does not

have edges 2. An independent set in H is a clique in G 3. Use the IS method on H and return its answer Same Problem Reductions IS to Clique Given a graph G and an integer k we want to know if there is an IS of size k in G 1. Construct a graph H with the same set of nodes as G and an edge wherever G does not

have edges 2. An independent set in H is a clique in G 3. Use the clique method on H and return its answer Example A E B

C G D Example A E

B C G D Example A E

B C G D Example C

A E B D G Example

C A E B G D Example

C A E B G D

Example C A B E A E

D G B C G D

Hamiltonian cycle from TSP Make complete graph from input graph, give original edges cost 1, added edges cost 2, and if there were K original edges solve TSP for K.

Recently Viewed Presentations

  • Land Mobile Radio System Upgrade Project Status Report

    Land Mobile Radio System Upgrade Project Status Report

    During the government shutdown, the FBI's radio shop was furloughed. As a result, key project tasks are lagging for the FBI portion of the project. The FBI is scrubbing their schedule to identify the impact and a realistic timeline for...
  • Supporting Students in Grade 4-6 with the Online Reference Centre

    Supporting Students in Grade 4-6 with the Online Reference Centre

    "Permalink" creates a static, unchanging URL that can be shared on a webpage, in an email and allows the user to open the TeachingBooks page without being logged into the LearnAlberta.ca webpage "Calendar" allows access to the literary calendar "Facebook,"...
  • Martin Luther wrote and posted the 95 Theses

    Martin Luther wrote and posted the 95 Theses

    Habsburg-Valois Wars . St. Bartholomew's Day Massacre. a) Identify and explain ONE change in France after the Edict of Nantes. After the Edict of Nantes, religious and political warfare between the Huguenots and Catholics ceased in France. Like much of...
  • Cloud Detection: Optical Depth Thresholds and FOV Considerations

    Cloud Detection: Optical Depth Thresholds and FOV Considerations

    Steven A. Ackerman, Richard A. Frey, Edwin Eloranta, and Robert Holz ... Comparison of satellite cloud amounts should account for the varying viewing and solar geometry. GCMs make extensive comparison with satellite derived cloud amount. Total cloud amount from different...
  • How Glaciers Change Our Earth - Denton ISD

    How Glaciers Change Our Earth - Denton ISD

    Glaciers cover about one-tenth of the Earth's surface. Most of the fresh water found on the Earth is frozen in glaciers. Glaciers move very slowly and can cause very slow changes to the Earth's surface. What are glaciers? How do...
  • Karla Homolka - Seneca Valley School District

    Karla Homolka - Seneca Valley School District

    Karla Homolka fits best under the Differential Association Theory, but not exactly. She also fits under Social Control Theory. Like the class example, Jill, Karla had many things that should have kept her from crime. She was well liked and...
  • Maple Valley Lacrosse - LeagueAthletics.com

    Maple Valley Lacrosse - LeagueAthletics.com

    Sr. Wyatt Philpot. Sr. Trevor Larsen. ... PRACTICE UNIFORM We are a team - look like one! 1.practice penny - Tahoma 2016 2. Practice Shorts (black) 3.Required Helmet. SLEUTH Fight to Compete. Cub TeamsAll Varsity players are required to coach...
  • Strategies for Reading Poetry - Mr. Chiasson&#x27;s Website

    Strategies for Reading Poetry - Mr. Chiasson's Website

    Strategies for Reading Poetry. ... "My Last Duchess" ... Theme. The previous steps should lead you to a statement of theme: what is the central message of the text, what do we learn about life from having read it. You...