The World of Computer ScienceWhat is Computer Science all About?Have we answered the questions?TerminologyMore TerminologyOraclesThe Hierarchy of ProblemsNP-Complete ProblemsCost of Graph Problems (review)Given a Problem, How do you Determine if it is Computable?Example 1: Is it Computable?Example 2: Is it Computable?Example 3: Is it Computable?The World of Computer ScienceAlgorithmsLanguages ArchitectureTheory ofAlgorithmsTheory ofLanguagesTheoreticalModel ofComputersReal WorldWorld of TheoryWhat is Computer Science all About?• The answer to the first question tells us whether a problem should even be attempted using a computer.–Some problems are perfectly suited for computers, others are not.•The answer to the second question tells us if it is worth doing.–The cost is in terms of some resource like time or memory usage.–We attempt to relate cost to problem size.–Problems are grouped into classes depending on their cost (Chptr 11) What problems can a computer solve? What is the computational cost of the solution?Have we answered the questions?•Yes and no: We have defined some problems that are and aren't computable, but there are an infinite number of problems.•We now have tools to decide if any problem is computable:–Definition of computability (can write an algorithm and cost is not too high) .–Definition of computational power (all computers are equal).–Definition of an algorithm (properties and format).–Order notation to compare costs.–Understanding that problems may be "mapped" to each other.–Understanding of programming languages (all of them).–Understanding of data structures and types.•These are all tools to help you decide if something can be done by a computer and how to do it.Terminology•Closed Problems: These problems are well understood. The known cost and known algorithms are of the same order. It is known whether they are computable or not•Open Problems: These problems are not as well understood. The cost of known algorithms to solve them and the theoretical best are not of the same order. •Tractable: Computable, specifically with respect to cost. Cost is polynomial.•Intractable: Not computable, specifically with respect to cost. Cost is exponential or worse.More Terminology•Undecidable Problems: These are problems for which no algorithm can be written (regardless of cost). They are not computable.•Deterministic Algorithms: Algorithms that have no randomness associated with them. They will always behave the same when given the same input.•Nondeterministic Algorithms: Algorithms that have random elements. They may behave differently when run repeatedly,even if the input is the same.Oracles•Oracles: A theoretical device that magically selects the correct choice for an algorithm when the algorithm has choices to make. •They don't exist, but are used to classify the "hardness" of problems. •Example: Traveling Salesman with oracle–We want to travel to n cities.–Recall that Traveling Salesman is an O(n!) problem.–With an oracle, we always make the best choice on each leg of the trip.–This means we only check out one path, and it is the optimal path. –Since there are n cities, we made n correct choices and the problem is O(n).•Since Traveling Salesman is intractable without the oracle, but tractable with the oracle, Traveling Salesman is an NP problem.The Hierarchy of ProblemsPNPHardP = Polynomial, O(nk).Easy to solve, easy to verify solution.Ex: Searching, sorting.NP = Non-Deterministic Polynomial, O(kn)Hard to solve, easy to verify solutionEx: Traveling Salesman Decision.Hard = Hard, O(kn)Hard to solve, hard to verify solution.Ex: Traveling Salesman optimization.NP-Complete Problems•There are literally hundreds of them.•They can all be mapped to each other (hence the "complete" part of the name).•They all have exponential upper bound costs (not computable).•They all have polynomial lower bound costs (computable). •It is possible that polynomial algorithms will be developed to solve one of them–If one is solved quickly, then they all are.–Until then the notion of nondterministic algorithm guided by an oracle is used to discuss them.Cost of Graph Problems (review)Name Description Cost * CommentsTraveling Salesman DecisionDoes a route exist with cost less than X?O(n!) Hard to solve, easy to verify.Traveling Salesman OptimizationWhat is the least cost route.O(n!) Hard to solve, hard to verify.Graph ColoringDecisionCan a graph be colored properly using X colors?O(n!) Hard to solve, easy to verify.Graph Coloring OptimizationWhat is the least number of colrs required to properly color a graph?O(n!) Hard to solve, hard to verify.Maximum Flow What is the most material that can be pushed through a network? O(n3) Polynomial solution time means easy to solve, easy to verify.Given a Problem, How do you Determine if it is Computable?•Method One (usually the hard way):–Write an algorithm to compute the solution for all inputs.–Determine the cost of the algorithm.–Compare to the problem hierarchy.•Method Two (usually the easy way):–Show that the new problem can be mapped to a known problem.–The new problem then has the same cost as the old.–If the old was computable, then so is the new.Example 1: Is it Computable?–You work for a stock exchange company doing e-trades. –Your boss wants you to develop a system by which your clients are ranked according to how valuable they are to your firm. When a stock becomes available that more than one client has previously requested, you offer it to the highest ranked client first. –All transactions are electronic and happen without human intervention and must be resolved fairly quickly (a couple of seconds).–Can it be done? What do you tell your boss?Example 2: Is it Computable?–You work for a stock exchange company doing e-trades. –Your boss wants you to develop a system by which your clients who request a sale of stock will have their request refused if they can get a higher price within the next three days. Guaranteed. –All transactions are electronic and happen without human intervention..–Can it be done? What do you tell your boss?Example 3: Is it Computable?–You work for a company streaming media for live events through the web. –Your boss wants you to develop a system that will reduce the bandwidth comming from your servers. She wants the sytem to track the users online and their connection