# Data Structures and Algorithms Guide

## Array

### Problems

two sum

search index

kth largest element in array

### Concepts

2d arrays

nd arrays

jagged array

## Linked list

Operations

Insert

Delete

Find

Reverse

counting

finding middle

merging

kth to last note

detecting cycles

## Stack

Towers of Hanoi

## Queue

LIFO

FIFO

## Tree

### Concepts

root

edge

leaf

depth

### Binary Tree

#### Binary Search Trees

##### Problems

level order traversalre

construct tree from traversal

### Balanced tree

AVL Tree

b-tree

### Operations

Insertion

Deletion

Traversal

Pre order

in order

post order

Search

Breadth First Search

Depth First Search

find min/max

find successor predecessor

## Hash table

### Implementations

Array

Linked List

Binary Tree

Operations

get

put

delete

Hash Function

Linear Probing

Quadratic Probing

Collision Resolution

### Problems

lru cache

## Heap

### Priority queue

heap

Compare function

enqueue

dequeue

peek

### Concepts

complete binary tree

priority queue

array representation

Min Heap

Max Heap

### Operations

build

insert

get

delete

heapify

heap sort in place

### Problems

merge k sorted lists

kth largest element in array

the skyline problem

## Trie

compressed trie

suffix trie

## Advanced data structures

skip list

suffix tree

suffix array

bloom filter

## Sorting

insertion sort

merge sort

quick sort

radix sort

sort stability

counting sort

### Problems

dutch national flag

merge two sorted arrays

## Graph

### Concepts

Graph theory

Pathfinding

Connectivity

Shortest Path

Minimum Spanning Tree

Cycles

disjoint graph

### Operations

Traversal

Breadth First Search

Depth First Search

bipartite graph

topological sort

djikstra’s algorithm

bellman-ford

Floyd-Warshall algorithm

Prim’s algorithm

Kruskal’s algorithm

### Graph Representations

adjacency list

adjacency matrix

## Recursion

### Concepts

Backtracking

Base Case

Recursive Case

Inductive Step

Tail Recursion

Memoization

### Problems

recursive factorial

recursive exponent

subsets of size n

fibonacci numbers

pascals triangle

towers of hanoi

combinatorial enumeration of binary strings

letter case permutations

subsets 1

permutations 1

permutations 2

subset sum

generate parenthesis

n queens

subarray sum equals k

valid parentesis

## String Algorithms

### Concepts

String matching

Pattern matching

String search

Data compression

Edit distance

Substring search

String similarity measures

### Operations

rabin karp

kmp knuth morris pratt

### Problems

non repeating characters

anagram

palindrome

frequency counting

reverse

## Dynamic Programming

### Problems

0/1 knapsack

longest common subsequence

subset sum

mimimum edit distance

minimum numbers of coins

longest increasing subsequence

longest palindromic subsequence

text justification

## Computational Geometry

## Network Flow Algorithms

network flow

maximum flow

minimum cut

Ford–Fulkerson

Edmonds–Karp

Dinic’s algorithm

König’s theorem

## NP-Complete

### Approximation

Simulated annealing

Tabu search

Genetic algorithms

Ant colony optimization

Particle swarm optimization

Cross-entropy method

### Examples of NP Problems

Set Cover

Knapsack

Bin Packing

Shortest Path

Maximum Flow

Minimum Cut

Vertex Cover

Hamiltonian Path

Traveling Salesman

Satisfiability Problem

Partition Problem

Clique Problem

Chromatic Number Problem

## Search

linear search

binary search

Depth-first search

Breadth-first search

Best-first search

A* search

Dijkstra’s algorithm

Bellman-Ford algorithm

Floyd-Warshall algorithm

Johnson’s algorithm

## Algorithm Design

Greedy algorithms

Dynamic programming

Divide and conquer

decrease and conquer

transform and conquer

Randomized algorithms

## Algorithm Analysis

Harmonic series

aritmetic geometric series

### Time Complexity

big-O notation

Omega notation

Theta notation

little-o notation

arithmetic series

harmonic series

arthmetic geometric series

### Space Complexity

{{embed website-outro}}