Skip to content
Elvis Chidera

[WIP] The Algorithm Design Manual - Notes

notes36 min read

Pet Peeve: The author sometimes skips steps without an explaination (like the integer truncation in "stop and think: incremental correctness"). Some examples are hard to follow for an international student (like understanding the lottery system in "war story: pschic modeling").

Chapter 1: Introduction to Algorithm Design

A computational problem is a specification of a desired input-output relationship. e.g.

Computational problem: Sorting

Input: A sequence of nn values a1a_1, ..., ana_n.

Output: The permutation (reordering) of the input sequence such that a1a2a'_1 \leq a'_2 ... an1ana'_{n-1} \leq a'_n.

An instance of a problem is all the inputs needed to compute a solution to the problem. Alternatively, a computational problem is the set of all (problem) instances and the desired output. e.g.

To sort the permutation {8, 3, 6, 7} is an instance of the general sorting problem and {3, 6, 7, 8} is the desired output.

An algorithm is a well-defined computational procedure that halts with a desired output when given any instance of the given computational problem. An algorithm is an abstract (idea) and can have multiple implementations (programs). e.g.

1/*
2Insertion sort is an algorithm to the sorting problem: Start with a single
3element (thus forming a trivially sorted list) and then incrementally inserts
4the remaining elements so that the list stays sorted.
5*/
6insertion_sort(item s[], int n)
7{
8 int i,j; /* counters */
9 for (i=0; i<n; i++) {
10 j=i;
11
12 while ((j>0) && (s[j] < s[j-1])) {
13 swap(&s[j],&s[j-1]);
14 j = j-1;
15 }
16 }
17}

Modeling the problem

Real-world applications involve real-world objects. However, most algorithms are designed to work on rigorously defined abstract structures. Modeling is the art of formulating your application in terms of procedures on such fundamental abstract structures so as to exploit the existing algorithms literature.

Determining that you are dealing with an instance of a general problem allows you to solve it using general well-known algorithms.

Certain problems can be modeled in several different ways, some much better than others. Modeling is only the first step in designing an algorithm for a problem. Be alert but not dismissive for how the details of your applications differ from a candidate model.

Combinatorial Objects

  1. Permutations are arrangements, or orderings, of items. E.g: {1,4,3,2} and {4,3,2,1} are two distinct permutations of the same set of four integers.
  2. Subsets represent selections from a set of items. E.g: {1,3,4} and {2} are two distinct subsets of the first four integers. Order does not matter in subsets the way it does with permutations.
  3. Trees represent hierarchical relationships between items.
  4. Graphs represent relationships between arbitrary pairs of objects.
  5. Points define locations in some geometric space.
  6. Polygons define regions in some geometric spaces.
  7. Strings represent sequences of characters, or patterns.

fig1 8

Modeling real-world structures with trees and graphs

Recursive Objects

Learning to think recursively is learning to look for big things that are made from smaller things of exactly the same type as the big thing.
If you think of houses as sets of rooms, then adding or deleting a room still leaves a house behind.

  1. Permutations: Delete the first element of a permutation of n things {1, ..., n} and you get a permutation of the remaining n-1 things. Basis case: {}
  2. Subsets: Every subset of {1, ..., n} contains a subset of (1, ..., n - 1) obtained by deleting element n. Basis case: {}
  3. Trees: Delete the root of a tree and you get a collection of smaller trees. Delete any leaf of a tree and you get a slightly smaller tree. Basis case: 1 vertex.
  4. Graphs: Delete any vertex from a graph, and you get a smaller graph. Now divide the vertices of a graph into two groups, left and right. Cut through all edges that span from left to right, and you get two smaller graphs, and a bunch of broken edges. Basis case: 1 vertex.
  5. Point sets: Take a cloud of points, and separate them into two groups by drawing a line. Now you have two smaller clouds of points. Basis case: 1 point.
  6. Polygons: Inserting any internal chord between two non-adjacent vertices of a simple polygon cuts it into two smaller polygons. Basis case: triangle.
  7. Strings: Delete the first character from a string, and you get a shorter string. Basis case: empty string.

Recursive descriptions of objects require both decomposition rules and basis cases, namely the specification of the smallest and simplest objects where the decomposition stops.

fig1 9

Recursive decompositions of combinatorial objects. (left column) Permutations, subsets, trees, and graphs. (right column) Point sets, polygons, and strings

An algorithmic problem is specified by describing the complete set of instances it must work on and of its output after running on one of these instances.

There is a distinction between a general problem and an instance of a problem. E.g:

Problem: Sorting
Input: A sequence of n keys a1,...,an.
Output: The permutation (reordering) of the input sequence such that: a′1 ≤ a′2 ≤ ··· ≤ a′n−1 ≤ a′n.
Instance of sorting problem: { Mike, Bob, Sally}; { 154, 245 }

An algorithm is a procedure that takes any of the possible input instances and transforms it to the desired output.

Three desirable properties for a good algorithm:

  • Correct
  • Efficient
  • Easy to implement
  1. Insertion sort is an algorithm to the sorting problem: English description:

    Start with a single element (thus forming a trivially sorted list) and then incrementally inserts the remaining elements so that the list stays sorted.

    Pseudocode:

    1array = input sequence
    2n = array size
    3i = 0
    4
    5while i < n
    6 j = i
    7 while j > 0 AND array[j] < array[j - 1]
    8 swap element at `j` with element at `j - 1` in array
    9 decrement j by 1
    10 increment i by 1

    Code:

    An animation of the logical flow of this algorithm on a particular instance (the letters in the word “INSERTIONSORT”) fig1 1

Robot Tour Optimization

Problem: Robot Tour Optimization (aka: Traveling Salesman Problem [TSP]).
Input: A set S of n points in the plane.
Output: What is the shortest cycle tour that visits each point in the set S?

Nearest-neighbor heuristic

A good instance for the nearest-neighbor heuristic

  1. English Description:

    Starting from some point p0, we walk first to its nearest neighbor p1 From p1, we walk to its nearest unvisited neighbor. Repeat this process until we run out of unvisited points After which we return to p0 to close off the tour.

  2. Pseudocode:
    1NearestNeighbor(P)
    2 Pick and visit an initial point p₀ from P
    3 p = p₀
    4 i = 0
    5
    6 While there are still unvisited points
    7 i = i + 1
    8 Select pᵢ to be the closest unvisited point to pᵢ₋₁
    9 Visit pᵢ
    10 Return to p₀ from pₙ₋₁
  3. Pros:
    • Easy to understand & implement
    • Reasonably efficient
  4. Cons: It's wrong — It always finds a tour, but it doesn’t necessarily find the shortest possible tour. E.g: A bad instance for the nearest-neighbor heuristic (top) & the optimal solution (bottom): fig1 3

Closest-pair heuristic

  1. English description:

    Repeatedly connect the closest pair of endpoints whose connection will not create a problem, such as premature termination of the cycle. Each vertex begins as its own single vertex chain. After merging everything together, we will end up with a single chain containing all the points in it. Connecting the final two endpoints gives us a cycle. At any step during the execution of this closest-pair heuristic, we will have a set of single vertices and vertex-disjoint chains available to merge.

  2. Pseudocode:

Reasoning about Correctness

Correct algorithms usually come with a proof of correctness, which is an explanation of why we know that the algorithm must take every instance of the problem to the desired result.

  1. We need tools to distinguish correct algorithms from incorrect ones, the primary one of which is called a proof.
  2. A proper mathematical proof consists of several parts:
    • A clear, precise statement of what you are trying to prove.
    • A set of assumptions of things that are taken to be true, and hence can be used as part of the proof.
    • A chain of reasoning that takes you from these assumptions to the statement you are trying to prove.
    • A little square (■) or QED at the bottom to denote that you have finished, representing the Latin phrase for "thus it is demonstrated."
  3. A proof is indeed a demonstration. Proofs are useful only when they are honest, crisp arguments that explain why an algorithm satisfies a non-trivial correctness property.

Problems and Properties

  1. It is impossible to prove the correctness of an algorithm for a fuzzily-stated problem.
  2. Problem specifications have two parts:
    1* The set of allowed input instances.
    2* The required properties of the algorithm's
    output.
  3. An important technique in algorithm design is to narrow the set of allowable instances until there is a correct and efficient algorithm. For example, we can restrict a graph problem from general graphs down to trees, or a geometric problem from two dimensions down to one.
  4. There are two common traps when specifying the output requirements of a problem:
    1* Asking an ill-defined question. E.g: Asking for the best route between two places on a map is a silly question, unless you define what best means.
    2* Creating compound goals. E.g: A goal like find the shortest route from **a** to **b** that doesn't use more than twice as many turns as necessary is perfectly well defined, but complicated to reason about and solve.

Expressing Algorithms

  1. The heart of any algorithm is an idea. If your idea is not clearly revealed when you express an algorithm, then you are using too low-level a notation to describe it.
  2. The three most common forms of algorithmic notation are
    • English
    • Pseudocode (a programming language that never complains about syntax errors)
    • A real programming language.
  3. All three methods are useful because there is a natural tradeoff between greater ease of expression and precision.

Demonstrating Incorrectness

  1. The best way to prove that an algorithm is incorrect is to produce a counter example, i.e: an instance on which it yields an incorrect answer.
  2. Good counterexamples have two important properties:
    • Verifiability: To demonstrate that a particular instance is a counterexample to a particular algorithm, you must be able to:
      • calculate what answer your algorithm will give in this instance, and
      • display a better answer so as to prove that the algorithm didn't find it.
    • Simplicity - Good counter-examples have all unnecessary details stripped away. They make clear exactly why the proposed algorithm fails. Simplicity is important because you must be able to hold the given instance in your head in order to reason about it.

Induction and Recursion

  1. Recursion is mathematical induction in action. In both, we have general and boundary conditions, with the general condition breaking the problem into smaller and smaller pieces. The initial or boundary condition terminates the recursion.
  2. The simplest and most common form of mathematical induction infers that a statement involving a natural number n (that is, an integer n ≥ 0) holds for all values of n. The proof consists of two steps:
    • The initial or base case: prove that the statement holds for a fixed natural number (usually 0 or 1).
    • The induction/inductive step: assume that the statement holds for some arbitrary natural number n = k, and prove that the statement holds for n = k + 1.
  3. The hypothesis in the inductive step, that the statement holds for n = k, is called the induction/inductive hypothesis. You're doing a thought experiment of what would happen if it was true for n = k. It might be clearer to use the phrase "suppose true when n = k" rather than "assume true when n = k" to emphasise this.
  4. To prove the inductive step, one assumes the induction hypothesis for n = k and then uses this assumption to prove that the statement holds for n = k + 1. We try to manipulate the statement for n = k + 1 so that it involves the case for n = k (which we assumed to be true).

Inductive proof for Insertion sort

  1. The basis case consists of a single element, and by definition a one-element array is completely sorted.
  2. We assume that the first n - 1 elements of array A are completely sorted after n - 1 iterations of insertion sort.
  3. To insert one last element x to A, we find where it goes, namely the unique spot between the biggest element less than or equal to x and the smallest element greater than x. This is done by moving all the greater elements back by one position, creating room for x in the desired location. ■

Modeling the Problem

  1. Modeling is the art of formulating your application in terms of precisely described, well-understood problems.
  2. Proper modeling is the key to applying algorithmic design techniques to real-world problems — it can eliminate the need to design an algorithm, by relating your application to what has been done before.
  3. Real-world applications involve real-world objects — like a system to route traffic in a network or find the best way to schedule classrooms in a university.
  4. Most algorithms, however, are designed to work on rigorously defined abstract structures such as permutations, graphs, and sets.
  5. To exploit the algorithms literature, you must learn to describe your problem abstractly, in terms of procedures on such fundamental structures.
  6. The act of modeling reduces your application to one of a small number of existing problems and structures. Such a process is inherently constraining, and certain details might not fit easily into the given target problem.

Proof by Contradiction

  1. The basic scheme of a contradiction argument is as follows:
    • Assume that the hypothesis (the statement you want to prove) is false.
    • Develop some logical consequences of this assumption.
    • Show that one consequence is demonstrably false, thereby showing that the assumption is incorrect and the hypothesis is true.
  2. The classic contradiction argument is Euclid's proof that there are an infinite number of prime numbers:
    • The negation of the claim would be that there are only a finite number of primes, say m, which can be listed as p₁,..., pₘ. So let's assume this is the case and work with it.
    • Prime numbers have particular properties with respect to division. Suppose we construct the integer formed as the product of "all" of the listed primes: [ N = \prod{i = 1}^{m} p{i} ]
    • This integer N has the property that it is divisible by each and every one of the known primes, because of how it was built.
    • But consider the integer N + 1. It can't be divisible by p₁ = 2, because N is.
    • The same is true for p₂ = 3 and every other listed prime. Since a +1 can’t be evenly split by any of the prime numbers because they are bigger.
    • Since N + 1 doesn't have any non-trivial factor, this means it must be prime.
    • But you asserted that there are exactly m prime numbers, none of which are N + 1, because N + 1 > m.
    • This assertion is false, so there cannot be a bounded number of primes.
  3. For a contradiction argument to be convincing, the final consequence must be clearly, ridiculously false.

Estimation

  1. Principled guessing is called estimation.
  2. Estimation problems are best solved through some kind of logical reasoning process, typically a mix of principled calculations and analogies.
  3. Principled calculations give the answer as a function of quantities that either you already know, can look up on Google, or feel confident enough to guess.
  4. Analogies reference your past experiences, recalling those that seem similar to some aspect of the problem at hand.

Exercises

Finding counter examples

  1. Show that a + b can be less than min(a, b).

    When:
       a and b < 0 (i.e: negative)
       a <= b
    Then:
       min(a, b) = a
       a + b < a
    Example:
       min(-6, -5) = -6
       -6 + -5 = -6 -5 = -11
       -11 < -6

  2. Show that a × b can be less than min(a, b).

    When:
       a < 0 (i.e: negative)
       b > 0 (i.e: positive)
    Then:
       min(a, b) = a
       a * b < a
    Example:
       min(-3, 4) = -3
       -3 * 4 = -12
       -12 < -3

  3. Design/draw a road network with two points a and b such that the fastest route between a and b is not the shortest route.

    1a──────c──────b
    2│             │
    3│ │
    4└────d────────┘
    5
    6Route `acb` have a toll gate, is in development and have a speed limit.
    7Route `adb` is longer, but has none of these impediment.
    8
    9Route `adb` will be faster than the shorter `acb` route.
  4. Design/draw a road network with two points a and b such that the shortest route between a and b is not the route with the fewest turns.

    1a────┐ ┌────b
    2│    └─c─┘    │
    3│ │
    4└──────d──────┘
    5
    6Route `acb` is the shortest but has 4 turns.
    7Route `adb` is the longest and has only 2 turns.

Induction

  1. Prove that i=1ni=n(n+1)2\sum_{i = 1}^{n} i = \frac{n(n + 1)}{2} for n ≥ 0, by induction.

Chapter 2: Algorithm Analysis

The analysis of algorithms is the process of finding the computational complexity of algorithms.

For an ordered list of size nn (3333 in the example above), binary search takes at most log2n\log_2 n check steps (55 steps in the example above); while linear search takes at most nn check steps (2828 steps in the example above).

🏋️‍♀️ Computational complexity

The computational complexity or simply complexity of an algorithm is the amount of resources required to run it.

Common types of resources include:

  1. Time — Time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. When "complexity" is used without qualification, this generally means time complexity.
  2. 🫙 Memory — Space complexity is the computational complexity that describes the amount of memory it takes to run an algorithm.
  3. 🎙️ Communication — The necessary amount of communication between executing parties in a distributed algorithm.

The computational complexity of an algorithm can be measured only when given a model of computation.

💻 The RAM model of computation

The most commonly used model of computation is the Random Access Machine (RAM) which is a hypothetical computation model where:

  • Each simple operation (like +, *, -, =, if, call, etc) takes exactly unit-time (i.e. 1 step).
  • Each complex operation (like loops and subroutines) is the composition of simple operations. The time it takes to run through a loop or execute a subprogram depends upon the number of loop iterations or the specific nature of the subprogram.
  • Each memory access takes exactly unit-time (i.e. 1 step), regardless of data location (cache or disk). There is also unlimited memory.

The RAM is a simple model of how computers perform. It allows the analysis of algorithms in a machine-independent way by assuming that simple operations take a constant amount of time on a given computer and change only by a constant factor when run on a different computer.

It doesn’t capture the full complexity of real computers (e.g. multiplying two numbers takes more time than adding two numbers on most processors). However, the RAM is still an excellent model for understanding how an algorithm will perform on a real computer.

A model is a simplification or approximation of reality and hence will not reflect all of reality. […] "all models are wrong, but some are useful." — Model Selection and Multimodel Inference

🏭 Computational complexity functions

Under the RAM model, we measure the computational complexity by counting the number of simple operations (also called steps) an algorithm takes on a given problem instance.

As the amount of resources required to run an algorithm generally varies with the size of the input, the complexity is typically expressed as a function nf(n)n \rightarrow f(n), where nn is the size of the input and f(n)f(n) is the computational complexity.

Aside: We can also use any other characteristic of the input influencing the computational complexity.

However, the complexity of an algorithm may vary dramatically for different inputs of the same size. Therefore, three complexity functions are commonly used:

  1. 🔵 Worst-case complexity: is the maximum of the complexity over all inputs of size nn.
    • It expresses the resources used by an algorithm at most.
    • e.g. the worst-case time complexity for a simple linear search on a list is nn and occurs when the desired element is the last element of the list or is not in the list.
    • Worst-case analysis gives a safe analysis (the worst case is never underestimated), but one which can be overly pessimistic, since there may be no (realistic) input that would take this many steps.
    • Generally, when "complexity" is used without being further specified, this is the worst-case computational complexity that is considered.
  2. 🟢 Average-case complexity: is the average of the complexity over all inputs of size nn.
    • It expresses the resources used by an algorithm on average.
    • Average-case analysis requires a notion of an "average" input to an algorithm, which leads to the problem of devising a probability distribution over inputs.
    • e.g. the average-case time complexity for a simple linear search on a list is n/2n/2 assuming the value searched for is in the list and each list element is equally likely to be the value searched for.
    • Con: Determining what typical input means is difficult and average case analysis tends to be more difficult.
  3. 🔴 Best-case complexity: is the minimum of the complexity over all inputs of size nn.
    • It expresses the resources used by an algorithm at least.
    • e.g. the best case time complexity for a simple linear search on a list is 11 and occurs when the desired element is the first element of the list.
    • Con: It's unlikely to happen in practice.
Line graph of worst, average, best case complexity

📈 Big oh notation

There are three problems with the complexity functions above:

  1. The exact computational complexity functions for any algorithm are liable to be complicated because they tend to have lots of up-and-down bumps.
  2. In addition, these exact values provide little practical application, as any change of computer or model of computation would change the complexity somewhat.
  3. Moreover, the resource use is not critical for small values of nn.

Complexity theory seeks to quantify the intrinsic time requirements of algorithms (independent of any external factors), that is, the basic time constraints an algorithm would place on any computer .

For these reasons, one generally focuses on the behavior of the complexity for large nn, that is on its asymptotic behavior when nn tends to infinity. Therefore, the complexity is generally expressed by using big O notation.

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards infinity. The formal definition of the big O notations are:

1. Big O (Upper bound)

Notation: f(n)=O(g(n))f(n) = O(g(n))

Meaning: There exists some constant cc such that f(n)cg(x)|f(n)| \leq c \cdot |g(x)| for large enough nn (i.e. for all nn0n \geq n_0, for some constant n0n_0).

Big O graph

2. Big Omega (Lower bound)

Notation: f(n)=Ω(g(n))f(n) = \Omega(g(n))

Meaning: Means there exists some constant cc such that f(n)cg(x)|f(n)| \geq c \cdot |g(x)| for large enough nn (i.e. for all nn0n \geq n_0, for some constant n0n_0).

Big Omega graph

3. Big Theta (Tight bound [upper & lower bound])

Notation: f(n)=Θ(g(n))f(n) = \Theta(g(n))

Meaning: Means there exists some constants c1c_1 and c2c_2 such that f(n)c1g(x)|f(n)| \leq c_1 \cdot |g(x)| and f(n)c2g(x)|f(n)| \geq c_2 \cdot |g(x)| for large enough nn (i.e. for all nn0n \geq n_0, for some constant n0n_0).

Big Theta graph

🙅‍♂️ Misconception: Conflating Big-O with complexity functions

The best/average/worst-case computational complexity is a function of the size of the input for a certain algorithm.

The OO, Ω\Omega, and Θ\Theta notations are used to describe the relationship between two functions.

Hence, each best/average/worst case computational complexity function has its corresponding OO, Ω\Omega, and Θ\Theta notation.

Conflating the big O notations with the computational complexity functions likely stems from the fact that in everyday use, “the big O of the worst-case computational complexity function” is used interchangeably with just “big O”, “time complexity”, “complexity”, etc.

🙈 Abuse of notation

There are two accepted abuses of notation in the computer science industry:

  1. Abuse of the equal sign: Technically, the appropriate notation is f(n)O(g(n))f(n) \in O(g(n)), because the equal sign does not imply symmetry.

  2. Abuse of the Big O notation: The big O notation is often used to describe an asymptotic tight bound where using big Theta Θ\Theta notation would be more factually appropriate. Big O notation provides an upper bound, but it doesn't necessarily provide a tight upper bound. For example, 2n2+3n+12n^2 + 3n + 1 is O(n2)O(n^2), but it is also O(n3)O(n^3), O(n4)O(n^4), etc. For contrast, the equation is only Θ(n2)\Theta(n^2).

Common Big O functions

The function g(x)g(x) appearing within the O()O(·) is typically chosen to be as simple as possible, omitting constant factors and lower-order terms.

Common Big O function classes
  • Constant functions:

    • f(n)=1f(n) = 1
    • In the big picture, there is no dependence on the parameter nn.
    • Such functions might measure the cost of adding two numbers or the growth realized by functions such as f(n)=min(n,100)f(n) = min(n, 100).
  • Logarithmic functions:

    • f(n)=log2nf(n) = \log_2 n
    • Logarithmic time complexity shows up in algorithms such as binary search
    • Such functions grow quite slowly as nn gets big.
  • Linear functions:

    • f(n)=nf(n) = n
    • Such functions measure the cost of looking at each item once (or twice, or ten times) in an nn-element array, say to identify the biggest item, the smallest item, or compute the average value.
  • Superlinear functions:

    • f(n)=nlog2nf(n) = n \log_2 n
    • This important class of functions arises in such algorithms as Quicksort and Mergesort.
  • Quadratic functions:

    • f(n)=n2f(n) = n^2
    • Such functions measure the cost of looking at most or all pairs of items in an nn-element universe. This arises in algorithms such as insertion sort and selection sort.
  • Cubic functions:

    • f(n)=n3f(n) = n^3
    • Such functions enumerate through all triples of items in an nn-element universe.
  • Exponential functions:

    • f(n)=cnf(n) = c^n for a given constant c>1c > 1
    • Functions like 2n2^n arise when enumerating all subsets of nn items.
  • Factorial functions:

    • f(n)=n!f(n) = n!
    • Functions like n!n! arise when generating all permutations or orderings of nn items.

Arithmetic operations with Big O notation

  1. Addition:

    • If f(n)f(n) is O(g(n))O(g(n)) and h(n)h(n) is O(k(n))O(k(n)), then f(n)+h(n)f(n) + h(n) is O(max(g(n),k(n)))O(\max(g(n), k(n))).
    • This is because the dominant function among g(n)g(n) and k(n)k(n) will dictate the overall growth rate.
  2. Multiplication by a constant:

    • If f(n)f(n) is O(g(n))O(g(n)), then cf(n)c \cdot f(n) is O(g(n))O(g(n)) for any constant c>0c > 0.
    • This is because multiplying a function by a constant simply scales the function but does not change its growth rate.
  3. Multiplication by non-constant:

    • If f(n)f(n) is O(g(n))O(g(n)) and h(n)h(n) is O(k(n))O(k(n)), then f(n)h(n)f(n) \cdot h(n) is O(g(n)k(n))O(g(n) \cdot k(n)).
    • TODO: This is because the product of the dominant terms will determine the overall growth rate.
  4. Transitivity:

    • If f(n)f(n) is O(g(n))O(g(n)) and g(n)g(n) is O(h(n))O(h(n)), then f(n)f(n) is O(h(n))O(h(n)).
    • This property allows for chaining comparisons of functions.

Reasoning about an algorithm's efficiency

1. Selection sort

1// Selection sort repeatedly identifies the smallest remaining unsorted element
2// and puts it at the end of the sorted portion of the array.
3void selectionSort(int arr[], int n) {
4 int i, j, minimum_element_index;
5
6 // One by one move the boundary of the unsorted subarray
7 for (i = 0; i < n; i++) {
8
9 // Find the minimum element in the unsorted array
10 minimum_element_index = i; // Assume the current element is the minimum
11
12 for (j = i + 1; j < n; j++) {
13 // If we find a smaller element, update the minimum_element_index
14 if (arr[j] < arr[minimum_element_index]) {
15 minimum_element_index = j;
16 }
17 }
18
19 // Swap the found minimum element with the first element
20 swap(&arr[minimum_element_index], &arr[i]);
21 }
22}

Analysis of the selection sort algorithm:

  1. The outer loop goes around nn times.
  2. The nested inner loop goes around n(i+1)n - (i + 1) times, where ii is the index of the outer loop.
  3. The exact number of times the if statement is executed is:T(n)=i=0n1j=i+1n11T(n) = \sum_{i=0}^{n-1} \sum_{j=i+1}^{n-1} 1
    • To calculate the inner summation, we multiply the number of terms by 11.
    • The number of terms in a summation can be calculated by subtracting the lower limit from the upper limit of the summation and then adding 1.
    • This gives (n1)(i+1)+1(n - 1) - (i + 1) + 1 which equals ni1n - i - 1. Obviously, multiplying that by 11 gives the same result.
    • Hence, the original equation simplifies to:
    i=0n1ni1\sum_{i=0}^{n-1} n - i - 1
  4. What the sum is doing is adding up the non-negative integers in decreasing order starting from n1n - 1:T(n)=(n1)+(n2)+(n3)+...+2+1+0T(n) = (n - 1) + (n - 2) + (n - 3) + ... + 2 + 1 + 0
  5. The formula for the sum of the first nn non-negative integers (derived from the sum of an arithmetic series) is given by:i=0n1i=n(n1)2\sum_{i=0}^{n-1} i = \frac{n(n - 1)}{2}
  6. Hence, we can simply the summation to:i=0n1ni1=n(n1)2=n2n2\sum_{i=0}^{n-1} n - i - 1 = \frac{n(n - 1)}{2}\\ = \frac{n^2 - n}{2}
  7. Therefore the time complexity of selection sort is:
    • O(n2)O(n^2), O(n3)O(n^3), O(n4)O(n^4), etc.
    • Ω(n2)\Omega(n^2)
    • Θ(n2)\Theta(n^2)

Logarithms and their applications

A logarithm is an inverse exponential function:

bx=yx=logbyb(logby)=yb^x = y \\ x = \log_b y \\ b^(\log_b y) = y

Exponential functions grow at a fast rate while logarithmic functions grow at a slow rate. Logarithms arise in any process where things are repeatedly halved. e.g.

  1. Logarithms and binary search:

    • Binary search is an example of an O(logn)O(\log n) algorithm.
    • The size of the list is halved with each iteration of the algorithm.
    • Thus, only 2020 comparisons suffice to find an element in an array with 1 million elements.How binary search works
  2. Logarithms and trees:

    • A binary tree of height 11 can have up to 22 leaf nodes, while one of height 22 can have up to 44 leaves. The number of leaves doubles each time we increase the height by 11.
    • To generalize to trees that have dd children, a tree of height 11 can have up to dd leaf nodes, while one of height 22 can have up to d2d^2 leaves. The number of leaves multiplies by dd each time we increase the height by 11.
    • To account for nn leaves, n=dhn = d^h, which implies that h=logdnh = \log_d nComplete binary tree
  3. Logarithms and bits:

    • There are 22 bit patterns of length 11 (i.e. 00 and 11), 44 of length 22 (i.e. 0000, 1111, 1010, 0101), and 88 of length 33.
    • The number of bit patterns doubles with each increase in the number of bits.
    • Let ww represent number of bits and nn represent number of bit patterns. Then 2w=n2^w = n or w=log2nw = \log_2 n.

Product property of logarithms

logb(ac)=logb(a)+logb(c)\log_b (a \cdot c) = \log_b (a) + \log_b (c)

A direct consequence of the product property is the power property:

logb(ac)=clogb(a)\log_b (a^c) = c \cdot \log_b (a)

Since cc is a constant, this implies raising the logarithm’s argument to a power doesn't affect the growth rate:

logb(ac)=Θ(logb(a))\log_b (a^c) = \Theta (\log_b (a))

Change of base property of logarithms

Changing the base of logb(a)\log_b (a) to base-c simply involves multiplying by logc(b)\log_c (b):

logb(a)=logc(a)logc(b)logc(a)=logb(a)logc(b)\log_b (a) = \frac{\log_c (a)}{\log_c (b)} \\ \log_c (a) = \log_b (a) \cdot \log_c (b)

Since cc and bb are constants, this property implies that the base of a logarithm has no impact on the growth rate:

log2(1,000,000)=19.9316log3(1,000,000)=12.5754log100(1,000,000)=3\log_2 (1,000,000) = 19.9316\\ \log_3 (1,000,000) = 12.5754\\ \log_100 (1,000,000) = 3

Aside: In practice, an asymptotically inefficient algorithm may be more efficient for small input sizes. This is particularly used in hybrid algorithms, like Timsort, which use an asymptotically efficient algorithm (here merge sort, with time complexity nlognn \log n), but switch to an asymptotically inefficient algorithm (here insertion sort, with time complexity n2n^2) for small data, as the simpler algorithm is faster on small data.

Chapter 3: Data structures

  1. A data type (or simply type) is a collection of data values, usually specified by:
    • A set of possible values,
    • A set of allowed operations on these values, and/or
    • A representation of these values as machine types.
  2. An abstract data type (ADT) is a data type that does not specify the concrete representation of the data. They are defined by their behavior (semantics) from the point of view of a user of the data, specifically in terms of:
    • Possible values, and
    • Possible operations on data of this type.
  3. The generic definition of data structure is anything that can hold your data in a structured way. ADT contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer.
  4. The distinction between ADTs and data structures lies in the POV / level of abstraction. Some important points:
    • User’s POV: An int in a programming language sense is a fixed-width data structure. An integer in a mathematical sense is an ADT. For most purposes the user can work with the abstraction rather than the concrete choice of representation, and can simply use the data as if the type were truly abstract.
    • Name overloading: An array is an ADT when viewed as a collection of items that can be accessed by an index. An array is a data structure when viewed as a collection of fixed sized items stored as contiguous blocks in memory.
    • ADT implementations: There are multiple implementations of an ADT. E.g: A list can be implemented as an array or a linked-list.
  5. Data structures can be classified into:
    • Contiguous data structures: composed of single slabs of memory. E.g. arrays, matrices, heaps, hash tables, etc.
    • Linked data structures: composed of distinct chunks of memory bound together by pointers. E.g. linked-list, trees, graph adjacency lists, etc.

Arrays

  1. Arrays are data structures of fixed-size elements stored contiguously such that each element can be efficiently located by its index.ElementAddress(i)=FirstElementAddress+(iElementSize)ElementAddress(i) = FirstElementAddress + (i \cdot ElementSize)
  2. Advantages of arrays:
    • Constant-time access given the index: because the index of each element maps directly to a particular memory address.
    • Space efficiency: because no space is wasted with links, end-of-element information, or other per element metadata.
    • Memory locality: because the physical continuity between successive data access helps exploit the high-speed cache memory on modern computer architecture.
  3. The primary disadvantage of arrays is that the number of elements (i.e. the array size) is fixed. The capacity needs to be specified at allocation.
  4. Dynamic arrays overcome the fixed-size limitation of static arrays.
  5. It does so by internally resizing when its capacity is exceeded:
    • Allocates a new bigger contiguous array.
    • Copy the content of the old array to the new array. Dynamic array
  6. To avoid incurring the cost of resizing many times, dynamic arrays resize by a large amount, such as doubling in size.
  7. Expanding the array by any constant proportion aa ensures that inserting nn elements takes O(n)O(n) time overall, meaning that each insertion takes amortized O(1)O(1) time. As nn elements are added, the capacities form a geometric progression.
  8. The key idea of amortized analysis is to consider the worst-case cost of a sequence of operations on a data structure, rather than the worst-case individual cost of any particular operation.
  9. The aggregate method is one of the methods for performing amortized analysis. In this method, the total cost of performing a sequence of mm operations on the data structure is divided by the number of operations mm, yielding an average cost per operation, which is defined as the amortized cost.
  10. The aggregate method of amortized analysis applied to dynamic arrays with doubling:
  • t(i)={2k+1if i=2k+1t(i) = \begin{cases} 2^{k}+1 &\text{if } i = 2^{k} + 1\\ \end{cases}
  • t(i)t(i) defines the time it takes to perform the ii-th addition.

  • The first case of t(i)t(i):

    • Defines the time taken when the array’s capacity is exceeded and has to doubled.
    • kk is a non-negative integer.
    • Because the array's capacity is doubled, this case happens when: i=20+1i = 2^{0} + 1, i=21+1i = 2^{1} + 1, ..., i=2n+1i = 2^{n} + 1.
    • The time taken is 2k+12^{k}+1 because:
      • 2k2^{k} elements has to be copied to the new array and
      • The ii-th element has to be added into the new array. This represents the +1+1.
  • The second case of t(i)t(i):

    • Defines the time taken when the array capacity is not exceeded.
    • This is constant time because only a single addition is performed.
  • e.g. Given a dynamic array initialized with a capacity of 11:

    i12345678910
    t(i)t(i)11223311551111119911
    Capacity112244448888888816161616
  • Amortized cost=i=1nt(i)nAmortized \space cost = \frac{\sum_{i=1}^{n}t(i)}{n}
  • e.g. Given n=4n = 4:

    Amortized cost=i=14t(i)n=1+(20+1)+(21+1)+1Amortized \space cost = \frac{\sum_{i=1}^{4}t(i)}{n}\\ = 1 + (2^0 + 1) + (2^1 + 1) + 1
  • We see that in both cases of the function, there is a +1+1. So summation from 11 to nn results in:

    i=1nt(i)=n+k=0log2(n1)2k\sum_{i=1}^{n}t(i) = n + \sum_{k=0}^{\log_2 (n - 1)}2^{k}
  • The second operand represents the total cost of the copy operation that occurs on each resizing. For nn addition, this happens log2(n1)+1\log_2 (n - 1) + 1 times. e.g.

    n12345678910
    log2(n1)\log_2 (n - 1)001111222222223333
    k=0log2(n1)2k\sum_{k=0}^{\log_2 (n - 1)}2^{k}1133337777777715151515
  • The second operand is the partial sum of a geometric series, which has the formula:

    k=0nxk=xn+11x1\sum_{k=0}^{n}x^{k} = \frac{x^{n+1} - 1}{x - 1}
  • Applying the formula to the second operand:

    k=0log2(n1)2k=2log2(n1)+1121=2log2(n1)+111=2log2(n1)+11=2log2(n1)211\sum_{k=0}^{\log_2 (n - 1)}2^{k} = \frac{2^{\log_2 (n - 1) + 1} - 1}{2 - 1}\\ = \frac{2^{\log_2 (n - 1) + 1} - 1}{1}\\ = 2^{\log_2 (n - 1) + 1} - 1\\ = 2^{\log_2 (n - 1)} \cdot 2^{1} - 1
  • log2(n1)\log_2 (n - 1) is the number to which 22 must be raised to obtain n1n - 1. Raising that number then to 22 results in n1n - 1. Hence, the last expression can be simplified to:

    =(n1)211=2(n1)1=2n3= (n - 1) \cdot 2^{1} - 1\\ = 2(n - 1) - 1\\ = 2n - 3
  • The summation can be re-expressed again as:

    i=1nt(i)=n+2n3\sum_{i=1}^{n}t(i) = n + 2n - 3
  • The 3-3 is inconsequencial in the time analysis, hence the summation can be simplified into:

    i=1nt(i)3n\sum_{i=1}^{n}t(i) \leq 3n
  • Interpretation: A sequence of nn add operations costs at most 3n3n, hence each add in the sequence costs at most 33 (constant time) on average, which is the amortized cost according to the aggregate method.

    Conclusion: This proves that the amortized cost of insertion to a dynamic array with doubling is O(1)O(1).

  1. The key idea behind amortized analysis is that the cost of a particular operation can be partially paid for by the cost of other operations that are performed later. It avoids the limitations of worst-case analysis, which can overestimate the performance of a data structure if the worst-case scenario is unlikely to occur frequently.

Pointers and linked structures

Singly linked list

  1. Pointers represent the address of a location in memory. Pointers are the connections that hold the nodes (i.e. elements) of linked data structures together.

  2. In C:

    • *p denotes the item that is pointed to by pointer p
    • &p denotes the address of (i.e. pointer to) a particular variable p.
    • A special NULL pointer value is used to denote unassigned pointers.
  3. All linked data structures share these properties:

    • Each node contains one or more data field.
    • Each node contains a pointer field to at least one other node.
    • Finally, we need a pointer to the head of the data structure, so we know where to access it.

    Example linked-list displaying these properties:

    1typedef struct list {
    2 data_type data; /* Data field */
    3 struct list *next; /* Pointer field */
    4} list;
  4. The linked-list is the simplest linked structure.

  5. Singly linked-list has a pointer to only the successor whereas a doubly linked-list has a pointer to both the predecessor and successor.

  6. Searching for data x in a linked-list recursively:

    1list *search_list(list *my_list, data_type x) {
    2 if (my_list == NULL) {
    3 return(NULL);
    4 }
    5
    6 // If `x` is in the list, it's either the first element or located in the rest of the list.
    7 if (my_list->data == x) {
    8 return(my_list);
    9 } else {
    10 return(search_list(my_list.next, x));
    11 }
    12}
  7. Inserting into a singly linked-list at the head:

    1list *insert_list(list **my_list, data_type x) {
    2 list *p; /* temporary pointer */
    3 p = malloc(sizeof(list));
    4 p->data = x;
    5 p->next = *my_list;
    6 // `**my_list` denotes that `my_list` is a pointer to a pointer to a list node.
    7 // This line copies `p` to the place pointed to by `my_list`,
    8 // which is the external variable maintaining access to the head of the list.
    9 *my_list = p;
    10}
  8. Deletion from a list:

    1// Used to find the predecessor of the item to be deleted.
    2list *item_ahead(list *my_list, list *x) {
    3 if ((my_list == NULL) || (my_list->next == NULL) {
    4 return(NULL);
    5 }
    6
    7 if ((my_list->next) == x) {
    8 return(my_list);
    9 } else {
    10 return(item_ahead(my_list->next, x));
    11 }
    12}
    13
    14// This is called only if `x` exists in the list.
    15void *delete_list(list **my_list, list **x) {
    16 list *p; /* element pointer */
    17 list *pred; /* predecessor pointer */
    18
    19 p = *my_list;
    20 pred = item_ahead(*my_list, *x);
    21
    22 // Given that we assume `x` exists in the list,
    23 // `pred` is only null when the first element is the target.
    24 if (pred == NULL) { /* splice out of list */
    25 // Special case: resets the pointer to the head of the list
    26 // when the first element is deleted.
    27 *my_list = p->next;
    28 } else {
    29 pred->next = (*x)->next
    30 }
    31
    32 free(*x) /* free memory used by node */
    33}
  9. The advantages of linked structures over static arrays include:

    • Overflow on linked structures never occurs unless the memory is actually full.
    • Insertion and deletion are simpler than for static arrays. With static arrays, insertions and deletions into the middle requires manually shifting elements.
    • With large records, moving pointers is easier and faster than moving the items themselves.
  10. Both arrays and lists can be thought of as recursive objects:

    • Lists — Chopping the first element off a linked-list leaves a smaller linked-list.
    • Arrays — Splitting the first kk elements off of an nn element array gives two smaller arrays, of size kk and nkn - k, respectively.
    • This insight leads to simpler list processing, and efficient divide-and-conquer algorithms like quick-sort and binary search.
  11. An array is only recursive conceptually: Every array "contains" a sub-array. However, an array isn't recursive in code: A structure is recursive if while navigating through it, you come across "smaller" versions of the whole structure. While navigating through an array, you only come across the elements that the array holds, not smaller arrays.

Stacks

  1. Stacks are an ADT that supports retrieval by last-in, first-out (LIFO).
  2. Primary operations are:
    • push(x) — Inserts item x at the top of the stack.
    • pop() — Return and remove the top item of the stack.

Queues

Queue

  1. Queues are an ADT that supports retrieval by first-in, first-out (FIFO).
  2. Primary operations are:
    • enqueue(x) — Inserts item x at the back of the queue.
    • dequeue() — Return and remove the front item from the queue.
  3. Stacks and queues can be effectively implemented using arrays or linked-list.

Dictionaries

  1. A dictionary is an ADT that stores a collection of (key, value) pairs, such that each possible key appears at most once in the collection.
  2. The primary operations of a dictionary are:
    • put(key, value)
    • remove(key)
    • get(key)
  3. These are two simple but less common implementations of a dictionary:
    • An association list is a linked list in which each node comprises a key and a value:
      • The time complexity of get and remove is O(n)O(n).
      • The time complexity of put is O(1)O(1) — if the list is unsorted.
    • Direct addressing into an array:
      • UU is the universe of numbers.
      • KK is a set of potential keys and KUK \subseteq U.
      • KiK_i can be kept under index KiK_i in a K\lvert K \rvert-element array.
      • The time complexity of put, get and remove is O(1)O(1).
      • The space complexity is K\lvert K \rvert. Hence, this structure is impractical when K>>n\lvert K \rvert >> n; where nn is the number of values actually inserted.
  4. These are the two common data structures used to implement a dictionary:
    • Hash tables.
    • Self-balancing binary search tree.
  5. Binary search tree based maps are in-order and hence can satisfy range queries (i.e. find all values between two bounds) whereas a hash-map can only efficiently find exact values.

Binary search tree (BST)

  1. A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.
  2. A binary tree can be viewed as a linked-list with two pointers per node.
  3. A rooted tree is a tree in which one node has been designated the root.
  4. A rooted binary tree is recursively defined as either being:
    • Empty or
    • Consisting of a node called the root, together with two rooted binary trees called the left and right subtrees.
  5. A binary search tree is a rooted binary tree data structure such that for any node xx, all nodes in the left subtree of xx have keys<xkeys < x while all nodes in the right subtree of xx have keys>xkeys > x.
  6. Binary search trees’ height range from log2n\log_2 n (when balanced) to nn (when degenerate).
  7. The time complexity of operations on the binary search tree is linear with respect to the height of the tree O(h)O(h).
  8. Hence, in a balanced binary search tree, the nodes are laid out so that each comparison skips about half of the remaining tree, the lookup performance is proportional to that of the binary logarithm O(logn)O(\log n).
  9. An implementation of a binary tree:
    1typedef struct tree {
    2 data_type data; /* Data field */
    3 struct tree *parent; /* Pointer to parent */
    4 struct tree *left; /* Pointer to left chid */
    5 struct tree *right; /* Pointer to right child */
    6} tree;
  10. Searching in a binary search tree:

Priority queue

  1. A priority queue is an ADT similar to a regular queue or stack ADT. Each element in a priority queue has an associated priority.
  2. Depending on the implementation, a priority queue can serve minimum priority elements first or maximum priority elements first. You can convert one implementation into the other by negating the priority on each element addition.
  3. Priority queues are often implemented using heaps.
  4. A priority queue can also be inefficiently implemented as an unsorted list or a sorted list.
  5. A priority queue can be used for sorting: insert all the elements to be sorted into a priority queue, and sequentially remove them.
  6. The primary operations of a priority queue are:
    • add() — an element with a given priority,
    • delete(x) — an element,
    • pull() — Get the the highest priority element and remove it, and
    • peek() — Get the the highest priority element without removing it.
  7. Stacks and queues can be implemented as particular kinds of priority queues, with the priority determined by the order in which the elements are inserted.

Hash tables

Hash table

  1. Hash tables are a data structure that efficiently implements a dictionary. They exploit the fact that looking an element up in an array takes constant time once you have its index.

  2. The basic idea is to pick a hash function hh that maps every possible key xx to a small integer h(x)h(x). Then we store xx and its value in an array at index h(x)h(x); the array itself is essentially the hash table.

  3. A hash function hh maps the universe UU of keys to array indices within the hash table.

    h:U{0,,n1}h : U → \{ 0, …, n - 1 \}
  4. Properties of a good hash function:

    • Efficient — Computing h(x)h(x) should require a constant number of steps per bit of xx.
    • Uniformhh should ideally map elements randomly and uniformly over the entire range of integers.
  5. A hash function for an arbitrary key xx (like a string) is typically defined as:

    h(x)=toInteger(x)modnh(x) = toInteger(x) \bmod n
  6. This is the polynomial function that Java uses to convert strings to integers:

    s[0]31n1+s[1]31n2+...+s[n1]s[0]*31^{n-1} + s[1]*31^{n-2} + ... + s[n-1]

    Which translates into the following code:

    1int hashcode = 0;
    2for (int i = 0; i < s.length(); i++) {
    3 hashcode = (hashcode * 31) + s.charAt(i);
    4}
  7. A collision occurs when:

    h(j)=h(k)jkh(j) = h(k) \land j \neq k
  8. Collisions can be minimized but cannot be eliminated (see Pigeon hole principle). It’s impossible to eliminate collisions without knowing the UU ahead of time.

  9. The two common methods for collision resolution are separate chaining and open addressing.

  10. In separate chaining, the values of the hash-table’s array is a linked-list.

    • Inserting adds the key and its value to the head of the linked-list at h(x)h(x) index in O(1)O(1) time. Keys that collided hence form a chain.

    • Searching involves going to h(x)h(x) index and iterating through the linked-list until a key equality check passes. Hash table separate chaining

  11. In open addressing, every key and its value is stored in the hash-table’s array itself, and the resolution is performed through probing.

    • Inserting goes to h(x)h(x) index. If it is occupied, it proceeds on some probe sequence until an unoccupied index is found.
    • Searching is done in the same sequence, until either the key is found, or an unoccupied array index is found, which indicates an unsuccessful search.
    • Linear probing is often used — it simply checks the next indices linearly: h(x)+1h(x) + 1, h(x)+2h(x) + 2. But there is quadratic probing and other probing sequences. Hash table open addressing
  12. Search algorithms that use hashing consist of two separate parts: hashing and collision resolution.

  13. Other uses of hashing (or a hash table):

1* Plagiarism detection using Rabin-Karp string matching algorithm
2* English dictionary search
3* Finding distinct elements
4* Counting frequencies of items
  1. Time complexity in big O notation

    OperationAverageWorst case
    SearchΘ(1)Θ(1)O(n)O(n)
    InsertΘ(1)Θ(1)O(n)O(n)
    DeleteΘ(1)Θ(1)O(n)O(n)
  2. Space complexity is O(n)O(n).

Excercises

  1. A common problem for compilers and text editors is determining whether the parentheses in a string are balanced and properly nested. For example, the string ((())())() contains properly nested pairs of parentheses, while the strings )()( and ()) do not. Give an algorithm that returns true if a string contains properly nested and balanced parentheses, and false if otherwise. For full credit, identify the position of the first offending parenthesis if the string is not properly nested and balanced.

    Solution
    1fun test() {
    2 System.out.println(areParentheseProperlyBalanced("((())())()"))
    3 System.out.println(areParentheseProperlyBalanced(")()("))
    4 System.out.println(areParentheseProperlyBalanced("())"))
    5 System.out.println(areParentheseProperlyBalanced(")))"))
    6 System.out.println(areParentheseProperlyBalanced("(("))
    7 }
    8
    9/**
    10 * @return -1 if [string] is valid, else a positive integer
    11 * that provides the position of the offending index.
    12 */
    13fun areParentheseProperlyBalanced(string: String): Int {
    14 val stack = Stack<Pair<Char, Int>>()
    15
    16 string.forEachIndexed { index, char ->
    17 if (char == '(') {
    18 stack.push(char to index)
    19 } else if (char == ')') {
    20 if (stack.empty()) {
    21 return index
    22 }
    23 stack.pop()
    24 } else {
    25 throw IllegalArgumentException("Only parenthesis are supported")
    26 }
    27 }
    28
    29 return if (stack.empty()) -1 else stack.peek().second
    30 }
  2. Give an algorithm that takes a string SS consisting of opening and closing parentheses, say )()(())()()))())))(, and finds the length of the longest balanced parentheses in SS, which is 12 in the example above. (Hint: The solution is not necessarily a contiguous run of parenthesis from SS)

    Solution
    1fun test() {
    2 System.out.println(lengthOfLongestBalancedParentheses("((())())()"))
    3 System.out.println(lengthOfLongestBalancedParentheses(")()(())()()))())))("))
    4 System.out.println(lengthOfLongestBalancedParentheses(")()("))
    5 System.out.println(lengthOfLongestBalancedParentheses("())"))
    6 System.out.println(lengthOfLongestBalancedParentheses(")))"))
    7 System.out.println(lengthOfLongestBalancedParentheses("(("))
    8}
    9
    10fun lengthOfLongestBalancedParentheses(string: String): Int {
    11 val stack = Stack<Char>()
    12 var numBalancedParenthesis = 0
    13
    14 string.forEachIndexed { index, char ->
    15 if (char == '(') {
    16 stack.push(char)
    17 } else if (char == ')') {
    18 if (!stack.empty()) {
    19 stack.pop()
    20 numBalancedParenthesis++
    21 }
    22 }
    23 }
    24
    25 // Multiplied by 2 because each balanced pair has a length of 2.
    26 return numBalancedParenthesis * 2
    27}
  3. Give an algorithm to reverse the direction of a given singly linked list. In other words, after the reversal all pointers should now point backwards. Your algorithm should take linear time.

    Solution
    1fun test() {
    2 val node1 = Node("Elvis", null)
    3
    4 val node2 = Node("Chidera", null)
    5 node1.next = node2
    6
    7 val node3 = Node("Nnajiofor", null)
    8 node2.next = node3
    9
    10 System.out.println(node1)
    11 System.out.println(reverse(node1))
    12}
    13
    14data class Node(
    15 val element: String,
    16 var next: Node?
    17)
    18
    19/**
    20 * Work through an example:
    21 * reverse(Node1 -> Node2 -> Node3)
    22 *
    23 * Node1 level:
    24 * val last = reverse(Node2 -> Node3) 🛑
    25 *
    26 * Node2 level:
    27 * val last = reverse(Node3) 🛑
    28 *
    29 * Node3 level:
    30 * return Node3
    31 *
    32 * Back to Node2 level:
    33 * val last = Node3 🟢
    34 * Node3.next = Node2
    35 * Node2.next = null
    36 * return last
    37 *
    38 * Back to Node1 level:
    39 * val last = Node3 🟢
    40 * Node2.next = Node1
    41 * Node1.next = null
    42 * return last
    43*/
    44fun reverse(node: Node): Node {
    45 // Base case
    46 if (node.next == null) return node
    47
    48 val last = reverse(node.next!!)
    49 node.next!!.next = node
    50 node.next = null
    51 return last
    52}
  4. Design a stack SS that supports S.push(x), S.pop(), and S.findmin(), which returns the minimum element of SS. All operations should run in constant time.

    Solution
    1fun test() {
    2 val stack = Stack()
    3 stack.push(50)
    4 stack.push(40)
    5 stack.push(30)
    6 stack.push(20)
    7 stack.push(10)
    8
    9 System.out.println(stack.findMin())
    10 stack.pop()
    11 System.out.println(stack.findMin())
    12 stack.pop()
    13 System.out.println(stack.findMin())
    14 stack.pop()
    15 System.out.println(stack.findMin())
    16 stack.pop()
    17 System.out.println(stack.findMin())
    18 stack.pop()
    19}
    20
    21data class Element(
    22 val num: Int,
    23 internal val minNumSoFar: Int
    24)
    25
    26class Stack {
    27
    28 private val list = mutableListOf<Element>()
    29
    30 fun push(num: Int) {
    31 list += Element(
    32 num = num,
    33 minNumSoFar = Math.min(num, list.lastOrNull()?.minNumSoFar ?: num)
    34 )
    35 }
    36
    37 fun pop(): Int {
    38 return list.removeLast().num
    39 }
    40
    41 fun findMin(): Int {
    42 return list.last().minNumSoFar
    43 }
    44}
  5. We have seen how dynamic arrays enable arrays to grow while still achieving constant-time amortized performance. This problem concerns extending dynamic arrays to let them both grow and shrink on demand.

    a. Consider an underflow strategy that cuts the array size in half whenever the array falls below half full. Give an example sequence of insertions and deletions where this strategy gives a bad amortized cost.

    b. Then, give a better underflow strategy than that suggested above, one that achieves constant amortized cost per deletion.

    Solution

    a. A sequence of insert, insert, delete, insert, delete, insert will lead to a bad amortized cost because the array will be busy resizing for most of the operations.

    b. A better underflow strategy is to cut the array size in half whenever the array falls below 1/41/4. 1/41/4 is arbitrary, but it gives the array good "slack" space. The goal is to select a number such that the array is not busy resizing for most of the operation. The smaller the cut-off ratio, the smaller the number of resizing but the more space the array uses.

  6. Suppose you seek to maintain the contents of a refrigerator so as to minimize food spoilage. What data structure should you use, and how should you use it?

    Solution

    Use a priority queue. The expiry date is the priority of each element. Elements with the lowest expiry date are served first (minElement).

  7. Work out the details of supporting constant-time deletion from a singly linked list as per the footnote from page 79, ideally to an actual implementation. Support the other operations as efficiently as possible.

    Solution
    1fun test() {
    2 val node3 = Node(3)
    3 val node2 = Node(2, node3)
    4 val node1 = Node(1, node2)
    5
    6 println(node1)
    7 println(deleteInConstantTime(node1, node2))
    8 println(deleteInConstantTime(node1, node3))
    9 println(deleteInConstantTime(node1, node1))
    10}
    11
    12fun deleteInConstantTime(head: Node, search: Node): Node? {
    13 if (head == search) {
    14 // Handle head case
    15 return head.next
    16 }
    17
    18 var node: Node? = head
    19 var prevNode: Node? = null
    20 while (node != null) {
    21 if (node == search) {
    22 if (node.next == null) {
    23 // Handle tail case
    24 prevNode?.next = null
    25 } else {
    26 node.element = node.next!!.element
    27 node.next = node.next?.next
    28 }
    29
    30 break
    31 } else {
    32 prevNode = node
    33 node = node.next
    34 }
    35 }
    36
    37 return head
    38}
    39
    40data class Node(
    41 var element: Int,
    42 var next: Node? = null
    43)
  8. Tic-tac-toe is a game played on an nnn * n board (typically n=3n = 3) where two players take consecutive turns placing “O” and “X” marks onto the board cells. The game is won if nn consecutive “O” or “X” marks are placed in a row, column, or diagonal. Create a data structure with O(n)O(n) space that accepts a sequence of moves, and reports in constant time whether the last move won the game.

    Solution
    1fun test() {
    2 var tickTacToe = TickTacToe(3)
    3 assertFalse(tickTacToe.playX(1, 1))
    4 assertFalse(tickTacToe.playO(1, 2))
    5 assertFalse(tickTacToe.playX(1, 3))
    6
    7 tickTacToe = TickTacToe(3)
    8 assertFalse(tickTacToe.playO(2, 1))
    9 assertFalse(tickTacToe.playX(2, 2))
    10 assertFalse(tickTacToe.playO(2, 3))
    11
    12 tickTacToe = TickTacToe(3)
    13 assertFalse(tickTacToe.playX(3, 1))
    14 assertFalse(tickTacToe.playX(3, 2))
    15 assertTrue(tickTacToe.playX(3, 3))
    16
    17 tickTacToe = TickTacToe(3)
    18 assertFalse(tickTacToe.playX(1, 1))
    19 assertFalse(tickTacToe.playO(2, 1))
    20 assertFalse(tickTacToe.playX(3, 1))
    21
    22 tickTacToe = TickTacToe(3)
    23 assertFalse(tickTacToe.playO(1, 2))
    24 assertFalse(tickTacToe.playX(2, 2))
    25 assertFalse(tickTacToe.playO(3, 2))
    26
    27 tickTacToe = TickTacToe(3)
    28 assertFalse(tickTacToe.playX(1, 3))
    29 assertFalse(tickTacToe.playX(2, 3))
    30 assertTrue(tickTacToe.playX(3, 3))
    31
    32 tickTacToe = TickTacToe(3)
    33 assertFalse(tickTacToe.playO(1, 1))
    34 assertFalse(tickTacToe.playO(2, 2))
    35 assertTrue(tickTacToe.playO(3, 3))
    36
    37 tickTacToe = TickTacToe(3)
    38 assertFalse(tickTacToe.playO(1, 3))
    39 assertFalse(tickTacToe.playO(2, 2))
    40 assertTrue(tickTacToe.playO(3, 1))
    41}
    42
    43private fun assertTrue(value: Boolean) {
    44 require(value)
    45 println("Won!!!")
    46}
    47
    48private fun assertFalse(value: Boolean) {
    49 require(!value)
    50 println("Not won yet")
    51}
    52
    53class TickTacToe(private val n: Int) {
    54
    55 private val columns = Array(n) {
    56 Slot(n)
    57 }
    58
    59 private val rows = Array(n) {
    60 Slot(n)
    61 }
    62
    63 private val diagonal = Slot(n)
    64
    65 private val antiDiagonal = Slot(n)
    66
    67 fun playX(rowPosition: Int, columnPosition: Int): Boolean {
    68 return play('X', rowPosition, columnPosition)
    69 }
    70
    71 fun playO(rowPosition: Int, columnPosition: Int): Boolean {
    72 return play('O', rowPosition, columnPosition)
    73 }
    74
    75 private fun play(char: Char, rowPosition: Int, columnPosition: Int): Boolean {
    76 return rows[rowPosition.toIndex].play(char) ||
    77 columns[columnPosition.toIndex].play(char) ||
    78 (rowPosition == columnPosition && diagonal.play(char)) ||
    79 ((rowPosition + columnPosition) == (n + 1) && antiDiagonal.play(char))
    80 }
    81
    82 private val Int.toIndex get() = this - 1
    83
    84 class Slot(private val n: Int) {
    85
    86 private var number = 0
    87
    88 fun play(char: Char): Boolean {
    89 val increment = if (char == 'X') 1 else -1
    90 val target = if (char == 'X') n else -n
    91
    92 number += increment
    93 return number == target
    94 }
    95 }
    96}
  9. Write a function which, given a sequence of digits 2–9 and a dictionary of nn words, reports all words described by this sequence when typed in on a standard telephone keypad. For the sequence 269 you should return any, box, boy, and cow, among other words.

    Solution
    1fun test() {
    2 println(words(arrayOf(2, 6, 9)))
    3 println(words(arrayOf(7, 6, 7, 7)))
    4}
    5
    6fun words(inputDigits: Array<Int>): List<String> {
    7 val words = setOf(
    8 "pops",
    9 "any",
    10 "box",
    11 "boy",
    12 "cow",
    13 "dad",
    14 "mom",
    15 )
    16 val charToDigitMapping = mapOf(
    17 'a' to 2,
    18 'b' to 2,
    19 'c' to 2,
    20 'd' to 3,
    21 'e' to 3,
    22 'f' to 3,
    23 'g' to 4,
    24 'h' to 4,
    25 'i' to 4,
    26 'j' to 5,
    27 'k' to 5,
    28 'l' to 5,
    29 'm' to 6,
    30 'n' to 6,
    31 'o' to 6,
    32 'p' to 7,
    33 'q' to 7,
    34 'r' to 7,
    35 's' to 7,
    36 't' to 8,
    37 'u' to 8,
    38 'v' to 8,
    39 'w' to 9,
    40 'x' to 9,
    41 'y' to 9,
    42 'z' to 9,
    43 )
    44
    45 val matchingWords = mutableListOf<String>()
    46 words.forEach { word ->
    47 word.forEachIndexed { index, char ->
    48 val charDigit = charToDigitMapping[char] ?: return@forEach
    49 val inputDigitAtIndex = inputDigits.getOrNull(index) ?: return@forEach
    50 if (charDigit != inputDigitAtIndex) {
    51 return@forEach
    52 }
    53 }
    54
    55 matchingWords += word
    56 }
    57
    58 return matchingWords
    59}
  10. Two strings XX and YY are anagrams if the letters of XX can be rearranged to form YY. For example, silent/listen, and incest/insect are anagrams. Give an efficient algorithm to determine whether strings XX and YY are anagrams.

    Solution
    1fun test() {
    2 println(isAnagram("silent", "listen"))
    3 println(isAnagram("silence", "listen"))
    4 println(isAnagram("incest", "insect"))
    5 println(isAnagram("incest", "insects"))
    6}
    7
    8fun isAnagram(s1: String, s2: String): Boolean {
    9 val map = mutableMapOf<Char, Int>()
    10
    11 s1.forEach { char ->
    12 map[char] = map.getOrPut(char) { 0 } + 1
    13 }
    14
    15 s2.forEach { char ->
    16 if (map.containsKey(char)) {
    17 map[char] = map.getValue(char) - 1
    18 } else {
    19 return false
    20 }
    21 }
    22
    23 map.values.forEach { number ->
    24 if (number != 0) {
    25 return false
    26 }
    27 }
    28
    29 return true
    30}
  11. Design a dictionary data structure in which search, insertion, and deletion can all be processed in O(1)O(1) time in the worst case. You may assume the set elements are integers drawn from a finite set 1,2,...,n1, 2, ..., n and initialization can take O(N)O(N) time.

    Solution
    1fun test() {
    2 val dictionary = Dictionary(10)
    3 dictionary.insert(4)
    4 println(dictionary.search(4))
    5 dictionary.delete(4)
    6 println(dictionary.search(4))
    7}
    8
    9class Dictionary(val capacity: Int) {
    10
    11 private val array = Array<Int?>(capacity) { null }
    12
    13 fun search(element: Int): Int? {
    14 return array[element.toIndex]
    15 }
    16
    17 fun delete(element: Int) {
    18 array[element.toIndex] = null
    19 }
    20
    21 fun insert(element: Int) {
    22 array[element.toIndex] = element
    23 }
    24
    25 private val Int.toIndex get() = this - 1
    26}
  12. The maximum depth of a binary tree is the number of nodes on the path from the root down to the most distant leaf node. Give an O(n)O(n) algorithm to find the maximum depth of a binary tree with nn nodes.

    Solution
    1fun test() {
    2 val root = BNode(
    3 element = 5,
    4 left = BNode(
    5 element = 3,
    6 left = BNode(
    7 element = 2,
    8 left = BNode(
    9 element = 1,
    10 left = null,
    11 right = null
    12 ),
    13 right = null
    14 ),
    15 right = null
    16 ),
    17 right = BNode(
    18 element = 7,
    19 left = null,
    20 right = BNode(
    21 element = 8,
    22 left = null,
    23 right = null
    24 )
    25 )
    26 )
    27
    28 println(maxDepth(root))
    29}
    30
    31fun maxDepth(root: BNode?): Int {
    32 if (root == null) {
    33 return 0
    34 }
    35
    36 val leftDepth = maxDepth(root.left)
    37 val rightDepth = maxDepth(root.right)
    38
    39 return max(leftDepth, rightDepth) + 1
    40}
  13. Two elements of a binary search tree have been swapped by mistake. Give an O(n)O(n) algorithm to identify these two elements so they can be swapped back.

    Solution
    1fun test() {
    2 val root = BNode(
    3 element = 5,
    4 left = BNode(
    5 element = 3,
    6 left = BNode(
    7 element = 8, // Swapped
    8 left = null,
    9 right = null
    10 ),
    11 right = null
    12 ),
    13 right = BNode(
    14 element = 7,
    15 left = null,
    16 right = BNode(
    17 element = 2, // Swapped
    18 left = null,
    19 right = null
    20 )
    21 )
    22 )
    23
    24 println(root)
    25 val recoverer = SwappedNodeRecoverer()
    26 recoverer.recover(root)
    27 println(root)
    28}
    29
    30class SwappedNodeRecoverer {
    31
    32 private var prev: BNode? = null
    33 private var first: BNode? = null
    34 private var second: BNode? = null
    35
    36 fun recover(root: BNode?) {
    37 recoverInternal(root)
    38
    39 if (first != null) {
    40 val firstElement = first!!.element
    41 first!!.element = second!!.element
    42 second!!.element = firstElement
    43 }
    44 }
    45
    46 private fun recoverInternal(root: BNode?) {
    47 if (root == null) {
    48 return
    49 }
    50
    51 recoverInternal(root.left)
    52
    53 if (prev != null && root.element < prev!!.element) {
    54 if (first == null) {
    55 // This handles adjacent node case
    56 first = prev
    57 second = root
    58 } else {
    59 second = root
    60 }
    61 }
    62
    63 prev = root
    64
    65 recoverInternal(root.right)
    66 }
    67}
    68
    69data class BNode(
    70 var element: Int,
    71 var left: BNode? = null,
    72 var right: BNode? = null,
    73)
  14. Given two binary search trees, merge them into a doubly linked list in sorted order.

    Solution
    1fun test() {
    2 val s1 = BNode(
    3 element = 5,
    4 left = BNode(
    5 element = 3,
    6 left = null,
    7 right = null
    8 ),
    9 right = BNode(
    10 element = 7,
    11 left = null,
    12 right = null
    13 )
    14 )
    15
    16 val s2 = BNode(
    17 element = 10,
    18 left = BNode(
    19 element = 8,
    20 left = null,
    21 right = null
    22 ),
    23 right = BNode(
    24 element = 12,
    25 left = null,
    26 right = null
    27 )
    28 )
    29
    30 println(merge(s1, s2))
    31}
    32
    33fun merge(tree1: BNode, tree2: BNode): Node {
    34 val tree1Nodes = toList(tree1)
    35 val tree2Nodes = toList(tree2)
    36
    37 var i1 = 0
    38 var i2 = 0
    39 val list = Node(Integer.MIN_VALUE) // Sentinel
    40 var lastListNode = list
    41 val addListNode = { node: Node ->
    42 lastListNode.next = node
    43 lastListNode = node
    44 }
    45
    46 while (i1 < tree1Nodes.size || i2 < tree2Nodes.size) {
    47 val tree1Node = tree1Nodes.getOrNull(i1)
    48 val tree2Node = tree2Nodes.getOrNull(i2)
    49
    50 if (tree1Node == null && tree2Node != null) {
    51 addListNode(Node(tree2Node.element))
    52 i2++
    53 } else if (tree2Node == null && tree1Node != null) {
    54 addListNode(Node(tree1Node.element))
    55 i1++
    56 } else if (tree1Node!!.element < tree2Node!!.element) {
    57 addListNode(Node(tree1Node.element))
    58 i1++
    59 } else if(tree1Node.element > tree2Node.element) {
    60 addListNode(Node(tree2Node.element))
    61 i2++
    62 } else {
    63 addListNode(Node(tree1Node.element))
    64 i1++
    65 addListNode(Node(tree2Node.element))
    66 i2++
    67 }
    68 }
    69
    70 return list.next!!
    71}
    72
    73fun toList(tree: BNode?): MutableList<BNode> {
    74 if (tree == null) {
    75 return mutableListOf()
    76 }
    77
    78 return (toList(tree.left) + tree + toList(tree.right)).toMutableList()
    79}
    80
    81data class BNode(
    82 val element: Int,
    83 var left: BNode?,
    84 var right: BNode?,
    85)
    86
    87data class Node(
    88 val element: Int,
    89 var next: Node? = null
    90)
  15. Describe an O(n)O(n)-time algorithm that takes an nn-node binary search tree and constructs an equivalent height-balanced binary search tree. In a height-balanced binary search tree, the difference between the height of the left and right subtrees of every node is never more than 1.

    Solution
    1fun test() {
    2 val root = BNode(
    3 element = 5,
    4 left = BNode(
    5 element = 3,
    6 left = BNode(
    7 element = 2,
    8 left = BNode(
    9 element = 1,
    10 left = null,
    11 right = null
    12 ),
    13 right = null
    14 ),
    15 right = null
    16 ),
    17 right = BNode(
    18 element = 7,
    19 left = null,
    20 right = BNode(
    21 element = 8,
    22 left = null,
    23 right = null
    24 )
    25 )
    26 )
    27
    28 println("Unbalanced tree: $root")
    29 println("Balanced tree: " + toBalancedTree(root))
    30}
    31
    32fun toBalancedTree(root: BNode): BNode {
    33 val nodes = toList(root)
    34 return sortedListToBinaryTree(nodes)!!
    35}
    36
    37fun sortedListToBinaryTree(list: List<BNode>): BNode? {
    38 if (list.isEmpty()) {
    39 return null
    40 }
    41
    42 val mid = list.size / 2
    43 val root = BNode(list[mid].element)
    44 root.left = sortedListToBinaryTree(list.slice(0 until mid))
    45 root.right = sortedListToBinaryTree(list.slice((mid + 1) until list.size))
    46
    47 return root
    48}
    49
    50fun toList(tree: BNode?): MutableList<BNode> {
    51 if (tree == null) {
    52 return mutableListOf()
    53 }
    54
    55 return (toList(tree.left) + tree + toList(tree.right)).toMutableList()
    56}
    57
    58data class BNode(
    59 val element: Int,
    60 var left: BNode? = null,
    61 var right: BNode? = null,
    62)
  16. Find the storage efficiency ratio (the ratio of data space over total space) for each of the following binary tree implementations on nn nodes:

    • All nodes store data, two child pointers, and a parent pointer. The data field requires 4 bytes and each pointer requires 4 bytes.
    • Only leaf nodes store data; internal nodes store two child pointers. The data field requires four bytes and each pointer requires two bytes.
    Solution

    Storage efficiency ratio = /fracSpace used to store dataSpace used to store data and pointers/frac{Space \space used \space to \space store \space data}{Space \space used \space to \space store \space data \space and \space pointers} For option A: Space taken by a single node = (2 pointers 4 bytes) + (1 pointer 4 bytes) + (4 bytes) = 16 bytes Given nn nodes Storage efficiency ratio = 4n16n=14\frac{4n}{16n} = \frac{1}{4}

    For option B: Space taken by a single internal node = 2 pointers * 2 bytes = 4 bytes Space taken by a single leaf node = 4 bytes In a full tree, given nn leaf nodes, there are n1n-1 internal nodes. Storage efficiency ratio = 4n4n+4(n1)=4n4n+4n4=4n8n4=4n8n=1/2\frac{4n}{4n + 4(n-1)} = \frac{4n}{4n + 4n - 4} = \frac{4n}{8n - 4} = \frac{4n}{8n} = \frac{1}/{2} (As nn gets larger, the constant 44 doesn't matter, hence why it was dropped)

    Option B has a higher storage efficiency to option A.

  17. Give an O(n)O(n) algorithm that determines whether a given nn-node binary tree is height-balanced (see Problem 3-15).

    Solution
    1fun test() {
    2 val root = BNode(
    3 element = 5,
    4 left = BNode(
    5 element = 3,
    6 left = BNode(
    7 element = 2,
    8 left = BNode(
    9 element = 1,
    10 left = null,
    11 right = null
    12 ),
    13 right = null
    14 ),
    15 right = null
    16 ),
    17 right = BNode(
    18 element = 7,
    19 left = null,
    20 right = BNode(
    21 element = 8,
    22 left = null,
    23 right = null
    24 )
    25 )
    26 )
    27
    28 println(isBalanced(root))
    29}
    30
    31fun isBalanced(root: BNode?): Pair<Boolean, Int> {
    32 if (root == null) {
    33 return true to 0
    34 }
    35
    36 val (isLeftBalanced, leftHeight) = isBalanced(root.left)
    37 if (!isLeftBalanced) {
    38 return false to 0
    39 }
    40
    41 val (isRightBalanced, rightHeight) = isBalanced(root.right)
    42 if (!isRightBalanced) {
    43 return false to 0
    44 }
    45
    46 if (abs(leftHeight - rightHeight) > 1) {
    47 return false to 0
    48 }
    49
    50 return true to (max(leftHeight, rightHeight) + 1)
    51}
    52
    53data class BNode(
    54 val element: Int,
    55 val left: BNode?,
    56 val right: BNode?,
    57)
  18. Describe how to modify any balanced tree data structure such that search, insert, delete, minimum, and maximum still take O(logn)O(log n) time each, but successor and predecessor now take O(1)O(1) time each. Which operations have to be modified to support this?

    Solution

    TODO

  19. Suppose you have access to a balanced dictionary data structure that supports each of the operations search, insert, delete, minimum, maximum, successor, and predecessor in O(logn)O(log n) time. Explain how to modify the insert and delete operations so they still take O(logn)O(log n) but now minimum and maximum take O(1)O(1) time. (Hint: think in terms of using the abstract dictionary operations, instead of mucking about with pointers and the like.)

    Solution

    Use two variables to maintain the maximum and minimum element. On:

    • Insert(x): If x<minimumx < minimum, set xx as new minimum; If x>maximumx > maximum, set xx as new maximum.
    • Delete(x): If x=minimumx = minimum, set minimum=sucessor(x)minimum = sucessor(x); If x=maximumx = maximum, set maximum=predecessor(x)maximum = predecessor(x).
  20. Design a data structure to support the following operations:

    • insert(x,T) – Insert item xx into the set TT.
    • delete(k,T) – Delete the kkth smallest element from TT.
    • member(x,T) – Return true iff xTx \in T.

    All operations must take O(logn)O(log n) time on an nn-element set.

    Solution

    g

  21. A concatenate operation takes two sets S1S_1 and S2S_2, where every key in S1S_1 is smaller than any key in S2S_2, and merges them. Give an algorithm to concatenate two binary search trees into one binary search tree. The worst-case running time should be O(h)O(h), where hh is the maximal height of the two trees.

    Solution
    1fun test() {
    2 val s1 = BNode(
    3 element = 5,
    4 left = BNode(
    5 element = 3,
    6 left = null,
    7 right = null
    8 ),
    9 right = BNode(
    10 element = 7,
    11 left = null,
    12 right = null
    13 )
    14 )
    15
    16 val s2 = BNode(
    17 element = 10,
    18 left = BNode(
    19 element = 8,
    20 left = null,
    21 right = null
    22 ),
    23 right = BNode(
    24 element = 12,
    25 left = null,
    26 right = null
    27 )
    28 )
    29
    30 println(concat(s1, s2))
    31}
    32
    33fun concat(s1: BNode, s2: BNode): BNode {
    34 val s1RightMostNode = rightMostNode(s1)
    35
    36 s1RightMostNode.right = s2
    37
    38 return s1
    39}
    40
    41fun rightMostNode(node: BNode): BNode {
    42 if (node.right == null) {
    43 return node
    44 }
    45
    46 return rightMostNode(node.right!!)
    47}
    48
    49data class BNode(
    50 val element: Int,
    51 var left: BNode?,
    52 var right: BNode?,
    53)
  22. Design a data structure that supports the following two operations:

    • insert(x) – Insert item xx from the data stream to the data structure.
    • median() – Return the median of all elements so far.

    All operations must take O(logn)O(\log n) time on an nn-element set.

    Solution
    1fun test() {
    2 val ds = DataStructure()
    3
    4 ds.insert(5)
    5 ds.insert(2)
    6 ds.insert(3)
    7
    8 println("Median: ${ds.median()}")
    9
    10 ds.insert(4)
    11 println("Median: ${ds.median()}")
    12}
    13
    14class DataStructure {
    15
    16 /* The head of this queue is the least element with respect to the specified ordering. */
    17 private val minHeap = PriorityQueue<Int>() // Represents the upper half
    18 private val maxHeap = PriorityQueue<Int>() // Represents the lower half
    19
    20 fun insert(x: Int) {
    21 if (maxHeap.isEmpty() || x <= -maxHeap.peek()) {
    22 maxHeap.offer(-x)
    23 } else {
    24 minHeap.offer(x)
    25 }
    26
    27 // Balance the heaps to ensure the size difference is at most 1
    28 if (maxHeap.size > minHeap.size + 1) {
    29 minHeap.offer(-maxHeap.poll())
    30 } else if (minHeap.size > maxHeap.size) {
    31 maxHeap.offer(-minHeap.poll())
    32 }
    33 }
    34
    35 fun median(): Double {
    36 return if (minHeap.size == maxHeap.size) {
    37 // If the number of elements is even, take the average of the middle two
    38 (minHeap.peek() + (-maxHeap.peek())) / 2.0
    39 } else {
    40 -maxHeap.peek().toDouble()
    41 }
    42 }
    43}
  23. Assume we are given a standard dictionary (balanced binary search tree) defined on a set of nn strings, each of length at most ll. We seek to print out all strings beginning with a particular prefix pp. Show how to do this in O(mllogn)O(m \cdot l \cdot \log n) time, where mm is the number of strings.

    Solution

    g

  24. An array AA is called kk-unique if it does not contain a pair of duplicate elements within kk positions of each other, that is, there is no ii and jj such that A[i]=A[j]A[i] = A[j] and jik|j - i| \leq k. Design a worst-case O(nlogk)O(n \cdot \log k) algorithm to test if AA is kk-unique.

    Solution

    g

  25. In the bin-packing problem, we are given nn objects, each weighing at most 1 kilogram. Our goal is to find the smallest number of bins that will hold the nn objects, with each bin holding 1 kilogram at most.

    • The best-fit heuristic for bin packing is as follows. Consider the objects in the order in which they are given. For each object, place it into the partially filled bin with the smallest amount of extra room after the object is inserted. If no such bin exists, start a new bin. Design an algorithm that implements the best-fit heuristic (taking as input the nn weights w1,w2,...,wnw_1, w_2, ..., w_n and outputting the number of bins used) in O(nlogn)O(n log n) time.
    • Repeat the above using the worst-fit heuristic, where we put the next object into the partially filled bin with the largest amount of extra room after the object is inserted.
    Solution

    g

  26. Suppose that we are given a sequence of nn values x1,x2,...,xnx_1, x_2, ..., x_n and seek to quickly answer repeated queries of the form: given ii and jj, find the smallest value in xi,...,xjx_i, . . . , x_j. a. Design a data structure that uses O(n2)O(n^2) space and answers queries in O(1)O(1) time. b. Design a data structure that uses O(n)O(n) space and answers queries in O(logn)O(log n) time. For partial credit, your data structure can use O(nlogn)O(n log n) space and have O(logn)O(log n) query time.

    Solution
    1fun test() {
    2 val numbers1 = listOf(1, 3, 9, 2, 5)
    3 println(solutionA(numbers1, 2, 5))
    4 println(solutionA(numbers1, 1, 3))
    5 println(solutionB(numbers1, 2, 5))
    6 println(solutionB(numbers1, 1, 3))
    7}
    8
    9fun solutionA(numbers: List<Int>, i: Int, j: Int): Int? {
    10 val list = Array<Array<Int?>>(numbers.size) { Array(numbers.size) { null } }
    11
    12 for (p in numbers.indices) {
    13 var minimumSoFar = Int.MAX_VALUE
    14
    15 for (q in (p+1) until numbers.size) {
    16 val qthNumber = numbers[q]
    17 if (qthNumber < minimumSoFar) {
    18 minimumSoFar = qthNumber
    19 }
    20
    21 list[p][q] = minimumSoFar
    22 }
    23 }
    24
    25 return list[i-1][j-1]
    26}
    27
    28fun solutionB(numbers: List<Int>, i: Int, j: Int): Int? {
    29 TODO()
    30}
  27. Suppose you are given an input set SS of nn integers, and a black box that if given any sequence of integers and an integer kk instantly and correctly answers whether there is a subset of the input sequence whose sum is exactly kk. Show how to use the black box O(n)O(n) times to find a subset of SS that adds up to kk.

    Solution
    1fun test() {
    2 println(findSubset(listOf(3, 5, 8, 2, 1), 6))
    3 println(findSubset(listOf(2, 3, 5, 8, 6, 4), 20))
    4}
    5
    6fun findSubset(s: List<Int>, k: Int): List<Int>? {
    7 if (!blackBox(s, k)) return null
    8
    9 var subset = s
    10 for (i in s.indices) {
    11 val subsetWithoutIthNumber = subset.filter { it != s[i] }
    12
    13 if (blackBox(subsetWithoutIthNumber, k)) {
    14 subset = subsetWithoutIthNumber
    15 }
    16 }
    17
    18 return subset
    19}
    20
    21fun blackBox(integers: List<Int>, k: Int): Boolean {
    22 // We were not told to implement the black box, so we will hack it for the tests
    23 return if (k == 6) {
    24 integers.containsAll(listOf(1, 2, 3))
    25 } else return if (k == 20) {
    26 integers.containsAll(listOf(2, 8, 6, 4)) || integers.containsAll(listOf(3, 5, 8, 4))
    27 } else {
    28 throw IllegalArgumentException()
    29 }
    30}
  28. Let A[1..n]A[1..n] be an array of real numbers. Design an algorithm to perform any sequence of the following operations:

    • Add(i,y) – Add the value yy to the iith number.
    • Partial-sum(i) – Return the sum of the first ii numbers, that is, j=1iA[j]\sum_{j=1}^i A[j].

    There are no insertions or deletions; the only change is to the values of the numbers. Each operation should take O(logn)O(log n) steps. You may use one additional array of size nn as a work space.

    Solution

    g

  29. Extend the data structure of the previous problem to support insertions and deletions. Each element now has both a ''key'' and a ''value''. An element is accessed by its key, but the addition operation is applied to the values. The ''Partial_sum'' operation is different.

    • Add(k,y) – Add the value yy to the item with key kk.
    • Insert(k,y) – Insert a new item with key kk and value yy.
    • Delete(k) – Delete the item with key kk.
    • Partial-sum(k) – Return the sum of all the elements currently in the set whose key is less than kk, that is, i<kxi\sum_{i < k} x_i.

    The worst-case running time should still be O(nlogn)O(n log n) for any sequence of O(n)O(n) operations.

    Solution

    g

  30. You are consulting for a hotel that has nn one-bed rooms. When a guest checks in, they ask for a room whose number is in the range [l,h][l, h]. Propose a data structure that supports the following data operations in the allotted time:

    • Initialize(n): Initialize the data structure for empty rooms numbered 1,2,...,n1, 2, . . . , n, in polynomial time.
    • Count(l, h): Return the number of available rooms in [l,h][l, h], in O(logn)O(log n) time.
    • Checkin(l, h): In O(logn)O(log n) time, return the first empty room in [l,h][l, h] and mark it occupied, or return NIL if all the rooms in [l,h][l, h] are occupied.
    • Checkout(x): Mark room xx as unoccupied, in O(logn)O(log n) time.
    Solution
    1fun test() {
    2 val ds = DataStructure()
    3 ds.initialize(10)
    4 println(ds.root)
    5
    6 println("Available in [2, 5]: ${ds.count(2, 5)}")
    7 val checkIn1 = ds.checkIn(2, 5)
    8 println("Available in [2, 5]: ${ds.count(2, 5)}")
    9 val checkIn2 = ds.checkIn(2, 5)
    10 println("Available in [2, 5]: ${ds.count(2, 5)}")
    11
    12 ds.checkOut(checkIn2!!)
    13 println("Available in [2, 5]: ${ds.count(2, 5)}")
    14 ds.checkOut(checkIn2)
    15 ds.checkOut(checkIn1!!)
    16 println("Available in [2, 5]: ${ds.count(2, 5)}")
    17}
    18
    19class DataStructure() {
    20
    21 lateinit var root: BNode
    22
    23 fun initialize(n: Int) {
    24 root = sortedListToBinaryTree((1..n).toList())!!
    25 }
    26
    27 fun sortedListToBinaryTree(list: List<Int>): BNode? {
    28 if (list.isEmpty()) {
    29 return null
    30 }
    31
    32 val mid = list.size / 2
    33 val root = BNode(list[mid])
    34 root.left = sortedListToBinaryTree(list.slice(0 until mid))
    35 root.right = sortedListToBinaryTree(list.slice((mid + 1) until list.size))
    36
    37 return root
    38 }
    39
    40 fun count(l: Int, h: Int): Int {
    41 return countInRange(l, h, root)
    42 }
    43
    44 fun checkIn(l: Int, h: Int): Int? {
    45 val first = findFirstInRange(l, h, root)
    46 first?.isCheckedIn = true
    47 return first?.element
    48 }
    49
    50 fun checkOut(x: Int) {
    51 find(x, root)?.isCheckedIn = false
    52 }
    53
    54 fun countInRange(l: Int, h: Int, node: BNode?): Int {
    55 if (node == null) {
    56 return 0
    57 }
    58
    59 val count = if (node.element in l..h && !node.isCheckedIn) 1 else 0
    60
    61 return if (node.element in l..h) {
    62 count + countInRange(l, h, node.left) + countInRange(l, h, node.right)
    63 } else if (node.element < l) {
    64 count + countInRange(l, h, node.right)
    65 } else {
    66 count + countInRange(l, h, node.left)
    67 }
    68 }
    69
    70 fun findFirstInRange(l: Int, h: Int, node: BNode?): BNode? {
    71 if (node == null) {
    72 return null
    73 }
    74
    75 if (node.element in l..h && !node.isCheckedIn) {
    76 return node
    77 }
    78
    79 return if (node.element < l) {
    80 findFirstInRange(l, h, node.right)
    81 } else if (node.element > h) {
    82 findFirstInRange(l, h, node.left)
    83 } else {
    84 findFirstInRange(l, h, node.left) ?: findFirstInRange(l, h, node.right)
    85 }
    86 }
    87
    88 fun find(x: Int, node: BNode?): BNode? {
    89 if (node == null) {
    90 return null
    91 }
    92
    93 return if (node.element == x) {
    94 node
    95 } else if (node.element < x) {
    96 find(x, node.right)
    97 } else {
    98 find(x, node.left)
    99 }
    100 }
    101}
    102
    103data class BNode(
    104 val element: Int,
    105 var isCheckedIn: Boolean = false,
    106 var left: BNode? = null,
    107 var right: BNode? = null,
    108)
  31. Design a data structure that allows one to search, insert, and delete an integer XX in O(1)O(1) time (i.e., constant time, independent of the total number of integers stored). Assume that 1Xn1 \leq X \leq n and that there are m+nm + n units of space available, where mm is the maximum number of integers that can be in the table at any one time. (Hint: use two arrays A[1..n]A[1..n] and B[1..m]B[1..m].) You are not allowed to initialize either AA or BB, as that would take O(m)O(m) or O(n)O(n) operations. This means the arrays are full of random garbage to begin with, so you must be very careful.

    Solution
    1fun test() {
    2 val ds = DataStructure(m = 5, n = 10)
    3 ds.insert(7)
    4 ds.insert(3)
    5 ds.insert(6)
    6 ds.insert(5)
    7 ds.insert(9)
    8
    9 println(ds.search(6))
    10 println(ds.search(9))
    11
    12 ds.delete(6)
    13 ds.delete(9)
    14
    15 println(ds.search(6))
    16 println(ds.search(9))
    17}
    18
    19class DataStructure(
    20 val m: Int,
    21 val n: Int
    22) {
    23
    24 val indices = arrayOfNulls<Int>(n + 1)
    25 val values = arrayOfNulls<Int>(m + 1)
    26 var k = 0
    27
    28 fun insert(x: Int) {
    29 k++
    30 indices[x] = k
    31 values[k] = x
    32 }
    33
    34 fun search(x: Int): Int? {
    35 val index = indices[x] ?: return null
    36 return values[index]
    37 }
    38
    39 fun delete(x: Int) {
    40 val xIndex = indices[x] ?: return
    41 if (k == 0) return
    42
    43 val lastValue = values[k]!!
    44 indices[lastValue] = xIndex
    45 values[xIndex] = lastValue
    46 values[k] = null
    47 indices[x] = null
    48
    49 k--
    50 }
    51}
  32. What method would you use to look up a word in a dictionary?

    Solution

    Use a hash table: Store the word as the key and the definition as the value.

  33. Imagine you have a closet full of shirts. What can you do to organize your shirts for easy retrieval?

    Solution

    Sort them based on specific property like color.

  34. Write a function to find the middle node of a singly linked list.

    Solution
    1fun test() {
    2 val node1 = Node("Elvis", null)
    3
    4 val node2 = Node("Chidera", null)
    5 node1.next = node2
    6
    7 val node3 = Node("Nnajiofor", null)
    8 node2.next = node3
    9
    10 val node4 = Node("Jollof", null)
    11 node3.next = node4
    12
    13 val node5 = Node("List", null)
    14 node4.next = node5
    15
    16 println(middleElement(node1))
    17}
    18
    19data class Node(
    20 val element: String,
    21 var next: Node?
    22)
    23
    24fun middleElement(head: Node): Node {
    25 var hare: Node? = head
    26 var tortoise: Node = head
    27
    28 while (hare?.next != null) {
    29 hare = hare.next?.next
    30 tortoise = tortoise.next!!
    31 }
    32
    33 return tortoise
    34}
  35. Write a function to determine whether two binary trees are identical. Identical trees have the same key value at each position and the same structure.

    Solution
    1fun test() {
    2 val s1 = BNode(
    3 element = 5,
    4 left = BNode(
    5 element = 3,
    6 left = null,
    7 right = null
    8 ),
    9 right = BNode(
    10 element = 7,
    11 left = null,
    12 right = null
    13 )
    14 )
    15
    16 val s2 = BNode(
    17 element = 10,
    18 left = BNode(
    19 element = 8,
    20 left = null,
    21 right = null
    22 ),
    23 right = BNode(
    24 element = 12,
    25 left = null,
    26 right = null
    27 )
    28 )
    29
    30 println(isIdentical(s1, s2))
    31 println(isIdentical(s1, s1))
    32 println(isIdentical(s2, s2))
    33}
    34
    35fun isIdentical(tree1: BNode?, tree2: BNode?): Boolean {
    36 if (tree1 == null || tree2 == null) {
    37 return tree1 == tree2
    38 }
    39
    40 return tree1.element == tree2.element &&
    41 isIdentical(tree1.left, tree2.left) &&
    42 isIdentical(tree1.right, tree2.right)
    43}
    44
    45data class BNode(
    46 val element: Int,
    47 var left: BNode?,
    48 var right: BNode?,
    49)
  36. Write a program to convert a binary search tree into a linked-list.

    Solution

    See Problem 14: Part of the solution involves converting a tree into a linked-list.

  37. Implement an algorithm to reverse a linked list. Now do it without recursion.

    Solution
    1fun test() {
    2 val node1 = Node("Elvis", null)
    3
    4 val node2 = Node("Chidera", null)
    5 node1.next = node2
    6
    7 val node3 = Node("Nnajiofor", null)
    8 node2.next = node3
    9
    10 println(reverse(node1))
    11}
    12
    13fun reverse(head: Node): Node {
    14 var currentNode: Node? = head
    15 var previousNode: Node? = null
    16
    17 while (currentNode != null) {
    18 val nextNode = currentNode.next
    19 currentNode.next = previousNode
    20 previousNode = currentNode
    21 currentNode = nextNode
    22 }
    23
    24 return previousNode!!
    25}
    26
    27data class Node(
    28 val element: String,
    29 var next: Node?
    30)
  1. What is the best data structure for maintaining URLs that have been visited by a web crawler? Give an algorithm to test whether a given URL has already been visited, optimizing both space and time.

    Solution

    A dictionary that acts as a set:

    • When a URL is visited, it's added to the dictionary.
    • To check if a URL has been visited, check if the dictionary contains the URL as a key.
  2. You are given a search string and a magazine. You seek to generate all the characters in the search string by cutting them out from the magazine. Give an algorithm to efficiently determine whether the magazine contains all the letters in the search string.

    Solution
    1fun test() {
    2 val node1 = Node("Elvis", null)
    3
    4 println(containsAllCharacters("Elvis", "The Elfs are very happy"))
    5 println(containsAllCharacters("Elvis", "The Elfs are very happy because it is christmas"))
    6}
    7
    8fun containsAllCharacters(string: String, magazine: String): Boolean {
    9 val map = mutableMapOf<Char, Int>()
    10
    11 string.forEach { char ->
    12 map[char] = map.getOrDefault(char, 0) + 1
    13 }
    14
    15 var matched = 0
    16 magazine.forEach { char ->
    17 val count = map[char] ?: 0
    18
    19 if (count > 0) {
    20 matched++
    21 map[char] = count - 1
    22 }
    23
    24 if (matched == string.length) {
    25 return true
    26 }
    27 }
    28
    29 return false
    30}
  3. Reverse the words in a sentence—that is, “My name is Chris” becomes “Chris is name My.” Optimize for time and space.

    Solution
    1fun test() {
    2 println(reverse("My name is Chris"))
    3}
    4
    5fun reverse(sentence: String): String {
    6 val words = sentence.split(" ")
    7 var reversedSentence = ""
    8
    9 var i = words.lastIndex
    10 while (i >= 0) {
    11 val word = words[i]
    12 reversedSentence += word
    13 i--
    14
    15 if (i >= 0) {
    16 reversedSentence += " "
    17 }
    18 }
    19
    20 return reversedSentence
    21}
  4. Determine whether a linked list contains a loop as quickly as possible without using any extra storage. Also, identify the location of the loop.

    Solution
    1fun test() {
    2 val node1 = Node("Elvis", null)
    3
    4 val node2 = Node("Chidera", null)
    5 node1.next = node2
    6
    7 val node3 = Node("Nnajiofor", null)
    8 node2.next = node3
    9
    10 val node4 = Node("Jollof", null)
    11 node3.next = node4
    12
    13 val node5 = Node("List", null)
    14 node4.next = node5
    15
    16 node5.next = node3
    17
    18 println(detectLoopLocation(node1)?.element)
    19}
    20
    21data class Node(
    22 val element: String,
    23 var next: Node?
    24)
    25
    26/**
    27* https://en.wikipedia.org/wiki/Cycle_detection#:~:text=Floyd's%20cycle%2Dfinding%20algorithm%20is,The%20Tortoise%20and%20the%20Hare.
    28*/
    29fun detectLoopLocation(head: Node): Node? {
    30 var hare: Node? = head
    31 var tortoise: Node? = head
    32
    33 while (hare != null) {
    34 hare = hare.next?.next
    35 tortoise = tortoise?.next
    36
    37 if (hare == tortoise) {
    38 break
    39 }
    40 }
    41
    42 if (head.next != null && hare == tortoise) {
    43 hare = head
    44 while (hare != tortoise) {
    45 hare = hare?.next
    46 tortoise = tortoise?.next
    47 }
    48
    49 return tortoise!!
    50 }
    51
    52 return null
    53}
  1. You have an unordered array XX of nn integers. Find the array MM containing nn elements where MiM_i is the product of all integers in XX except for XiX_i. You may not use division. You can use extra memory. (Hint: there are solutions faster than O(n2)O(n^2).)

    Solution
    1fun test() {
    2 println(transform(arrayOf(3, 5, 4)).toList())
    3 println(transform(arrayOf(2, 3, 4, 5, 6)).toList())
    4}
    5
    6fun transform(x: Array<Int>): Array<Int> {
    7 val prefixProducts = Array(x.size) { 0 }
    8 val suffixProducts = Array(x.size) { 0 }
    9
    10 var prefixProduct = 1
    11 x.forEachIndexed { i, xi ->
    12 prefixProducts[i] = prefixProduct
    13 prefixProduct *= xi
    14 }
    15
    16 var suffixProduct = 1
    17 var i = x.lastIndex
    18 while (i >= 0) {
    19 val xi = x[i]
    20 suffixProducts[i] = suffixProduct
    21 suffixProduct *= xi
    22 i--
    23 }
    24
    25 return Array(x.size) {
    26 prefixProducts[it] * suffixProducts[it]
    27 }
    28}
  2. Give an algorithm for finding an ordered word pair (e.g. “New York”) occurring with the greatest frequency in a given webpage. Which data structures would you use? Optimize both time and space.

    Solution
    1fun test() {
    2 println(findOrderedWordPairWithMaxFrequency("New york is a great city. I love new york."))
    3 println(findOrderedWordPairWithMaxFrequency("My name is Elvis Chidera. Elvis Chidera is me."))
    4}
    5
    6/*
    7Punctuation marks can mess up the algorithm. Only "." is handled.
    8 */
    9fun findOrderedWordPairWithMaxFrequency(text: String): Pair<String, String> {
    10 val words = text.replace(".", "").split(" ")
    11 if (words.size <= 1) throw IllegalArgumentException("Text is empty or only has one word")
    12
    13 val wordPairs = mutableMapOf<Pair<String, String>, Int>()
    14
    15 var i = 1
    16 while (i < words.size) {
    17 val previousWord = words[i - 1]
    18 val currentWord = words[i]
    19 val wordPair = previousWord to currentWord
    20
    21 wordPairs[wordPair] = wordPairs.getOrDefault(wordPair, 1) + 1
    22 i++
    23 }
    24
    25 var maxFrequency = 0
    26 var wordPairWithMaxFrequency: Pair<String, String>? = null
    27 wordPairs.forEach { (wordPair, frequency) ->
    28 if (frequency > maxFrequency) {
    29 maxFrequency = frequency
    30 wordPairWithMaxFrequency = wordPair
    31 }
    32 }
    33
    34 return wordPairWithMaxFrequency!!
    35}

Chaper 4: Sorting

This chapter discusses sorting, algorithm design paradigms espoused by sorting algorithms and how sorting can be applied in solving other problems.

Applications of sorting

The first algorithm design paradigm is the application of sorting as an initial step to simplify another computational problem. e.g.

  • Searching – Preprocessing the search items by sorting them allows an efficient O(logn)O(\log n) algorithm like binary search to be used.
  • Closest pair – Once a set of numbers are sorted, the closest pair of numbers must lie next to each other somewhere in sorted order. Thus, a linear-time scan through the sorted list completes the job, for a total of O(nlogn)O(n \log n) time including the sorting.
  • Element uniqueness – An efficient algorithm sorts the elements and then does a linear scan checking all adjacent pairs.
  • Finding the mode – When the items are sorted, we can sweep from left to right and count the number of occurrences of each element, since all identical items will be adjacent to each other after sorting,
  • Selection – If the keys are placed in sorted order, the kth largest item can be found in constant time because it must sit in the kth position of the array.

Sorting pragmatics

Pairwise comparison (i.e. is aa >> or << or == to bb) is typical abstracted away into a comparison function that is then passed to the sorting algorithm. This allows the sorting algorithm to be independent of application-specific comparison concerns like:

  • Alphabetizing – A collating sequence (also called a sort sequence) defines how characters in a character set relate to each other when they are compared and ordered. This can vary from usecase to usecase, e.g. should "Elvis" be equivalent to "elvis"?
  • Arbitrary elements – What properties of the element should be used as the key for comparisons?
  • Sort order – A set of keys SS are sorted in ascending order when SiSi+1S_i \leq S_{i+1} for all 1i<n1 \leq i < n. They are in descending order when SiSi+1S_i \geq S_{i+1} for all 1i<n1 \leq i < n. Different applications call for different orders and this can be handled by only changing the comparison function.
  • Handling equal elements – Elements with equal key values all bunch together in any total order. When the relative order among these keys matters, a common strategy is to sort the equal elements using a secondary key, which can be handled easily with the comparison function.

An example comparison function:

1/**
2* Returns a negative integer if `e1` is less than `e2`.
3* Returns zero if `e1` is equal `e2`.
4* Returns a positive integer if `e1` is greater than `e2`.
5*/
6fun compare(e1: Element, e2: Element): Int {
7
8}

Stable sorting algorithms maintain the relative order of elements with equal keys. That is, a sorting algorithm is stable if whenever there are two elements RR and SS with the same key and with RR appearing before SS in the original list, RR will appear before SS in the sorted list.

Few fast algorithms are naturally stable. Stability can be achieved for any sorting algorithm by adding the initial position as a secondary key.

When equal elements are indistinguishable, such as with integers, or more generally, any data where the entire element is the key, stability is not an issue.

Heap: Data structure

A heap is a tree-based data structure that satisfies the heap property:

  • In a max heap, for any given node CC, if PP is a parent node of CC, then the key (the value) of PP is greater than or equal to the key of CC.
  • In a min heap, the key of PP is less than or equal to the key of CC.

The heap is one maximally efficient implementation of a priority queue ADT. In a heap, the highest (or lowest) priority element is always stored at the root. A heap is a useful data structure when it is necessary to repeatedly remove the object with the highest (or lowest) priority.

However, a heap is not a sorted structure; it can be regarded as being partially ordered: there is no implied ordering between siblings or cousins and no implied sequence for an in-order traversal. The heap relation mentioned above applies only between nodes and their parents, grandparents, etc.

Implementation

Heaps are usually implemented with an array:

  • Each element in the array represents a node of the heap, and
  • The parent / child relationship is defined implicitly by the elements' indices in the array. This implicit structure is space efficient as it eliminates the need for pointers to give an explicit relationship between elements.

For a binary heap, in the array:

  • The first index contains the root element.
  • The next two indices of the array contain the root's children.
  • The next four indices contain the four children of the root's two child nodes, and so on.

This can be generalized into:

Given a node at index ii,

Its left child is at index 2i+12i + 1

Its right child is at index 2i+22i + 2

And its parent is at index (i1)/2\lfloor (i - 1) / 2 \rfloor

This simple indexing scheme makes it efficient to move "up" or "down" the tree.

This implicit structure trades space efficiency for flexibility. e.g. With pointers, we can move subtrees around by changing a single pointer.

To avoid potentially requiring a 2n12^n - 1 array to store an nn-element heap, it's required that the binary heap is complete with its element inserted from left to right. This structural constraint allows us to store the nn-element heap with the first nn indices of the array. When a heap is a complete binary tree, it has the smallest possible height — a heap with NN nodes and aa branches for each node always has logaN\log_a N height.

Heap as an array

1/**
2 * Put elements of [array] in heap order, in-place.
3 *
4 * Consider the array in reverse order, starting from the last (nth) position. It represents a leaf of the tree and
5 * so trivial obeys the heap property (i.e. it's larger than its non-existent children). The same is the case for
6 * the last n/2 positions in the array, because all are leaves.
7 *
8 * If we continue to walk backwards through the array we will eventually encounter an internal node with children.
9 * This element may not obey the heap property (because it might be smaller than its children),
10 * but its children represent well-formed (if small) heaps. This situation is exactly what [siftDown] was designed
11 * to do: given a "damaged" binary heap, where the max-heap property (no child is greater than its parent) holds
12 * everywhere except possibly between the root node and its children, repair it to produce an undamaged heap.
13 *
14 * To see that this takes O(n) time, count the worst-case number of [siftDown] iterations.
15 * The last half of the array requires zero iterations, the preceding quarter requires at most one iteration,
16 * the eighth before that requires at most two iterations, the sixteenth before that requires at most three, and so on.
17 */
18private fun heapify(array: ArrayList<Int>) {
19 // Start is initialized to the first leaf node
20 // Find the parent of the last element.
21 var start = iParent(array.lastIndex) + 1
22
23 while (start > 0) {
24 // Go to the last non-heap node
25 start -= 1
26 // Sift down the node at index 'start' to the proper place such that all nodes below the start index are in heap order
27 siftDown(array, start, array.lastIndex)
28 }
29
30 // After sifting down the root all nodes/elements are in heap order.
31}
32
33private fun siftUp(array: ArrayList<Int>, index: Int) {
34 var index = index
35
36 while (index > 0) {
37 val parentIndex = iParent(index)
38
39 if (array[parentIndex] < array[index]) {
40 swap(array, parentIndex, index)
41 index = parentIndex
42 } else {
43 return
44 }
45 }
46}
47
48/**
49 * Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid.
50 *
51 * The number of iterations in any one [siftDown] call is bounded by the height of the tree, which is ⌊log2 n⌋ = O(log n).
52 */
53fun siftDown(array: ArrayList<Int>, rootIndex: Int, endIndex: Int) {
54 var rootIndex = rootIndex
55 while (iLeftChild(rootIndex) <= endIndex) { // While the root has at least one child
56 var biggerChildIndex = iLeftChild(rootIndex)
57
58 // If there is right child and that child is greater
59 if (iRightChild(rootIndex) <= endIndex && array[biggerChildIndex] < array[iRightChild(rootIndex)]) {
60 biggerChildIndex = iRightChild(rootIndex)
61 }
62
63 if (array[rootIndex] < array[biggerChildIndex]) {
64 swap(array, rootIndex, biggerChildIndex)
65 rootIndex = biggerChildIndex
66 // Repeat to continue sifting down the child now.
67 } else {
68 // The root holds the largest element. Since we may assume the heaps rooted at the children are valid,
69 // this means that we are done.
70 return
71 }
72 }
73}
74
75private fun swap(array: ArrayList<Int>, i: Int, j: Int) {
76 val temp = array[i]
77 array[i] = array[j]
78 array[j] = temp
79}
80
81fun iParent(i: Int): Int {
82 return floor(i / 2.0).toInt()
83}
84
85fun iLeftChild(i: Int): Int {
86 return (i * 2) + 1
87}
88
89fun iRightChild(i: Int): Int {
90 return (i * 2) + 2
91}
92
93data class Heap(private val array: ArrayList<Int>) {
94
95 init {
96 heapify(array)
97 }
98
99 /**
100 * Add the new element at the end of the heap, in the first available free space.
101 * If this violates the heap property, sift up the new element until the heap property has been reestablished.
102 * Since the heap is balanced, the height is $log_2 n$ and hence each insertion costs at most $O(log_2 n)$.
103 */
104 fun insert(element: Int) {
105 array.add(element)
106 siftUp(array, array.lastIndex)
107 }
108
109 /**
110 * Remove the root and insert the last element of the heap in the root.
111 * If this violates the heap property, sift down the new root to reestablish the heap property.
112 */
113 fun pop(): Int {
114 val root = array[0]
115 val lastChild = array.removeLast()
116 array[0] = lastChild
117 siftDown(array, 0, array.lastIndex)
118 return root
119 }
120
121 /**
122 * Remove the root and put the new element in the root and sift down.
123 * When compared to pop followed by insert, this avoids a sift up step.
124 */
125 fun replaceRoot(element: Int) {
126 array[0] = element
127 siftDown(array, 0, array.lastIndex)
128 }
129}

Heapsort: Fast sorting via data structures

Heapsort is an in-place comparison-based sorting algorithm which can be thought of as "an implementation of selection sort using the right data structure." Like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. Unlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure to efficiently find the largest element in each step.

Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantages of very simple implementation and a more favorable worst-case O(nlogn)O(n \log n) runtime. Most real-world quicksort variants include an implementation of heapsort as a fallback should they detect that quicksort is becoming degenerate.

Heapsort is an example of the second algorithm design paradigm: Use an appropriate data structure.

1/**
2 * The steps are:
3 *
4 * 1. Call the [heapify] function on the array. This builds a heap from an array in O(n) operations.
5 * 2. Swap the first element of the array (the largest element in the heap) with the final element of the heap. Decrease the considered range of the heap by one.
6 * 3. Call the [siftDown] function on the array to move the new first element to its correct place in the heap.
7 * 4. Go back to step (2) until the remaining array is a single element.
8 *
9 * The [heapify] operation is run once, and is O(n) in performance.
10 * The [siftDown] function is called n times and requires O(log n) work each time, due to its traversal starting from the root node.
11 * Therefore, the performance of this algorithm is O(n + n log n) = O(n log n).
12 */
13fun heapsort(array: ArrayList<Int>): ArrayList<Int> {
14 // Build the heap in the array so that largest value is at the root
15 heapify(array)
16 var endIndex = array.lastIndex
17
18 // The following loop maintains the invariants that every element between 0 to endIndex is a heap, and
19 // every element beyond endIndex is greater than everything before it (in sorted order).
20 while (endIndex > 0) {
21 // [0] is the root and largest value. The swap moves it in front of the sorted elements.
22 swap(array, 0, endIndex)
23 // The heap size is reduced by one.
24 endIndex--
25 // The swap ruined the heap property, so restore it.
26 siftDown(array, 0, endIndex)
27 }
28
29 return array
30}
© 2024 by Elvis Chidera. All rights reserved.