wuihee/data-structures-and-algorithms

Data structures and algorithms.

Data Structures & Algorithms

My Python implementation of data structures and algorithms. Work in progress.

Data Structures

Implementations

• Dynamic Array
• Stack
• Queue
• Doubly Linked List
• Priority Queue
• Union Find
• Binary Search Tree
• Trie
• Hash Table (Separate Chaining)
• Hash Table (Open Addressing)

Priority Queue

• Heap Sort

Programming Paradigm

Divide and Conquer

• Binary Search
• Maximum Sub-Array
• Merge Sort
• Quicksort (2-Way Partition)
• Quicksort (3-Way Partition)

Greedy

• Fractional Knapsack
• Interval Scheduling
• Job Sequencing
• Optimal Merge Pattern
• Huffman Coding
• Longest Increasing Subsequence with Binary Search

Backtracking

• Knight's Tour
• N-Queens
• Sum of Subsets
• Rat in a Maze

Dynamic Programming

Classic Problems

• Rod Cutting Problem
• 0-1 Knapsack
• Longest Common Subsequence
• Longest Increasing Subsequence
• Edit Distance

Min. / Max. Way to Reach a Path

• Minimum Path Sum
• Coin Change
• Triangle
• Dungeon Game
• Maximal Square
• Perfect Squares
• Ones and Zeros
• 2 Key Keyboard
• Minimum Refuels

Distinct Ways

• Target Sum
• Out of Boundary Paths
• Domino and Tromino Tiling

Graph Theory

Basics

• Depth-First Search
• Khan's Topological Sort
• Strongly Connected Components

Single-Source Shortest Path (SSSP)

• Dijkstra's
• Bellman-Ford

All-Pairs Shortest Path (APSP)

• Floyd Warshall

Math

Basic Algorithms

• Euclidean GCD

Factorization

• Naive Factorization
• Pollard's Rho Algorithm

Fibonacci

• Pisano Period

Primality Testing

• Sieve of Eratosthenes

Miscellaneous

• Sliding Window
• Two Pointers