程序代写代做代考 C case study algorithm graph Algorithms Week 1

Algorithms Week 1
Ljubomir Perkovi ́c, DePaul University

Course overview
We will cover techniques for designing computer algorithms, including:
• divide-and-conquer
• backtracking
• dynamic programming • greedy
We will later use graph algorithms as a case study.
Throughout, we will also make use of techniques for analyzing computer algorithms and problems including, towards the end of the course, the theory of NP-completeness.

Course mechanics
See the course web site https://reed.cs.depaul.edu/lperkovic/courses/csc421
• Find there the course syllabus
• My weekly lecture slides and video recordings will be posted there on Mondays
I will hold optional, recorded Zoom discussion sessions to discuss the week’s topics on Wednesdays
• The discussion session recording will be posted on the course web site
• The weekly homework assignment will be posted on Wednesday as well
• The homework assignment will be due the following Wednesday
A final exam will be given at the end of the course.

Contact
Discussion sessions: Wed, 7:30pm-9:00pm CT, Zoom meeting link in D2L
Office hours: Mon, 3:00pm-4:30pm and 7:30pm-9:00pm, Zoom meeting link in D2L
Discussion forum: Discord server link in D2L E-mail: lperkovic@cs.depaul.edu
Phone: 312-362-8337 (leave a message)

Algorithms
An algorithm is a step-by-step procedure for solving a problem • Typically developed before doing any programming
• In fact, it is independent of any programming language
Efficient algorithms can have a dramatic effect on our problem-solving capabilities

Algorithm design concerns
The issues that will concern us when developing algorithms:

Algorithm design concerns
The issues that will concern us when developing algorithms:
1 Problem specification – Is the problem clearly and precisely stated?

Algorithm design concerns
The issues that will concern us when developing algorithms:
1 Problem specification – Is the problem clearly and precisely stated?
2 Simplicity and clarity – Is the algorithm clear? Is there a simpler and clearer algorithm?
3 Algorithm correctness – Is the algorithm correct?
4 Amount of work done – What is the running time of the algorithm in terms of the input size (independent of hardware and programming language)?
5 (Sometimes) amount of space used – How much extra memory space does the algorithm use (here we mean the amount of extra space beyond the size of the input). We will say that an algorithm is in place if the amount of extra space is constant with respect to input size.

Polynomial evaluation
We consider the problem of evaluating a polynomial. A precise specification of the problem would be:
Input:
Output: Example:
A polynomial p(x) = a0 + a1x + a2x2 + … + anxn and a value z. We assume the coefficient are stored in an array a[0..n].
The evaluation of p(x) at z, i.e. p(z).
Iftheinputisp(x)=x2+2x+1andz=3thenthe output should be p(3) = 16

Naive solution
We assume that the coefficients a0, a1, a2, . . . , an are stored in an array a[0..n] of size n + 1.
NaiveEvaluation(a, n, z) res ← 0
for i ← 0 to n
zpoweri ← 1 for j ← 1 to i
zpoweri ← zpoweri * z res ← res + a[i] * zpoweri
return res

Running time analysis
What do we mean by time?
Suppose that we mean the number of lines of pseudocode executed. The question is still imprecise, as the answer will depend on the size of the input.
Let us denote the size of the input by n.
The problem is then to determine the number of lines T(n)
executed by our algorithm on a polynomial of degree n. The number of lines executed is
nn
2+􏰀(3+2i) = 2􏰀i +3(n+1)+2 i=0 i=0
= n2+4n+5

Naive solution
NaiveEvaluation(a, n, z) res ← 0
for i ← 0 to n
zpoweri ← 1 for j ← 1 to i
zpoweri ← zpoweri * z res ← res + a[i] * zpoweri
return res

More efficient solution
BetterEvaluation(a, n, z) res ← 0
zpoweri ← 1
for i ← 0 to n
res ← res + a[i] * zpoweri
zpoweri ← zpoweri * z return res

More efficient solution
BetterEvaluation(a, n, z) res ← 0
zpoweri ← 1
for i ← 0 to n
res ← res + a[i] * zpoweri
zpoweri ← zpoweri * z return res
The number of lines executed is
n
3 + 􏰀 3 = 3n + 6 i=0

Running time comparison
500
400
300 T(n)
200 100 0
0 5 10 15 20
n
Note that the comparison of the two functions boils down to the a comparison of the two functions’ growth rates
n2 +4n+5
3n + 6

Asymptotic notation
Consider the function T (n) = n2 + 4n + 5 that we produced as the running time of the naive polynomial evaluation algorithm.
We can approximate the behavior of an algorithm by considering only the highest order term in the function T(n). This is because as the size of the problem gets larger, the fastest growing term represents the corresponding growth of the running time.
In this course we will only be interested in this asymptotic behavior of algorithms. This motivates us to define a notation that will make the analysis of algorithms simpler.

Big-O notation
We will be interested in three types of asymptotic behavior.
O notation is used to bound the asymptotic behavior of a function from above (upper bound).
Definition
Let f and g be (non-negative) functions. If there exist positive constants c and n0 such that f (n) ≤ cg(n) for all n ≥ n0 then we say that f (n) is O(g(n)), typically denoted by f (n) = O(g(n)).
• Does this mean that f (n) is always ≤ g (n)? No! • Does it mean that f (n) is always ≤ cg (n)?

Example
Consider the function T (n) = n2 + 4n + 5 that we produced as the running time of the naive polynomial evaluation algorithm.
Claim
T(n) = O(n2)
Proof.
Choosec=10andn0 =1. Weverifythatforalln≥1, n2 + 4n + 5 ≤ 10n2:
n2+4n+5 ≤ n2+4n2+5n2 (sincen≥1) ≤ 10n2

Example
Consider the function T (n) = 3n + 6 that we produced as the running time of the better polynomial evaluation algorithm.
Claim
T(n) = O(n)
Proof.
Choosec=9andn0 =1. Weverifythatforalln≥1, 3n + 6 ≤ 9n:
3n+6 ≤ 3n+6n(sincen≥1) ≤ 9n

Example
Consider the function T (n) = 3n + 6 that we produced as the running time of the better polynomial evaluation algorithm.
Claim
T(n) = O(n2)
Proof.
Left as an exercise

Example
Consider again the function T (n) = n2 + 4n + 5 that we produced as the running time of the naive polynomial evaluation algorithm.
Claim
T(n) = O(n)

Example
Consider again the function T (n) = n2 + 4n + 5 that we produced as the running time of the naive polynomial evaluation algorithm.
Claim
T(n) = O(n)
No, that is not true!
If it were true, it would mean that there exist positive constants c
andn0 suchthatn2+4n+5≤cnforalln≥n0.
However, when n ≥ c then n2 + 4n + 5 ≥ cn + 4n + 5 > cn
So, for n ≥ max{n0, c} we get that n2 + 4n + 5 ≤ cn and that n2 + 4n + 5 > cn which is a contradiction

Big-Omega
Ω notation is used to bound the asymptotic behavior of a function from below (lower bound).
Definition
Let f and g be (non-negative) functions. If there exist positive constants c and n0 such that f (n) ≥ cg(n) for all n ≥ n0 then we say that f (n) is Ω(g (n)), denoted by f (n) = Ω(g (n)).
It means that f (n) is eventually ≥ cg (n).

Example
Consider again the function T (n) = n2 + 4n + 5 that we produced as the running time of the naive polynomial evaluation algorithm.
Claim
T(n) = Ω(n2).
Proof.
Choosec=1andn0 =1. Weeasilyverifythatforalln≥1 n2 + 4n + 5 ≥ n2
So T(n) = O(n2) and T(n) = Ω(n2)

Big-Theta
Θ notation is used to capture exactly the asymptotic behavior of a function
Definition
Let f and g be (non-negative) functions. If there exist positive constants c1, c2 and n0 such that for all n ≥ n0,
c1g(n) ≤ f (n) ≤ c2g(n) then we say that that f (n) is Θ(g(n)), denoted f (n) = Θ(g (n)).
In other words,
f (n) = Θ(g(n)) if and only if f (n) = O(g(n) and f (n) = Ω(g(n)),
and g(n) is said to be an asymptotically tight bound on the function f(n)

Properties
Claim (Transitivity)
If f (n) = O(g(n)) and g(n) = O(h(n)) then f (n) = O(h(n)).
Note: This also holds for Ω and Θ.
Proof.
Iff(n)=O(g(n))thenthereexistc1,n1 s.t. foralln≥n1, f (n) ≤ c1g(n).
If g(n) = O(h(n)) then there exist c2,n2 s.t. for all n ≥ n2, g(n) ≤ c2h(n).
Letn3=max{n1,n2}andletc3 =c1∗c2. Thenforalln≥n3, f (n) ≤ c1g(n) ≤ c1c2h(n) = c3h(n). Thus f (n) = O(h(n)).

Properties
Claim
If f1(n) = O(g1(n)), f2(n) = O(g2(n)), and g1(n) = O(g2(n)) then f1(n) + f2(n) = O(g2(n))).
The proof is left as a homework problem.
Exercise
Compare the asymptotic growth rates of the following functions: 1,lgn,n,nlgn,n2,2n.

Exercise (cont.)
2n
60
40 T(n)
20
0
n2
nlogn n
log n 1
0123456
n

Optimality
Consider again our algorithm for polynomial evaluation:
BetterEvaluation(a, n, z) res ← 0
zpoweri ← 1
for i ← 0 to n
res ← res + a[i] * zpoweri
zpoweri ← zpoweri * z return res

Horner’s method
By rewriting p(x) as
p(x) = a0 +a1x +a2x2 +…+anxn
= a0 + x(a1 + x(a2 + x(a3 + x(…(an−1 + x(an + 0))…)))) we develop an alternate algorithm:
HornersMethod(a, n, z) res ← 0
for i ←n downto 0
res ← res * z + a[i] output res
The number of lines executed by Horner’s method is
n
2 + 􏰀 2 = 2 + 2(n + 1) = 2n + 4 i=0
which is less than 3n + 6.

Optimality
Consider again our algorithm for polynomial evaluation:
BetterEvaluation(a, n, z) res ← 0
zpoweri ← 1
for i ← 0 to n
res ← res + a[i] * zpoweri
zpoweri ← zpoweri * z return res
Is it optimal?
Horner’s algorithm is clearly better but the running time of both algorithms is O(n)
Because any polynomial evaluation algorithm must run in time Ω(n) (why?), Horner’s and BetterEvaluation algorithms are both asymptotically optimal

Course overview: Describing algorithms
A complete description of any algorithm has four components:
What: How: Why:
How fast:
A precise statement of the problem.
A precise description of the algorithm.
A proof that the algorithm is correct, i.e. it solves the problem it is supposed to solve.
An analysis of the running time of the algorithm, also known as asymptotic analysis.

Sorting
A fundamental problem is sorting an array of numbers. Input: A array a[0..n − 1] of n numbers
Output: A re-ordering of the numbers in the array such that a[0] ≤ a[1] ≤ · · · ≤ a[n − 1]
There are many different ways of approaching the problem
InsertionSort works by repeatedly moving elements into their proper relative positions

InsertionSort
The steps of the algorithm are:
1 Move a[1] to the left until all elements to its left are no greater than it
2 Move a[2] to the left until all elements to its left are no greater than it
3 Repeat up until element a[n − 1]

InsertionSort example
For example, let the input list of numbers be 5, 2, 4, 6, 1, 3. Then the iterations of the algorithm will be the following:
Initial order:
After 1st iteration: After 2nd iteration: After 3rd iteration: After 4th iteration: After 5th iteration:
5 2 2 5 2 4 2 4 1 2 1 2
4 6 4 6 5 6 5 6 4 5 3 4
1 3 1 3 1 3 1 3 6 3 5 6

InsertionSort
If a[0..n-1] is an array of numbers to be sorted, the pseudocode for insertion sort is:
InsertionSort(a, n) for j ← 1 to n-1
key ← a[j]
i ← j-1
while i ≥ 0 and a[i] > key
a[i+1] ← a[i]
i ← i-1 a[i+1] ← key

InsertionSort running time analysis
Because we are only interested in the asymptotic behavior of the algorithm, we need only focus on an operation in the innermost loop, e.g. the while loop condition:
n−1
T(n) = 􏰀􏰀1.
j=1 ?
The first summation counts the number of iterations of the for-loop, and the second summation counts the number of times the while-loop condition is evaluated within a single iteration of the outer for-loop
We know that the for-loop will be executed n − 1 times.
What about the number of times the while-loop condition will be evaluated?

InsertionSort running time analysis
Suppose that the list contains 1 2 3 4 5 6. Then the execution will look like the following:
Initialorder: 1 2 3 4 5 6

InsertionSort running time analysis
Suppose that the list contains 1 2 3 4 5 6. Then the execution will look like the following:
Initialorder: 1 2 3 4 5 6 After 1st iteration: 1 2 3 4 5 6

InsertionSort running time analysis
Suppose that the list contains 1 2 3 4 5 6. Then the execution will look like the following:
Initial order:
After 1st iteration: After 2nd iteration: After 3rd iteration: After 4th iteration: After 5th iteration:
1 2 1 2 1 2 1 2 1 2 1 2
3 4 5 6 3 4 5 6 3 4 5 6 3 4 5 6 3 4 5 6 3 4 5 6

InsertionSort running time analysis
Suppose that the list contains 6 5 4 3 2 1. Then the execution will look like the following:
Initialorder: 6 5 4 3 2 1

InsertionSort running time analysis
Suppose that the list contains 6 5 4 3 2 1. Then the execution will look like the following:
Initialorder: 6 5 4 3 2 1 After 1st iteration: 5 6 4 3 2 1

InsertionSort running time analysis
Suppose that the list contains 6 5 4 3 2 1. Then the execution will look like the following:
Initial order:
After 1st iteration: After 2nd iteration: After 3rd iteration: After 4th iteration: After 5th iteration:
6 5 5 6 4 5 3 4 2 3 1 2
4 3 2 1 4 3 2 1 6 3 2 1 5 6 2 1 4 5 6 1 3 4 5 6
Within iteration j of the outer for-loop, the while-loop condition is evaluated for i = j − 1, j − 2, . . . , 0, i.e. a total of j times. Thus
n−1 n(n − 1)
T(n) = 􏰀j = 2 = O(n2)
j=1

InsertionSort running time analysis
The running time of an algorithm can depend on the type of input it is given. Some inputs are ”harder” than others for an algorithm. There are three different approaches to analyzing running times:
Best-case
This is the minimum number of steps the algorithm can take on an input of size n. It is produced by the inputs on which the algorithm behaves the best. Example 1 is the best case for insertion sort.
This represents the maximum number of steps the algorithm can take on an input of size n. It provides a guarantee of performance. Example 2 is the worst case for insertion sort.
Worst-case

InsertionSort average-case analysis
If we assume that any ordering is equally likely, then we can argue that we expect that each a[j] moves 1 (j − 1) positions to the
2
left. In other words, the number of times the while-loop condition
is evaluated in each iteration of the outer for-loop is 1j. The 2
expected number of steps is then
n−1 1 n(n − 1) T(n)=􏰀 j=
=O(n2)
j=1
24

Course overview: core techniques
Algorithm design techniques that we will use in this class include: 1 divide-and-conquer
2 backtracking
3 dynamic programming
4 greedy
All of the above techniques rely on reductions.

Reductions
As your textbook says:
“Reductions are the single most common technique used in designing algorithms.
Reducing one problem X to another problem Y means to write an algorithm for X that uses an algorithm for Y as a black box or subroutine.
Crucially, the correctness of the resulting algorithm for X cannot depend in any way on how the algorithm for Y works. The only thing we can assume is that the black box solves Y correctly. The inner workings of the black box are simply none of our business; they’re somebody else’s problem. It’s often best to literally think of the black box as functioning purely by magic.”

Reduction examples
1 The problem of evaluating a polynomial is reduced to the basic operations of addition and subtraction
2 In InsertionSort, the problem of sorting is reduced to the (easier) problem of inserting a number into an already sorted list
3 In your textbook, the Huntington-Hill algorithm reduces the problem of apportioning Congress to the problem of maintaining a priority queue that supports the operations Insert and ExtractMax.

Recursion
Recursion is a special type of reduction that reduces a problem instance to one or more simpler instances of the same problem.
All four algorithm design techniques 1 divide-and-conquer
2 backtracking
3 dynamic programming
4 greedy
that we will use in this class can be described using recursion.

Divide-and-conquer approach
A divide-and-conquer algorithm works as follows:
1 If the problem is small enough, solve it directly (and quickly).
2 Otherwise, divide it into subproblems (Divide) that your solve recursively (“as a black box functioning purely by magic”!)
3 Combine the solutions to the subproblems into a solution of the original problem (Conquer)

Exponentiation
Consider the problem of computing an:
Input: number a and positive integer n
Output: an
Example: givena=1.5andn=2,an =1.52 =2.25
The obvious algorithm:
SlowPower(a, n) res ← a
for i ← 2 to n
res ← res * a return res

Fast exponentiation
Indian scholar Pingala proposed the following recursive formula in 2nd century BCE!
1 if n = 0
an =(an/2)2 ifn>0andniseven
(a⌊n/2⌋)2a otherwise
which leads to the following exponentiation algorithm:
PingalaPower(a, n) if n ← 1
return a
tmp ← PingalaPower(a, ⌊n/2⌋) if n is even
return tmp*tmp
else
return tmp*tmp*a

Fast exponentiation
Why is it said to be fast?
PingalaPower(a, n) if n ← 1
return a
tmp ← PingalaPower(a, ⌊n/2⌋) if n is even
return tmp*tmp
else
return tmp*tmp*a

Fast exponentiation
Why is it said to be fast?
How many multiplications are performed by this algorithm?
PingalaPower(a, n) if n ← 1
return a
tmp ← PingalaPower(a, ⌊n/2⌋) if n is even
return tmp*tmp
else
return tmp*tmp*a

Related Posts