CS计算机代考程序代写 data structure chain AVL algorithm CSC 226 Algorithms & Data Structures II

CSC 226 Algorithms & Data Structures II
Nishant Mehta Lecture 1
http://xkcd.com/1667

The biggest difference between time and space is that you can’t reuse time.
—Merrick Furst

•
An Algorithm is a sequence of unambiguous instructions for solving a problem for obtaining the desired output for any legitimate input in a finite amount of time.
(Levitin, Introduction to the Design & Analysis of Algorithms)
Definition of Algorithm

• • • •
It really does have to be unambiguous
Care has to be taken in specifying the range of inputs There can be different ways to implement an algorithm
The same problem might be solvable by very different algorithms, and these algorithms can have very different efficiencies.
•
An Algorithm is a sequence of unambiguous instructions for solving a problem for obtaining the desired output for any legitimate input in a finite amount of time.
(Levitin, Introduction to the Design & Analysis of Algorithms)
Definition of Algorithm

• •
Example: Matrix-chain multiplication
Suppose you are given a chain of matrices A1, A2, …, An and want to compute the product A1 A2 ⋯ An
Is A1 A2 ⋯ An an algorithm?

• •
•
Example: Matrix-chain multiplication
Suppose you are given a chain of matrices A1, A2, …, An and want to compute the product A1 A2 ⋯ An
Is A1 A2 ⋯ An an algorithm?
Consider n = 3 with the matrices having dimensions: 3×500, 500×2, and 2×2000

• •
Example: Matrix-chain multiplication
Suppose you are given a chain of matrices A1, A2, …, An and want to compute the product A1 A2 ⋯ An
Is A1 A2 ⋯ An an algorithm?
Consider n = 3 with the matrices having dimensions:
•
3×500, 500×2, and 2×2000
•
Order of multiplication matters!

•
Time Complexity: How fast does the algorithm run?
Complexity
•
Extra space means space in excess of the input
Space Complexity: How much (extra) space does the algorithm require?
• •
Time complexity typically is lower bounded by space complexity. Why?

Two Types of Analysis
(1) The Empirical Method: “just run it and see what happens”
•
Complexity measure: number of clock cycles Method: Instrumentation and Profiling
•
Closer to software engineering; covered in SENG 265
•

Two Types of Analysis
(2) The Theoretical Method: “hypothetically, how many primitive operations would this perform if I ran it?”
•
Complexity measure: number of primitive operations Method: Math and Theoretical Computer Science
•
Derive upper and lower bounds on complexity
•

Two Types of Analysis
Good
Empirical Method
More precise comparison for typical inputs and particular machine
Theoretical Method
Consider all possible inputs
Compares algorithms in an architecture-agnostic way
No implementation required
Bad
Ugly

Two Types of Analysis
Good
Empirical Method
More precise comparison for typical inputs and particular machine
Requires implementation
Limited by the set of inputs used Hard to identify good set of inputs
Can only compare algorithms on the same machine
Theoretical Method
Consider all possible inputs
Compares algorithms in an architecture-agnostic way
No implementation required
May be too pessimistic if one considers worst-case inputs
Might be hard to analyze algorithms
Bad
Ugly

Bad
Two Types of Analysis
Good
Empirical Method
More precise comparison for typical inputs and particular machine
Requires implementation
Limited by the set of inputs used Hard to identify good set of inputs
Can only compare algorithms on the same machine
Theoretical Method
Consider all possible inputs
Compares algorithms in an architecture-agnostic way
No implementation required
May be too pessimistic if one considers worst-case inputs
Might be hard to analyze algorithms
Ugly

• • • • •
Complexity as a function of input size
Measured in terms of number of primitive operations worst-case, best-case, average case
Abstracting to asymptotic behavior/order of growth For recursive analysis, use the master theorem
Time complexity analysis

Two wands problem
Input: n boxes, where boxes 1,…, i contain pearls, and boxes i + 1,…, n are empty, for some i
Output: i, where i is the index of the rightmost box containing a pearl
•
Can this problem be solved using two wands with o(n) worst-case cost?
•
•
Model of Computation: At a cost of 1, a wand taps a box and reveals if it is empty or not. If empty, the wand disappears.

• •
• •
Two wand problem
What does a solution look like?
Need to give an algorithm, along with:
Proof of correctness: does it correctly identify i ? Cost analysis. Is the number of boxes tapped o(n) ?

•
•
•
Big-O O (g (n))
Big-Omega
Big-Theta
Less commonly used (but still important!)
•
Little-o o(g(n))
• •
Little-omega !(g (n))
Asymptotic notation

Big-O notation
Let f : N ! R, g : N ! R
We say that f is O(g(n)) if, for some c > 0 and n0 > 0 ,
for all n n0 it holds that:
f (n)  cg(n)
•
• •
“For all n ‘big enough’ and for some c ‘big enough’, ff(n) is at most a constant c times g (n) ”

Examples of Big-O
f(n)=n4 +7n2 +3

Examples of Big-O
f(n)=n4 +7n2 +3 f(n)=O(n4)

Examples of Big-O
f(n)=n4 +7n2 +3 f(n)=O(n4) f (n) = 2 log n

Examples of Big-O
f(n)=n4 +7n2 +3 f(n)=O(n4) f(n) = 2logn f(n) = O(logn)

Examples of Big-O
f(n)=n4 +7n2 +3 f(n)=O(n4) f(n) = 2logn f(n) = O(logn)
f (n) = log(n4)

Examples of Big-O
f(n)=n4 +7n2 +3 f(n)=O(n4) f(n) = 2logn f(n) = O(logn)
f (n) = log(n4)
f (n) = O(log n)

Examples of Big-O
f(n)=n4 +7n2 +3 f(n)=O(n4) f(n) = 2logn f(n) = O(logn)
f (n) = log(n4) f (n) = 3000
f (n) = O(log n)

f(n)=n4 +7n2 +3 f(n) = 2logn
f (n) = log(n4) f(n) = 3000
f(n)=O(n4) f(n) = O(logn) f (n) = O(log n)
f(n) = O(1)
Examples of Big-O

f(n)=n4 +7n2 +3 f(n) = 2logn
f (n) = log(n4) f(n) = 3000
f (n) = 4/n
f(n)=O(n4) f(n) = O(logn) f (n) = O(log n)
f(n) = O(1)
Examples of Big-O

f(n)=n4 +7n2 +3 f(n) = 2logn
f (n) = log(n4) f(n) = 3000 f(n) = 4/n
f(n)=O(n4) f(n) = O(logn) f (n) = O(log n)
f(n) = O(1) f(n) = O(1/n)
Examples of Big-O

f(n)=n4 +7n2 +3 f(n) = 2logn
f (n) = log(n4)
f(n) = 3000
f(n) = 4/n
f (n) = log n + log log n
f(n)=O(n4) f(n) = O(logn) f (n) = O(log n)
f(n) = O(1) f(n) = O(1/n)
Examples of Big-O

f(n)=n4 +7n2 +3 f(n) = 2logn
f (n) = log(n4)
f(n) = 3000
f(n) = 4/n
f (n) = log n + log log n
f(n)=O(n4) f(n) = O(logn) f (n) = O(log n)
f(n) = O(1) f(n) = O(1/n) f (n) = O(log n)
Examples of Big-O

f(n)=n4 +7n2 +3 f(n) = 2logn
f (n) = log(n4)
f(n) = 3000
f(n) = 4/n
f (n) = log n + log log n
f (n) = n(n log n + 3 log n)
f(n)=O(n4) f(n) = O(logn) f (n) = O(log n)
f(n) = O(1) f(n) = O(1/n) f (n) = O(log n)
Examples of Big-O

f(n)=n4 +7n2 +3 f(n) = 2logn
f (n) = log(n4)
f(n) = 3000
f(n) = 4/n
f (n) = log n + log log n
f (n) = n(n log n + 3 log n)
f (n) = 2log2 n
f(n)=O(n4) f(n) = O(logn) f (n) = O(log n)
f(n) = O(1) f(n) = O(1/n) f (n) = O(log n)
f (n) = O(n2 log n)
Examples of Big-O

•
•
•
•
Sum
Product
Properties of Big-O
f (n) = O(a(n)) and g(n) = O(b(n)) Then f (n) + g(n) = O(a(n) + b(n))
Suppose that
f (n) = O(a(n)) and g(n) = O(b(n)) Then f (n) · g(n) = O(a(n) · b(n))
Suppose that
Multiplication by a constant
Suppose that f (n) = O(a(n))
Then, for any c > 0 , c · f (n) = O(a(n))
Transitivity
Suppose that f (n) = O(g(n)) and g(n) = O(h(n)) Then f (n) = O(h(n))

•
•
•
Max degree
Suppose that
Properties of Big-O
f(n)=a0 +a1n+…+adnd Then f(n)=O(nd)
Polynomial is subexponential
Let d > 0 be arbitrary.
Then nd = O(an) for all a > 1
Polylogarithmic is subpolynomial
Let d > 0 be arbitrary. Then (log n)d = O(nr ) for all
r>0

Proof that polylogarithmic is subpolynomial
To be shown: Is there some c > 0 such that for all large enough n, we have:
d?? r (logn) cn
m
?? 1/d r/d lognc n
m
?? k logn  bn
for b = c
1/d
and k = r/d
And we are done! By choosing c large enough, we can make b large enough such that the last inequality holds (since log(n) is O (g (n)) for any polynomial g (n) , including g (n) = nk )

Common Examples of Big-O Accessing min in a min-heap
Search in a balanced binary tree
(i) Median. (ii) Range-limited Radix sort Merge sort
Insertion sort
Brute force sorting
increasing complexity

Big-Omega notation
Let f : N ! R, g : N ! R
We say that f is ⌦(g(n)) if, for some c > 0 and n0 > 0 ,
for all n n0 it holds that:
f (n) cg(n)
• •
• •
“For all n ‘big enough’ and for some c ‘small enough’, ff(n(n)) is at least a constant c times g(n)”
Equivalently, f is ⌦(g(n)) if and only if g is O(f (n))

•
•
Let f : N ! R, g : N ! R
We say that f is ⇥(g(n)) if f = O(g(n)) and f = ⌦(g(n))
Big-Theta notation
•
i.e. there are constants c1 , c2 > 0 such that:
“For all n ‘big enough’, f and g grow at the same rate, c1g(n)  f (n)  c2g(n)

• •
Asymptotic dominance
These usually don’t come up in computer science, but they
Little-o and little-omega
do come up in statistics, optimization, machine learning
We say that f is o(g(n)) if, for all ” > 0, there is some n0 > 0
•
such that, for all n n0 it holds that:
•
f (n)  “g(n)
f is !(g(n)) if and only if g is o(f (n))

Little-o and little-omega
•
f(n)iso(g(n)) if lim f(n) =0
If g is non-zero for large enough n , then we can use shorter, calculus-based definitions:
n!1 g(n) f(n)is!(g(n)) if lim f(n) =1
• •
n!1 g(n)
little-o: “the growth of f is nothing compared to the growth of g ”
little-omega: “the growth of f strictly dominates the growth of g ”

Typical model of computation: RAM model
•
•
•
Primitive operations (can be done in 1 time step):
Addition, Subtraction, Multiplication, Division, Exponentiation, Boolean operations, Assignment, Array indexing, Function calls when each operand fits in one word of storage
When using this model, we will implicitly assume that a word contains O(log n) bits, for input size n. Why?

Typical model of computation: RAM model
•
• •
contains O(log n) bits, for input size n. Why?
Does the code below run in polynomial time with respect to input n?
x←2
for i = 1 to n
x ← x2
Primitive operations (can be done in 1 time step):
•
When using this model, we will implicitly assume that a word
Addition, Subtraction, Multiplication, Division, Exponentiation, Boolean operations, Assignment, Array indexing, Function calls when each operand fits in one word of storage

Mean(x, n): sum ← 0
1 A
(n + 1) · A + (n + 1) · C + n · S n · (I + S + A)
1 · (A + D)
For j = 0 to n − 1 sum ← sum + x[j]
mean ← sum/n return mean
Example
A: Assignment C: Comparison S: Subtraction D: Division
I: array Indexing

Mean(x, n): sum ← 0
Example
A: Assignment C: Comparison S: Subtraction D: Division
I: array Indexing
1 A
(n + 1) · A + (n + 1) · C + n · S n · (I + S + A)
1 · (A + D)
Ignore! O(1)
Complexity: (2A + 2S + C + I) · n + (3A + C + D) · 1 = O(n)
For j = 0 to n − 1 sum ← sum + x[j]
mean ← sum/n return mean

Back to the two wands problem
Input: n boxes, where boxes 1,…, i contain pearls, and boxes i + 1,…, n are empty, for some i
Output: i, where i is the index of the rightmost box containing a pearl
•
Can this problem be solved using two wands with o(n) worst-case cost?
•
•
Model of Computation: At a cost of 1, a wand taps a box and reveals if it is empty or not. If empty, the wand disappears.

Solution to the two wands problem

From CSC 225, you will be expected to know
• • • • • • • •
• •
Pseudocode, counting number of operations
Recursion
Proof by induction: review this ASAP if you need to
Big-O analysis: review this ASAP if you need to
Merge sort, Quicksort, Priority queues (heaps)
Lower bounds for sorting
Selection in linear-time (Quickselect)
Trees, Binary Search Trees, Balanced Binary Search Trees (e.g. red-black trees, 2-3 trees, AVL trees)
Graph theory topics from CSC 225 BFS, DFS, strong connectivity

Graph Algorithms & Graph Theory
Randomized Algorithms
More Algorithms
Minimum Spanning Trees Introductory Graph Theory Shortest Path Algorithms Network Flow
Randomized Quickselect and Quicksort Hashing
String Search Algorithms
Greedy Algorithms
Data Compression Dynamic Programming
Course Outline

Administrivia
Instructor: Nishant Mehta Email: n|m|e|h|t|a|@uvic.ca Office: ECS 608
Office hours (tentative):
Mondays and Thursdays, 5pm – 6pm
TAs:
Joe Howie, Ali Mortazavi, Azadeh Mousavi, Koosha Samieefar, Steve Scinocca
Course webpage: http://web.uvic.ca/~nmehta/csc226_spring2021

Administrivia
Lectures, via Zoom
Mondays and Thursdays, 11:30am – 12:50pm
Labs, via Zoom, Instructed by Joe and Steve
Mondays Tuesdays Wednesdays
2:30pm – 3:20pm 3:30pm – 4:20pm 2:30pm – 3:20pm 3:30pm – 4:20pm 11:30am – 12:20pm 12:30pm – 1:20pm
(B01) (B02) (B03) (B04) (B05) (B06)
First lab is January 18th–20th (next week)
Please register for labs as soon as possible
Course webpage: http://web.uvic.ca/~nmehta/csc226_spring2021

•
•
When emailing: always start your subject line with [CSC226]
•
•
Administrivia
Any student who has registered in CSC 226 and does not have the required prerequisites and no waiver must drop the class. Otherwise: the student will be dropped and a prerequisite drop will be recorded on the student’s record.
Taking the course more than twice:
According to university rules, you must request (in writing) permission from the Chair of the Department and the Dean of the Faculty to be allowed to stay registered in the course. The letter should be submitted to Irene Statham, the CSC Undergraduate Advisor

•
4 Problem Sets – 7.5% each (total 30%)
•
•
•
•
•
Points breakdown:
•
Evaluation
Midterm – 25%
Final – 40%
Participation (probably via lab quizzes) – 5%
Even though the final only counts for 40%, you must pass the final to pass the course!!
The midterm exam will be in-class and is scheduled to take place on February 22nd. The final exam will be 3 hours and scheduled by the registrar. For both exams, you cannot use any devices or material (no books or notes)

Problem Sets
There will be 4 problem sets
•
•
•
•
•
• •
Late submissions won’t be accepted: With a valid excuse, the weight of the other problem sets will be increased
Collaborating:
You may discuss problem sets at a high level
(you can discuss major ideas but not detailed solutions), but your solutions must be written individually, from scratch, and all programming must be done individually (you can’t share written code)
Cheating
First time offense: zero on the entire problem set or exam Second time offense: you fail the course

Required
(1) Introduction to Algorithms, 3rd edition (Cormen, Leiserson, Rivest, Stein)
(2) Algorithm Design, 1st edition (Kleinberg and Tardos)
Textbooks

Related Posts