DATA STRUCTURES AND ALGORITHMS 🧮

PURPOSE

This repository is a collection of data structures and algorithms implemented in Python and JavaScript. It's my personal collection of data structures and algorithms written in Python and JavaScript. I will be updating this repository in the future to include interpretations of the algorithms in other languages.

TABLE OF CONTENTS

• Big O Complexity
• What is an Algorithm?
• What is a Data Structure?
• Algorithms
  • Search Algorithms
  • Binary Search
  • Breadth-First Search
  • Sort Algorithms
    • Bubble Sort
    • Counting Sort
    • Insertion Sort
    • Merge Sort
    • Quick Sort
    • Radix Sort
    • Selection Sort
• Data Structures
  • Cache
    • Least Recently Used
    • Ring Buffer
  • Filters
    • Bloom Filter
  • Graph 🚧 Under Construction 🚧
  • Hash Tables 🚧 Under Construction 🚧
  • Heap
    • Max Binary Heap
    • Priority Queue
  • Linked List
    • Singly-Linked List
    • Doubly-Linked List
  • Queue
  • Stack
  • Tree
    • Binary Search Tree
      • Breadth-First Search
      • Depth-First Search Pre-Order
      • Depth-First Search Post-Order
      • Depth-First Seach In-Order
  • Trie
• Author
• Acknowledgements

BIG O COMPLEXITY

Big O notation helps us evaluate decisions between multiple implementations of the same function. It helps us decide, "Which way is best?"

It allows us to talk formally about how the runtime of an algorithm grows as the inputs grow. We don't care about the details, only the broad trends. When we talk about Big O, we're typically talking about the worst case scenario runtime for the algorithm.

For instance, here's a function called addUpTo() with a runtime of O(1):

def add_up_to(num):
  return ((num * (num + 1)) / 2)

This is because the num is a constant. No matter how big the number, it will always take the same amount of complexity to run the function.

There are two variations of Big O:

1. Time Complexity
2. Space Complexity

Time Complexity is used to measure the efficienty of operations in the code, while Space Complexity is used to indicate the amount of memory efficiency the code has.

Here's a graph that compares various common Big O curves:

WHAT IS AN ALGORITHM?

An "algorithm is an unambiguous specification of how to solve a class of problems. Algorithms can perform calculation, data processing, and automated reasoning tasks." In this respect, algorithms govern much of what computer scientists, data scientists, and machine learning scientists do, as the algorithms built define and interpret the data needing to be parsed or calculated.

WHAT IS A DATA STRUCTURE?

A data structure "allows data organization, management, and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationship among them, and the functions or operations that can be applied to the data."

Author

• Nathan Thomas

ACKNOWLEDGEMENTS

• Thanks Beej Jorgenson for being a boss of a computer science instructor at Lambda School. You make things simple, easy, and understandable. That's the highest praise I could ever give someone teaching a complicated topic like CS.
• Thank you to Brad Fukumoto. You're so knowledgeable, but you're also super approachable as a teacher; your passion for teaching shines through. Also, you have boss-level hobbies.
• To Sean Chen, your skills are honestly off-the-rails. I have learned so much from watching you work. Thank you!
• To Brian Doyle, thanks for being a friendly and knowledgeable CS instructor. You came in at the hardest point of CS and somehow made it great. Thank you!
• Huge thanks to Byron Homes for getting me excited about data structures and algorithms. You're awesome and a genius.
• Thanks to Frank Faustino for inspiring me to create, build, and make my own data structures and algorithms repository. Your own journey has inspired my own.
• Thanks to Aditya Bhargava, the author of Grokking Algorithms. You inspired me to learn this stuff and start documenting it for ease of later use.
• Thanks to bigocheatsheet.com for your useful descriptions of Big O Notation and graphs that I have used in this README.