COMP 3711 Design and Analysis of Algorithms

Lecture 1: Course Mechanics Review of Asymptotic Notations

• Lectures • L1

Copyright By cscodehelp代写 加微信 cscodehelp

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代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com