liveBookmanning.com

What you will learn in Classic Computer Science Problems in Swift: Essential techniques for practicing programmers

Essential techniques for practicing programmers

by David Kopec

Read it on liveBook Get the book at manning.com

Chapter by chapter

Concepts explained in this book

• neuronA neuron is a computational unit that combines input signals with weights, applies an activation function, and produces an output signal.
• learning rateA learning rate is a training hyperparameter that controls the size of parameter updates made while fitting a model.
• trainingTraining is the process of fitting a machine-learning model by providing examples and adjusting its parameters to reduce output error.
• input layerAn input layer is the first neural-network layer that receives input signals and passes them into the network.
• hidden layerA hidden layer is a neural-network layer between the input and output layers whose outputs are not the network's final outputs.
• output layerAn output layer is the final neural-network component that transforms internal representations into task-specific predictions, scores, or other outputs.
• stackA stack is a last-in-first-out data structure in which insertion and removal occur at the same end.
• genetic algorithmAn evolutionary optimization technique that searches for solutions by iteratively selecting, combining, and mutating candidate representations according to their fitness.
• Euclidean distanceEuclidean distance is the straight-line distance between two points calculated from the square root of the sum of squared coordinate differences.
• inner productA dot product is the scalar obtained by multiplying corresponding components of two equal-length vectors and summing the products.
• weighted graphA weighted graph is a graph whose edges have associated values representing connection costs or other quantities.
• A-star algorithmA* search explores a state graph using the sum of a path cost and a heuristic estimate of the remaining cost to prioritize states.
• breadth-first searchA graph or state-space search algorithm that explores all states at the current distance before proceeding to greater distances.
• depth-first searchDepth-first search explores one path as deeply as possible before backtracking to an earlier decision point.
• heuristic functionA heuristic function estimates the remaining cost from a search state to a goal state.
• accuracyAccuracy is the proportion of evaluated examples that a classifier assigns to the correct category.
• fitnessA function that assigns a score indicating how well a candidate solution satisfies the problem objective.
• activation functionAn activation function is a function applied to a neuron's output to introduce nonlinearity and constrain the output range in a neural network.
• classifierA classification problem is a machine-learning problem in which data items are assigned to one of a predefined set of categories.
• admissible heuristicAn admissible heuristic is a heuristic that never overestimates the cost of reaching the goal.
• frontierA frontier is the collection of discovered search states that remain candidates for exploration.
• MazeLocationMazeLocation is a book-specific value type representing a row-and-column position in a maze.
• NodeNode is a book-specific wrapper that stores a search state together with its parent, cost, and heuristic information.
• successorssuccessors is a function that returns the reachable neighboring maze locations from a given location.
• Manhattan distanceManhattan distance is the sum of the absolute differences between corresponding coordinates of two points.
• mazeA navigational problem space consisting of connected locations and passages with a goal of finding a path between locations.
• priority queueA priority queue is a data structure that removes elements according to priority rather than insertion order.
• queueA queue is a first-in-first-out data structure in which the earliest inserted item is removed first.
• objective functionAn error function is a mathematical function that assigns a numerical measure to the discrepancy between predicted and expected outputs.
• chromosomeA chromosome is a candidate solution representation that provides fitness evaluation, copying, random initialization, crossover, mutation, and human-readable output for a genetic algorithm.
• neural network layerA layer is an organized group of neural-network neurons that receives signals from a preceding layer and produces outputs for the next layer.
• normalizationNormalization is the process of transforming a value, representation, or data structure to satisfy a specified standard, scale, or structural constraint.
• deltaA delta is a neural-network error signal that combines a neuron's error with the derivative of its activation function to quantify the adjustment direction.
• K-means clusteringK-means clustering is an iterative unsupervised learning algorithm that partitions data points into a predefined number of clusters by repeatedly assigning points to their nearest centroid and recomputing the centroids.
• crossoverA genetic algorithm technique that combines portions of parent chromosomes to produce offspring chromosomes.
• mutationMutation is a change to an existing value, object, data structure, state, or representation.
• embeddingA vector is an ordered collection of numerical components representing a quantity or point in a mathematical space.
• weighted edgeA graph edge carrying a comparable value that represents a cost, distance, or other quantity associated with the connection.
• backtrackingBacktracking search explores candidate solutions incrementally and reverses decisions when a partial candidate cannot lead to a solution.
• shortest pathA shortest path is a path between vertices whose total edge cost is minimal among the available paths.
• constraintA book-specific class whose instances store constrained variables and provide a method for checking whether an assignment satisfies the constraint.
• unweighted graphAn unweighted graph is a graph whose edges do not have numerical costs or distances.
• nucleotideA nucleotide is a molecular unit of DNA, with the DNA nucleotides in this section represented by A, C, G, or T.
• feedforward networkA feed-forward network is a neural network in which signals move through successive layers in a single direction without cycles.
• Traveling Salesman problemThe Traveling Salesman problem asks for a minimum-cost cycle that visits every city exactly once and returns to the starting city.
• recursionAn algorithm that solves a problem by invoking itself on smaller instances of the same problem.
• domainIn a constraint-satisfaction problem, a domain is the set of possible values that may be assigned to a variable.
• first-in-last-out structureLast-in-first-out is an access-ordering rule in which the most recently inserted item is removed first.
• populationA population in a genetic algorithm is a collection of candidate solutions maintained as a group during evolution.
• DataPointDataPoint is a book-specific Swift interface for comparable, printable points whose coordinates are represented by a fixed number of Double dimensions.
• meanA mean is a measure of central tendency, calculated as the arithmetic average of values or, for a random variable, as the probability-weighted average of its possible values.
• feature scalingFeature scaling is the transformation of a feature's values from an original numeric range to a common scale such as 0 to 1.
• wine datasetThe wine dataset is a labeled collection of 178 wine-cultivar samples represented by chemical-analysis attributes and belonging to three cultivars.
• iris datasetThe iris dataset is a labeled collection of 150 iris-plant samples from three species, each represented by four measured attributes.
• validationValidation is the evaluation of a trained model on examples held apart from the data used to adjust its parameters.
• constraint-satisfaction problemA constraint-satisfaction problem is a problem defined by variables, possible values for those variables, and constraints restricting compatible assignments.
• min-max gameMinimax is a decision-making algorithm for two-player zero-sum games that selects a move by maximizing the player's outcome while accounting for an opponent who minimizes it.
• backpropagationBackpropagation is a procedure for computing derivatives of an output or loss with respect to inputs and parameters by applying the chain rule backward through a computational graph.
• geneGene is a book-specific array-based representation of a nucleotide sequence as an ordered collection of codons.
• clusteringClustering is a computational technique that divides data points into groups whose members are related according to some measure or interpretation.
• stopping criterionThe terminating condition of a recursive algorithm that can be solved directly without another recursive invocation.
• connected graphA connected graph is a graph in which a path exists between every pair of vertices.
• Jarnik's algorithmJarnik's algorithm, commonly called Prim's algorithm, constructs a minimum spanning tree by repeatedly adding the lowest-weight edge connecting the current tree to an outside vertex.
• SummableA book-specific Swift protocol for types whose instances can be combined with the + operator.
• minimum spanning treeA minimum spanning tree is a spanning tree of a weighted graph whose total edge weight is minimal among all spanning trees of that graph.
• spanning treeA spanning tree is a tree that includes every vertex of a graph.
• treeA tree is a connected, acyclic structure of nodes, commonly organized hierarchically through parent-child relationships and optionally around a designated root.
• centroidA centroid is a representative center of a cluster, typically computed as the mean position of its member points.
• dynamic programmingDynamic programming is an algorithmic technique that solves a problem by combining solutions to overlapping smaller subproblems, typically storing intermediate results.
• knapsack problemThe knapsack problem is an optimization problem that selects items with given values and weights to maximize total value without exceeding a capacity limit.
• failureError is the discrepancy between a model's actual output and the expected output for an input.
• gradient descentGradient descent is an iterative optimization method that updates parameters opposite the gradient of an objective function to reduce its value.
• supervised learningSupervised learning is a machine-learning approach that learns from inputs paired with known target outputs.
• brute-force searchBrute-force search systematically examines many or all possible candidates until a valid solution is found.
• generationA generation is one evolutionary cycle in which a genetic algorithm evaluates and transforms a population of candidate solutions.
• A* evaluation functionThe A* evaluation function is the sum of the accumulated path cost and the heuristic estimate for a state.
• heapA binary heap is a tree-shaped priority-queue implementation that maintains an ordering relationship between parents and children.
• Comparable interfaceComparable is a Swift standard-library protocol for types whose values can be ordered relative to one another.
• HashableHashable is a Swift protocol for types whose values can be represented by hash values for hashed collection membership and lookup.
• inoutinout is a Swift parameter modifier that allows a function to modify the caller's original variable.
• astarastar is a book-specific function that performs A* search over maze states.
• CellCell is a book-specific enumeration representing the contents of a maze location, including empty and blocked spaces.
• generateMazegenerateMaze is a book-specific function that constructs a randomly sparsified maze.
• heuristicFnheuristicFn is a book-specific function parameter that supplies a heuristic score for a search state.
• successorsForMazesuccessorsForMaze is a book-specific function that produces a maze-specific successor function.
• SwiftPriorityQueueSwiftPriorityQueue is an open-source Swift library providing a priority queue implementation.
• visitedvisited is the set of search states that have already been explored.
• mathematical variableA mathematical variable is a symbol or quantity representing a value or attribute that can vary or be determined within a defined domain.
• tournament selectionA genetic algorithm selection technique that randomly challenges several chromosomes and selects the one with the best fitness.
• binary searchA binary search locates a value in an ordered, index-accessible collection by repeatedly comparing with the middle element and halving the candidate range.
• linear searchA linear search examines elements sequentially in their data-structure order until it finds the sought value or reaches the end.
• adjacency listA graph representation that stores, for each vertex, the vertices or edges directly connected to it.
• associatedtypeA Swift protocol declaration feature that defines a placeholder type to be specified by each conforming type.
• bidirectional edgeA graph edge that permits travel between its two endpoint vertices in both directions.
• protocolA Swift language construct that specifies requirements for types to adopt without defining a class hierarchy.
• protocol extensionA Swift extension mechanism that adds implementations and other members to a protocol or its conforming types.
• protocol-oriented programmingA programming style that emphasizes protocols and composition over class inheritance.
• unweighted edgeA graph edge that represents a connection without an associated weight.
• permutationA permutation is an ordering of the elements of a collection in which each element appears exactly once.
• z-scoreA z-score is a standardized value expressing how many standard deviations a value lies from its distribution's mean.
• GeneticAlgorithmA book-specific generic implementation of a genetic algorithm that operates on types conforming to Chromosome.
• roulette-wheel selectionA genetic algorithm selection technique that chooses chromosomes with probabilities proportional to their fitness.
• standard deviationStandard deviation is the square root of variance and measures the typical magnitude of deviations from the mean.
• KMeansKMeans is a book-specific generic Swift class that maintains clusters and executes the k-means clustering algorithm for types conforming to DataPoint.
• factorialA factorial is the product of all positive integers from one through a given nonnegative integer.
• near-optimal solutionA near-optimal solution is a feasible solution whose objective value is close to the best possible value without necessarily being optimal.
• NP-hard problemAn NP-hard problem is a problem at least as difficult as every problem in NP under polynomial-time reductions and not known to have a polynomial-time solution.
• compressionCompression is the process of representing data with fewer bits by eliminating or encoding redundancy.
• codonA codon is a sequence of three nucleotides that specifies an amino acid.
• capacityKnapsack capacity is the maximum total weight that the selected items may occupy.
• final stateA terminal position is a game state at which play ends because a player has won or the game is drawn.
• Tic-Tac-ToeTic-tac-toe is a two-player game played on a three-by-three grid in which players alternately place marks and aim to form a line of three matching marks.
• activation function derivativeAn activation function derivative is the derivative of an activation function evaluated with respect to its input.
• @escaping@escaping is a Swift parameter annotation indicating that a closure may be stored or invoked after the function receiving it returns.
• training datasetA collection of examples or observations supplied to a learning procedure to fit or adapt a model or learn its patterns or parameters.
• memoizationMemoization is an optimization technique that caches the results of computations so repeated requests for the same inputs can be answered without recomputation.
• one-time padA symmetric encryption technique that combines plaintext with an equally long, secret, random pad so that the plaintext cannot be recovered without both resulting components.
• Dijkstra's algorithmDijkstra's algorithm computes shortest paths from a source vertex to reachable vertices in a weighted graph with nonnegative edge weights.
• permutation generationPermutation generation is the systematic production of possible orderings formed from a set of elements.
• Towers of Hanoi puzzleA mathematical puzzle involving moving a stack of differently sized discs between three pegs while allowing one disc at a time and forbidding wider discs from resting on narrower discs.
• cryptarithmetic puzzleA mathematical puzzle in which letters represent digits and an arithmetic statement must be made true subject to digit-assignment constraints.
• Fibonacci sequenceThe sequence of integers in which each term is the sum of the two preceding terms, typically starting with 0 and 1.
• decompressionDecompression is the process of reversing a compressed representation to recover the original data.
• varianceVariance is a statistical measure of the average squared deviation of values from their mean.
• optimizationOptimization is the process of selecting or constructing a solution that minimizes or maximizes an objective under given conditions.
• distanceA measure of separation between locations or points in a feature space.
• single-source shortest pathThe single-source shortest path problem asks for the minimum-weight paths from one starting vertex to every other vertex in a weighted graph.
• constraint-satisfaction frameworkA constraint-satisfaction framework represents variables, their possible values, and constraints and provides procedures for finding satisfying assignments.
• logical XORThe exclusive-or operation that returns true for exactly one true operand and false when both operands have the same truth value.
• AccelerateAccelerate is Apple's framework for high-performance numerical, signal-processing, and image-processing operations on its platforms.
• BLASBLAS is a standard interface and family of routines for basic vector and matrix operations in numerical computing.
• vector and matrix arithmeticVector and matrix arithmetic is numerical computation on ordered collections and rectangular arrays of numbers.

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.