Chapter 2

Summary

The author talks about why worst-case approach the complexity is used rather than its seemingly attractive alternative—average performance. It is hard to define what random input should we generate to evaluate the complexity.

two important definitions:

Proposed Definition of Efficiency (2): An algorithm is efficient if it achieves qualitatively better worst-case performance, at an analytical level, than brute-force search. =⇒ quantify “qualitatively better” =⇒ polytime

Proposed Definition of Efficiency (3)“ An algorithm is efficient if it has a polynomial running time.

The author concludes that there is a final, fundamental benefit to making our definition of efficiency so specific: it becomes negatable. It becomes possible to express the notion that there is no efficient algorithm for a particular problem.

Readable: 7/Interesting: 5

Summary the way we quantitatively measure the complexity is intrinsically based on the worst case analysis. We provide a upper bound where the runtime is bounded by some other c*F(n) and also a lower bound where the runtime function is lower bounded by some Omega(n). The author then talks about some asymtotic bounds for common functions such as poynomials, exponentials, and logarithms. And showed their asymtotic bounds.

Readable: 7/Interesting: 2

SUMMARY This section covers the discussion as to the underlying data structure to implement the stable matching algorithm. The discussion is essentially about the tradeoffs of using a list versus an array. Comparison:

Array: fast, constant time to access an element given an index. List: more flexible, but slower to access each element. O(N).

Array Add element O(1) Delete element O(N) Find element O(N)

List Add element O(1) Delete element O(1) Find element O(N)

It takes O(N) to convert from an array to a list and the same the other way around.

Refer back to the 1/17 slide for the breakdown of the running time of O(N²) of the the total running time.

Interesting/Readability: 8 5

Summary When trying to analyze a new algorithm, it helps to have a rough sense of the “landscape” of different running times. So this section covers some of the common types of running times that we are going to keep refering back to later.

Linear time: O(N) An example would be iterating through a collection and perform some constant operation on each elment of that collection. Examples:

• Computing the max of a list.
• Merging the two sorted list. Only have to go through the two lists once to get it done.

O(NlogN) Time Examples

• Mergesort — divide into logN pieces of small problems and for each one perform the merge which takes N.
• Time stamp problem

Quadratic Time O(N²) Exaples:

• Matching problem.
• calculating distances between any given points.

Cubic Time O(N³) For each set Si ,For each other set Sj, For each element p of Si, Determine whether p also belongs to Sj.

O(N^k) Time Independent set of size k. Given a graph,are there k nodes such that no two are joined by an edge?

Note: Summary of running times. P20 slide 1/19

Interesting/Readability: 8 5

Motivation: After overcoming higher-level obstacles, lower-level implementation details can improve runtime.

Summary Priority Queue revisited:

Maintains a set of elements S • Each element v ∈ S has a key(v) for its priority  Smaller keys represent higher priorities  Supported operations • Add, delete elements • Select element with smallest key

Implementing data structures: for sorting If we use unsorted lists: N² -why?

If we use array: logn*N²

If we use heaps: NlogN

Implementation of Heaps: Know the implementation of the Heapify-up and Heapify-down with an array based implementation.

Interesting/Readability: 7 7