CSE 101: Introduction to Algorithms
CSE 101: Introduction to Algorithms
Professor: Daniel Kane
Course webpage:
http://cseweb.ucsd.edu/~dakane/CSE101/
Lecture Zoom Meeting Link:
https://ucsd.zoom.us/j/93843292201?pwd=a1FDQS9Da0ZWWjRKUnZ3a3FQWHo5QT09
Basic Logistical Information
Course Technology Guide:
http://cseweb.ucsd.edu/~dakane/CSE101/Technology.pdf
Course Syllabus:
http://cseweb.ucsd.edu/~dakane/CSE101/Syllabus.pdf
Practice Quiz
Office Hours
Daniel Kane: Thursday and Friday 2:30-4:00pm or by appointment
https://ucsd.zoom.us/my/dankane
TAs:
Jiabei Han:Monday, Wednesday, Friday 4:00-5:00pm pacific over zoom at https://ucsd.zoom.us/j/92571674513.
Vaishakh Ravindrakumar:Monday, Wednesday, Friday 11:00am-12:00pm pacific over zoom at https://ucsd.zoom.us/j/7577412678.
Manish Kumar Singh:Tuesday 4:00-6:00pm and Thursday 5:00-6:00pm pacific over zoom at https://ucsd.zoom.us/j/9029365896.
Chutong Yang:Tuesday 8:00-9:00pm and Thursday 7:00-9:00pm pacific over zoom at https://ucsd.zoom.us/s/5785340529.
Tutor:
Harrison Matt Ku:Tuesday, Thursday 1:00-2:30pm pacific over zoom at https://ucsd.zoom.us/my/harrisonku.
Introduction
What kinds of problems will we consider in this course?
Fibonacci numbers.
Asymptotic Runtimes.
Levels of algorithm design.
Straightforward Programming Problems
Display text
Copy a file
Count number of occurrences of a given word
Each has a straightforward algorithm that is hard to improve upon.
Algorithms Problems
Find a shortest path in a city
Find the best pairing of students to dorm rooms
Find the best schedule of classes
These problems are
Well defined mathematically
Still not easy to solve
AI Problems
Image recognition
Game playing
Understanding natural language
For these problems, much of the difficulty is in formalizing exactly what you are trying to do.
This Class
We will focus on algorithms problems
Problem: Fibonacci Numbers
Definition:
The Fibonacci numbers are the sequence
1, 1, 2, 3, 5, 8, 13, 21, 34, 55,…
Defined by
F0 = F1 = 1
Fn = Fn-1 + Fn-2 for n ≥ 2
Problem: Given n, compute Fn.
Naïve Algorithm
There is an easy recursive algorithm.
Fib(n)
If n ≤ 1
Return 1
Else
Return Fib(n-1)+Fib(n-2)
Essentially turned definition into an algorithm.
Runtime
Lets compute T(n) = number of lines of code Fib(n) needs to execute.
Fib(n)
If n ≤ 1
Return 1
Else
Return Fib(n-1)+Fib(n-2)
2 lines
1+T(n-1)+T(n-2) lines
T(n) =
2 if n ≤ 1
T(n-1)+T(n-2)+3 else
Question: Runtime
If your computer executes a billion lines of code per second, approximately how long does it take to compute F(100)?
A millisecond
A second
A year
100,000 years
Forever
T(100) ≈ 2.87 · 1021
At a billion lines of code per second, this is just over 90,000 years.
Why So Slow?
Too many recursive calls.
F(5)
F(4)
F(3)
F(3)
F(2)
F(2)
F(1)
F(0)
F(1)
F(0)
F(1)
F(1)
F(2)
F(1)
F(0)
How do we improve this?
Avoid having to recompute things.
How would you do it by hand?
F0 = 1
F1 = 1
F2 = 2
F3 = 3
F4 = 5
As long as you have records of the previous answers, you can just write down the next one.
Improved Algorithm
Simulate the above idea using array A to store values A[n] = Fn.
Fib2(n)
Initialize A[0..n]
A[0] = A[1] = 1
For k = 2 to n
A[k] = A[k-1] + A[k-2]
Return A[n]
2 lines
2(n-1) lines
1 line
T(n) = 2n+1
Runtime
With the new algorithm T(100) = 201. Easily runable on almost any computer.
The power of algorithms: Sometimes the right algorithm is the difference between something working and not finishing in your lifetime.
Question: Runtime
Is T(n) = 2n+1 a good description of this program’s runtime?
Fib2(n)
Initialize A[0..n]
A[0] = A[1] = 1
For k = 2 to n
A[k] = A[k-1] + A[k-2]
Return A[n]
2 lines
2(n-1) lines
1 line
Yes
No
Discussion of Runtimes
Is T(n) = 2n+1 really an accurate description of that program’s runtime?
Is initializing an array one operation or several?
What about adding large integers?
Should we count machine ops?
Doesn’t this depend on implementation?
Bottom Line
What we really care about is how long it takes program to run on a real machine.
Unfortunately, this depends on:
CPU speed
Memory architecture
Compiler optimizations
Background processes
Too much to consider for every analysis
Asymptotic Analysis
These issues usually just constant factors.
If we analyze runtime in a way that ignores constant factors (like big-O), we don’t have to deal with them.
But ignoring constant factors 1 second is the same as 100,000 years.
On the other hand, we can still compare things asymptotically. A Θ(n) algorithm will beat an Θ(n2) algorithm for n large enough.
Advantages and Disadvantages of Asymptotic Analysis
Disadvantages:
Cannot tell you whether algorithm is practical on given inputs.
Ignores constant factor runtime improvements which are important in practice.
Advantages:
Independent of hardware and implementation.
Allows you to compare behavior on sufficiently large inputs.
Usually an algorithm with better asymptotic behavior will do better in practice (though there are notable exceptions).
Because of this, this class will almost exclusively use big-O analysis.