Michael's Wiki

Stable matching problem

Self-enforcing recruitment/matching process

Outcome is stable if E prefers ever one of its accepted applicants to A; or

A prefers her current situation over working for employer E.

Important to think about how resource requirements – the amount of time and space an algorithm will use- will scale with increasing input size

Algorithms should be fundamentally discrete.

An algorithm is efficient if, when implemented, it runs quickly on real input instances

→

Leaves out test case size, and bad algorithms can pass this test and so can good algorithms coded poorly

An algorithm is efficient if it achieves qualitatively better worst-case performance, at an analytical level, than brute-force search.

-too vague

→

An algorithm is efficient if it has a polynomial running time

Helps to see that there might not be an efficient algorithm for a particular problem

O() expressed upper bound, not the exact growth rate

Upper, Lower, and limit bounds

Transitivity, A upper bound = b upper bound, b upper bound = c upper bound, then c upper bound = a upper bound

Polynomials - asymptotic rate of growth is determined by their “high-order term”

Logarithms- slow growing

Exponentials- fast growing

Every exponential grows faster than every polynomial

Summary: Goes over various common running times and common problems associated with those running times. Search space : The set of all possible solutions the search for algorithms' whose performance is more efficient than a brute-force enumeration of this search space. One of the goals of the book is to improve on brute-force algorithms

Linear Time

-At most a constant factor time the size of the input

Ex.

Computing the Maximum

Merging Two Sorted Lists

O(n logn) Time:

Running time of any algorithm that splits its input into two equal-sized pieces, solves each piece recursively, and then combines the two solutions in linear times

Ex.

Sorting Algorithms like Mergesort

Algorithms whose most expensive step is to sort the input

Quadratic Time:

Performing a search over all pairs of inputs and spending constant time per pair

Also arises naturally from nested loops.

Cubic Time:

More elaborate sets of nested loops.

Ex.

Finding sets which are disjoint

O(n^k) Time

Arises for any constant k when we search over all subsets of size k

Ex.

Finding independent sets in a graph

Summary: Priority Queue can be implemented well using a Heap data structure which is like a balanced binary tree. The Heap data structure with Heapify-down and Heapify-up operations can efficiently implement a priority queue that is constrained to hold at most N elements at any point in time

We seek algorithms that improve qualitatively on brute-force search and in general we use polynomial-time solvability as the concrete formulation of this.

Priority Queue – designed for applications in which elements have a priority value or key and each time we need to select an element form S, we want to take the one with the highest priority

-Smaller keys represent higher priorities

-Supports addition and deletion of elements from the set and also the selection of the element with smallest key

Heap data structure- Useful data structure for implementing a priority queue

Combines the benefits of a sorted array and list

Useful to think of as a balanced binary tree

Tree will have a root, and each node can have up to two children, a left and a right child

Heap Order: for every element v, at a node I, the element w at I's parent satisfies key(w) ⇐ key(v)

Common Operations:

Accessing Min- O(1) time because it will be the root

Heapify-Up – Used to 'fix' the heap after an element is added or deleted and an element is in a spot it is 'too big' for

Heapify-Down – Inverse of Heapify-up : is used to 'fix' the heap when an element is deleted or added and an element is 'too small' for its current spot.

Summary: Goes over some basic graph types and some uses for a graph

Graph – collection of things and join some of them by edged

Examples/Uses:

• Transportation Networks
• Communication Networks
• Information Networks
• Social Networks

Simple Path- all vertices are distinct from one another

Cycle – a path v1,v2,…vk-1,vk in which k >2, the first k-1 nodes are all distinct, and v1=vk. In other words, the sequence of nodes “cycles back: to where it began.

Tree – an undirected graph, is connected and does not contain a cycle, the simplest kind of connected graph.

-Rooted trees help to explain the concept of hierarchy in computer science.

Theorem 3.2: Let G be an undirected graph on n nodes. Any two of the following statements implies the third. - G is connected - G does not contain a cycle - G has n-1 edges.