References

Author: Jacob Park

Fundamental Data Structures and Algorithms

Data Structures

List of Data Structures

• Arrays
• Linked List
• Stack
• Queue
• Hash Table
• Binary Search Tree
• Priority Queue
• Set
• Graph

Algorithms

List of Algorithms

• Sorting Algorithms
  • Insertion Sort
  • Merge Sort
  • Quick Sort
  • Counting Sort
  • Radix Sort
  • Timsort
• Linear Search Algorithm
• Binary Search Algorithm
• Divide-and-Conquer Algorithm
• Greedy Algorithm
• Dynamic Programming
• Backtracking
  • Branch and Bound Technique
  • Best-First Search Technique
  • Iterative Deepening Technique
• Range Query
  • Fenwick Tree
  • Segment Tree
• Tree Algorithms
  • Tree Traversal
  • Lowest Common Ancestor
  • Prefix Tree
  • Suffix Tree
  • Threading
• Graph Algorithms
  • Graph Traversal
  • Bellman-Ford Algorithm: Shortest Path (All Weights)
  • Dijkstra's Algorithm: Shortest Path (Positive Weights)
  • Floyd-Warshall Algorithm: All-Pairs Shortest Paths
  • Topological Sort
  • Kruskal's Algorithm: Minimum Spanning Tree
    • Disjoint Set
  • Kosaraju's Algorithm: Strongly Connected Components
  • Hierholzer's Algorithm: Eulerian Path
  • Ford-Fulkerson Algorithm: Maximum Flow
• Optimizations
  • Bit Masks
  • Square Root Sized Blocks
  • Two Pointers

Advanced Topics in Data Structures and Algorithms

Hashing

• Hash Function
• Hash Table
  • Chaining
  • Open Addressing
  • Cuckoo Hashing
• Universal Hashing
• Locality-Sensitive Hashing
• Consistent Hashing
• MurmurHash
• MinHash
• Merkle Tree
• Survey: Hashing Techniques: A Survey and Taxonomy

  Chi, Lianhua, and Xingquan Zhu. "Hashing techniques: A survey and taxonomy." ACM Computing Surveys (CSUR) 50.1 (2017): 11.

Probabilistic Data Structures / Randomized Algorithms

• Bloom Filter: Approximate Set Membership
• Count-Min Sketch: Approximate Frequency Counting
• HyperLogLog: Approximate Set Cardinality
• Reservoir Sampling: $k$-Sampling without Replacement
• Treap: Randomized Binary Search Tree

Succinct Data Structures

• Succinct Data Structures
• Left-Child Right-Sibling Binary Tree
• Interface: Parallel Implementation of Tree Skeletons

  Skillicorn, David B. "Parallel implementation of tree skeletons." Journal of Parallel and Distributed Computing 39.2 (1996): 115-125.

• Implementation: Practical Implementation of Rank and Select Queries

  González, Rodrigo, et al. "Practical implementation of rank and select queries." Poster Proc. Volume of 4th Workshop on Efficient and Experimental Algorithms (WEA). 2005.

Concurrency

Basic Synchronization Patterns

• Barrier
• Lightswitch
• Mutex
• Message Queue
• Multiplex
• Producer-Consumer
• Reader-Writer
• Rendezvous
• Reusable Barrier
• Semaphore
• Turnstile

Advanced Synchronization Patterns

• Banker's Algorithm
• Conflict-Free Replicated Data Type
• Copy-On-Write
• Distributed Transaction
• Exponential Backoff
• Primitive Atomic Instructions
• Memory Barrier
• Multi-Version Concurrency Control
• Non-Blocking Algorithm
• Optimistic Concurrency Control
• Pipeline Stall
• Software Transactional Memory
• Spin Lock
• Thread-Local Storage
• Ticket Lock
• Timestamp-Based Concurrency Control
• Vector Clock
• Wait-For-Graph

Communication Patterns

• Channel
• Distributed Object
• Inter-Process Communication
• Message Passing
• Shared Memory
• Signal

Execution Models

• Actors
• Async/Await
• Coroutine
• Fibers
• Futures and Promises
• Interrupt
• Light-Weight Processes
• Processes
• SIMD
• Threads

Concurrency Issues

• Blocking
• Cache Coherence
• Context Switch
• Deadlock
• Livelock
• Lock Convoy
• Preemption
• Priority Inversion
• Race Condition
• Contention
• Starvation
• Thread Safety
• Thundering Herd

Object-Oriented Design Patterns

SOLID Principles

• Single Responsibility Principle
• Open-Closed Principle
• Liskov Substitution Principle
• Interface Segregation Principle
• Dependency Inversion Principle

Creational Patterns

• Abstract Factory Pattern
• Builder Pattern
• Factory Method Pattern
• Prototype Pattern
• Singleton Pattern

Structural Patterns

• Adapter Pattern
• Bridge Pattern
• Composite Pattern
• Decorator Pattern
• Facade Pattern
• Flyweight Pattern
• Proxy Pattern

Behavioral Patterns

• Chain of Responsibility Pattern
• Command Pattern
• Interpreter Pattern
• Iterator Pattern
• Mediator Pattern
• Memento Pattern
• Observer Pattern
• State Pattern
• Strategy Pattern
• Template Method Pattern
• Visitor Pattern

Functional Design Patterns

• Higher-Order Function
  • Fold
  • Map
  • Filter
• Composition
• Currying
• Recursion
  • Tail Recursion
  • Structural Recursion
• Lazy Evaluation
• Pattern Matching
• Algebraic Data Type
• Monoid
• Monad
  • I/O
  • State
• Applicative Functor
• Arrow
• Zipper
• Lenses

Enterprise Integration Patterns

Channel Patterns

• Message Channel
• Point-to-Point Channel
• Publish-Subscribe Channel
• Datatype Channel
• Invalid Message Channel
• Dead Letter Channel
• Guaranteed Delivery
• Channel Adapter
• Messaging Bridge
• Message Bus

Message Construction Patterns

• Message
• Command Message
• Document Message
• Event Message
• Request Reply
• Return Address
• Correlation Identifier
• Message Sequence
• Message Expiration
• Format Indicator

Routing Patterns

• Pipes and Filters
• Message Router
• Content-Based Router
• Message Filter
• Dynamic Router
• Recipient List
• Splitter
• Aggregator
• Resequencer
• Composed Message Processor
• Scatter-Gather
• Routing Slip
• Process Manager
• Message Broker

Transformation Patterns

• Message Translator
• Envelope Wrapper
• Content Enricher
• Content Filter
• Claim Check
• Normalizer
• Canonical Data Model

Endpoint Patterns

• Message Endpoint
• Messaging Gateway
• Messaging Mapper
• Transactional Client
• Polling Consumer
• Event-Driven Consumer
• Competing Consumers
• Message Dispatcher
• Selective Consumer
• Durable Subscriber
• Idempotent Receiver
• Service Activator

System Management Patterns

• Control Bus
• Detour
• Wire Tap
• Message History
• Message Store
• Smart Proxy
• Test Message
• Channel Purger

Links

• Awwwards
• Brendan Gregg's Performance Analysis
• CSS Tricks
• Developer Roadmaps
• Green Tea Press: Free Books
• Laws of UX
• Ops School Curriculum
• System Design Primer
• The Architecture of Open Source Applications