Book Club: Grokking Algorithms. 7: Where to go next and Final Discussion
Tags: books, algorithms, bookclub, discuss
Published: 2023-10-12 08:58:09

---
title: Book Club: Grokking Algorithms. 7: Where to go next and Final Discussion
published: true
description: Book Club discussion for Grokking Algorithms by Aditya Y. Bhargava
tags: [books, algorithms, bookclub, discuss]
series: ["book club Grokking Algorithms"]
---

#### **Grokking Algorithms** An _illustrated_ guide for programmers and other curious people, by Aditya Y. Bhargava

-----

## Chapter 11: Where to go next

If you read this chapter, please go ahead and discuss what you thought in the comments! 

:memo: This is the last chapter in the book, and is a summary of 10 algorithms for further optional reading. You can read my notes below.

-----

## Where to go Next

key topics covered: `suggestions`, `binary search tree`, `The Fourier Transform`, `Parallel algorithms`, `MapReduce`, `Bloom Filters`, `HyperLogLog`, `SHA`, `Diffie-Hellman`, `key exchange`, `locality-sensitive`, `hashing`, `linear programming`

### Binary Search Tree

_Good for learning about `databases` and `data structures`_

A _binary search tree_ is faster for insertions and deletions than a sorted array in average, because a _binary search tree_ allows you to find or insert in a more granular but sorted way. They *don't* allow random access, and the good performance times are based on a balanced tree (too many nodes on one side will be imbalanced, and performance will be affected - _red-black trees_ are self-balancing so that might be a good option).

![What is and isn't a binary search tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7b7or8o57jyhteyadybz.png)
<figcaption><sup>copyright Manning Publications, drawn by adit.io</sup></figcaption>


### Inverted Indexes

_Good for learning about `search`_

This data structur is a hash that maps words to places where they appear, and is commonly used in search engines.

### The Fourier Transform

_Good for `compression` and `format`s like MP3 or JPG, and `music tech`_

This algorithm can take a digital music signal & break it into individual frequencies so that the file can be reduced (like in MP3) or frequecies can be boosted or reduced in music production. It also works for images in the same way, and can be used in applications like earthquake prediction and DNA analysis, with those digital signals.

### Parallel algorithms

_Good for speed optimisation_

These allow you to spread work out in parallel so that it can be completed sooner. But they're hard to design, test, and predict the cost benefit of as the time gains aren't linear.

### MapReduce

_Good for speed and load balancing_

This is a popular _distributed algorithm_ (a subtype of parralel algorithm). Distributed algos are useful when you have a lot of work to do as they will cut out a lot of time to do it by spreading work across multiple machines. an example is Apache Hadoop.

### Bloom filters

_Good for quick approximations_

These are _probabilistic data structures_ (they give you a likely correct answer but it could be a false positive). This is an alternative to a `hash` (which will give you the correct answer) but for a large hash index might not be practical, and a `bloom filter` approximation might be good enough.

### HyperLogLog

_Good for quick approximations_

A similar _probabilistic algorithm_ that approximates the number of unique elements in a set.

### SHA algorithms

_Good for unbiased comparison_
This is a _secure hash algorithm_ (a `SHA` is a hash function, which generates a string in this context called a `hash`). Unlike has functions which goes from (e.g.) string to array index, SHA goes from string to string. You can use the SHA to tell if objects, files or strings (like passwords) are the same without revealing the original content. [note: this is not the gold-standard for password-hashing]

### Localilty-sensitive hashing

_Good for biased comparison_

SHA is locality insensitive - similar starting strings will not have similar hashes. A locality-sensitive hash such as `Simhash` will generate a string that is similarly represented so that you can compare two hashes for similarity of content - e.g. for plagiarism checks.

### Diffie-Hellman key exchange

_Good for cryptography_

The _Diffie-Hellman algorithm_ is used for message encryption. It has a public key for sharing which is used to encrypt a message, and a private key which can decode the message and is 'owned' by one person. It's hard to decode without the private key and the cipher does not need to be communicated so it is still used in practise alongside RSA.

### Linear programming

_Good for optimization_
Graph algorithms in the book are a subset of _linear programming_, which uses the complex _Simplex algorithm_.

-----

## Discussion for this chapter

0. Are there any algorithms you're going to investigate that aren't recommended in this list or in the book?
0. Have you used any of these 10 algorithms? Or, did you consider any of these but opted for a different algorithm instead?

## Discussion for the entire book

Please visit the [discussion questions](https://dev.to/ruthmoog/book-club-grokking-algorithms-2-2pe6) post to reflect on the book, and add your answers to the comments along wit any of your own questions or reflections you have.