Chapter 2 – Basics of Algorithm Analysis

My notes on the assigned sections of Chapter 2 of Algorithm Design by Jon Kleinberg and Éva Tardos. This chapter details the resource requirements for algorithms, talking about the time and space that they use, later developing run-time bounds for some basic, popular algorithms.

Section 1 of chapter 2 attempts to define what efficiency is in terms of an algorithm. The initial proposed definition of efficiency from the book is when an algorithm is “implemented, it runs quickly on real input instances”. Bad algorithms can run fast with small test cases, and good algorithms can run slowly if they are coded poorly. Furthermore, this definition doesn't take into account how an algorithm scales with increasing input. So, a second definition is proposed: “an algorithm is efficient if it achieves qualitatively better worst-case performance, at an analytical level, than brute-force search”. So, we use polynomial time as a definition of efficiency. With polynomial time, when the input size increases by a constant factor, the algorithm should slow by a constant factor C. “If the input size increases from N to 2N, the bound on the running time increases from cN^d to c(2N)^d”. This marks a slow-down of a factor of 2^d. The third definition of efficiency says that polynomial time is efficient. With large constants or high exponents, polynomial time won't run efficiently.

This section was very readable, and I would give it a score of 10/10 on both readability and my interest in it.

This section covers the ways in which we can classify an algorithm's order of growth. This classifiers are O, Ω, and Θ. O(.) defines the asymptotic upper bound for an algorithm, Ω(.) defines the asymptotic lower bound for an algorithm, and Θ defines the asymptotically tight bound for an algorithm. An asymptotically tight bound means that O(.) == Ω(.). Asymptotic growth rates have many properties including transitivity: if f = O(g) and g = O(h), then f = O(h) and if f = Ω(g) and g = Ω(h), then f = Ω(h). They also interesting results when you add 2 functions, like f = O(h) and g = O(h), then f + g = O(h). For polynomials, asymptotic rate of growth is determined by their higher order term. Algorithms can be polynomial time even if they aren't written as n raised to an integer power (like O(nlogn)). For logarithms, “the base of the logarithm is not important when writing the bounds in asymptotic notation”. Finally, with exponentials, the terminology gets very sloppy, but when someone refers to an algorithm as exponential, then they mean that the running time grows as fast as some exponential function.

Overall I thought this section was pretty readable and very interesting. I'd give it a 7/10 for readability and a 10/10 for how interesting I thought it was. A couple of the proofs were a bit difficult to follow, but with a slow, careful read I was able to understand them.

This section goes over the actual way to program the G-S Stable Matching Algorithm with commonly used data structures. We can do this with some preprocessing of data structures as well. The 2 simple data structures that will be used are lists (linked list implementation; O(i) access, O(1) adding, O(i) deleting) and arrays (O(1) access, O(1) adding but might have to double space in memory for a resize, and O(n) deleting). Preprocessing these two data structures is easy as you can convert between arrays and lists in O(n) time. We previously showed that the algorithm runs in O(n^2) time, so we need to be able to implement the following 4 things in constant time for that to happen:

1. Identify a free man
2. For a man m, we need to find the highest-ranked woman to whom he hasn't proposed
3. For a woman w, we need to find out if she's currently engaged, and if so, ID her current partner
4. For a woman w and two men m and m', we need to decide which w prefers

Free men will be implemented as a linked list because we will need to easily manipulate its contents (lends better to a linked implementation so we don't have to deal with shifting). Here we can delete first man in list in constant time and insert another man in the list in constant time. To ID the highest-ranked woman to who m hasn't proposed to, we can have an array for all men Next[m], where it is initialized to 1 and incremented for each proposal regardless of outcome. To decide if w is currently engaged and to get her partner, we can have an array of size n Current[w], which is w's current partner (null if she doesn't have one). The naive way to determine which out of m and m' w prefers is to walk through w's list one by one to compare the two, giving us a O(n) runtime. However, if we initialize an nxn array Ranking at the beginning, where Ranking[w, m] contains rank of m in the sorted order of w's preferences, we can compare m and m's ranking in O(1) time.

This section was explained very well and I'd give it a 10/10 in both readability and my interest. The only thing I'm still a tiny bit confused about is how the algorithm is still O(n^2) with the Ranking initialization. Is it because this initialization technically isn't part of the algorithm, so you don't count it in the algorithm runtime?