Notes on: A Common-Sense Guide to Data Structures and Algorithms — Jay Wengrow
(Second Edition) by Jay Wengrow
Disclaimer: This is my personal notes on what I’ve learned from a book written by Jay Wengrow: A Common-Sense Guide to Data Structures and Algorithms, Second Ed. Check the book here.
NOTES IN PROGRESS
My teacher recommended this book since it’s beginner-friendly. So, I started to read & learn from this book in June 2021 with a friend. We try to regularly study together and so far we’re still in chapter 9. Hopefully, we can finish the book and I can share my full-notes here. 😄
(Last update: 02 June 2022)
Contents
- Chapter 1 — Why data structures matter
- ✖️ Chapter 2 — Why Algorithms Matter
- ✖️ Chapter 3 — O Yes! Big O Notation
- ✖️ ️️Chapter 4 — Speeding Up Your Code with Big O
- ✖️ Chapter 5 — Optimizing Code with and Without Big O
- ✖️ ️️️️Chapter 6 — Optimizing for Optimistic Scenarios
- ✖️ Chapter 7 — Big O in Everyday Code
- ✖️ Chapter 8 — Blazing Fast Lookup with Hash Tables
- ✖️ Chapter 9 — Crafting Elegant Code with Stacks and Queues
- ✖️ Chapter 10 — Recursively Recurse with Recursion
- ✖️ Chapter 11 — Learning to Write in Recursive
- ✖️ Chapter 12 — Dynamic Programming
- ✖️ Chapter 13 — Recursive Algorithms for Speed
- ✖️ Chapter 14 — Node-Based Data Structures
- ✖️ Chapter 15 — Speeding Up All the Things with Binary Search Trees
- ✖️ Chapter 16 — Keeping Your Priorities Straight with Heaps
- ✖️ Chapter 17 — It Doesn’t Hurt to Trie
- ✖️ Chapter 18 — Connecting Everything with Graphs
- ✖️ Chapter 19 — Dealing with Space Constraints
- ✖️ Chapter 20 — Techniques for Code Optimization
Chapter 1 — Why data structures matter
27 June 2021
Data Structures
Code quality measurement: Maintainability
- Readability
- Organization
- Modularity (Modular Programming allows development to be divided by splitting down a program into smaller programs in order to execute a variety of tasks)
Code quality measurement: Efficiency
- How fast the code runs
Data Structures
- Data (all types of information; most basic: numbers & strings)
- Data structures (Data organization/arrangement)
- Code efficiency (fast/slow) depends on the structures of its data.
Measuring Speed
Measurements
- Not time, but #STEPS
Why #steps?
- Time makes the measurement undependable; the time will always change depending on the hardware it is run on.
- Steps are more reliable.
Illustration:
Let say we have a chunk of codes like this.
some_asean_countries = ["Indonesia", "Malaysia", "Singapore", "Brunei"]for x in some_asean_countries:
print(x)
Running the codes in a laptop from 2000s might need more time than running the same codes in a new laptop from 2022. However, the number of steps needed to run the codes will be the same. In our case, it will be four steps (#running print() function).
Time complexity
- The number of steps needed for an operation to run
- Synonyms: Speed, Efficiency, Performance, Runtime
Data Structures Operations
- READING: finding what value is contained at a certain location.
- SEARCHING: looking for the location of an existing value.
- INSERTION: adding a new value at a given location.
- DELETION: deleting a value at a certain location.
Notes: location ~ index
Array
Array
👉 List of data elements; duplicate values allowed
👉 Terms:
- Size (#elements in the array)
- Index (the position of an element within the array)
👉 Example (in Python)
some_asean_countries = ["Indonesia", "Malaysia", "Singapore", "Brunei"]size of some_asean_countries = 4
some_asean_countries[0] = "Indonesia"
some_asean_countries[2] = "Singapore"
Data Structures Operations in An Array
Assumption: #cells of the array = N.
’- 1) READING
👉 definition: To find what value is contained at a certain index in an array.
👉 max #steps to operate: 1.
👉 additional notes: it has the ability to jump to a specific index in an array in one step.
’- 2) SEARCHING
👉 definition: looking for the index of a certain value that exists inside an array.
👉 max #steps to operate: N.
👉 additional notes:
- the computer checks each cell one by one.
- the process starts from the beginning of the array.
’- 3) INSERTION
👉 definition: adding a new value within an array at a given index.
👉 max #steps to operate: N+1 (N steps to shift + 1 step to insert).
👉 additional notes:
- the process starts from the end of the array.
- the efficiency of the process depends on the new value’s location/index.
’- 4) DELETION
👉 definition: deleting a value at a certain index.
👉 max #steps to operate: N (1 step to delete + (N-1) steps to shift).
👉 additional notes: -
Sets
(Array-based) Sets
- Definition 👉 Similar to array; ⛔️ NO duplicate values allowed
- Useful to store data with no duplication.
- Example (in Python)👉
some_cities_indonesia = {"Medan", "Jakarta", "Bandung"}Notes:
In Python, if we have a set with some duplicate values, automatically, only unique values will be stored inside the set.
Data Structures Operations in An Array
Assumption: #cells of the array = N.
’- 1) READING
👉 max #steps to operate: 1.
’- 2) SEARCHING
👉 max #steps to operate: N.
’- 3) INSERTION
👉 max #steps to operate: 2N+1 (N steps to search + N steps to shift + 1 step to insert).
’- 4) DELETION
👉 max #steps to operate: N.
Chapter 2 — Why Algorithms Matter
30 June 2021
Chapter 3 — O Yes! Big O Notation
05 July 2021
Chapter 4 — Speeding Up Your Code with Big O
13–15 July 2021
Chapter 5 — Optimizing Code with and Without Big O
22 July 2021
Chapter 6 — Optimizing for Optimistic Scenarios
02 - 05 August 2021
Chapter 7 — Big O in Everyday Code
09 August 2021
Chapter 8 — Blazing Fast Lookup with Hash Tables
12 Aug 2021
Chapter 9 — Crafting Elegant Code with Stacks and Queues
09 December 2021
