Effective Considerations in Algorithm Design and Analysis
In the realm of algorithm design, ensuring correctness, feasibility, efficiency, and the quest for improvements are pivotal concerns. This involves writing programs that humans can comprehend and implement accurately. Checking the equality of polynomials serves as an illustrative example emphasizing the importance of correct and efficient algorithms. The need for continuous improvement and the balance between these fundamental aspects shape the landscape of algorithm programming.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 2: Correctness, feasibility, efficiency, improvements
Introduction Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. Algorithm Program ? Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. Algorithm Program ? Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction \\ check if two polynomials are the same EQUAl(P(x), Q(x)) 1. determine the degree n of P and Q; 2. pick n+1 different numbers x0, , xn; Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. 3. if (P(xh) == Q(xh)) for all h then return ( yes ); else return ( no ). Algorithm Program ? Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction \\ check if two polynomials are the same EQUAl(P(x), Q(x)) 1. determine the degree n of P and Q; 2. pick n+1 different numbers x0, , xn; Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. 3. if (P(xh) == Q(xh)) for all h then return ( yes ); else return ( no ). Algorithm Program difficult problem, far from being solved. ? Checking algorithm/program correctness is an extremely Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. Algorithm Program ? Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction \\ check if an integer n is a prime PRIME(n) 1.for (i = 2; i++; i < n) Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. if (i divides n) return ( no ); 2. Return ( yes ). Algorithm Program ? Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction \\ check if an integer n is a prime PRIME(n) 1.for (i = 2; i++; i < n) Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. if (i divides n) return ( no ); 2. Return ( yes ). Algorithm Program bits). While time of order 2100 is totally infeasible for computers ? The integer n in practice can be very large (several hundred Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. Algorithm Program ? Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction \\ searching in bigdata SEARCH(T[n], P[m]) 1. for (i = 0; i++; i < n-m+1) Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. if (T[i, i+m-1] == P[m]) return (i); 2. Return ( no match ). Algorithm Program ? Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction \\ searching in bigdata SEARCH(T[n], P[m]) 1. for (i = 0; i++; i < n-m+1) Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. if (T[i, i+m-1] == P[m]) return (i); 2. Return ( no match ). Algorithm Program in kilobytes), the time of order n m steps can be days or weeks. ? When n is large (e.g. in terabytes) and m is not too small (e.g., Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. Algorithm Program ? Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction \\ check if two polynomials are the same EQUAl(P(x), Q(x)) 1. determine the degree n of P and Q; 2. pick n+1 different numbers x0, , xn; Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. 3. if (P(xh) == Q(xh)) for all h then return ( yes ); else return ( no ). Algorithm Program ? Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction \\ check if two polynomials are the same EQUAl(P(x), Q(x)) 1. randomly pick a number x*; 2. if (P(x*) == Q(x*)) then return ( yes ); else return ( no ). \\ check if two polynomials are the same EQUAl(P(x), Q(x)) 1. determine the degree n of P and Q; 2. pick n+1 different numbers x0, , xn; Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. 3. if (P(xh) == Q(xh)) for all h then return ( yes ); else return ( no ). Algorithm Program ? Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction \\ check if two polynomials are the same EQUAl(P(x), Q(x)) 1. randomly pick a number x*; 2. if (P(x*) == Q(x*)) then return ( yes ); else return ( no ). \\ check if two polynomials are the same EQUAl(P(x), Q(x)) 1. determine the degree n of P and Q; 2. pick n+1 different numbers x0, , xn; Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. 3. if (P(xh) == Q(xh)) for all h then return ( yes ); else return ( no ). Algorithm Program unlikely that a randomly picked number is a root. ? A polynomial has only finitely many roots. Thus, it is very Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction \\ check if an integer n is a prime PRIME(n) 1.for (i = 2; i++; i < n) Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. if (i divides n) return ( no ); 2. Return ( yes ). Algorithm Program ? Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction \\ check if an integer n is a prime PRIME(n) 1.for (i = 2; i++; i < ?) if (i divides n) return ( no ); 2. Return ( yes ). \\ check if an integer n is a prime PRIME(n) 1.for (i = 2; i++; i < n) Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. if (i divides n) return ( no ); 2. Return ( yes ). Algorithm Program ? Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction \\ check if an integer n is a prime PRIME(n) 1.for (i = 2; i++; i < ?) if (i divides n) return ( no ); 2. Return ( yes ). \\ check if an integer n is a prime PRIME(n) 1.for (i = 2; i++; i < n) Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. if (i divides n) return ( no ); 2. Return ( yes ). Algorithm Program ? If n is not a prime, one of its factors is not larger than ?. Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction \\ check if an integer n is a prime PRIME(n) 1.for (i = 2; i++; i < ?) if (i divides n) return ( no ); 2. Return ( yes ). \\ check if an integer n is a prime PRIME(n) 1.for (i = 2; i++; i < n) Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. if (i divides n) return ( no ); 2. Return ( yes ). Algorithm Program Actually, there are much faster algorithms for the problem ? If n is not a prime, one of its factors is not larger than ?. Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction \\ searching in bigdata SEARCH(T[n], P[m]) 1. for (i = 0; i++; i < n-m+1) Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. if (T[i, i+m-1] == P[m]) return (i); 2. Return ( no match ). Algorithm Program in kilobytes), the time of order n m steps can be days or weeks. ? When n is large (e.g. in terabytes) and m is not too small (e.g., Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction There is a search algorithm that runs in about n+m steps. \\ searching in bigdata SEARCH(T[n], P[m]) 1. for (i = 0; i++; i < n-m+1) Algorithms are programs written in languages that humans can naturally understand and precisely implement, so that we can concentrate on the critical steps in design and analysis. if (T[i, i+m-1] == P[m]) return (i); 2. Return ( no match ). Algorithm Program in kilobytes), the time of order n m steps can be days or weeks. ? When n is large (e.g. in terabytes) and m is not too small (e.g., Major Concerns Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
Introduction CSCE-411 Design and Analysis of Algorithms This is all we want to do in this course Design and analysis techniques for algorithms Correctness: is the program correct? Feasibility: can the program be used? Efficiency: is the program fast? Improvement: is there a faster program?
O-Notation \\ searching in bigdata SEARCH(T[n], P[m]) 1. for (i = 0; i++; i < n-m+1) if (T[i, i+m-1] == P[m]) return (i); 2. Return ( no match ).
O-Notation How many steps? \\ searching in bigdata SEARCH(T[n], P[m]) 1. for (i = 0; i++; i < n-m+1) if (T[i, i+m-1] == P[m]) return (i); 2. Return ( no match ).
O-Notation How many steps? \\ searching in bigdata SEARCH(T[n], P[m]) 1. for (i = 0; i++; i < n-m+1) if (T[i, i+m-1] == P[m]) return (i); 2. Return ( no match ). m steps, each step takes constant number c1 of basic operations.
O-Notation How many steps? \\ searching in bigdata SEARCH(T[n], P[m]) 1. for (i = 0; i++; i < n-m+1) if (T[i, i+m-1] == P[m]) return (i); 2. Return ( no match ). How many times? m steps, each step takes constant number c1 of basic operations.
O-Notation How many steps? \\ searching in bigdata SEARCH(T[n], P[m]) 1. for (i = 0; i++; i < n-m+1) if (T[i, i+m-1] == P[m]) return (i); 2. Return ( no match ). How many times? m steps, each step takes constant number c1 of basic operations. At most n-m+1 times Besides T[i, i+m-1] == P[m])", each time takes constant number c2 of basic operations.
O-Notation How many steps? \\ searching in bigdata SEARCH(T[n], P[m]) 1. for (i = 0; i++; i < n-m+1) if (T[i, i+m-1] == P[m]) return (i); 2. Return ( no match ). How many times? m steps, each step takes constant number c1 of basic operations. At most n-m+1 times Besides T[i, i+m-1] == P[m])", each time takes constant number c2 of basic operations. Constant number: a number that does not depend on the input length.
O-Notation How many steps? \\ searching in bigdata SEARCH(T[n], P[m]) 1. for (i = 0; i++; i < n-m+1) if (T[i, i+m-1] == P[m]) return (i); 2. Return ( no match ). How many times? m steps, each step takes constant number c1 of basic operations. At most n-m+1 times Besides T[i, i+m-1] == P[m])", each time takes constant number c2 of basic operations. Constant number: a number that does not depend on the input length. Thus, each execution of the for-loop takes at most c1m+c2 c3m basic operations.
O-Notation How many steps? \\ searching in bigdata SEARCH(T[n], P[m]) 1. for (i = 0; i++; i < n-m+1) if (T[i, i+m-1] == P[m]) return (i); 2. Return ( no match ). How many times? m steps, each step takes constant number c1 of basic operations. When we do not know the exact value, we consider the worst case. At most n-m+1 times Besides T[i, i+m-1] == P[m])", each time takes constant number c2 of basic operations. Constant number: a number that does not depend on the input length. Thus, each execution of the for-loop takes at most c1m+c2 c3m basic operations.
O-Notation How many steps? \\ searching in bigdata SEARCH(T[n], P[m]) 1. for (i = 0; i++; i < n-m+1) if (T[i, i+m-1] == P[m]) return (i); 2. Return ( no match ). How many times? m steps, each step takes constant number c1 of basic operations. When we do not know the exact value, we consider the worst case. At most n-m+1 times Thus, the algorithm SEARCH(T[n], P[m]) takes (n-m+1) c3m + c4 c5 n m basic operations (i.e., steps) Besides T[i, i+m-1] == P[m])", each time takes constant number c2 of basic operations. Constant number: a number that does not depend on the input length. Thus, each execution of the for-loop takes at most c1m+c2 c3m basic operations.
O-Notation How many steps? \\ searching in bigdata SEARCH(T[n], P[m]) 1. for (i = 0; i++; i < n-m+1) if (T[i, i+m-1] == P[m]) return (i); 2. Return ( no match ). How many times? m steps, each step takes constant number c1 of basic operations. When we do not know the exact value, we consider the worst case. At most n-m+1 times Thus, the algorithm SEARCH(T[n], P[m]) takes (n-m+1) c3m + c4 c5 n m basic operations (i.e., steps) Besides T[i, i+m-1] == P[m])", each time takes constant number c2 of basic operations. Constant number: a number that does not depend on the input length. Instead of computing the exact number of steps of an algorithm, we compute the order of the number of steps. Thus, each execution of the for-loop takes at most c1m+c2 c3m basic operations.
O-Notation Definition. Let f(n), g(n) be functions. We say that f(n) = O(g(n)) if there is a constant c such that f(n) c g(n) for all n 1.
O-Notation Definition. Let f(n), g(n) be functions. We say that f(n) = O(g(n)) if there is a constant c such that f(n) c g(n) for all n 1.
O-Notation Definition. Let f(n), g(n) be functions. We say that f(n) = O(g(n)) if there is a constant c such that f(n) c g(n) for all n 1. sufficiently large
O-Notation Definition. Let f(n), g(n) be functions. We say that f(n) = O(g(n)) if there is a constant c such that f(n) c g(n) for all n 1. sufficiently large e.g., f(n) = n+1000, g(n) = n2
O-Notation Definition. Let f(n), g(n) be functions. We say that f(n) = O(g(n)) if there is a constant c such that f(n) c g(n) for all n 1. sufficiently large e.g., f(n) = n+1000, g(n) = n2 Example. We say that an algorithm runs in time O(n2) if there is a constant c, such that for all n, the algorithm on inputs of length n runs in at most c n2 steps.
O-Notation Definition. Let f(n), g(n) be functions. We say that f(n) = O(g(n)) if there is a constant c such that f(n) c g(n) for all n 1. sufficiently large e.g., f(n) = n+1000, g(n) = n2 Example. We say that an algorithm runs in time O(n2) if there is a constant c, such that for all n, the algorithm on inputs of length n runs in at most c n2 steps. Discussion. Precisely, O(g(n)) is a set of functions: for each h(n) in O(g(n)), there is a c such that h(n) c g(n) for all n 1.
O-Notation Definition. Let f(n), g(n) be functions. We say that f(n) = O(g(n)) if there is a constant c such that f(n) c g(n) for all n 1. sufficiently large e.g., f(n) = n+1000, g(n) = n2 Example. We say that an algorithm runs in time O(n2) if there is a constant c, such that for all n, the algorithm on inputs of length n runs in at most c n2 steps. Discussion. Precisely, O(g(n)) is a set of functions: for each h(n) in O(g(n)), there is a c such that h(n) c g(n) for all n 1. By f(n) is O(g(n)) or f(n) = O(g(n)) , we really mean f(n) is in O(g(n)) .
O-Notation Definition. Let f(n), g(n) be functions. We say that f(n) = O(g(n)) if there is a constant c such that f(n) c g(n) for all n 1. sufficiently large e.g., f(n) = n+1000, g(n) = n2 Example. We say that an algorithm runs in time O(n2) if there is a constant c, such that for all n, the algorithm on inputs of length n runs in at most c n2 steps. Discussion. Precisely, O(g(n)) is a set of functions: for each h(n) in O(g(n)), there is a c such that h(n) c g(n) for all n 1. By f(n) is O(g(n)) or f(n) = O(g(n)) , we really mean f(n) is in O(g(n)) . Example. 1 log?, (2) n log?, (3) 1000n2, (4) 10n2+1000n log?+ ? are all (in) O(n2).
O-Notation Definition. Let f(n), g(n) be functions. We say that f(n) = O(g(n)) if there is a constant c such that f(n) c g(n) for all n 1. sufficiently large e.g., f(n) = n+1000, g(n) = n2 Example. We say that an algorithm runs in time O(n2) if there is a constant c, such that for all n, the algorithm on inputs of length n runs in at most c n2 steps. Discussion. Precisely, O(g(n)) is a set of functions: for each h(n) in O(g(n)), there is a c such that h(n) c g(n) for all n 1. By f(n) is O(g(n)) or f(n) = O(g(n)) , we really mean f(n) is in O(g(n)) . Example. 1 log?, (2) n log?, (3) 1000n2, (4) 10n2+1000n log?+ ? are all (in) O(n2). Notational Conventions. O(n) = O(n2) O(n log? + ?) = O(n2)
O-Notation Definition. Let f(n), g(n) be functions. We say that f(n) = O(g(n)) if there is a constant c such that f(n) c g(n) for all n 1. sufficiently large e.g., f(n) = n+1000, g(n) = n2 Example. We say that an algorithm runs in time O(n2) if there is a constant c, such that for all n, the algorithm on inputs of length n runs in at most c n2 steps. Discussion. Precisely, O(g(n)) is a set of functions: for each h(n) in O(g(n)), there is a c such that h(n) c g(n) for all n 1. By f(n) is O(g(n)) or f(n) = O(g(n)) , we really mean f(n) is in O(g(n)) . Example. 1 log?, (2) n log?, (3) 1000n2, (4) 10n2+1000n log?+ ? are all (in) O(n2). Notational Conventions. O(n) = O(n2) O(n log? + ?) = O(n2) But not O(n2) = O(n) !!!
