- Home
- Documents
*Algorithm Design and amotong/teaching/algorithm design...¢ (Design) Algorithm design...*

prev

next

out of 44

View

6Download

0

Embed Size (px)

Algorithm Design and Analysis

Version: Summer 2018 Amo G. Tong 1

• Course ID: CISC621010

• Time: Tues. and Thur. 8:00am-9:15am

• Location: GOR116

• Instructor: Dr. Tong • Email: guangmot@gmail.com (temporary)

• Office hours: Tues 9:30am-11:00am

• Office: 412 Smith Hall

• TA: Fanchao Meng • Email: fcmeng@udel.edu

• Office hours: Thurs 5:00pm-7:00pm

• Office: 201 Smith Hall

Course Information

Version: Summer 2018 Amo G. Tong 2

• Text book: • Cormen, Leiserson, Rivest and Stein, Introduction to

Algorithms (3rd edition) McGraw-Hill & MIT Press.

• Other materials: • As announced.

• Prerequisite: • Undergraduate algorithm course • Discreate math • Or equivalent.

Course Information

Version: Summer 2018 Amo G. Tong 3

• Organization

• Five assignments. (35%)

• Midterm one. (25%)

• Midterm two. (Homework demo) (10%)

• Final exam. (25%)

• Pop quiz in class. (5%)

• Extra credits. (5% more or less)

Course Information

Version: Summer 2018 Amo G. Tong 4

• Pop quiz

• Pop quiz is used to encourage class participation.

• The ultimate goal is to learn well.

• A student will automatically get full credit for pop quiz if

they get no less than 92 out of 100 points in the final exam.

Course Information

Version: Summer 2018 Amo G. Tong 5

• Final Grading Letter

• The score in each category is less important than the score

relative to the class average. There is no fixed curve. If

everyone performs well in the class then everyone can get

top grades.

Course Information

Version: Summer 2018 Amo G. Tong 6

• Canvas

• Online systems will be available soon.

Course Information

Version: Summer 2018 Amo G. Tong 7

Lecture 1 Introduction and Sorting • Introduction

• O-notation

• Sorting

Version: Summer 2018 Amo G. Tong 8

Introduction

Version: Summer 2018 Amo G. Tong 9

Algorithm This Course

The way we solve problems. (Design) Algorithm design

Implementation (Design) Pseudocode

Introduction

Version: Summer 2018 Amo G. Tong 10

Algorithm This Course

The way we solve problems. (Design) Algorithm design

Implementation (Design) Pseudocode

Effectiveness (Analysis and Proofs) Correctness and optimality

Efficiency (Analysis) Time and space complexity

Hardness of problems (Analysis and Proofs) Computing theory and Np-completeness

Introduction

Version: Summer 2018 Amo G. Tong 11

Algorithm This Course

The way we solve problems. (Design) Algorithm design

Implementation (Design) Pseudocode

Effectiveness (Analysis and Proofs) Correctness and optimality

Efficiency (Analysis) Time and space complexity

Hardness of problems (Analysis and Proofs) Computing theory and Np-completeness

Typically, given a problem, we design an algorithm, provide pseudocode, prove the correctness, and analyze the running time.

• Algorithm Design:

• Self-reducibility • Solve the problem by solving sub-problems

• Merge sort

• Incremental Method • Update the current solution until a desired one is found.

• Insertion sort.

Introduction

Version: Summer 2018 Amo G. Tong 12

• Time Complexity: • 𝑇(𝑛): running time (# of operations) with respect to the

input size 𝑛. • Worst-case

• Average (assume some distribution of the input)

Introduction

Version: Summer 2018 Amo G. Tong 13

• Time Complexity: • 𝑇(𝑛): running time (# of operations) with respect to the

input size 𝑛. • Worst-case

• Average (assume some distribution of the input)

• Asymptotic analysis: • Ignore constants and look at 𝑇 𝑛 when 𝑛 approaches to +∞

• 𝑂-notation, Ω-notation, Θ-notation.

Introduction

Version: Summer 2018 Amo G. Tong 14

• Time Complexity: • 𝑇(𝑛): running time (# of operations) with respect to the

input size 𝑛. • Worst-case

• Average (assume some distribution of the input)

• Asymptotic analysis: • Ignore constants and look at 𝑇 𝑛 when 𝑛 approaches to +∞

• 𝑂-notation, Ω-notation, Θ-notation.

• Find time complexity: • Compute directly

• Solve recurrence

Introduction

Version: Summer 2018 Amo G. Tong 15

• Hardness of the problem:

• Is this problem solvable? (easy)

• Can we solve the problem in 𝑂(𝑓(𝑛)) time? (hard)

• Can we solve the problem in polynomial time? (hard)

• What is fastest possible algorithm? (hard)

Introduction

Version: Summer 2018 Amo G. Tong 16

• 𝑂-notation, Ω-notation, Θ-notation.

Big O notation

Version: Summer 2018 Amo G. Tong 17

(Def) 𝑂-notation:

𝑂(𝑔(𝑛)) = {𝑓(𝑛): there exist positive constants 𝑐 and 𝑛0 such that 0 ≤ 𝑓 𝑛 ≤ 𝑐 𝑔(𝑛) for all 𝑛 ≥ 𝑛0}.

• 𝑂-notation, Ω-notation, Θ-notation.

• We write 𝑓(𝑛) = 𝑂(𝑔(𝑛)) if 𝑓 𝑛 ∈ 𝑂(𝑔(𝑛)).

• Asymptotic upper bound

• 𝑐 is independent of 𝑛.

Big O notation

Version: Summer 2018 Amo G. Tong 18

(Def) 𝑂-notation:

𝑂(𝑔(𝑛)) = {𝑓(𝑛): there exist positive constants 𝑐 and 𝑛0 such that 0 ≤ 𝑓 𝑛 ≤ 𝑐 𝑔(𝑛) for all 𝑛 ≥ 𝑛0}.

• 𝑂-notation, Ω-notation, Θ-notation.

Big O notation

Version: Summer 2018 Amo G. Tong 19

(Def) 𝑂-notation:

𝑂(𝑔(𝑛)) = {𝑓(𝑛): there exist positive constants 𝑐 and 𝑛0 such that 0 ≤ 𝑓 𝑛 ≤ 𝑐 𝑔(𝑛) for all 𝑛 ≥ 𝑛0}.

Example: 𝑛 = 𝑂(𝑛2) ? yes ! 𝑛 ≤ 𝑛2 when 𝑛 ≥ 1.

• 𝑂-notation, Ω-notation, Θ-notation.

Big O notation

Version: Summer 2018 Amo G. Tong 20

(Def) 𝑂-notation:

𝑂(𝑔(𝑛)) = {𝑓(𝑛): there exist positive constants 𝑐 and 𝑛0 such that 0 ≤ 𝑓 𝑛 ≤ 𝑐 𝑔(𝑛) for all 𝑛 ≥ 𝑛0}.

Example: 𝑛 = 𝑂(𝑛2) ? yes ! 𝑛 ≤ 𝑛2 when 𝑛 ≥ 1. 𝑛 = 𝑂(𝑛2 − 10000) ? Yes ! 𝑛 ≤ 𝑛2 when 𝑛 ≥ 1000. 𝑛 = 𝑂(𝑛2 − 1000000000000) ? Yes !

• 𝑂-notation, Ω-notation, Θ-notation.

Big O notation

Version: Summer 2018 Amo G. Tong 21

(Def) 𝑂-notation:

𝑂(𝑔(𝑛)) = {𝑓(𝑛): there exist positive constants 𝑐 and 𝑛0 such that 0 ≤ 𝑓 𝑛 ≤ 𝑐 𝑔(𝑛) for all 𝑛 ≥ 𝑛0}.

Example: 𝑛 = 𝑂(𝑛2) ? yes ! 𝑛 ≤ 𝑛2 when 𝑛 ≥ 1. 𝑛 = 𝑂(𝑛2 − 10000) ? Yes ! 𝑛 ≤ 𝑛2 when 𝑛 ≥ 1000. 𝑛 = 𝑂(𝑛2 − 1000000000000) ? Yes ! 𝒏 = 𝑶(𝐥𝐨𝐠𝒏) ? No !

Proof: for any constant 𝒄, there exists some 𝒏𝟎 depending on 𝒄, such that 𝒏 > 𝒄𝐥𝐨𝐠𝒏 when 𝒏 > 𝒏𝟎

• 𝑂-notation, Ω-notation, Θ-notation.

Big O notation

Version: Summer 2018 Amo G. Tong 22

(Def) 𝑂-notation:

𝑂(𝑔(𝑛)) = {𝑓(𝑛): there exist positive constants 𝑐 and 𝑛0 such that 0 ≤ 𝑓 𝑛 ≤ 𝑐 𝑔(𝑛) for all 𝑛 ≥ 𝑛0}.

(Def) 𝛀-notation:

𝑶(𝒈(𝒏)) = {𝒇(𝒏): there exist positive constants 𝒄 and 𝒏𝟎 such that 𝟎 ≤ 𝒄𝒈 𝒏 ≤ 𝒇(𝒏) for all 𝒏 ≥ 𝒏𝟎}.

Asymptotic lower bound

• 𝑂-notation, Ω-notation, Θ-notation.

Big O notation

Version: Summer 2018 Amo G. Tong 23

(Def) 𝑂-notation:

𝑂(𝑔(𝑛)) = {𝑓(𝑛): there exist positive constants 𝑐 and 𝑛0 such that 0 ≤ 𝑓 𝑛 ≤ 𝑐 𝑔(𝑛) for all 𝑛 ≥ 𝑛0}.

(Def) Ω-notation:

𝑂(𝑔(𝑛)) = {𝑓(𝑛): there exist positive constants 𝑐 and 𝑛0 such that 0 ≤ 𝑐𝑔 𝑛 ≤ 𝑓(𝑛) for all 𝑛 ≥ 𝑛0}.

Asymptotic tight bound

(Def) 𝚯-notation:

𝑶(𝒈(𝒏)) = {𝒇(𝒏): there exist positive constants 𝒄𝟏, 𝒄𝟐 and 𝒏𝟎 such that 𝟎 ≤ 𝒄𝟏𝒈 𝒏 ≤ 𝒇(𝒏) ≤ 𝒄𝟐𝒈 𝒏 for all 𝒏 ≥ 𝒏𝟎}.

• 𝑂-notation, Ω-notation, Θ-notation.

Big O notation

Version: Summer 2018 Amo G. Tong 24

Practice: For any two functions 𝑓(𝑛) and 𝑔(𝑛), we have 𝑓(𝑛) = Θ(𝑔(𝑛)) if and only if 𝑓(𝑛) = 𝑂(𝑔(𝑛)) and 𝑓(𝑛) = Ω(𝑔(𝑛)).

Practice:

𝑓 𝑛 = 𝑂 𝑔 𝑛 ⇔ 𝑔(𝑛) = Ω(𝑓(𝑛))

• Logarithms

Big O notation

Version: Summer 2018 Amo G. Tong 25

log 𝑛 = log2 𝑛 lg 𝑛 = log10 𝑛 ln 𝑛 = log𝑒 𝑛

This is different from the notations used in the textbook. (ref. Chapter 3.2)

Practice: 𝑓 𝑛 = 𝑂 log 𝑛 ⇔ 𝑓 𝑛 = 𝑂 lg 𝑛