In the Asynchronous Lecture
In the Synchronous Lecture
If you have any questions while watching the pre-recorded material, be sure to write them down and to bring them up during the synchronous portion of the lecture.
The following tabs contain pre-recorded lecture materials for class this week. Please review these materials prior to the synchronous lecture.
Total time: 1 hour and 28 minutes.
# Same algorithm but the readability of the program differs
def alg1(n):
theSum = 0
for i in range(1,n+1):
theSum = theSum + i
return theSum
def alg2(tom):
fred = 0
for bill in range(1,tom+1):
barney = bill
fred = fred + barney
return fred
print(alg1(10))
print(alg2(10))
# Faster algorithm using a closed form solution to the problem
def alg3(n):
return (n*(n+1))/2
print(alg3(10))| f(n) | Name | Notation |
|---|---|---|
| \(1\) | Constant | \(O(1)\) |
| \(log(n)\) | Logarithmic | \(O(log n)\) |
| \(n\) | Linear | \(O(n)\) |
| \(n log(n)\) | Log Linear | \(O(n log n)\) |
| \(n^2\) | Quadratic | \(O(n^2)\) |
| \(n^3\) | Cubic | \(O(n^3)\) |
| \(2^n\) | Exponential | \(O(2^n)\) |
# %% Constant Time O(1) -----------------------------------------
def fun_constant(n):
print(n)
fun_constant(10)
# %% Logarithmic Time O(log n) -----------------------------------------
def fun_log(n):
while n > 0:
n = int(n/2)
print(n,end=" ")
fun_log(10)
# %% Linear Time O(n) -----------------------------------------
def fun_linear(n):
for i in range(n):
print(i,end=" ")
fun_linear(10)
# %% Log Linear Time O(n log n) -----------------------------------------
def fun_log_lin(n):
for i in range(n):
a = i
while a > 0.1:
a = a/2
print(a)
fun_log_lin(10)
# %% Quadratic Time O(n^2) -----------------------------------------
def fun_quadratic(n):
for i in range(n):
for j in range(n):
print( (i,j))
fun_quadratic(10)
# %% Cubic Time O(n^3) -----------------------------------------
def fun_cubic(n):
for i in range(n):
for j in range(n):
for k in range(n):
print( (i,j,k))
fun_cubic(10)# %% Sequential Search -----------------------------------------
# Input:
students = ["Madeline","Yousuf","Justine","Ella","Ruyi"]
value = "Eric"
# Output: True/False
# Sequentially compare every item in the list
students[0] == value
students[1] == value
# ...
students[4] == value
# A function that accomplishes sequential comparisosn
def sequential_search(data,value):
for d in data:
if d == value:
return True
return False
# Test
sequential_search(students,"Yousuf")
sequential_search(students,"Eric")
# What is the best case run time? O(1)
# What is the worst case run time? O(N)# %% Binary Search -----------------------------------------
numbers = [3,7,55,2,90,10,25,33]
numbers.sort() # List must be sorted. Best Run time for a sorting alg. is O(n log n)
numbers
# The Gist of Binary Search
item = 3
first = 0
last = 7
numbers[first]
numbers[last]
midpoint = (first + last)//2
numbers[midpoint] == item
item > numbers[midpoint]
item < numbers[midpoint]
last = midpoint -1
midpoint = (first + last)//2
numbers[midpoint] == item # Found it!
# Written up as an algorithm
def binarySearch(alist, item):
first = 0
last = len(alist)-1
found = False
while first<=last and not found:
midpoint = (first + last)//2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1
return found
# Implement the Algorithm
numbers
binarySearch(numbers,90)
# What is the best case run time? O(1)
# What is the worst case runtime? O(log n)# %% Hashing -----------------------------------------
hash_table = [None]*11
hash_table
numbers = [33,51,23,97,13]
numbers
numbers[4]%11
# F(item) -> pos in table
# %% Hash Function -----------------------------------------
def hash_function(item):
'''remainder hash function'''
return item%11
for i in numbers:
ind = hash_function(i)
hash_table[ind] = i
hash_table
hash_function(13)
hash_table[2]
# Look up in O(1)
# %% More complicated hash function -----------------------------------
students = ["Madeline","Yousuf","Justine","Ella","Ruyi"]
hash_table = ['']*11
ord("E") + ord("l") +ord("l") +ord("a")
381%11
list("Ella")
def hash_func2(name):
score = 0
for i in list(name):
score += ord(i)
return score%11
hash_func2("Ruyi")
for student in students:
ind = hash_func2(student)
hash_table[ind] = student
hash_table
hash_func2("Madeline")
hash_func2("Ruyi")
# %% Collision Resolution -----------------------------------------
# When the hash function stores values in the same location, we get a "collision"
hash_table = [None]*11
# One way to deal with a collision is to store multiple values in the same
# location and then iterate through them when looking a value up.
for student in students:
ind = hash_func2(student)
if hash_table[ind] is None:
hash_table[ind] = [student]
else:
hash_table[ind].append(student)
# Run time for instances with a collision is O(m) where m is the number of items
# in the name location. That is, we have constant time for looking the value up
# and then it's a sequential search from there. The following survey asks you quick questions regarding the usefulness of the asynchronous lecture materials. Feedback will be used to modify aspect of the asynchronous materials moving forward.
These exercises are designed to help you reinforce your grasp of the concepts covered in the asynchronous lecture material.
Give the Big-O performance of the following code fragment:
i = n
while i > 0:
k = 2 + 2
i = i // 2\(O(log N)\)
Give the Big-O performance of the following code fragment:
for i in range(n):
for j in range(n):
for k in range(n):
k = 2 + 2\(O(N^3)\)
Give the Big-O performance of the following code fragment:
for i in range(n):
k = 2 + 2
for j in range(n):
k = 2 + 2
for k in range(n):
k = 2 + 2\(O(N)\)
The following materials were generated for students enrolled in PPOL564. Please do not distribute without permission.
ed769@georgetown.edu | www.ericdunford.com