Fluent Essays

Use Python language for this Assignment. Find the Resources (Week to week lecture) for this Assignment. Avoid Plagiarism. Book: Data Structures and Algorithms in Python Please check the attached zip file for resources -  This assignment is on this topic - ·  Stack and Queue ·  Linked List and Circular List  ·  Optimize merge  ·  Matrix ·  Search Trees ·  Optimizing Storage ·  Map colouring  Please be specific to every answer. HIT220 - Assignment 2 Cat Kutay Aug 2020 1 Rubric 1. This document is available https://www.overleaf.com/read/cgwdgmvhppzr 2. Submit as a pdf by on Learnline 3. Hand drawings can be scanned and inserted 4. Marking rubric for each question: Marks will be awarded for accuracy, completeness, and well communicated reasoning which demon- strates your depth of understanding of the subject matter. Unless marks otherwise divided up: a Advanced questions only given marks if correct. Otherwise: b Full marks are possible if provide working code c three quarter marks are possible if provide pseudo code d For these marks: i. Half marks will be given for right answer ii. Half marks will be given for working shown with clear explanation of working All questions total marks are shown. Not all parts are of equal value. 2 Questions 1. (4 points) Stack and Queue When working with data in a queue, write the following for the different data structures that are proposed: a You are given an array of k single-linked-lists of length n, where each linked-list is sorted in ascending order. Write code or pseudo code to merge all the linked-lists into one sorted ascending linked-list and return it. b Write the algorithm using (a) iteration and (b) recursion. What is the Big O complexity of each version of the algorithm c Implement a queue using two stacks. What methods do you need to implement for a Queue? What is the worst-case run time complexity of the method to remove an element? Advanced Write a method 1 def contains(queueName: Queue, search: str): return bool which will take a Queue and a String, and returns True if the Queue contains this string of characters in the same sequence. Return false if not found in the Queue. The elements in the Queue must remain in their original order once this method is complete. 2. (3 points) Optimize Merge a Given an array arr[] of n integers, construct an output array prod[] such that prod[i] is equal to the product of all the elements of arr[] except arr[floor(i/2)]. Note: floor() is the largest integer < n/2. b You are to provide code that does not use the division operator and completes in O(n) time. Advanced Can you improve the space complexity to O(1) 3. (2 points) Matrix a Given an n x m matrix write the code to output the transpose of the matrices as an m x n matrix First consider how to store a matrix in your code b Given an n x m matrix write the code to output the diagonal elements of the matrix as a vector or sequence of values. c Given an n x n matrix where each of the rows and columns are sorted in ascending order, return the kth smallest element in the matrix. Note that it is the kth smallest element in sorted order of the entire matrix, not the kth distinct element in the matrix array of arrays∣∣∣∣∣∣ 1 5 9 10 11 13 12 13 15 ∣∣∣∣∣∣ The 8th element is 13 as the elements of the matrix are [1,5,9,10,11,12,13,13,15]. 4. (4 points) Search Trees The insertion of data into a tree can be done in various ways to ensure the height of the tree is minimum, and that searching the tree for an item is not more than O(log n). a Draw separate trees with 8 nodes that are either: balanced; binary tree; neither of these. b Write in pseudo code or code to traverse the tree and verify if it is balanced and/or binary. First consider how you will represent the edges and nodes as data in your program and used this in your code. c Then consider which search method you will use, and name it in your code. Advanced Assume your tree is binary. Now: (a) Write pseudo code or code to carry out a breadth first search of a binary tree (b) What is the complexity of the search? (c) What data structure did you use for the storage of nodes as your run the search above? 5. (3 points) Optimizing storage [Advanced] a We are looking to store water for fire management, and we have located a suitable area, but want to map out the storage, based on the height map of the surrounding area. b Given n non-negative integers representing an elevation map where the width of each bar is 1, write code or pseudo code to calculate the maximum amount of water this elevation can trap between any two peaks. See example below. Page 2 c Note you cannot tilt the elevation map. 6. (4 points) Map colouring Using the Bush Fire Map [2 points]: Figure 1: input heights = [0,1,0,2,1,0,1,3,2,1,2,1]. Output = 4. a Draw a graph of the regions on the map b Store the graph of this map in code c Write an algorithm in code or pseudo code to find if the map is 4-colourable d Are you using an exhaustive or greedy algorithm method? Explain. Advanced 2 points Use your code to advise each region where they can get extra fire trucks from, in an emergency. Assume the trucks are on average based in the centre of each region during fire season. Rough estimate of distance is sufficient. Page 3 Figure 2: Bush Fire regions Page 4 __MACOSX/._Assignment 2_Resources Assignment 2_Resources/.DS_Store __MACOSX/Assignment 2_Resources/._.DS_Store Assignment 2_Resources/Assignment_2_HIT220 (1).pdf HIT220 - Assignment 2 Cat Kutay Aug 2020 1 Rubric 1. This document is available https://www.overleaf.com/read/cgwdgmvhppzr 2. Submit as a pdf by on Learnline 3. Hand drawings can be scanned and inserted 4. Marking rubric for each question: Marks will be awarded for accuracy, completeness, and well communicated reasoning which demon- strates your depth of understanding of the subject matter. Unless marks otherwise divided up: a Advanced questions only given marks if correct. Otherwise: b Full marks are possible if provide working code c three quarter marks are possible if provide pseudo code d For these marks: i. Half marks will be given for right answer ii. Half marks will be given for working shown with clear explanation of working All questions total marks are shown. Not all parts are of equal value. 2 Questions 1. (4 points) Stack and Queue When working with data in a queue, write the following for the different data structures that are proposed: a You are given an array of k single-linked-lists of length n, where each linked-list is sorted in ascending order. Write code or pseudo code to merge all the linked-lists into one sorted ascending linked-list and return it. b Write the algorithm using (a) iteration and (b) recursion. What is the Big O complexity of each version of the algorithm c Implement a queue using two stacks. What methods do you need to implement for a Queue? What is the worst-case run time complexity of the method to remove an element? Advanced Write a method 1 def contains(queueName: Queue, search: str): return bool which will take a Queue and a String, and returns True if the Queue contains this string of characters in the same sequence. Return false if not found in the Queue. The elements in the Queue must remain in their original order once this method is complete. 2. (3 points) Optimize Merge a Given an array arr[] of n integers, construct an output array prod[] such that prod[i] is equal to the product of all the elements of arr[] except arr[floor(i/2)]. Note: floor() is the largest integer < n/2. b You are to provide code that does not use the division operator and completes in O(n) time. Advanced Can you improve the space complexity to O(1) 3. (2 points) Matrix a Given an n x m matrix write the code to output the transpose of the matrices as an m x n matrix First consider how to store a matrix in your code b Given an n x m matrix write the code to output the diagonal elements of the matrix as a vector or sequence of values. c Given an n x n matrix where each of the rows and columns are sorted in ascending order, return the kth smallest element in the matrix. Note that it is the kth smallest element in sorted order of the entire matrix, not the kth distinct element in the matrix array of arrays∣∣∣∣∣∣ 1 5 9 10 11 13 12 13 15 ∣∣∣∣∣∣ The 8th element is 13 as the elements of the matrix are [1,5,9,10,11,12,13,13,15]. 4. (4 points) Search Trees The insertion of data into a tree can be done in various ways to ensure the height of the tree is minimum, and that searching the tree for an item is not more than O(log n). a Draw separate trees with 8 nodes that are either: balanced; binary tree; neither of these. b Write in pseudo code or code to traverse the tree and verify if it is balanced and/or binary. First consider how you will represent the edges and nodes as data in your program and used this in your code. c Then consider which search method you will use, and name it in your code. Advanced Assume your tree is binary. Now: (a) Write pseudo code or code to carry out a breadth first search of a binary tree (b) What is the complexity of the search? (c) What data structure did you use for the storage of nodes as your run the search above? 5. (3 points) Optimizing storage [Advanced] a We are looking to store water for fire management, and we have located a suitable area, but want to map out the storage, based on the height map of the surrounding area. b Given n non-negative integers representing an elevation map where the width of each bar is 1, write code or pseudo code to calculate the maximum amount of water this elevation can trap between any two peaks. See example below. Page 2 c Note you cannot tilt the elevation map. 6. (4 points) Map colouring Using the Bush Fire Map [2 points]: Figure 1: input heights = [0,1,0,2,1,0,1,3,2,1,2,1]. Output = 4. a Draw a graph of the regions on the map b Store the graph of this map in code c Write an algorithm in code or pseudo code to find if the map is 4-colourable d Are you using an exhaustive or greedy algorithm method? Explain. Advanced 2 points Use your code to advise each region where they can get extra fire trucks from, in an emergency. Assume the trucks are on average based in the centre of each region during fire season. Rough estimate of distance is sufficient. Page 3 Figure 2: Bush Fire regions Page 4 __MACOSX/Assignment 2_Resources/._Assignment_2_HIT220 (1).pdf __MACOSX/Assignment 2_Resources/._Week 2 __MACOSX/Assignment 2_Resources/._Week 4 __MACOSX/Assignment 2_Resources/._Week 5 Assignment 2_Resources/Instruction for Assignment 2.docx For this assessment you will need to show the various stages of the solution as you work through the problem, not just the final outcome. You may create your answers as an electronic document which is machine readable. As explained in class, the use of tables to contain material or images of hand drawings is not allowed except for illustration, These will not be considered full answers. Save to pdf and upload. · No Plagiarism · No Copying from internet · Follow the marking rubric __MACOSX/Assignment 2_Resources/._Instruction for Assignment 2.docx __MACOSX/Assignment 2_Resources/._Week 3 __MACOSX/Assignment 2_Resources/._Week 6 Assignment 2_Resources/Week 2 /.DS_Store __MACOSX/Assignment 2_Resources/Week 2 /._.DS_Store Assignment 2_Resources/Week 2 /Week2.pptx Week 2: Computational Complexity Cat Kutay Click on Insert > new slide to choose your cover, then delete this page. 1 Complex Issue Feedback Why do we give it How do we give it Finding it on Learn line Consultation time Will you use it When do you want it Click on Insert > new slide to choose your cover, then delete this page. Reference See Chapter 3 in text. For another similar approach see Drozdek Ch2 library site Computers and Intractability , A guide the Theory of NP-Completeness, Garey and Johnson, W.H.Freeman and Company, New York, 1979. Algorithms and Complexity, Second Edition, Herbert S. Wilf, AK Peter Ltd Canada, 2002. The Nature of Computation, Christopher Moore and Stephan Mertens, Oxford University Press, 2011 Click on Insert > new slide to choose your cover, then delete this page. Meet some Ancestors Abu Ja’far Mohammed ibn Mûsâ al-Khowârizmî was a Persian mathematician (ca. 780–850) who wrote a book that was the foundation of algebra and algorithms Alan Turing, developed Computer Science -  Please watch the You tube by Cambridge University 8 min "Alan Turing - Celebrating the Life of a Genius"  The HIT220 resources page also contains links to you tubes about Turing, Turing Machines and the Halting Problem.   Leonard Euler, The Father of Graph Theory was one of the most prolific mathematicians of all time.  Worth at look around about his contributions to mathematics and science but entirely optional. Euclid developed Geometry.  We studied the Euclidean Algorithm last week however Euclid is more famous for his 5 postulates.  Euclid's Book/s "The Elements" is the most published book of all time.   Beyond Geometry, Euclid proved many results in number theory which we love to use. The Fundamental Theorem of Arithmetic says that every positive integer greater than 1 has a unique prime decomposition.  So useful for finding GCD, LCM, simplifying fractions.  Ada Lovelace developed the first computer algorithm designed for Babbage’s proposed computer, to calculate Bernoulli numbers Click on Insert > new slide to choose your cover, then delete this page. Computational Complexity “As soon as an Analytic Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will arise – By what course of calculation can these result be arrived at by the machine in the shortest test time?” Charles Babbage (~1864) http://www.cbi.umn.edu/about/babbage.html “A wide variety of commonly encountered problems from mathematics, computer science, and operations research are known to be NP-complete ….. it is important for anyone concerned with the computational aspects of these fields to be familiar with the meaning and implications of this concept.” Garey & Johnson, 1978 Click on Insert > new slide to choose your cover, then delete this page. 5 In defining a measure of efficiency The efficiency of execution of an algorithm depends on the hardware, programming language used, compiler, programming skill, etc. These variables are not useful for measuring efficiency of an algorithm. A computing time for millions of bits of input data can be expected to take longer than one where a small amount of input is required. To evaluate an algorithm’s efficiency, logical time units that express a relationship between the size of an input and the amount of time and space required to process the input should be used. Desirable scaling property – When the input size doubles, the algorithm should only slow down by some constant factor. Click on Insert > new slide to choose your cover, then delete this page. Why not good to look at hardware? 6 Analysis of Algorithms Analysis of an algorithm gives insight into how long the program runs and how much memory it uses time complexity space complexity Click on Insert > new slide to choose your cover, then delete this page. Complexity Analysis The same problem can frequently be solved with different algorithms which differ in efficiency. Or choice of data structure – e.g. Linked list vs array Time is generally the most important Space (memory) Tradeoffs between time and space complexity Type of measurement Worst-case Best- case Average-case Generally concerned with worst case analysis. We also study best case but will usually skip average case analysis. Worst case analysis provides a running time guarantee for all inputs. Click on Insert > new slide to choose your cover, then delete this page. Computational Complexity The computational complexity of an algorithm is measure of how many steps the algorithm will require in the worst case for an instance or input of a given size.  Most commonly used notation for describing asymptotic complexity is “big oh" or "big O" notation (O for order of the complexity).   Very loosely, this notation strips away the less significant calculations to give the magnitude of the number of operations for a large input size.   Click on Insert > new slide to choose your cover, then delete this page. Experimental Analysis and Challenges One way to study the efficiency of an algorithm is to implement it and experiment by running the program on various test inputs while recording the time spent during each execution. While experimental studies of running times are valuable, especially when finetuning production-quality code, there are three major limitations to their use for algorithm analysis: Experimental running times of two algorithms are difficult to directly compare unless the experiments are performed in the same hardware and software environments. Experiments can be done only on a limited set of test inputs; hence, they leave out the running times of inputs not included in the experiment (and these inputs may be important). An algorithm must be fully implemented in order to execute it to study its running time experimentally (most serious drawback). Click on Insert > new slide to choose your cover, then delete this page. Moving Beyond Experimental Analysis The goal is to develop an approach to analysing the efficiency of algorithms that: Allows us to evaluate the relative efficiency of any two algorithms in a way that is independent of the hardware and software environment. Is performed by studying a high-level description of the algorithm without need for implementation. Takes into account all possible inputs. Click on Insert > new slide to choose your cover, then delete this page. Counting Primitive Operations To analyse the running time of an algorithm without performing experiments, we perform an analysis directly on a high-level description of the algorithm. We base the description on a set of primitive operations such as the following: Assigning a value to a variable Following an object reference Performing an arithmetic operation (i.e. adding two numbers) Comparing numbers Accessing a single element of an array by index Calling a method Returning from a method Click on Insert > new slide to choose your cover, then delete this page. Primitive Operations This operation count will correlate to an actual running time in a specific computer, for each primitive operation corresponds to a constant number of instructions, and there are only a fixed number of primitive operations. The implicit assumption in this approach is that the running times of different primitive operations will be fairly similar. Thus, the number, t, of primitive operations an algorithm performs will be proportional to the actual running time of that algorithm. Click on Insert > new slide to choose your cover, then delete this page. Measuring Operations as a Function of Input Size To capture the order of growth of an algorithm's running time, we will associate, with each algorithm, a function f(n) that characterizes the number of primitive operations that are performed as a function of the input size n. Click on Insert > new slide to choose your cover, then delete this page. Classification An algorithm is deemed efficient if it has a polynomial running time (e.g. f(n)=n2). Polynomial time classification typically exposes or indicates the existence of “essential structure”. When there are high constants and/or exponents, over a period of time improved algorithms are often discovered. Exceptions – some polynomial time algorithms are not (practically) efficient. Click on Insert > new slide to choose your cover, then delete this page. Worst Case Analysis is main focus Running time guarantee for any input size. Some algorithms of exponential time complexity are successful/practical because the worst case occurs rarely. Best Case Analysis Average case analysis (typically complex calculations) Amortized Complexity – Sections 5.3 Textbook. Read about it so that you could discuss the idea. Click on Insert > new slide to choose your cover, then delete this page. Amortized – break down 16 The order of a nested loop for to for to next next Exercise: Count the number of operations which are additions, subtractions, multiplication. Click on Insert > new slide to choose your cover, then delete this page. Counting elementary operations What is classified as an “elementary operation” may vary. E.g. Drozdek focuses on counting the number of assignments (eg changing values in memory) rather than operations. In fact a general rule of thumb is: Memory references are counted in a data intensive operation as this will correlate well with running time on any machine Comparison numbers will be the most important in a search of a list. Elementary operations used in an algorithm to evaluate a polynomial, are the additions and multiplications needed Click on Insert > new slide to choose your cover, then delete this page. for to for to next next Number of calculations is: Order of complexity: There are two additions, one multiplication and one subtraction for each iteration of the inner loop. i.e. 4 operations per iteration of inner loop. Inner loop executes when: Click on Insert > new slide to choose your cover, then delete this page. 19 To get the order Which is the simplest rising function that is bigger than f(n) From Drozdek Click on Insert > new slide to choose your cover, then delete this page. Function growth and complexity Function growth Big-O notation – informally Tractability Polynomial growth Exponential growth Execution times Click on Insert > new slide to choose your cover, then delete this page. Growth Functions Different functions can effect numbers, and how the growth can happen rapidly. Smallest to Greatest O(1), log2(n), n, (n)log2(n), n2, 2n , n! Consider N=10 0(1) = 1 log2 (10)= 3.32 10 10 log2 (10)= 33.32 102= 100 210= 1024 10!= 3,628,800 Click on Insert > new slide to choose your cover, then delete this page. Function growth within polynomial time lg n is base 2 logarithm Orders of magnitude: O(1) constant O(log n) logarithmic O(n) linear O(n log n) O(n2) quadratic O(n3) cubic Note axis scale is very limited. Figure 2-5 (of Drozdek) Typical functions applied in big-O estimates Click on Insert > new slide to choose your cover, then delete this page. Evaluating Click on Insert > new slide to choose your cover, then delete this page. Asymptotic complexity In algorithm analysis, we focus on the growth rate of the running time as a function of the input size n, taking a "big-picture" approach. For example, it is often enough just to know that the running time of an algorithm grows proportionally to n. The asymptotic complexity is the limiting behaviour of the execution time of an algorithm when the size of the problem goes to infinity. This is usually denoted in big-O notation. Definition: A theoretical measure of the execution of an algorithm, usually the time or memory needed, given the problem size n, which is usually the number of input items. Informally, saying some equation f(n) = O(g(n)) means it is less than some constant multiple of g(n). Click on Insert > new slide to choose your cover, then delete this page. Rescaling of time axis Image source Moore & Mertens Click on Insert > new slide to choose your cover, then delete this page. Big-O notation Formal Definition: f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.  Click on Insert > new slide to choose your cover, then delete this page. Big-O notation – the definition f(n) is O(g(n)) if there exists numbers c, N > 0 such that for each n ≥ N f(n) ≤ c∙g(n) The meaning: f(n) is larger than g(n) only for finite number of n’s a constant c and a value N can be found so that for every value of n ≥ N f(n) ≤ c∙g(n) (such c and the N are called witnesses) f(n) does not grow more than a constant factor faster than g(n) We may write f(n) = O(g(n)) but the “=“ does not represent genuine equality. We say that f(n) is O(g(n)), (because O(g(n)) is a collection - an infinite set). Click on Insert > new slide to choose your cover, then delete this page. Big-O notation: illustration N c∙g(n) f(n) n f(n) ≤ c∙g(n) n ≥ N The function f(n) is O(g(n)), since f(n) ≤ c·g(n) when n ≥ N. Click on Insert > new slide to choose your cover, then delete this page. General rules Ignore constants 5n -> 0(n) Certain terms ‘dominate’ others O(1) < 0(logn) < o(n), o(nlogn) < o(n2)< o(2n) < o(n!) e.g. ignore low-order terms when they dominated by higher one X=5+(15*20) ; Independent of input size, N O(1) ‘big O of one’ x=5+(15*20) ; y=15-2; Print x + y Total time = 0(1) + 0(1) + 0(1) 3* O(1) drop constants O(1) Click on Insert > new slide to choose your cover, then delete this page. Cont. Linear time: for x in range (0,n): print x; // O(1) N * O(1) = O(N) x=5+(15*20) ; //O(1) for x in range (0,n): print x; Total number = O(1) + O(N) = O(N) In another word, when N gets large, the time it takes to compute Y is meaningless, as the for-loop dominate the run time. }//O(N) Click on Insert > new slide to choose your cover, then delete this page. Constants i :=0; while i<n Do i=i+1 i :=0; while i<n Do i=i+3 F(n) = n O(f(n)) = O(n) F(n) = n/3 O(f(n)) = O(n) Click on Insert > new slide to choose your cover, then delete this page. Quadratic time for x in range (0,n): for x in range (0,n): print x*y // O(1) Total number = O(N2) }//O(N2) Click on Insert > new slide to choose your cover, then delete this page. O(?) for x in range (0,n): print x; for x in range (0,n): for x in range (0,n): print x*y What is the total runtime ??? In workshop Click on Insert > new slide to choose your cover, then delete this page. Big O and efficiency An algorithm is deemed efficient if it has a polynomial running time i.e. O(nc) where c is a constant. Polynomial time classification typically exposes or indicates the existence of “essential structure”. When there are high constants and/or exponents, over a period of time improved algorithms are often discovered. Exceptions – some polynomial time algorithms are not (practically) efficient. More exceptions - Some exponential time algorithms work well in practice because the worst case occurs rarely. Click on Insert > new slide to choose your cover, then delete this page. Big-O notation: properties 1. (transitivity) If f(n) is O(g(n)) and g(n) is O(h(n)), then f(n) is O(h(n)) (i.e., f(n) = O(g(n)) = O(O(h(n))) = O(h(n)). 2. If f(n) is O(h(n)) and g(n) is O(h(n)), then f(n) + g(n) is O(h(n)). 3. ank is O(nk). 4. nk is O(nk+j) for any j > 0. 5. If f(n) = cg(n), then f(n) = O(g(n)). 6. logan = O(logbn) for any numbers a, b > 1. 7. logan is O(log2n) for any positive a ≠ 1 Click on Insert > new slide to choose your cover, then delete this page. Section 2.3. Analysis of Algorithms Relatives of Big-Oh big-Omega f(n) is (g(n)) if there is a constant c > 0 and an integer constant n0  1 such that f(n)  c•g(n) for n  n0 big-Theta f(n) is (g(n)) if there are constants c’ > 0 and c’’ > 0 and an integer constant n0  1 such that c’•g(n)  f(n)  c’’•g(n) for n  n0 Click on Insert > new slide to choose your cover, then delete this page. Intuition for Asymptotic Notation Analysis of Algorithms Big-Oh f(n) is O(g(n)) if f(n) is asymptotically less than or equal to g(n) big-Omega f(n) is (g(n)) if f(n) is asymptotically greater than or equal to g(n) big-Theta f(n) is (g(n)) if f(n) is asymptotically equal to g(n) Click on Insert > new slide to choose your cover, then delete this page. Analysis of Algorithms Example Uses of the Relatives of Big-Oh f(n) is (g(n)) if it is (n2) and O(n2). We have already seen the former, for the latter recall that f(n) is O(g(n)) if there is a constant c > 0 and an integer constant n0  1 such that f(n) < c•g(n) for n  n0 Let c = 5 and n0 = 1 5n2 is (n2) f(n) is (g(n)) if there is a constant c > 0 and an integer constant n0  1 such that f(n)  c•g(n) for n  n0 let c = 1 and n0 = 1 5n2 is (n) f(n) is (g(n)) if there is a constant c > 0 and an integer constant n0  1 such that f(n)  c•g(n) for n  n0 let c = 5 and n0 = 1 5n2 is (n2) Click on Insert > new slide to choose your cover, then delete this page. 39 Tractability - overview The area of tractability explores problems and algorithms that can take an impossible amount of computation to solve except perhaps for very small examples of the problem. Tractable – an efficient algorithm. i.e. Polynomial time. Efficient - time complexity is at most a polynomial function of input size. Inefficient: A brute force algorithm or exhaustive search examines every possibility. For non-trivial problems this approach leads to “combinatorial explosion” in the number of possibilities. Unacceptable running time on large inputs. Typically 2n time or worse for inputs of size n. i.e. Exponential run time. “Or Worse” - the input size need not be very large at all to generate a running time well beyond the lifetime of the universe. Click on Insert > new slide to choose your cover, then delete this page. Intractability examples A problem is intractable in the strongest sense if the problem is undecidable. i.e. No algorithm is possible. Read about Russel’s Paradox, and Turing’s Halting Problem. Another strong sense of intractability occurs when the running time to output a solution to a problem is excessive. Click on Insert > new slide to choose your cover, then delete this page. Paradox – set of all sets that do not contain themselves Halting - machine or algorithm that says if any algorithm will halt – put through an algorithm that is the machine plus a not gate 41 P vs. NP and the Computational Complexity Zoo https://www.youtube.com/watch?v=YX40hbAHx3s Many examples in this video are not decision problems, so do not use such problems as examples in your assignments Click on Insert > new slide to choose your cover, then delete this page. Decision problems In HIT220 you only look at decision problems These are yes-or-no question on an infinite set of inputs. The classification of computational complexity classes (e.g. P, NP,NPC) is based on decision problems. Click on Insert > new slide to choose your cover, then delete this page. Class P A deterministic algorithm is a uniquely defined (determined) sequence of steps for a particular input. There is only one way to determine the next step that the algorithm can make. A problem belongs to the class P of decision problems if it can be solved in polynomial time with a deterministic algorithm. Two members of P: Graph 2-colourability Is G Eulerian? The bridges of Königsberg problem solved by Euler in 1736. Click on Insert > new slide to choose your cover, then delete this page. The Seven Bridges of Königsberg https://www.youtube.com/watch?v=f-Zy1q9XFQE Click on Insert > new slide to choose your cover, then delete this page. The graph of the Bridges of of Königsberg has 4 vertices (land) and 7 edges (representing the bridges). One could solve the problem using “Brute Force”. An exhaustive search of all possibilities. Exponential time complexity. Euler’s insight: In order to cross each edge once, any time we arrive at a vertex along one edge, we have to depart on a different edge. Hence the degree of a vertex v, that is the number of edges incident to each v , must be even. Click on Insert > new slide to choose your cover, then delete this page. Class NP A non-deterministic algorithm is an algorithm that can use a special operation that makes a guess when a decision is to be made. A problem belongs to the class NP of decision problems if it can be solved by a non-deterministic polynomial time algorithm (on a theoretical machine allowing infinite parallelism). The class of NP problems consists of problems with the property that “checking” whether or not a claimed solution is correct can be performed in polynomial time. Two members of NP: Graph k-colourability, Is G Hamiltonian? A Hamiltonian path, also called a Hamilton path, is a graph path between two vertices of a graph that visits each vertex exactly once. If a Hamiltonian path exists whose endpoints are adjacent, then the resulting graph cycle is called a Hamiltonian cycle (or Hamiltonian cycle). So to prove that a decision problem is in NP we would only need to show that checking can be performed in polynomial time. i.e. That there is an efficient checking algorithm. (Probably the most useful thinking for HIT220) Click on Insert > new slide to choose your cover, then delete …