COMP 3711 Design and Analysis of Algorithms
Lecture 1: Course Mechanics Review of Asymptotic Notations
• Lectures • L1
Copyright By PowCoder代写 加微信 powcoder
COMP3711 –Basics
• Tuesday & Thursday, 16:30 – 17:50
• Zoom Meeting ID: 927 5139 3911
• Monday 13:30-14:50,
• Zoom Meeting ID: 960 0689 7256 • Friday 9:00 – 10:00
• Zoom Meeting ID: 957 2701 1117 • Instructor: Professor Dimitris Papadias
• https://www.cse.ust.hk/~dimitris
• Tutorials (links to be announced) • T1: Tuesday, 18:00 – 18:50
• Zoom Meeting ID: 914 1942 5408 • T2: Friday, 15:30 – 16:20
• Zoom Meeting ID: 960 0689 7256 • T3: TBA
First Tutorial on Tuesday, Feb 15, 2022
Topics Covered (tentative)
• Techniques (with multiple examples)
• Divide & Conquer
• Greedy Algorithm Design
• Dynamic Programming
• Basic Randomized Algorithms
• Graph Algorithms
• Breadth & Depth First Search
• Shortest Paths
• Spanning Trees
• Maximum Flow and Bipartite Matchings
• Extra topics (if time available)
• AVL Trees
• Basic String Matching
About the Class
• What this class is
• Learning algorithmic techniques to solve problems.
• Learning how to prove correctness of algorithms.
• Learning how to model problems.
• What this class isn’t • Coding.
• Language specific programming hacks.
Prerequisites
• COMP2711 – Discrete Math • In particular
Basic Formulas, e.g., formulas for ,
, geometric
Basic Combinatorics, e.g, =
• COMP 2011 – Basic Data Structures • In particular
• Linked Lists (singly and doubly)
• Stacks and Queues
• Binary (Search) Trees
Accessing Course Material
The CANVAS system is used for COMP3711.
Assignments will be given out via canvas. All assignments must be submitted online via canvas. Hard copies will not be accepted. Email submissions will not be accepted. Late submissions will not accepted without prior approval.
Until further notice, all teaching will be online using Zoom
• The zoom meeting information for COMP 3711 is given on the canvas course page.
• Links to lecture recordings will also be posted on the canvas course page.
Tentative Grading Scheme
• 50% Written Assignments • 4-5 written assignments
• Assignments are a combination of problems that require you to work through taught algorithms on given input and problems that require you to design new algorithms
• Submission will be online via Canvas. You can typeset your solution, or scan your handwritten solutions, take pictures of your handwritten solutions.
• 50% Final Exam
• Will cover the entire semester’s material. Format not finalized yet.
Office Hours
• Office hours will be Zoom meetings by appointment
• Please feel free to email the instructor or your TAs to set up an
appointment
• If we receive multiple requests for appointments, especially
about similar topics, we might hold group meetings
Course Policies
• Making up Missed Finals
• Only for medical reasons (with Doctor’s note)
• OR prior approval of instructor, e.g., need to be away for academic competition
• Assignments
• Plagiarism: While collaboration is allowed,
• Assignment solutions must be written in your own words (not copied or modified from someone else’s write-up).
• You must understand your solution and its derivation. (We may ask you to explain it.)
• You must explicitly acknowledge in writing in the assignment your collaborators (whether or not they are classmates) or any other outside sources on each assignment.
• Failing to do any of these will be considered plagiarism, and may result in a failing grade in the course and notification for appropriate disciplinary action.
Review Material – Input Size of Problems
The input size indicates how large the input is. Since we assume that any number can be stored in a computer word and each arithmetic operation takes constant time, we take the number of items in the input as the input size (instead of bits).
By an item, we mean something that can be represented by a number and so it can be stored using one computer word.
Examples: Sorting
Graph problems Searching
Size of the list or array Numbers of vertices and edges Number of input keys
Measuring Running Time using Asymptotic Notation
Throughout the class we will measure the running time/cost of algorithms
as a function of input size:
using the number of instructions/steps/operations (e.g., comparisons
between two numbers)
using asymptotic notation, which ignores constants and non-dominant
growth terms.
Which algorithm is better for large ?
For Algorithm 1, For Algorithm 2,
Clearly, Algorithm 2 is better for large inputs
Behavior of some Commonly Encountered Functions
1,073,741,824
20,971,520
1,000,000,000,000
Asymptotic Notation: Quick Revision
Upper bounds.
ifexistconstants𝑐>0and𝑛00suchthatforall𝑛𝑛0, 𝑇 𝑛 ≤𝑐·𝑓(𝑛).
Lower bounds. ifexistconstants𝑐>0and𝑛00suchthatforall𝑛𝑛0, 𝑇 𝑛 ≥𝑐·𝑓(𝑛).
Tight bounds.
if 𝑇 𝑛 = 𝑂(𝑓(𝑛))and 𝑇 𝑛 = (𝑓(𝑛)).
Note: Here “=” means “is”, not equal.
Big-O Notation
Big-O notation is a mathematical notation for upper-bounding a function’s rate of growth.
T(n) = O(g(n))
∃c,n0 >0s.t.∀n≥n0, 0 ≤ T(n) ≤ c⋅g(n)
T(n) describes the running time of an algorithm.
T(n) = O(g(n)) means that there exists some c and n0 such that the pink line given by c⋅g(n) is above the yellow line for all values to the right of n0.
Big-O Notation
T(n) = O(g(n))
∃c,n0 >0s.t.∀n≥n0, 0 ≤ T(n) ≤ c⋅g(n)
T(n) doesn’t always have to be linear.
Big-O Notation
T(n) = O(g(n))
∃c,n0 >0s.t.∀n≥n0, 0 ≤ T(n) ≤ c⋅g(n)
T(n) and g(n) do not always T(n) have to be increasing.
Here, any choice for n0 is OK.
Big-O Notation Proofs
● Big-O is the most common notation because it is used to provide an upper bound for the cost of algorithms in the worst case
● To prove T(n) = O(g(n)), show that there exists c and n0 that satisfies the definition.
○ For example,
Suppose T(n) = n and g(n) = n log(n). We prove that T(n) =
Selectthevaluesc=1andn0 =2.Wehaven≤cnlog(n)for n≥n0 sincenispositiveand1≤lognforn≥2.
T(n) = O(g(n))
∃c,n0 >0s.t.∀n≥n0, 0 ≤ T(n) ≤ c⋅g(n)
Big-O Notation Proofs
● To prove T(n) ≠ O(g(n)), proceed by contradiction. ○ For example,
Suppose T(n) = n2 and g(n) = n. We prove that T(n) ≠ O(g(n)).
Suppose there exists some c and n0 such that for all n ≥ n0, n2 ≤cn.Then,n≤c, n≥n0, whichisnotpossiblebecausec is a constant and n can be arbitrarily large.
T(n) = O(g(n))
∃c,n0 >0s.t.∀n≥n0, 0 ≤ T(n) ≤ c⋅g(n)
Big-Ω Notation
● Big-Ω notation is a mathematical notation for lower-bounding a function’s rate of growth.
● Let T(n), g(n) be functions of positive integers.
○ You can think of T(n) as being a runtime: positive and
increasing as a function of n.
● We say “T(n) is Ω(g(n))” if g(n) grows at most as fast as T(n) as n gets large. Formally,
T(n) = Ω(g(n)) iff
c,n0 >0s.t. n≥n0, 0 ≤ c g(n) ≤ T(n)
Big-Ω Notation
T(n) = Ω(g(n)) iff
∃c,n0 >0s.t.∀n≥ n0,
0 ≤ c⋅g(n) ≤ T(n)
Big-Ω defines “T(n) = Ω(g(n))” to mean there exists some c and n0 such that the pink line given by c⋅g(n) is below the yellow line for all values to the
c g(n) right of n0.
Big-Θ Notation
We say “T(n) is Θ(g(n))” iff T(n) = O(g(n)) AND T(n) is Ω(g(n)) c’ g(n)
Discussion about constants and non-dominant growth terms
Asymptotic notations ignore constants and non-dominant growth terms.
If the number of steps taken by an algorithm A is and another algorithm B is , then both have Θ(n) running time, but algorithm A is superior in practice.
If two algorithms have the same asymptotic running time, implementation and experimentation is necessary to determine the best.
Nevertheless if algorithm A is asymptotically slower than B, then A is very likely to be (much) slower than B in practice.
Sorting Example
Population
Insertion Sort
Merge Sort
Macau (0.5M)
China (1357M)
Basic Facts on Exponents and Logarithms
c-n=1/cn ———-> c-1=1/c
c1/n=nc ———-> c1/2=c
(cm)n=(cn)m=cnm ———-> 22n = (2n)2 (2n); set x=2n, then x2 (x) cmcn=cn+m ———-> 2n+2 = 222n =(2n); (2n+c)=(2n)
logc(ab) = logca + logcb
logc(ba) =alogcb ———-> log(n3)=3logn=(logn) In general, log(nc)=(logn)
logba = logca/logcb ——–> log10n=log2n/log210 =(logn) (log210 is constant) In general, the base of the logarithm is not important and logcn=(logn)
logc(1/a) = logc(a−1) = −logca logba = logaa/logab = 1/logab
alogbn= nlogba ——–> 4logn = nlog4 = n2
Important note on growth of functions
constant < logarithmic < polynomial < exponential
<
< .< < <
----------> set m=logn, then logm= O(m)
.
Exercise 1
Note: constant < logarithmic < polynomial < exponential
Only the largest term is important
For each of the following statements, answer whether the statement is true or false.
(a) 1000n + nlogn = O(nlogn)
True. Also Ω and Θ
(b) n2 + nlog(n3) = O(n log(n3 ))
False. n2 + nlog(n3) = n2 + 3nlog(n) = Θ(n2)
(c) n3 = Ω(n)
(d)n2 +n=Ω(n3)
False. n2 + n = Ω(n2) (also Ω of any function smaller than n2)
(e) n3 = O(n10)
(f) n3 + 1000n2.9 = Θ(n3)
(g)n3 −n2 =Θ(n)
False. n3 − n2 = Θ(n3)
Exercise 2
Let f(n) and g(n) be non-negative functions. Using the basic definition of Θ-notation, prove that max(f(n),g(n)) = Θ(f(n)+g(n))
• We will prove that max(f(n), g(n)) = O(f(n)+g(n)) and max(f(n), g(n))=Ω(f(n)+g(n)). Therefore, max(f(n),g(n)) = Θ(f(n)+g(n))
• For any value of n, max(f(n), g(n)) is either equal to f(n) or equal to g(n). Therefore, for all n, max(f(n), g(n)) ≤ f (n) + g(n) and max(f(n), g(n)) = O(f(n)+g(n)).
• For all n, max(f(n),g(n)) ≥ f(n) and max(f(n), g(n)) ≥ g(n).
Then 2·max(f(n), g(n)) ≥ f (n)+g(n) max(f(n), g(n)) ≥ 1/2 (f(n)+g(n))
max(f(n), g(n))=Ω(f(n)+g(n))
Exercise 3
For each pair of expressions (A, B) below, indicate whether A is O, Ω, or Θ of B. List all correct relations that hold for each pair
(a)A=n3 +nlogn;B=n3 +n2logn
(b) A = log(√n); B = √logn.
Ω. Set m=√n. Then A=log(√n)=logm=Θ(logm) and B=√logn=√log(m2)=√2log(m)=(2logm)1/2=Θ(logm)1/2 (c) A = nlog3n; B = nlog4n
(d)A=2n ;B=2n/2 Ω.Setm=2n/2.B=2n/2=m.A=2n =2n/22n/2 =m2 (e) A = log(2n); B =log(3n).
Ω, Θ, O. log(2n)=nlog2=n=Θ(n). log(3n)=nlog3= Θ(n)
Exercise 4a Bounds of series, Arithmetic Series Prove that
First, I will prove that
(replace each i with n)
Then, I will prove that
(remove all terms < n/2, replace the remaining ones with n/2)
Closed formula for arithmetic series We will solve it in the next class.
Exercise 4b Polynomial Series Prove that 𝑐 , where c is a constant
First, I will prove that
𝑐𝑐𝑐 Then, I will prove that
No closed formula for polynomial series
Exercise 4c Harmonic Series Hn
Prove that . Let k=logn, i.e., n=2k
lower bound
upper bound
(1/2)+(1/3)
(1/4)+(1/5)+(1/6)+(1/7)
2k-1x1/2k=1/2 1⁄2
(1/2k-1)+(1/(2k-1+1))+..(1/(2k-1))
2k-1x1/2k-1=1 1
Each of the right-hand sums (upper bounds) is 1. The number of sums is logn+1. Thus, Hn ≤ logn+1, and Hn = O(logn).
Each of the left-hand sums is 1/2. Thus, 1⁄2(logn +1) ≤ Hn, and Hn = Ω(logn).
Combining: Hn=Θ(logn)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com