Week 5: Algorithms 1 Flashcards
algorithm (three things)
- a finite sequence of precise instruction for performing a computation or for solving a problem
- defined on specified input and generates an output
- stops after finitely many instructions are executed
input
- property of an algorithm
- an algorithm has input values from a specified set
output
- property of an algorithm
- from each set of input values an algorithm produces output values from a specified set
- the output values values are called the solution to the problem
properties of an algorithm (5 things)
- input
- output
- correctness
- effectiveness
- finiteness
- generality
how to express an algorithm?
- through pseudocode
- pseudocode is an intermediate between an English description and an implementation in a particular language
pseudocode
- an intermediate between an English description and an implementation in a particular language
- ex words like for _ to _ do , if _ then return(), end if, end for, end function
searching algorithms
- Given a sequence of n elements and an element x, determine whether
element x is present - If x is present, return the “location”
- If not, return -1
- Elements represented in an array in non-decreasing order
(e.g., -5, -1, 0, 4, 4, 8 12)
linear search for finding given element in sorted array
- for searching a sorted array for a given element
- compare x with each element until match is found or end of list is reached
binary search
- for searching a sorted array for a given element
- compare x with element in middle of array
- if equal, x is found, otherwise search in either left or right half of array
- list must be SORTED
is binary search more efficient?
- binary search executes at most log base 2 n iterations
- linear executes up to n iterations
- binary search does more computations in one iteration than linear
- for more than 20 elements, binary search is faster
bubble sort
- for arranging n elements in non-decreasing order
- compare adjacent element a[j] and a[j+1] and exchange their positions to put them in non-decreasing order if necessary
- repeatedly swap elements
- perform repeated passes over the data until sorted
- one pass is one scan over unsorted data, repeat until done
- after at most n-1 passes it’s sorted
insertion sort
- scan array from left to right
- entries to left of index are in non-decreasing order, right are in original order
- basic operation is to take first element of unsorted portion and place it in correct position within the sorted portion of the list
cashier’s algorithm
- cashier’s algorithm does not always produce correct result for certain
denominations - always makes changes using the fewest
coins possible when change is made from quarters, dimes, nickels, and
pennies
the growth of functions
- time required to solve a problem depends on
- number of operations executed
- speed of hardware/software
- Big-O notation estimates the GROWTH of functions representing the number of operations executed
how to analyze algorithms
- express running time as a function of the input size (ex. f(n))
- do NOT compare execution times or number of statements executed
complexity of an algorithm
- refers to the amount of time and space required to execute an algorithm
- computing the amount of time and space used without having the actual program requires one to focus on essential features that affect perfomance
Big-O Notation
- Estimate the growth of a function without
worrying about constant multipliers or
smaller order terms - to do this assume that different operations take the same time (ex. + and /)
Theorem 1 w/Big-O Notation
- let f(n) = a_kn^k + a_k-1 n^(k-1) =.. + a_1n + a_0 be a polynomial in n of degree k
- then, f(n) is O(n^k)
- ex. 2n^8 + 55n^5 + 40 = O(n^8)
common growth functions and the order they grow in (fastest to slowest)
Factorial O(n!)
Exponential O(c^n)
Polynomial O(n^2)
Linearithmic O(nlogn)
Linear O(n)
Logarithmic O(logn)
Constant O(1)
Big-Omega
- let f and g be functions from N to R
- f(x) is Ω(g(x)) if there are constants C > 0 and k such that
|f(x)| >= C|g(x)| for all integers x > k
Big-Theta
- let f and g be functions from N to R
- when f(x) is Θ(g(x)), we say that f(x) is of order g(x)
- f(x) and g(x) are of the same order
- g(x) is also Θ(g(x))
Important Big-O Relationships: log base 2 n and n
log base 2 n = O(n), reverse is not true
Important Big-O Relationships: log base 2 n and √’n
log base 2 n = O(√’n), reverse not true
Important Big-O Relationships: log base 2 n and log base b n, b > 1
log base 2 n and log base b n are both O(log n)
Important Big-O Relationships: log base 2 n and n ^(1/8)
log base 2 n = O(n ^(1/8)), reverse not true
Important Big-O Relationships: (log base 2 n)^4 and √’n
(log base 2 n)^4 = O(√’n), reverse not true
Important Big-O Relationships: nlogn and n^2
nlogn = O(n^2), reverse not true
Note: in algorithm examples, array indices typically start at…
1
problem solving tips for algorithms
- fully understand the problem
- understand how to solve it “by hand”
- develop a first, possibly straightforward algorithm
- take a close and critical look at your solution and ask how could it be improved?
- solutions that repeat or duplicate computations are often not efficient and can be improved
linear search definition
- an algorithm that checks each item in a list one by one until it finds a match
- starts at beginning, compares to target
- stops searching when found, checks entire list if not
binary search definition
- an efficient algorithm for finding an item from a sorted list of item
- works by repeatedly dividing in half the portion of the list that could contain the item, until you’ve narrowed down the possible locations to just one
What data results in the maximum number of passes for bubble sort?
A data set that is already sorted in descending order (largest to smallest)
total number of comparisons for bubble sort is bounded by:
(n-1) + (n-2) + .. _ 1 =
n(n-1) / 2
total max number of comparisons for insertion sort
n(n+1) / 2
Formal definition of Big-O
- let f and g be functions from N to R
- f(x) is O(g(x)) if there are constants C and k such that
- |f(x)| <= C|g(x)| for integers x > k
Big-O and Big-Omega Connection
f(x) is Ω(g(x)) iff g(x) is O(f(x))
