Chapter 2

The goal of this course is to write correct and efficient algorithms and this sections goes through how we define efficiency.

Intial attempt at defining efficiancy: “An algorithm is efficient if when, when implemented, it runs quickly on real input instances” What works:

• Good initial intro to what we want. Need to get things done quickly!

What doesn't work:

• Too vague: need where and how well
  • Will it be fast on more than just small cases?
  • What are real input instances?

Worst-Case Running Times and Brute-Force Search: “An algorith is efficient if it achieves qualitatviely better worst-case performance, at an analytical level, than brute-force search” Why it works:

• brute-force search is just going through each option so imporving is needed.
• shows intrinsic structure and computational tractability about the problem

Why it doesn't works:

• qualitatively better performance is too vague

Polynomial Time as a Definition of Efficiency “An algorithm is efficient if it has a polynomial running time.” Why it works:

• very specific
• makes it easier to prove there is no efficient algorithm

Why it doesn't work

• Too specific

This section discuss how to measure the order of an algorithm and looks at how to find a lower bound, an upper bound, and a tight bound. Our goal is to express the growth rate of running times of algorithms.

Upper bounds:

• If T(n) is ⇐ c*f(n) for some c > 0 then T is asymptotically bounded above by f.
• We will denote an upper bound as O. There can be multiple upper bounds.

Lower bound:

• IF T(n) is >=ξ*f(n) for some ξ>0 then T is asymptotically bounded below by f.
• we will denote this as Ω

Tight bounds:

• If T(n) is both O(f(n)) and Ω(f(n)) then we've found a asymptically tight bound
• T is bound tightly by f(n)
• our tight bound is denoted as Θ
• another way to find Θ is through the limit!

Properties of Asymptotic Growth Rates

1. Transitivity: 
  * If f = O(g) and g = O(h) then f = O(h)
  * If f = Ω(g) and g = Ω(h) then f = Ω(h)
  * If f = Θ(g) and g = Θ(h) then f = Θ(h)
2. Sum of Functions
  * Suppose that f and g are two functions such that for some other function h, we have f=O(h) and g = O(h) then f+g=O(h)
  * The same can be said for a finite number of functions
  * g = O(f) then f+g = O(f)

Asymptotic bounds for the some common fuctions

• polynomials: f is o degree d then f = O(n^d)
• logs: log_b(n) = O(n^x) where x > 0 and b > 1
• Exponentials: f(n)=r^n where r > 1 and d > 0 → O(r^n) = n^d

Helpful to have the bounds for common functions, but I am wondering how will we find them in the future?

Moving from general discussion of GS algorithm to actual implementation. First need to figure out what Data Structures to use.

Arrays:

• Arrays have length n and A[i] is the ith element in the list.
• Give direct access to ith elements - there for O(1) time to get value A[i]
• check if e is in A, (e = A[i] for some i), then it will take O(n) time
• if elements are sorted check for e in O(logn) using binary search.
• “An array is less good for dynamically mainting a list of elements that changes over time, such as a l ist of free men”

Lists:

• can delete or add
• should use a linked list
• possible option is doubly linked list:
  • deletion: constant time
  • insertion: constant time
  • ith access: O(i) time. No direct access.

We will need to use both in the stable matching alogorithm

• identify a free man - use a linked list
• for a man m identify his highest ranked woman who he has not proposed to - array
• for a woman w, decide if w is currently engaged and who her current partner is - use an array.
• for a woman w and two men m and m' we need to be able to check in constant time which W prefers m or m'. - inialize with an n x n array of preferences then we can use constant time access through out algorithm

This gives O(n^2) running time.

Getting into this stuff is more difficult for me. I don't remember running times as much and I try to think of it logically and actually go through the process, but it doesn't always work. Any step by step process would be helpful, but I am guessing it's something you get better at with time.

This section was easier to read since we just spent so much time on it and I felt pretty comfortable with it.

Linear time

• O(n)
• takes a constant times n amount of time
• computing the maximum - have to go through all n objects
• Merging Two Sorted Lists - basically have to check the min in each list against the other min. pop off the smaller one and add it to a new list.
• The book has more info on why this is O(n) look it over if confused: p. 50

O(n*logn) time

• very common
• Mergesort algorithm the set of input #s into two equal-sized pieces than solves each half recursively.
• common because most expensive step is sorting.

Quadratic time:

• O(n^2)
• trying to find all the pairs
• two nested loops

Cubic time

• O(n^3)
• trying to find all three tuples
• “elaborate sets of nested loops”

O(n^k)

• similar to quadratic and cubic times

Beyond polynomial time

• find maximum independent set in graph of k nodes
  • talked about this in class
• n! is huge and usually away to find smaller bounds

Sublinear time

• Binary search = logn
• O(logn) arises when we are doing constant amount of work in order to throw away a fraction of the input.

This all makes sense to me, I think the biggest struggle will be when I need to design an alogirthm with a certain running time, but these are the notes I should look at!

Priority Queue:

• Designed for applications in which elements have a priority value, or key, and each time we need to select an element from S, we want to take the one with highest priority.
• A priority queue is a data structure that maintains a set of elements S, where each element v in S has an associated value key(v) that denotes the priority of element v; smaller keys represent higher priorities.

Use a heap to implement a priority queue

• gets us the O(log n)
• For every element v, at a node i, the element w at i's parents satisfies key(w) ⇐ key(v)
• leftchild(i) = 2i, rightchild(i) = 2i+1
• Heapify up and heapify down - allows for log n

Use these operations:

• StartHeap(N)
• Insert(H,V)
• FindMin(H)
• Delete(H,i)
• ExtractMin(H)

I think heaps are soooo fun! I enjoyed this chapter because it layed out the code in a pretty readabe way.