Computer Science Distilled: Learn the Art of Solving Computational Problems

My personal notes on the book Computer Science Distilled: Learn the Art of Solving Computational Problems.

1. Basics

  • Dump all important stuff on paper.
  • Probability

    • The formula:
      \(P(event) = \frac{\#\ of\ ways\ event\ can\ happen}{\#\ of\ possible\ outcomes}\)

    • Independent events: \(P(A \cap B) = P(A) \cdot P(B)\)
    • Mututally exclusive events: \(P(A \cup B) = P(A) + P(B)\)
    • Complimentary events: \(1 = P(A) + P(B)\)
    • The Gambler’s Fallacy: past events never affect the outcome of an independent event.

2. Complexity

  • Time complexity, denoted by T(n), gives the number of operations the number of operations the algorithm performs when processing an input of size n.
    • When an algorithm can have different values of T(n) for the same value n, we resort to cases:
      • Best case
      • Worst case
      • Average case
    • In general, the most important is the worst case (baseline).
  • We can find the time complexity of an algorithm by counting the number of basic operations it requires for an hypothetical input of size n.
    • We can approximate T(n) by its fastest-growing term, called the dominant term: \(T(n) = n^2 + n - 2 \approx O(n^2)\)
  • The Big-O notation
    • This notation is used to express the dominant term of an algorithm’s cost function in the worst case. A function with a fastest-growing term of \(2^n\) or “weaker” is \(O(2^n)\)
  • Space complexity measures the working storage for an algorithm.

3. Strategy

  • The iterative strategy consists of using loops to repeat a process until a condition is met.
  • The recursive strategy consists of using functions that deleted work to “clones of itself”.
  • The brute force strategy solves problems by inspecting all off the problem’s possible solution candidates.
  • The backtrack strategy involves rolling back the previous step and continuing the search. It works best in problems where the solution is a sequence of choices and making a choice restrains subsequent choices.
  • A heuristic (method) leads to a solution without guaranteeing it is the best or optimal one.
    • Greedy approach: the opposite of backtracking; it consist in never coming back to previous choices.
  • The divide and conquer strategy divides a problem over and over into subproblems, until the become easy enough to solve. The subproblem solutions are combined to obtain the original problem solution.
  • Dynaminc programming is identifying repeated subproblems in order to compute them only once.
    • Memoization allows the reuse of partial calculations.
  • Brand and bound strategies provide a solution in the form of a sequence of choices. It works by detecting and discarding bad choices.

4. Data

  • Abstractions are interfaces that let us omit details.
  • An Abstract Data Type (ADT) is the specification of a group of operations that make sense for a given data type.
  • Common abstractions
    • Primitive data types
    • Stack
    • Queue
    • Priority queue
    • List
    • Sorted list
    • Map
    • Set
  • Structures
    • Data structures describe how data is to be organized and accessed in the computer’s memory.
    • Array: the simplest way to store stuff in computer memory. It consists in allocation sequential space in the memory, and writing your data sequentially on that space.
    • Linked list: data is stored in a chain of cells that doesn’t need to be at sequential memory addresses. Memory for each cell is allocated as needed.
    • Double linked list
    • Tree: they are similar to lists, but are more suitable to hierarchical data.
    • Binary search tree: it’s a special type of tree that can be efficiently searched.
      • Red-black tree
      • AVL tree
      • B-tree
    • Binary heap: it’s a special type of search tree, in which we can find the smallest (or biggest) item instantly (\(O(1)\)), because it’s always the root node of the tree.
    • Graph: data is freely arranged as nodes and edges; it can represent almost any kind of data.
    • Hash table: it’s a data structure that allows finding items in \(O(1)\) time.

5. Algorithms

  • Sorting
    • Insertion sort: it’s very efficient at sorting near sorted datasets, regardless of size.
    • Quicksort and mergesort, both \(O(n \log n)\), are efficient for large datasets.
  • Searching
    • Binary search: \(O(\log n)\) search in arrays.
    • Hash table: \(O(1)\) search.
  • Graphs
    • They can be searched in two ways: DFS and BFS.
    • Depth-first search (DFS): we keep following edges, going deeper and deeper in the graph; when we reach a node that has no edges to any new nodes, we go back to the previous node and continue the process. We use a stack to keep track of the trail, pushing a node when we explore it, and popping a node when we need to go back.
    • Breadth-first search (BFS): it explores the graph per level, first the neighboors of your start node, then its neighboors’ neighboors, and so on. To keep track of nodes we visit, we use a queue: once we explore a node, we enqueue its children, then dequeue the next node to explore.
  • Operations research
    • It involes defining an objective to “maximize” or “minimize”.
    • Linear optimization problems are problems where the objective can be modeled using linear equations.
    • The simplex method solves an optimization problem with the input functions and the equations that model its constraints. Example:
      • Equation: z = 8x + 12y
      • Budget constraints: 10x + 20y <= 140
      • Space constraint: 6x + 8y <= 72
      • We can’t have negative items: x >=0, y >= 0