Asymptotic Notation,

算法常用术语中英对照以下是一些算法常用术语的中英对照，供参考：1. Algorithm 算法2. Data structure 数据结构3. Array 数组4. Stack 栈5. Queue 队列6. Linked list 链表7. Tree 树8. Binary tree 二叉树9. Graph 图10. Hash table 哈希表11. Sorting algorithm 排序算法12. Bubble sort 冒泡排序13. Insertion sort 插入排序14. Selection sort 选择排序15. Merge sort 归并排序16. Quick sort 快速排序17. Binary search 二分查找18. Depth-first search (DFS) 深度优先19. Breadth-first search (BFS) 广度优先20. Dijkstra's algorithm 迪杰斯特拉算法21. Prim's algorithm 普里姆算法22. Greedy algorithm 贪心算法23. Dynamic programming 动态规划24. Recursion 递归25. Backtracking 回溯29. Big O notation 大O符号30. Worst case scenario 最坏情况31. Best case scenario 最好情况32. Average case scenario 平均情况33. Asymptotic analysis 渐近分析34. Brute force 暴力解法35. Heuristic algorithm 启发式算法36. Randomized algorithm 随机算法37. Divide and conquer 分治法38. Memorization 记忆化39. Online algorithm 在线算法40. Offline algorithm 离线算法41. Random access 随机访问42. Sequential access 顺序访问45. In-place algorithm 原地算法46. Stable algorithm 稳定算法47. Unstable algorithm 不稳定算法48. Exact algorithm 精确算法49. Approximation algorithm 近似算法这些术语覆盖了算法和数据结构的各个方面，从基础的数据结构到排序算法、算法、图算法等等。

1.The O-notation provides an asymptotic upper bound. The Ω-notationprovides an asymptotic lower bound. The Θ-notation asymptoticallya function form above and below.2.To represent a heap as an array，the root of tree is A[1], and giventhe index i of a node, the indices of its parent Parent(i) { return ⎣i/2⎦; }，left child, Left(i) { return 2*i; }，right child, right(i) { return 2*i + 1; }.代表一个堆中的一个数组，树的根节点是A[1]，并且给出一个节点i，那么该节点的父节点是左孩子右孩子3.Because the heap of n elements is a binary tree, the height of anynode is at most Θ(lg n).因为n个元素的堆是一个二叉树，任意节点的树高最多是4.In optimization problems, there can be many possible solutions. Eachsolution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem.在最优化问题中，有很多可能的解，每个解都有一个值，我们希望找到一个最优解（最大或最小），我们称这个解为最优解问题。

AsymptoticWhat is Asymptotic?Asymptotic is a term used in mathematics and computer science to describe the behavior of a function or algorithm as the input size grows towards infinity. It allows us to analyze the efficiency and performance of algorithms and make predictions about their behavior in the long run. Asymptotic analysis helps us identify the best algorithm for a given problem and understand how it scales with larger inputs.Big O NotationOne common way to express asymptotic behavior is through the use of Big O notation. Big O notation provides an upper bound on the growth rate of a function. It describes the worst-case scenario, or the slowest possible growth, as the size of the input increases.The Big O notation is represented as O(f(n)), where f(n) is a function representing the growth rate. For example, if an algorithm has a time complexity of O(n), it means that the runtime of the algorithm grows linearly with the size of the input. If the time complexity is O(n²), it means that the runtime grows quadratically with the input size.Asymptotic Complexity ClassesAsymptotic analysis allows us to categorize algorithms into different complexity classes based on their growth rates. Here are some commonly encountered complexity classes:1.O(1) - Constant Time Complexity: The algor ithm’s runtime remainsconstant, regardless of the input size. This is the most efficient complexity class.2.O(log n) - Logarithmic Time Complexity: The algorithm’s runtimegrows logarithmically with the input size. Common examples include binary search and some divide-and-conquer algorithms.3.O(n) - Linear Time Complexity: The algorithm’s runtime growslinearly with the input size. This is considered a good complexity class in most cases.4.O(n log n) - Linearithmic Time Complexity: The algorithm’sruntime grows in proportion to n multiplied by the logarithm of n.5.O(n²) - Quadratic Time Complexity: The algorithm’s runtime growsquadratically with the input size. This is considered lessefficient than linear time complexity.6.O(2^n) - Exponential Time Complexity: The algorithm’s runtimegrows exponentially with the input size. This is generallyconsidered inefficient and should be avoided if possible.There are also higher complexity classes such as O(n!) (factorial time complexity) and O(n^n) (polynomial time complexity), which are even less efficient.Analyzing Algorithms with Asymptotic MethodsTo analyze the efficiency of an algorithm, we typically look at three aspects: time complexity, space complexity, and auxiliary space complexity.Time Complexity: It meas ures how the algorithm’s runtime grows as the input size increases. It helps us understand how much time an algorithm will take to solve a problem of a certain size.Space Complexity: It measures how much additional memory an algorithm requires as the input size increases. It is important to optimize space usage, especially in resource-constrained environments.Auxiliary Space Complexity: It measures the extra space required by an algorithm apart from the input size. It helps us determine theadditional memory space needed for intermediate calculations or function calls.By analyzing these aspects, we can choose the most efficient algorithm for a given problem and estimate its performance with larger inputs. However, it’s important to note that asymptotic an alysis provides a high-level understanding of an algorithm’s efficiency. Other factors, such as the actual implementation details and hardware capabilities, can also affect the algorithm’s performance in practice.Asymptotic Notation in PracticeAsymptotic analysis and Big O notation are widely used in computer science and play a crucial role in algorithm design and analysis.Without understanding the asymptotic behavior of algorithms, it would be difficult to make informed decisions about which algorithm to use for a given problem.For example, suppose we have two algorithms to solve a sorting problem: Algorithm A with time complexity O(n²) and Algorithm B with time complexity O(n log n). If the input size is small, Algorithm A may perform better due to its lower constant factors. However, as the input size increases, Algorithm B will eventually outperform Algorithm A due to its better growth rate.Asymptotic analysis is also useful for predicting how an algorithm will perform when faced with larger datasets or when deployed in real-world scenarios. It helps us understand the inherent scalability of algorithms and make informed choices about system architecture and resource allocation.ConclusionAsymptotic analysis and the use of Big O notation are fundamental concepts in computer science and mathematics. They allow us to analyze the efficiency and behavior of algorithms as the input size grows. By understanding the asymptotic complexity of algorithms, we can make informed decisions about which algorithm to use for a given problem and estimate its performance with larger inputs.Remember, asymptotic analysis provides a high-level understanding of an algorithm’s behavior, and other factors, such as actual implementation details, hardware capabilities, and real-world constraints, can also impact the algorithm’s performance. Neverthe less, a solid understanding of asymptotic analysis is crucial for effectively designing and analyzing algorithms in various fields, including computer science, mathematics, and data science.。

数学专有名词英文词典Mathematics Glossary: A Comprehensive English Dictionary of Mathematical TermsIntroduction:Mathematics is a language of numbers, shapes, patterns, and relationships. It plays a crucial role in various fields, including science, engineering, economics, and finance. To effectively communicate and understand mathematical concepts, it is essential to have a solid grasp of mathematical vocabulary. This article aims to provide a comprehensive English dictionary of mathematical terms, allowing readers to enhance their mathematical knowledge and fluency.A1. Abacus: A counting device that uses beads or pebbles on rods to represent numbers.2. Absolute Value: The distance of a number from zero on a number line, always expressed as a positive value.3. Algorithm: A set of step-by-step instructions used to solve a particular problem or complete a specific task.4. Angle: The measure of the separation between two lines or surfaces, usually measured in degrees.5. Area: The measure of the amount of space inside a two-dimensional figure, expressed in square units.B1. Base: The number used as a repeated factor in exponential notation.2. Binomial: An algebraic expression with two unlike terms connected by an addition or subtraction sign.3. Boundary: The edge or perimeter of a geometric shape.4. Cartesian Coordinates: A system that uses two number lines, the x-axis and y-axis, to represent the position of a point in a plane.5. Commutative Property: The property that states the order of the terms does not affect the result of addition or multiplication.C1. Circle: A closed curve with all points equidistant from a fixed center point.2. Congruent: Two figures that have the same shape and size.3. Cube: A three-dimensional solid shape with six square faces of equal size.4. Cylinder: A three-dimensional figure with two circular bases and a curved surface connecting them.5. Decimal: A number written in the base-10 system, with a decimal point separating the whole number part from the fractional part.D1. Denominator: The bottom part of a fraction that represents the number of equal parts into which a whole is divided.2. Diameter: The distance across a circle, passing through the center, and equal to twice the radius.3. Differential Equation: An equation involving derivatives that describes the relationship between a function and its derivatives.4. Dividend: The number that is divided in a division operation.5. Domain: The set of all possible input values of a function.E1. Equation: A mathematical statement that asserts the equality of two expressions, usually containing an equal sign.2. Exponent: A number that indicates how many times a base number should be multiplied by itself.3. Expression: A mathematical phrase that combines numbers, variables, and mathematical operations.4. Exponential Growth: A pattern of growth where the quantity increases exponentially over time.5. Exterior Angle: The angle formed when a line intersects two parallel lines.F1. Factor: A number or expression that divides another number or expression without leaving a remainder.2. Fraction: A number that represents part of a whole, consisting of a numerator anda denominator.3. Function: A relation that assigns each element from one set (the domain) to a unique element in another set (the range).4. Fibonacci Sequence: A sequence of numbers where each number is the sum of the two preceding ones.5. Frustum: A three-dimensional solid shape obtained by slicing the top of a cone or pyramid.G1. Geometric Sequence: A sequence of numbers where each term is obtained by multiplying the previous term by a common ratio.2. Gradient: A measure of the steepness of a line or a function at a particular point.3. Greatest Common Divisor (GCD): The largest number that divides two or more numbers without leaving a remainder.4. Graph: A visual representation of a set of values, typically using axes and points or lines.5. Group: A set of elements with a binary operation that satisfies closure, associativity, identity, and inverse properties.H1. Hyperbola: A conic section curve with two branches, symmetric to each other, and asymptotic to two intersecting lines.2. Hypotenuse: The side opposite the right angle in a right triangle, always the longest side.3. Histogram: A graphical representation of data where the data is divided into intervals and the frequency of each interval is shown as a bar.4. Hexagon: A polygon with six sides and six angles.5. Hypothesis: A proposed explanation for a phenomenon, which is then tested through experimentation and analysis.I1. Identity: A mathematical statement that is always true, regardless of the values of the variables.2. Inequality: A mathematical statement that asserts a relationship between two expressions, using symbols such as < (less than) or > (greater than).3. Integer: A whole number, either positive, negative, or zero, without any fractional or decimal part.4. Intersect: The point or set of points where two or more lines, curves, or surfaces meet.5. Irrational Number: A real number that cannot be expressed as a fraction or a terminating or repeating decimal.J1. Joint Variation: A type of variation where a variable is directly or inversely proportional to the product of two or more other variables.2. Justify: To provide a logical or mathematical reason or explanation for a statement or conclusion.K1. Kernel: The set of all inputs that map to the zero element of a function, often used in linear algebra and abstract algebra.L1. Line Segment: A part of a line bounded by two distinct endpoints.2. Logarithm: The exponent or power to which a base number must be raised to obtain a given number.3. Limit: The value that a function or sequence approaches as the input or index approaches a particular value.4. Linear Equation: An equation of the form Ax + By = C, where A, B, and C are constants, and x and y are variables.5. Locus: The set of all points that satisfy a particular condition or criteria.M1. Median: The middle value in a set of data arranged in ascending or descending order.2. Mean: The average of a set of numbers, obtained by summing all the values and dividing by the total count.3. Mode: The value or values that appear most frequently in a data set.4. Matrix: A rectangular array of numbers, symbols, or expressions arranged in rows and columns.5. Midpoint: The point that divides a line segment into two equal halves.N1. Natural Numbers: The set of positive whole numbers, excluding zero.2. Negative: A number less than zero, often represented with a minus sign.3. Nonagon: A polygon with nine sides and nine angles.4. Null Set: A set that contains no elements, often represented by the symbol Ø or { }.5. Numerator: The top part of a fraction that represents the number of equal parts being considered.O1. Obtuse Angle: An angle that measures more than 90 degrees but less than 180 degrees.2. Octagon: A polygon with eight sides and eight angles.3. Origin: The point (0, 0) on a coordinate plane, where the x-axis and y-axis intersect.4. Order of Operations: The set of rules for evaluating mathematical expressions, typically following the sequence of parentheses, exponents, multiplication, division, addition, and subtraction.5. Odd Number: An integer that cannot be divided evenly by 2.P1. Parabola: A conic section curve with a U shape, symmetric about a vertical line called the axis of symmetry.2. Pi (π): A mathematical constant representing the ratio of a circle's circumference to its diameter, approximately equal to3.14159.3. Probability: The measure of the likelihood that a particular event will occur, often expressed as a fraction, decimal, or percentage.4. Prime Number: A natural number greater than 1 that has no positive divisors other than 1 and itself.5. Prism: A three-dimensional figure with two parallel congruent bases and rectangular or triangular sides connecting the bases.Q1. Quadrant: One of the four regions obtained by dividing a coordinate plane into four equal parts.2. Quadrilateral: A polygon with four sides and four angles.3. Quartile: Each of the three values that divide a data set into four equal parts, each containing 25% of the data.4. Quotient: The result obtained from the division of one number by another.5. Quaternion: A four-dimensional extension of complex numbers, often used in advanced mathematics and physics.R1. Radius: The distance from the center of a circle or sphere to any point on its circumference or surface, always half of the diameter.2. Radical: The symbol √ used to represent the square root of a number or the principal root of a higher-order root.3. Ratio: A comparison of two quantities, often expressed as a fraction, using a colon, or as a verbal statement.4. Reflection: A transformation that flips a figure over a line, creating a mirror image.5. Rhombus: A parallelogram with all four sides of equal length.S1. Scalene Triangle: A triangle with no equal sides.2. Sector: The region bounded by two radii of a circle and the arc between them.3. Series: The sum of the terms in a sequence, often represented using sigma notation.4. Sphere: A three-dimensional object in which every point on the surface is equidistant from the center point.5. Square: A polygon with four equal sides and four right angles.T1. Tangent: A trigonometric function that represents the ratio of the length of the side opposite an acute angle to the length of the adjacent side.2. Theorem: A mathematical statement that has been proven to be true based on previously established results.3. Transversal: A line that intersects two or more other lines, typically forming angles at the intersection points.4. Trapezoid: A quadrilateral with one pair of parallel sides.5. Triangle: A polygon with three sides and three angles.U1. Union: The combination of two or more sets to form a new set that contains all the elements of the original sets.2. Unit: A standard quantity used to measure or compare other quantities.3. Unit Circle: A circle with a radius of 1, often used in trigonometry to define trigonometric functions.4. Undefined: A term used to describe a mathematical expression or operation that does not have a meaning or value.5. Variable: A symbol or letter used to represent an unknown or changing quantity in an equation or expression.V1. Vertex: A point where two or more lines, rays, or line segments meet.2. Volume: The measure of the amount of space occupied by a three-dimensional object, often expressed in cubic units.3. Variable: A symbol or letter used to represent an unknown or changing quantity in an equation or expression.4. Vector: A quantity with both magnitude (size) and direction, often represented as an arrow.5. Venn Diagram: A graphical representation of the relationships between different sets using overlapping circles or other shapes.W1. Whole Numbers: The set of non-negative integers, including zero.2. Weighted Average: An average calculated by giving different weights or importance to different values or data points.3. Work: In physics, a measure of the energy transfer that occurs when an object is moved against an external force.4. Wavelength: The distance between two corresponding points on a wave, often represented by the symbol λ.5. Width: The measurement or extent of something from side to side.X1. x-axis: The horizontal number line in a coordinate plane.2. x-intercept: The point where a graph or a curve intersects the x-axis.3. x-coordinate: The horizontal component of a point's location on a coordinate plane.4. xy-plane: A two-dimensional coordinate plane formed by the x-axis and the y-axis.5. x-variable: A variable commonly used to represent the horizontal axis or the input in a mathematical equation or function.Y1. y-axis: The vertical number line in a coordinate plane.2. y-intercept: The point where a graph or a curve intersects the y-axis.3. y-coordinate: The vertical component of a point's location on a coordinate plane.4. y-variable: A variable commonly used to represent the vertical axis or the output in a mathematical equation or function.5. y=mx+b: The equation of a straight line in slope-intercept form, where m represents the slope and b represents the y-intercept.Z1. Zero: The number denoted by 0, often used as a placeholder or a starting point in the number system.2. Zero Pair: A pair of numbers that add up to zero when combined, often used in integer addition and subtraction.3. Zero Product Property: The property that states if the product of two or more factors is zero, then at least one of the factors must be zero.4. Zero Slope: A line that is horizontal and has a slope of 0.5. Zeroth Power: The exponent of 0, which always equals 1.Conclusion:This comprehensive English dictionary of mathematical terms provides an extensive list of vocabulary essential for understanding and communicating mathematical concepts. With the knowledge of these terms, readers can enhance their mathematical fluency and explore various branches of mathematics with greater confidence. Remember, mathematics is not just about numbers, but also about understanding the language that describes the beauty and intricacies of the subject.。

英语听课笔记范文10篇试卷讲解Lecture Notes Template 1。

Title: Introduction to Artificial Intelligence.Lecturer: Dr. Emily Jones.Date: September 5, 2023。

Key Concepts:Artificial Intelligence (AI): The science of creating intelligent machines that can perform tasks typically requiring human intelligence.Machine Learning (ML): A subset of AI that allows computers to learn from data without explicit programming.Deep Learning (DL): A type of ML that uses artificial neural networks to process data and make predictions.Natural Language Processing (NLP): A field of AI focused on enabling computers to understand and generate human language.Computer Vision (CV): A field of AI that enables computers to analyze and understand images and videos.Lecture Outline:I. What is AI?Definition, scope, and applications.II. Types of AI.Narrow AI vs. General AI.Symbolic AI vs. Statistical AI.III. Machine Learning.Supervised, unsupervised, and reinforcement learning.Algorithms and techniques.IV. Deep Learning.Artificial neural networks.CNNs, RNNs, and LSTMs.V. NLP and CV.Text processing, machine translation, speech recognition.Image classification, object detection, facial recognition.Key Takeaways:AI is a rapidly growing field with the potential torevolutionize many industries.Machine learning and deep learning are fundamental techniques in AI.NLP and CV enable computers to interact with humans and the world in a more meaningful way.Lecture Notes Template 2。

Introduction to Algorithms September 24, 2004Massachusetts Institute of Technology 6.046J/18.410J Professors Piotr Indyk and Charles E. Leiserson Handout 7Problem Set 1 SolutionsExercise 1-1. Do Exercise 2.3-7 on page 37 in CLRS.Solution:The following algorithm solves the problem:1.Sort the elements in S using mergesort.2.Remove the last element from S. Let y be the value of the removed element.3.If S is nonempty, look for z=x−y in S using binary search.4.If S contains such an element z, then STOP, since we have found y and z such that x=y+z.Otherwise, repeat Step 2.5.If S is empty, then no two elements in S sum to x.Notice that when we consider an element y i of S during i th iteration, we don’t need to look at the elements that have already been considered in previous iterations. Suppose there exists y j∗S, such that x=y i+y j. If j<i, i.e. if y j has been reached prior to y i, then we would have found y i when we were searching for x−y j during j th iteration and the algorithm would have terminated then.Step 1 takes �(n lg n)time. Step 2 takes O(1)time. Step 3 requires at most lg n time. Steps 2–4 are repeated at most n times. Thus, the total running time of this algorithm is �(n lg n). We can do a more precise analysis if we notice that Step 3 actually requires �(lg(n−i))time at i th iteration.However, if we evaluate �n−1lg(n−i), we get lg(n−1)!, which is �(n lg n). So the total runningi=1time is still �(n lg n).Exercise 1-2. Do Exercise 3.1-3 on page 50 in CLRS.Exercise 1-3. Do Exercise 3.2-6 on page 57 in CLRS.Exercise 1-4. Do Problem 3-2 on page 58 of CLRS.Problem 1-1. Properties of Asymptotic NotationProve or disprove each of the following properties related to asymptotic notation. In each of the following assume that f, g, and h are asymptotically nonnegative functions.� (a) f (n ) = O (g (n )) and g (n ) = O (f (n )) implies that f (n ) = �(g (n )).Solution:This Statement is True.Since f (n ) = O (g (n )), then there exists an n 0 and a c such that for all n √ n 0, f (n ) ←Similarly, since g (n )= O (f (n )), there exists an n � 0 and a c such that for allcg (n ). �f (n ). Therefore, for all n √ max(n 0,n Hence, f (n ) = �(g (n )).�()g n ,0← �),0c 1 � g (n ) ← f (n ) ← cg (n ).n √ n c � 0 (b) f (n ) + g (n ) = �(max(f (n ),g (n ))).Solution:This Statement is True.For all n √ 1, f (n ) ← max(f (n ),g (n )) and g (n ) ← max(f (n ),g (n )). Therefore:f (n ) +g (n ) ← max(f (n ),g (n )) + max(f (n ),g (n )) ← 2 max(f (n ),g (n ))and so f (n ) + g (n )= O (max(f (n ),g (n ))). Additionally, for each n , either f (n ) √max(f (n ),g (n )) or else g (n ) √ max(f (n ),g (n )). Therefore, for all n √ 1, f (n ) + g (n ) √ max(f (n ),g (n )) and so f (n ) + g (n ) = �(max(f (n ),g (n ))). Thus, f (n ) + g (n ) = �(max(f (n ),g (n ))).(c) Transitivity: f (n ) = O (g (n )) and g (n ) = O (h (n )) implies that f (n ) = O (h (n )).Solution:This Statement is True.Since f (n )= O (g (n )), then there exists an n 0 and a c such that for all n √ n 0, �)f ()n ,0← �()g n ,0← f (n ) ← cg (n ). Similarly, since g (n ) = O (h (n )), there exists an n �h (n ). Therefore, for all n √ max(n 0,n and a c � such thatfor all n √ n Hence, f (n ) = O (h (n )).cc�h (n ).c (d) f (n ) = O (g (n )) implies that h (f (n )) = O (h (g (n )).Solution:This Statement is False.We disprove this statement by giving a counter-example. Let f (n ) = n and g (n ) = 3n and h (n )=2n . Then h (f (n )) = 2n and h (g (n )) = 8n . Since 2n is not O (8n ), this choice of f , g and h is a counter-example which disproves the theorem.(e) f(n)+o(f(n))=�(f(n)).Solution:This Statement is True.Let h(n)=o(f(n)). We prove that f(n)+o(f(n))=�(f(n)). Since for all n√1, f(n)+h(n)√f(n), then f(n)+h(n)=�(f(n)).Since h(n)=o(f(n)), then there exists an n0such that for all n>n0, h(n)←f(n).Therefore, for all n>n0, f(n)+h(n)←2f(n)and so f(n)+h(n)=O(f(n)).Thus, f(n)+h(n)=�(f(n)).(f) f(n)=o(g(n))and g(n)=o(f(n))implies f(n)=�(g(n)).Solution:This Statement is False.We disprove this statement by giving a counter-example. Consider f(n)=1+cos(�≈n)and g(n)=1−cos(�≈n).For all even values of n, f(n)=2and g(n)=0, and there does not exist a c1for which f(n)←c1g(n). Thus, f(n)is not o(g(n)), because if there does not exist a c1 for which f(n)←c1g(n), then it cannot be the case that for any c1>0and sufficiently large n, f(n)<c1g(n).For all odd values of n, f(n)=0and g(n)=2, and there does not exist a c for which g(n)←cf(n). By the above reasoning, it follows that g(n)is not o(f(n)). Also, there cannot exist c2>0for which c2g(n)←f(n), because we could set c=1/c2if sucha c2existed.We have shown that there do not exist constants c1>0and c2>0such that c2g(n)←f(n)←c1g(n). Thus, f(n)is not �(g(n)).Problem 1-2. Computing Fibonacci NumbersThe Fibonacci numbers are defined on page 56 of CLRS asF0=0,F1=1,F n=F n−1+F n−2for n√2.In Exercise 1-3, of this problem set, you showed that the n th Fibonacci number isF n=�n−� n,�5where �is the golden ratio and �is its conjugate.A fellow 6.046 student comes to you with the following simple recursive algorithm for computing the n th Fibonacci number.F IB(n)1 if n=02 then return 03 elseif n=14 then return 15 return F IB(n−1)+F IB(n−2)This algorithm is correct, since it directly implements the definition of the Fibonacci numbers. Let’s analyze its running time. Let T(n)be the worst-case running time of F IB(n).1(a) Give a recurrence for T(n), and use the substitution method to show that T(n)=O(F n).Solution: The recurrence is: T(n)=T(n−1)+T(n−2)+1.We use the substitution method, inducting on n. Our Induction Hypothesis is: T(n)←cF n−b.To prove the inductive step:T(n)←cF n−1+cF n−2−b−b+1← cF n−2b+1Therefore, T(n)←cF n−b+1provided that b√1. We choose b=2and c=10.∗{For the base case consider n0,1}and note the running time is no more than10−2=8.(b) Similarly, show that T(n)=�(F n), and hence, that T(n)=�(F n).Solution: Again the recurrence is: T(n)=T(n−1)+T(n−2)+1.We use the substitution method, inducting on n. Our Induction Hypothesis is: T(n)√F n.To prove the inductive step:T(n)√F n−1+F n−2+1√F n+1Therefore, T(n)←F n. For the base case consider n∗{0,1}and note the runningtime is no less than 1.1In this problem, please assume that all operations take unit time. In reality, the time it takes to add two num­bers depends on the number of bits in the numbers being added (more precisely, on the number of memory words). However, for the purpose of this problem, the approximation of unit time addition will suffice.Professor Grigori Potemkin has recently published an improved algorithm for computing the n th Fibonacci number which uses a cleverly constructed loop to get rid of one of the recursive calls. Professor Potemkin has staked his reputation on this new algorithm, and his tenure committee has asked you to review his algorithm.F IB�(n)1 if n=02 then return 03 elseif n=14 then return 15 6 7 8 sum �1for k�1to n−2do sum �sum +F IB�(k) return sumSince it is not at all clear that this algorithm actually computes the n th Fibonacci number, let’s prove that the algorithm is correct. We’ll prove this by induction over n, using a loop invariant in the inductive step of the proof.(c) State the induction hypothesis and the base case of your correctness proof.Solution: To prove the algorithm is correct, we are inducting on n. Our inductionhypothesis is that for all n<m, Fib�(n)returns F n, the n th Fibonacci number.Our base case is m=2. We observe that the first four lines of Potemkin guaranteethat Fib�(n)returns the correct value when n<2.(d) State a loop invariant for the loop in lines 6-7. Prove, using induction over k, that your“invariant” is indeed invariant.Solution: Our loop invariant is that after the k=i iteration of the loop,sum=F i+2.We prove this induction using induction over k. We assume that after the k=(i−1)iteration of the loop, sum=F i+1. Our base case is i=1. We observe that after thefirst pass through the loop, sum=2which is the 3rd Fibonacci number.To complete the induction step we observe that if sum=F i+1after the k=(i−1)andif the call to F ib�(i)on Line 7 correctly returns F i(by the induction hypothesis of ourcorrectness proof in the previous part of the problem) then after the k=i iteration ofthe loop sum=F i+2. This follows immediately form the fact that F i+F i+1=F i+2.(e) Use your loop invariant to complete the inductive step of your correctness proof.Solution: To complete the inductive step of our correctness proof, we must show thatif F ib�(n)returns F n for all n<m then F ib�(m)returns m. From the previous partwe know that if F ib�(n)returns F n for all n<m, then at the end of the k=i iterationof the loop sum=F i+2. We can thus conclude that after the k=m−2iteration ofthe loop, sum=F m which completes our correctness proof.(f) What is the asymptotic running time, T�(n), of F IB�(n)? Would you recommendtenure for Professor Potemkin?Solution: We will argue that T�(n)=�(F n)and thus that Potemkin’s algorithm,F ib�does not improve upon the assymptotic performance of the simple recurrsivealgorithm, F ib. Therefore we would not recommend tenure for Professor Potemkin.One way to see that T�(n)=�(F n)is to observe that the only constant in the programis the 1 (in lines 5 and 4). That is, in order for the program to return F n lines 5 and 4must be executed a total of F n times.Another way to see that T�(n)=�(F n)is to use the substitution method with thehypothesis T�(n)√F n and the recurrence T�(n)=cn+�n−2T�(k).k=1Problem 1-3. Polynomial multiplicationOne can represent a polynomial, in a symbolic variable x, with degree-bound n as an array P[0..n] of coefficients. Consider two linear polynomials, A(x)=a1x+a0and B(x)=b1x+b0, where a1, a0, b1, and b0are numerical coefficients, which can be represented by the arrays [a0,a1]and [b0,b1], respectively. We can multiply A and B using the four coefficient multiplicationsm1=a1·b1,m2=a1·b0,m3=a0·b1,m4=a0·b0,as well as one numerical addition, to form the polynomialC(x)=m1x2+(m2+m3)x+m4,which can be represented by the array[c0,c1,c2]=[m4,m3+m2,m1].(a) Give a divide-and-conquer algorithm for multiplying two polynomials of degree-bound n,represented as coefficient arrays, based on this formula.Solution:We can use this idea to recursively multiply polynomials of degree n−1, where n isa power of 2, as follows:Let p(x)and q(x)be polynomials of degree n−1, and divide each into the upper n/2 and lower n/2terms:p(x)=a(x)x n/2+b(x),q(x)=c(x)x n/2+d(x),where a(x), b(x), c(x), and d(x)are polynomials of degree n/2−1. The polynomial product is thenp(x)q(x)=(a(x)x n/2+b(x))(c(x)x n/2+d(x))=a(x)c(x)x n+(a(x)d(x)+b(x)c(x))x n/2+b(x)d(x).The four polynomial products a(x)c(x), a(x)d(x), b(x)c(x), and b(x)d(x)are com­puted recursively.(b) Give and solve a recurrence for the worst-case running time of your algorithm.Solution:Since we can perform the dividing and combining of polynomials in time �(n), re­cursive polynomial multiplication gives us a running time ofT(n)=4T(n/2)+�(n)=�(n2).(c) Show how to multiply two linear polynomials A(x)=a1x+a0and B(x)=b1x+b0using only three coefficient multiplications.Solution:We can use the following 3 multiplications:m1=(a+b)(c+d)=ac+ad+bc+bd,m2=ac,m3=bd,so the polynomial product is(ax+b)(cx+d)=m2x2+(m1−m2−m3)x+m3.� (d) Give a divide-and-conquer algorithm for multiplying two polynomials of degree-bound nbased on your formula from part (c).Solution:The algorithm is the same as in part (a), except for the fact that we need only compute three products of polynomials of degree n/2 to get the polynomial product.(e) Give and solve a recurrence for the worst-case running time of your algorithm.Solution:Similar to part (b):T (n )=3T (n/2) + �(n )lg 3)= �(n �(n 1.585)Alternative solution Instead of breaking a polynomial p (x ) into two smaller poly­nomials a (x ) and b (x ) such that p (x )= a (x ) + x n/2b (x ), as we did above, we could do the following:Collect all the even powers of p (x ) and substitute y = x 2 to create the polynomial a (y ). Then collect all the odd powers of p (x ), factor out x and substitute y = x 2 to create the second polynomial b (y ). Then we can see thatp (x ) = a (y ) + x b (y )· Both a (y ) and b (y ) are polynomials of (roughly) half the original size and degree, and we can proceed with our multiplications in a way analogous to what was done above.Notice that, at each level k , we need to compute y k = y 2 (where y 0 = x ), whichk −1 takes time �(1) per level and does not affect the asymptotic running time.。