Chapter 2

Algorithm Goals

1. Many algorithms are discrete: the goal is to efficiently find a solution that satisfies certain very clear conditions.
2. Running Time
3. Efficiency: amount of space (or memory)

Defining Efficiency

• Consider scalability of algorithm: how does this effect efficiency?
• Goal: concrete definition of efficiency that is platform-independent, instance-independent, and of predictive value when it comes to increasing input sizes

Worst-Case Running Times and Brute-Force Search

• Worst-Case: bound on the largest possible running time the algorithm could have over all inputs of a given size N; see how this scales with N
• Brute-Force: check all perfect matchings by enumeration to see if each is stable (slow & not intellectual)

Polynomial Time

• When input size increases by a constant factor, the algorithm should only slow down by some constant factor C
• In general, each problem has an intrinsic level of computational traceability (some with efficient solutions, others without)
• Polynomial Running Time: When running time increases by lower-degree polynomials it exhibits better scaling behavior than when it increases by higher-degree polynomials (this is not always the best metric, but normally tends to be so)

Running Time: Coarser Level of Granularity

• Calculating precise bounds is exhausting and meaningless
• Goal: identify broad classes of algorithms with similar behavior
• Goal: express growth rate in a way that is insensitive to constant factors and low-order terms

O, Ω, and Θ

• Asymptotic Upper Bound: T(n) is O(f(n)), if there exists constants c>0 and n₀≥0 so that for all n≥n₀, we have T(n)≤c*f(n) → T is asymptotically upper bounded by f.
• Asymptotic Lower Bound: T(n) is Ω(f(n)), if there exists constants Ω>0 and n₀≥0 so that for all n≥n₀, we have T(n)≥ε*f(n) → T is asymptotically lower bounded by f.
• Asymptotic Tight Bounds: if we can show that a running time T(n) is both O(f(n)) and also Ω(f(n)), then T(n) grows exactly like f(n) to within a constant factor.

Properties of Asymptotic Growth Rates

• Transitivity: if a function f is asymptotically upper-bounded by a function g, and if g in turn is asymptotically upper-bounded by a function h, then f is asymptotically upper-bounded by h.

• Sums of Functions: if we have an asymptotic upper bound that applies to each of two functions f and g, then it applies to their sum

Asymptotic Bounds for Some Common Functions

• Polynomials: Asymptotic rate of growth is determined by their “high-order term,” the one that determines the degree. Let f be a polynomial of degree d, in which the coefficient a_d is positive. Then f=O(n^d).
• Logarithms: For every b>1 and everyx>0, we have log_bn = O(n^x)
• Exponentials: For every r>1 and every d.0, we have n^d = O(rⁿ)

Asymptotically speaking, exponential functions are all different. Logarithms grow more slowly than polynomials, and polynomials grow more slowly than exponentials.

While this chapter dove into more of the complex details, it still was laid out in a way that was pretty easy to understand. 2.1 was definitely easier to understand than 2.2. Obviously there are a lot of notations that correspond to various functions, but I believe the overall concepts make sense. It would help to see applications of each of these bounds, which would also make this more interesting. Readability: 7 Interesting: 5

Arrays and Lists

Arrays:

• Direct access to A[i]: O(1)
• Search: O(n)
• Binary Search (for a sorted array): O(log n)

• Not good for frequent additions and deletions from the array

Linked List:

• For each element v, we need to maintain a pointer to the next element
• The last element i's pointer is set to null
• Pointer First points to the first element
• Pointer Last points to the last element
• Can allocate a record e for each element we want to include in the list: e.val and e.Next (also e.Prev, if doubly linked list)

• Traversal: O(n)

Doubly Linked List:

• Deletion: change pointers for e.Prev and e.Next
• Insertion: change pointers for e.Prev and e.Next

• Search: O(n)

Implementing the Stable Matching Algorithm

• For runtime to be proportional to n², each iteration must occur in constant time.

• Each man is associated with a number from 0 to n, where n represents the total number of men. The same is done with the women.
• 2 arrays: for the men and women's preference lists
  • ManPref[m,i] & WomanPref[w,i]
  • Space needed for 2n individual: O(n²)

Required Constant Time Actions

1. Identify a free man
2. For a man m, identify the highest-ranked woman to whom he has not yet proposed
3. For a woman w, decide is she is currently engaged, and if so, identify her current partner
4. For a woman w and two men m and m', decide who is preferred by w

1. Identify a free man: use a linked list; take the first man on the list, delete him when engaged, potentially insert m' at the front of the list
2. Identify the highest-ranked woman on a list: have an array Next that indicates the position of the next woman on his list for each man; initialization: Next[m] = 1; search: ManPref[m,Next[m]], increment value of Next[m] after proposal
3. Identify Engaged Woman's Current Partner: have an array Current; Current[w] = man she is currently engaged to; initialization: Current[w] = null
4. Identify Woman's Preference between m and m': use a 2D array Ranking consisting of [w,m] for each woman and her preferences. Compare values of Ranking[w,m] and Ranking[w,m'] in constant time.

Total Implementation Runtime: O(n²)

This section was relatively easy to understand as it was mostly review from CSCI 112. The refresher on lists and arrays was helpful, and was useful to review before exploring the implementation of the Stable Matching Problem. Between class lecture and this textbook section, the implementation and the associated running time makes sense. Readability: 10 Interesting: 8

Two Kinds of Bounds:

• On the goal running time
• On the size of the problem's natural search space

Linear Time

Computing the Maximum

• Check to see if the current number is greater than the maximum while traversing through the list/array: O(n)

Merging Two Sorted Lists

• Look at first value of each list to see which is smaller, and continue through both lists

• Each element can be involved in at most O(n) comparisons → Running-Time Bound: O(n²)
• Accounting Scheme: cost of each iteration at the time the element is selected and added to output list → Total Running Time: O(2n) → O(n)

O(n log n) Time

Common for any algorithm that splits input into two equal-sized parts, solves each part recursively, and then combines the two in linear time

• Merge Sort is an example
• Common because sorting input can be the most expensive step for many algorithms

Quadratic Time

• Perform a search over all pairs of input items and spending constant time per pair: multiply the number of ways of choosing the first member of the pair by the number of ways of choosing the second member of the pair → n * n → O(n²)
  • This is also the brute force approach because all pairs are being enumerated
• Nested Loops: each loop with O(n) time results in O(n²) iterations

Cubic Time

• Identify if there is disjoint (no elements in common) in some pair of sets (S₁, S₂,…S_n): for pair of sets S_i and S_j, determine whether S_i and S_j have an element in common.

O(n^k) Time

• Suppose we want to know if a given n-node input graph G has an independent set of size K
  • Natural Brute-Force Algorithm: Enumerates all subsets of k nodes & for each subset S, check whether there is an edge joining any two members of S
  • Outer loop: O(n^k) iterations in order to try all k-node subsets of the n nodes of the graph
  • Inner loop: O(k²) iterations in order to test where there is an edge joining each pair of nodes within the set
  • Total: O(k²n^k) → O(n^k) because constants can be dropped

Beyond Polynomial Time

• Running times that grow faster than any polynomial: 2ⁿ and n!
• Given a graph, find an independent set of maximum size

• Total number of subsets: 2ⁿ
• Outer Loop: O(2ⁿ)
• Inner Loop: Checking all pairs from a set S → O(n²)
• Total: O(n²2ⁿ) → O(2ⁿ)

• n!: number of ways to match up n items with n other items (number of perfect matches in the Stable Matching Problem)
• n!: search space consists of all ways to arrange n items in order (Traveling Salesman Problem)
• There are ways to solve n! algorithms in shorter times.

Sublinear Time

• Running times are asymptotically smaller than linear → goal is to minimize the amount of querying necessary
• Binary Search Algorithm: shrinking the size of the region where p might be by a factor of 2 each time/probe → after k probes, size is at most (1/2)^kn
  • For active region to be a constant: k = log₂n
  • This means search becomes constant time
  • Running Time: O(log n)

• O(log n) tends to be the time bound when a constant amount of work happens in order to throw away a constant fraction of input

This section was useful to read, as I sometimes struggle to identify situations where different running times apply. The more basic running times make sense, but I did struggle a little bit to understand the more complex running times (O(n^k) time, sublinear time, etc.). This section will be good to look back upon when we get into later algorithms. Readability: 6 Interesting: 6

The Problem

• Priority Queue: Elements have a priority value (key), and each time we need to select an element from S, we want to take the one with highest priority.
  1. Set of elements S
  2. Smaller keys represent higher priority
• Good for processing real-time events such as the scheduling of processes on a computer
• Priority Queue Operations: any sequence of priority queue operations that results in the sorting of n numbers → O(nlogn)

A Data Structure for Implementing a Priority Queue

• List: have a pointer to the min; adding new elements is easy, but extracting the minimum requires O(n) scan to find the new minimum
• Sorted Array: binary search to find position of insertion + shifting all elements → O(nlogn)
• Sorted Doubly Linked List: insertions are O(1), but O(n) to find position of insertion

The Heap: balanced binary tree; root + nodes with up to two children; key of any element is at least as large as the key of the parent node

• For a heap with bound N, we can use an array
• H[1] is the root
• leftChild(i) = 2i
• rightChild(i) = 2i+1

Implementing the Heap Operations

• Identifying Minimal Element: O(1)
• Adding an Element: add element to the final position, then perform heapify-up recursively → O(logn)

• Deleting an Element: move element w in position n to position i; key of element w may either be too small or too bit → O(logn)
• * If key is too small: use heapify-up to reestablish order
• * If key is too large: use heapify-down to sway the element with one of its children

Implementing Priority Queues with Heaps

• StartHeap(N): returns an empty heap that is set up to store at most N elements → O(n)
• Insert(H,v): inserts item v into heap H → O(logn)
• FindMin(H): identifies the min → O(1)
• Delete(H,i): deletes element in position i → O(logn)
• ExtractMin(H): identifies and deletes minimum key element → O(logn)

This section was pretty straightforward and easy to follow. I think going over the concepts in class before reading this section of the textbook was helpful in clarifying things that maybe would have been otherwise confusing. I appreciated the summary of the operation run times as these can sometimes be difficult to recall. Readability: 9 Interesting: 6