Errata for Data Structures & Algorithms in Kotlin 2nd Edition

Creating this topic to catch any typos and bugs in the 2nd Edition of Data Structures & Algorithms in Kotlin.

There seem to be some problems with the challenge problem for Chapter 11, that is,
implementing a function ArrayList.findIndices(value: T) where T: Comparable
which returns a range of indices satisfying this[index] == value.

arrayListOf(0,1,3,3).findIndices(2)
// -> This will throw a StackOverflowException
//    with the subroutine call 
//    startIndex(2, 0..3) going into an infinite recursion 
//    on the empty range 2..1

The problem here is with missing a check for emptiness of the range.

A second problem with both subfunctions startindex and endIndex on the pages 221 and 222 is the checking for the middleIndex lying on either boundary of the list.

val arr = arrayListOf(0,1)
arr.findIndices(0)
// → returns null where it should return 0..0

Here the first computed middleIndex 1 is already the right boundary of the list.
Then the following will falsely return null in the previous example:

// 2 
if (middleIndex == 0 || middleIndex == size – 1) { // ?????
    return if (this[middleIndex] == value) {
        middleIndex 
    } else {
        null    // ?????
    }
}

I didn’t quite succeed in fixing every issue with the book implementation though.
There seem to be yet more issues with corner cases.
I did however find a solution which is loosely based on the approach from the following video lecture

Here’s an alternative solution:

/**
 * binaryFindFirst is only applicable on 'this' with argument prop if 
 *
 * this.map{ prop(this,it) } == [false, ... , false, true, ... , true]
 *    or
 * this.map{ prop(this,it) } == [false, ... , false]
 *    or 
 * this.map{ prop(this,it) } == [true , ... , true]
 * 
 * In other words:
 * If there exist indices i such that prop(this, i) == true 
 * then the list 'this' is partitioned such that all elements j with 
 * prop(this, j) == false lie on the left, and those indices 
 * i with prop(this,i) == true lie on the right.
 */
 
fun <T> List<T>.binaryFindFirst(
    prop: (l: List<T>, ind: Int) -> Boolean
): Int? {
    var res: Int? = null 
    var l = 0
    var r = this.lastIndex 
    while(l <= r) {
        val m = l + (r - l)/2 
        if (prop(this,m)) {
            res = m 
            r = m - 1
        }
        else 
            l = m + 1
    }
    return res
}

/**
 * binaryFindLast is only applicable on 'this' with argument prop if 
 *
 * this.map{ prop(this,it) } == [true, ... , true, false, ... , false]
 *    or
 * this.map{ prop(this,it) } == [false, ... , false]
 *    or 
 * this.map{ prop(this,it) } == [true , ... , true]
 *
 * In other words:
 * If there exist indices i such that prop(this, i) == true 
 * then the list 'this' is partitioned such that all elements j with 
 * prop(this, j) == false lie on the right, and those indices 
 * i with prop(this,i) == true lie on the left.
 */

fun <T> List<T>.binaryFindLast(
    prop: (l: List<T>, ind: Int) -> Boolean
): Int? {
    var res: Int? = null 
    var l = 0
    var r = this.lastIndex 
    while(l <= r) {
        val m = l + (r - l)/2 
        if (prop(this,m)) {
            res = m 
            l = m + 1
        }
        else 
            r = m - 1
    }
    return res    
}

/**
 * findIndices only applies to sorted lists.
 */
fun <T: Comparable<T>> List<T>.findIndices(value: T): IntRange? {
    // 1
    val left = binaryFindFirst { list, index ->
        list[index] >= value
    } ?: return null
    
    // 2
    if (this[left] != value) return null

    // 3
    val right = binaryFindLast { list, index -> 
        list[index] <= value
    } ?: return null

    // 4
    return left..right
}

/*
  1. The list must by assumption be sorted and any indices k 
     such that list[k] >= value are on the right.
     So binaryFindFirst is applicable.
 
  2. By assumption the list is sorted.
     Thus if the first index k such that list[k] >= value 
     does not satisfy list[k] == value, then list[k] > value
     and there can be no index j satisfying 
     list[j] == value. Hence we can return null.
 
  3. The list is by assumption sorted and all indices k such that 
     list[k] <= value are on the left (if existant).
     So binaryFindLast is applicable.
 
  4. If there exists any index k with list[k] == value,
     then all indices j within left..right satisfy list[j] == value.
 */

Note:

I guess technically for this problem we don’t need to pass both list and index to the lambdas. But this way the binaryFindFirst and binaryFindLast methods are also applicable in situations, where the property does not only depend on the list’s value at the current index.

For instance, there is a problem from the above video around minute 14:

Assume we are given a formerly sorted array from small to big, that was changed by applying a circular shift, e.g. [6,7,9,15,19,2,3] is the sorted array [2,3,6,7,9,15,19] after a two-fold circular left shift.

Find the smallest element in such a rotated sorted array.

In this case we can just use our binaryFindFirst method to find the first element smaller or equal to the leftmost entry.

fun <T: Comparable<T>> List<T>.findMinInRotatedList(): Int =
    binaryFindFirst { list, index -> list[index] <= list[0] }!!

Here the property does not only depend on the value at current index,
but also on the value at 0.

[Edited for better names and readability.]

Hi, great book, massive help so far.

There seems to be a double print of the code associated with Creating a Vertex, in Chapter 19 - Graphs. The code for createVertex() is printed twice in the code section, but each with a different set of steps.

The same thing happens in the same chapter, couple of pages further along, in the Visualize an adjacency matrix section, the toString() method is printed twice in the code section

Since I’m a new user here I cannot attach more than 1 media element but you can see this in the section mentioned above

Thanks a lot for all your efforts, this book helped a lot in everything

yes. thanks for information

I already bought the 1st edition, how different is the 2nd edition??
Is there an “errata” page that can save me another $60 ???