Notes on 📕Algorithms by 🐯Sedgewick & Wayne</i>

These are thoughts I had, and things I found interesting, while reading Algorithms

The notes are still in progress as I have not yet finished reading the book

1. Fundamentals

An algorithm is defined in Wikipedia as “a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation”. I don’t really like the Wikipedia definition, the definition in this book is better.

1.1 Basic Programming Model

Data abstraction is defined in Wikipedia as “a clear separation between the abstract properties of a data type and the concrete details of its implementation”
The book recommends using data all of the same primitive data type in expressions if at all possible instead of trying to figure out the intricacies of type conversion
Strongly typed is definited in Wikipedia as “stricter typing rules at compile time, which implies that errors are more likely to happen during compilation”
The books points out that recursive calls that overlap create great inefficiencies. This is why memoization / dynamic programming can help to avoid exponential running times.
The book points out that the variable in a for loop is only in scope in the for loop block. If you need the value of that value outside the block, use a while loop (or save it somewhere)
To print an array, use the Arrays.toString helper functions

1.2 Data Abstraction

Abstract data type is defined in Wikipedia as “a mathematical model for data types, defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations”
Aliasing is defined in Wikipedia as “a situation in which a data location in memory can be accessed through different symbolic names in the program”
Java’s parameter-passing strategy is sometimes called “call by sharing,” but I agree with the book that it’s pass by value for all practical purposes
Generic type is defined by the Java documentation as “a generic class or interface that is parameterized over types”
There’s a nod in the book toward factory method patterns, but then it clarifies that the only advanced Java language topics that are going to be used are generics and iterators
Encapsulation is defined in Wikipedia as “the bundling of data with the mechanisms or methods that operate on the data. It may also refer to the limiting of direct access to some of that data, such as an object’s components”
The book warns that APIs typically become too wide, because it’s easy to add methods, but difficult to deprecate them
The book contrasts interface inheritance / subtyping, with implementation inheritance / subclassing, though the definitions are a bit mixed together. Differences includee that the latter does not necessarily imply behavioral subtyping, and the latter can break encapsulation. The book recommends using interface inheritance, but using implementation inheritance only in particular situations and not in general
Fragile base class problem is defined by Wikipedia as “base classes (superclasses) are considered “fragile” because seemingly safe modifications to a base class, when inherited by the derived classes, may cause the derived classes to malfunction”
Equivalence relation is defined by Wikipedia as “a binary relation that is reflexive, symmetric, and transitive”
The book recommends a standard equals implementation: check for reference equality, check for null, use getClass to check for same class (this is mostly, but not always desired), then check instance variables
Final is defined in Wikipedia as “an entity that can only be assigned once”. Note that even if a field is final, if it is a reference type, the underlying object can change state
The book states immutable objects means that you are always creating new objects when you work with them, but that the Java garbage collector is optimized for that case
Design by contract is defined in Wikipedia as “software designers should define formal, precise and verifiable interface specifications for software components, which extend the ordinary definition of abstract data types with preconditions, postconditions and invariants”
The book recommends using exceptions to guard against problems outside your control, and assertions to guard against problems inside your control
Fail-fast system is defined in Wikipedia as “immediately reports at its interface any condition that is likely to indicate a failure. Fail-fast systems are usually designed to stop normal operation rather than attempt to continue a possibly flawed process”
The book questions why Java does not have first class functions. Modern versions of Java have lambda expressions and functional interfaces, which provide an approximation
The book points out that Java use of both primitive and reference types is a compromise to allow the performance boost from primitive types
The book points out that though Java is not thought of as having pointers, it does, but they are restricted to creation and assignment operators, which along with a good garbage collection algorithm and strong typing, eliminates many pointer problems
The book recommends not using static variables except in certain cases

1.3 Bags, Queues & Stacks

Parametric polymorphism is defined in Wikipedias as “allows a single piece of code to be given a “generic” type, using variables in place of actual types, and then instantiated with particular types as needed”
Autoboxing is defined in the Java documentation as “automatic conversion that the Java compiler makes between the primitive types and their corresponding object wrapper classes… If the conversion goes the other way, this is called unboxing”
Iterable is described in the Java documentation as “implementing this interface allows an object to be the target of the enhanced for statement (sometimes called the “for-each loop” statement)… Iterator<T> iterator() Returns an iterator over elements of type T.”
The book explains that stacks are useful for reversing the order of an arbitrary number of inputs
The book describes an algorithm for evaluating arithmetic expressions that are fully surrounded by parentheses using an operator and an operand stack (pop from both as necessary and evaluate when hit a right parenthesis)
Interpreter is defined in Wikipedia as “computer program that directly executes instructions written in a programming or scripting language, without requiring them previously to have been compiled into a machine language program”
The restrictions on generics in the Java documentation include “you cannot create arrays of parameterized types”
java.util.Arrays.copyOf is described in the Java documentation as “copies the specified array, truncating or padding with nulls (if necessary) so the copy has the specified length”
The book recommends setting references to null when no longer needed, rather than letting them loiter and avoid being garbage collected
java.util.Iterator is described in the Java documentation as “boolean hasNext() Returns true if the iteration has more elements. E next() Returns the next element in the iteration”
The book recommends overriding the default remove method for Iterators with a blank one (or throw an UnsupportedOperationException), because using the remove method can cause all kinds of confusion
In the Iterator example in the book, ReverseArrayIterator isn’t ReverseArrayIterator<Item> because it uses the outer class’s type parameter, not defines a new one of its own
Initializing fields is discussed in the Java documentation as “you can often provide an initial value for a field in its declaration…. However, this form of initialization has limitations because of its simplicity…. Instance variables can be initialized in constructors, where error handling or other logic can be used”
The book explains that adding a new field (like adding a tail reference to a linked list) may make certain operations easier/faster, but also adds new invariants that need to be maintained in all operations (like when removing the first item in a list)
Doubly linked lists are described in Wikipedia as “while adding or removing a node in a doubly linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified”
The book provides a for loop idiom to traverse a linked list. I prefer a while loop–to me, it makes it easier to understand the traversal
The book explains how data structures drive the fields of a class, while algorithms guide the methods. I think the separation is more porous–data structures often encompass the operations on the values
Covariant arrays are described in Wikipedia as “early versions of Java and C# did not include generics, also termed parametric polymorphism. In such a setting, making arrays invariant rules out useful polymorphic programs…. Therefore, both Java and C# treat array types covariantly…. With the addition of generics, Java and C# now offer ways to write this kind of polymorphic function without relying on covariance”
Type erasure is described in the Java documentation as “To implement generics, the Java compiler applies type erasure to: Replace all type parameters in generic types with their bounds or Object if the type parameters are unbounded. The produced bytecode, therefore, contains only ordinary classes, interfaces, and methods…”
The book points out that you can create an array of parametrized types by creating an array of the raw type then using an unchecked conversion to the parametrized type. However, it’s better to use something like an ArrayList instead
Static nested class is defined in the Java documentation as “do not have access to other members of the enclosing class…. In effect, a static nested class is behaviorally a top-level class that has been nested in another top-level class for packaging convenience.” Because static inner classes are treated like a top-level class, you have to be careful with generics
The Java documentation describes the following classes: “ArrayList - Resizable array implementation of the List interface (an unsynchronized Vector). The best all-around implementation of the List interface. [removeFirst is not O(1)] ArrayDeque - Efficient, resizable array implementation of the Deque interface. LinkedList - Doubly-linked list implementation of the List interface. Provides better performance than the ArrayList implementation if elements are frequently inserted or deleted within the list. Also implements the Deque interface. When accessed through the Queue interface, LinkedList acts as a FIFO queue”. The book points out that these classes frequently have wide interfaces, which may make them less efficient, and the client code harder to understand, than classes with more narrow interfaces
Fail-fast iterator is defined in the Java documentation as “if the list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future”

1.4 Analysis of Algorithms

The book points out that analyzing software is much less involved that analyzing the physical sciences and engineering world
Log–log plot is defined in Wikipedia as “two-dimensional graph of numerical data that uses logarithmic scales on both the horizontal and vertical axes. Power functions – relationships of the form y=axk – appear as straight lines in a log–log graph, with the exponent corresponding to the slope, and the coefficient corresponding to the intercept”. The book points out that y=axklg x looks similar
Power law is defined in Wikipedia as “functional relationship between two quantities, where a relative change in one quantity results in a relative change in the other quantity proportional to the change raised to a constant exponent: one quantity varies as a power of another”
Combination is defined in Wikipedia as “selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations)” (n choose k) = n!/k!(n-k)!
Asymptotic analysis is defined in Wikipedia as “method of describing limiting behavior…. Formally, given functions f (x) and g(x), we define a binary relation f(x) ~ g(x) (as x→∞) if and only if… lim_x→∞ f(x)/g(x) = 1”
Uniform cost / unit-cost model is defined in Wikipedia as “assigns a constant cost to every machine operation, regardless of the size of the numbers involved”
The number of bits in the binary representation of a positive integer n is described in Wikipedia as “integral part of 1 + lg n, i.e. floor(lg n) + 1”
Harmonic number is defined in Wikipedia as “sum of the reciprocals of the first n natural numbers: H_n = 1 + 1/2 + 1/3 + … + 1/n… The harmonic numbers roughly approximate the natural logarithm function”
Triangular number is defined in Wikipedia as “counts objects arranged in an equilateral triangle… 1+2+…+n = … = n(n+1)/2 = (n+1 choose 2)”
Stirling’s approximation is defined in Wikipedia as “ln(n!) = n ln n - n + O(ln n)”
Binomial coefficient has the property as described in Wikipedia that “(n choose k) ≤ nk / k!”
3SUM is defined in Wikipedia as “given set of n real numbers contains three elements that sum to zero…. integer (word RAM) models of computing, 3SUM can be solved in O(n2) time on average by inserting each number S[i] into a hash table, and then, for each index i and j, checking whether the hash table contains the integer -(S[i]+S[j]). It is also possible to solve the problem in the same time in a comparison-based model of computing or real RAM, for which hashing is not allowed. The algorithm below first sorts the input array and then tests all possible pairs in a careful order that avoids the need to binary search [an O(n2log n algorithm] for the pairs in the sorted list, achieving worst-case O(n2) time” For each i, do a two pointer sweep from i+1 and end, toward the middle
The book, which was published in 2011, agreed with Wikipedia that “It was conjectured that any deterministic algorithm for the 3SUM requires Ω(n2) time”, but “In 2014, the original 3SUM conjecture was refuted by Allan Grønlund and Seth Pettie who gave a deterministic algorithm that solves 3SUM in O(n2/(log n/log log n)2/3) time”
Moore’s law is defined in Wikipedia as “observation that the number of transistors in an integrated circuit (IC) doubles about every two years”
The book points out that sometimes analyzing algorithms where you need to know the structure of the input is hard, because sometimes the purpose of the algorithm is to discover pattern in inputs from, say, natural processes
Randomized algorithm is defined in Wikipedia as “employs a degree of randomness as part of its logic or procedure”
Amortized analysis is defined in Wikipedia as “averages the running times of operations in a sequence over that sequence”
I think the internal String representations have changed over time for optimization purposes since Strings are used to often, so I’m not sure if the description in the 2011 book still match the current Java internals
The book describes how Java stacks are allocated, but it seems a bit different from the current version as described in the Java documentation: “Because the Java Virtual Machine stack is never manipulated directly except to push and pop frames, frames may be heap allocated. The memory for a Java Virtual Machine stack does not need to be contiguous”
Heap is described in the Java documentation as “_shared among all Java Virtual Machine threads. The heap is the run-time data area from which memory for all class instances and arrays is allocated… Heap storage for objects is reclaimed by an automatic storage management system (known as a garbage collector); objects are never explicitly deallocated. _”
This chapter suggests generating a list of random numbers, saved to a test file, that you can use as test input to stay consistent. However, the use of seeds is preferred as described in the Java documentation: “If two instances of Random are created with the same seed, and the same sequence of method calls is made for each, they will generate and return identical sequences of numbers”
The book defines Big O notation with a < sign, but typically, it’s defined with a ≤ sign. I don’t know if it makes any difference in practice since you can just slightly increase c or N₀ to break the equality

The book contrasts Big O notation and asymptotic equivalence (~). They are contrasted in Wikipedia as “_Big O:

is asymptotically bounded above by g (up to constant factor k). lim sup_n→∞

f(n)

/g(n) < ∞” vs. “_Asymptotic equivalence: f is equal to g asymptotically. lim_n→∞ f(n)/g(n) = 1”

I prefer Big O notation to the book’s emphasis on asymptotic equivalence (~). I think it’s easier to understand and use

1.5 Case Study: Union-Find

Equivalence relation is defined in Wikipedia as “binary relation that is reflexive, symmetric, and transitive…. Each equivalence relation provides a partition of the underlying set into disjoint equivalence classes”
Dynamic connectivity structure is defined in Wikipedia as “dynamically maintains information about the connected components of a graph”
Union–find data structure is defined in Wikipedia as “stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them with their union), and finding a representative member of a set. The last operation makes it possible to determine efficiently whether any two elements belong to the same set or to different sets. While there are several ways of implementing disjoint-set data structures, in practice they are often identified with a particular implementation known as a disjoint-set forest. This specialized type of forest performs union and find operations in near-constant amortized time…. Each node in a disjoint-set forest consists of a pointer and some auxiliary information, either a size or a rank (but not both). The pointers are used to make parent pointer trees, where each node that is not the root of a tree points to its parent. To distinguish root nodes from others, their parent pointers have invalid values, such as a circular reference to the node or a sentinel value. Each tree represents a set stored in the forest, with the members of the set being the nodes in the tree. Root nodes provide set representatives: Two nodes are in the same set if and only if the roots of the trees containing the nodes are equal. Nodes in the forest can be stored in any way convenient to the application, but a common technique is to store them in an array. In this case, parents can be indicated by their array index”
The book describes an proof by induction by showing the property is true at the start, and that each operation preserves the property
Various tree terms are defined in Wikipedia as “The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path)…. Size of a tree: Number of nodes in the tree”
Path compression during find operations is defined in Wikipedia as “makes every node between the query node and the root point to the root”
Cell-probe model of computation is defined in Wikipedia as “similar to the random-access machine, except all operations are free except memory access. This model is useful for proving lower bounds of algorithms for data structure problems”
The book points out that deleting items efficiently from a data structure is often a harder problem than query and addition operations

2. Sorting

2.1 Elementary Sorts

Comparable<T> is described in the Java documentation as “imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class’s natural ordering, and the class’s compareTo method is referred to as its natural comparison method. Lists (and arrays) of objects that implement this interface can be sorted automatically by Collections.sort (and Arrays.sort)”
Selection sort is defined in Wikipedia as “proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right…. While selection sort is preferable to insertion sort in terms of number of writes (n-1 swaps versus up to n(n-1)/2 swaps, with each swap being two writes)…. This can be important if writes are significantly more expensive than reads, such as with EEPROM or Flash memory, where every write lessens the lifespan of the memory”
Insertion sort is defined in Wikipedia as “_ Adaptive, i.e., efficient for data sets that are already substantially sorted…. At each array-position, it checks the value there against the largest value in the sorted list (which happens to be next to it, in the previous array-position checked). If larger, it leaves the element in place and moves to the next. If smaller, it finds the correct position within the sorted list, shifts all the larger values up to make a space, and inserts into that correct position_”
Law of large numbers is defined in Wikipedia as “average of the results obtained from a large number of independent random samples converges to the true value, if it exists. More formally…given a sample of independent and identically distributed values, the sample mean converges to the true mean”
Shellsort is defined in Wikipedia as “starts by sorting pairs of elements far apart from each other, then progressively reducing the gap between elements to be compared. By starting with far-apart elements, it can move some out-of-place elements into the position faster than a simple nearest-neighbor exchange…. an optimization of insertion sort that allows the exchange of items that are far apart…. the last gap is always 1 to finish the sort (effectively finishing with an ordinary insertion sort)… since it can be implemented using little code and does not use the call stack, some implementations of the qsort function in the C standard library targeted at embedded systems use it instead of quicksort”
The book points out that large gap subsequences are short, and small gap subsequences are partially sorted, both of which are strengths of insertion sort
The book points out that as computers have gotten faster, small improvements in algorithms make less difference in practice

2.2 Mergesort

Merge sort is defined in Wikipedia as “Divide the unsorted list into n sub-lists, each containing one element (a list of one element is considered sorted). Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list”
Divide and conquer is defined in Wikipedia as “recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem”
Top-down merge sort is defined in Wikipedia as “recursively splits the list (called runs in this example) into sublists until sublist size is 1, then merges those sublists to produce a sorted list”
The book presents an interesting optimization of testing whether the right side of the left partition is less than or equal to the left side of the right partitition, to avoid an unnecessary merge
The book recommends against premature optimization: implement the simplest algorithm, then optimize if necessary
Bottom-up merge sort is defined in Wikipedia as “treats the list as an array of n sublists (called runs in this example) of size 1, and iteratively merges sub-lists back and forth between two buffers…. Each 1-element run in A is already “sorted”… Make successively longer sorted runs of length 2, 4, 8, 16… until the whole array is sorted.” This algorithm is iterative
java.util.Arrays.sort for reference types is described in the Java documentation as “stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered. If the input array is nearly sorted, the implementation requires approximately n comparisons. Temporary storage requirements vary from a small constant for nearly sorted input arrays to n/2 object references for randomly ordered input arrays. The implementation takes equal advantage of ascending and descending order in its input array, and can take advantage of ascending and descending order in different parts of the same input array. It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array. The implementation was adapted from Tim Peters’s list sort for Python ( TimSort)…”
java.util.Arrays.parallelsort for refererence types is described in the Java documentation as “parallel sort-merge that breaks the array into sub-arrays that are themselves sorted and then merged. When the sub-array length reaches a minimum granularity, the sub-array is sorted using the appropriate Arrays.sort method. If the length of the specified array is less than the minimum granularity, then it is sorted using the appropriate Arrays.sort method. The algorithm requires a working space no greater than the size of the original array”
Permutation of a set is defined in Wikipedia as “an arrangement of its members in a sequence or linear order…. The number of permutations of n distinct objects is n factorial, usually written as n!, which means the product of all positive integers less than or equal to n”
Perfect binary tree is defined in Wikipedia as “all interior nodes have two children and all leaves have the same depth”
Complete binary tree is defined in Wikipedia as “every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes at the last level h”
The definition of complete binary tree in the book is a bit different from Wikipedia: “Some authors use the term complete to refer instead to a perfect binary tree as defined above”
Stirling’s approximation is defined in Wikipedia as “lg(n!)= n lg n - n lg e + O(lg n)”
Comparison sort is defined in Wikipedia as “only reads the list elements through a single abstract comparison operation (often a “less than or equal to” operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list… A comparison sort must have an average-case lower bound of Ω(n log n) comparison operations…. In this sense, mergesort…are asymptotically optimal in terms of the number of comparisons they must perform, although this metric neglects other operations. Non-comparison sorts…can achieve O(n) performance by using operations other than comparisons, allowing them to sidestep this lower bound (assuming elements are constant-sized)”

2.3 Quicksort

Quicksort is defined in Wikipedia as “selecting a “pivot” element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot…. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting”
The book points out that in merge sort, the sub-arrays are recursively sorted, then the combination is merged, while in quicksort, the main array is partitioned, then the sub-arrays are recursively sorted
The book uses a variant of the Hoare partition scheme which is described in Wikipedia as “two pointers (indices into the range) that start at both ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater than the pivot at the first pointer, and one less than the pivot at the second pointer; if at this point the first pointer is still before the second, these elements are in the wrong order relative to each other, and they are then exchanged. After this the pointers are moved inwards, and the search for an inversion is repeated; when eventually the pointers cross (the first points after the second), no exchange is performed; a valid partition is found, with the point of division between the crossed pointers (any entries that might be strictly between the crossed pointers are equal to the pivot and can be excluded from both sub-ranges formed)