Data Structures	Algorithms

Data Structures

Linear Data Structure

[1] LinkedList
LinkedList Implementation

[2] Queue
Queue Implementation

[3] Stack
Stack Implementation

Tree

Tree Traveral
二叉树遍历

[1] Threaded binary tree

[2] Tries

[Tries (also known as radix trees or prefix trees)] REF. geeksforgeeks
Tries, code

[3] Segment Tree

[4] Splay Tree

Splay Tree

Heap

Graph

Graph and its representations
Why is the complexity of DFS of adjacency lists is O(V+E)

[1] Minimum Spanning Tree (MST)

[2] Shortest Path

Dijkstra’s – Shortest Path Algorithm (SPT) – Adjacency Matrix – Java Implementation

[3] Detect Cycle in an Undirected Graph

[4] Topological Sorting

[5] Others

Articulation Points (or Cut Vertices) in a Graph
Bridges in a graph
[Connected Components in an undirected graph] REF. geeksforgeeks Code

Algorithms

Backtracking

Backtracking is an approach to solving constraint-satisfaction problems without trying all possibilities

Dynamic Programming

How should I explain dynamic programming to a 4-year-old?

Dynamic Programming Methods.pdf
overlapping sub-problems and optimal substructure
Rrecurrence Relation: f(k)=max(f(k–2)+Ak,f(k–1)) 198. House Robber
Memoization vs Tabulation
Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work?

Greedy

45. Jump Game II

Search Algorithm

Linear Search, Binary Search Tree and Hash Table

Binary Search

String:

[1] Sliding Window:

Linear-time & constant-time(rolling hash || bitmasks)

[2] Palindromic:

Manacher’s Algorithm

[3] Longest Common Prefix:

Horizontal scanning, Vertical scanning, Divide and conquer, Binary search, Prefix trie.

[4] Substring search algorithms
KMP and Rabin-Karp

Array

[1] Permutations

Sorting Methods

Sorting_algorithm wiki

Data Structures & Algorithms