Creating this topic to catch any typos and bugs in the 5th Edition of Data Structures & Algorithms in Swift.
2 Likes
Hi @jellodiil
I found a potential mistake in one of the challenges, but I’m not sure if I might have missed something from the lesson. In Graph Chapter → DFS lesson → Challenge 3 (Checking for a Cycle in a Graph), the provided solution seems to always return true, even when the graph does not contain a cycle.
let graph = AdjacencyList()
let a = graph.createVertex(data: “A”)
let b = graph.createVertex(data: “B”)
let c = graph.createVertex(data: “C”)
let d = graph.createVertex(data: “D”)
graph.add(.directed, from: a, to: b, weight: nil)
graph.add(.directed, from: b, to: c, weight: nil)
graph.add(.directed, from: c, to: a, weight: nil)
graph.add(.directed, from: c, to: d, weight: nil)
//graph.add(.directed, from: d, to: c, weight: nil) // This will cause a cycle
print(“Has cycle: (graph.hasCycle(from: a))”)
Based on this setup, the graph should not contain a cycle unless we explicitly add the edge from d to c. However, graph.hasCycle(from: a) always returns true, which seems incorrect.
Since this is my first time posting here, I’d appreciate any guidance on whether I should report this differently. Let me know if you need more details!
is this book going to be available as an update for previous purchases?
right now is listed as a 5th edition but only available to download until 4th edition
There is an error in LinkedList index implementation.
extension LinkedList: Collection {
public struct Index: Comparable {
public var node: Node<Value>?
static public func ==(lhs: Index, rhs: Index) -> Bool {
switch (lhs.node, rhs.node) {
case let (left?, right?):
return left.next === right.next
case (nil, nil):
return true
default:
return false
}
}
static public func <(lhs: Index, rhs: Index) -> Bool {
guard lhs != rhs else {
return false
}
let nodes = sequence(first: lhs.node) { $0?.next }
return nodes.contains { $0 === rhs.node }
}
}
}
The comparison should just compare the nodes for referential equality, as it is both simpler, and it is possible that two nodes have same next node, while not being equal (hence difference positions, and probably in different lists…).
In Chapter 7 Solutions, the “naive” solution to exercise 3 is wrong, as only the head gets updated, while tail remains invalid.
The solution to Chapter 7, Exercise 4 is a bit problematic as well. The result breaks the lists, as it modifies their nodes directly instead of copying them. I understand that it is done to illustrate working with linked structures, but such functions should in general be made inout, and since it is a beginner book after all, it I believe it should be emphasized that direct access to mutable nodes is a bad practice (they should not be exposed, at least the mutable parts), as it allows to break the LinkledList value semantics by explicitly manipulating its nodes.
Anyway, the solution should be accept two inout lists, as it modifies them.
Another option would to make them consuming with appropriate adjustments.
I believe semething like this should do the job.
Another option would to make them consuming with appropriate adjustments.
I believe something like this guarantees that copy is performed, unless the the lists are unique (that’s why we use consuming) in which case nothing is copied.
func mergeSorted<T: Comparable>(
_ left: consuming LinkedList<T>,
with right: consuming LinkedList<T>
) -> LinkedList<T> {
var currentLeftNode = left.copyNodes(returningCopyOf: left.head)
var currentRightNode = right.copyNodes(returningCopyOf: right.head)
let newHead: Node<T>?
switch (currentLeftNode?.value, currentRightNode?.value) {
case (nil, nil):
return left
case (nil, _):
return right
case (_, nil):
return left
case let (leftValue?, rightValue?) where leftValue < rightValue:
newHead = currentLeftNode
currentLeftNode = currentLeftNode?.next
default:
newHead = currentRightNode
currentRightNode = currentRightNode?.next
}
var currentTail = newHead
while currentLeftNode != nil && currentRightNode != nil {
switch (currentLeftNode?.value, currentRightNode?.value) {
case (let leftValue?, let rightValue?) where leftValue < rightValue:
currentTail?.next = currentLeftNode
currentLeftNode = currentLeftNode?.next
default:
currentTail?.next = currentRightNode
currentRightNode = currentRightNode?.next
}
currentTail = currentTail?.next
}
currentTail?.next = currentLeftNode ?? currentRightNode
currentTail = if currentLeftNode != nil { left.tail } else { right.tail }
var result: LinkedList = .init()
result.head = newHead
result.tail = currentTail
return result
}