This repository contains all the algorithms implementation & problems solution, assignment solution, Interview question solution & other related materials(Slides,Resources) related to Princeton University algorithms Part I & II course at COURSERA
Course 1 Link : Algorithms Part I
Course 2 Link : Algorithms Part II
Princeton University Course : Princeton Algorithms
Booksite Link : Booksite
[NB: There are a lot of extra implementations and problems in the booksite]
[NB: Beside my solution, I have added two web solution url(Collected from github) for all interview questions at the respective week's quiz directory]
- Quick Find
- Quick Union
- Weighted Quick Union
- Weighted Quick Union With Path Compression
- ThreeSum Problem
- Stacks
- FixedCapacityStackOfStrings
- ResizingArrayStackOfStrings
- LinkedStackOfStrings
- LinkedStackIterable
- ResizingArrayQueueOfStrings
- LinkedQueueOfStrings
- ArrayQueueIterable
- Dijkstra Algorithm
- Parenthesis Problem
- Selection Sort
- Insertion Sort
- Shell Sort
- Shuffle
- SortingUsingCustomDatatype
- Some Visualization Code
- Merge Sort
- BottomUp Merge Sort
- MergeSort Performance Improvement
- Quick Sort
- QuickSort Improvement
- QuickSort Space Improvement
- Randomized QuickSort
- QuickSelect
- Dihkstra3wayPartition For DuplicateKeys
- Dihkstra3wayPartition For Randomized QuickSort
- BentleyMcIlroy3wayPartition
- KedallTau Distance
- YaroslavskiyDualPivot Quicksort
- Convex Hull
- CountSort
- UnorderedArray Implementation
- OrderedArray Implementation
- MINPQBinaryHeap
- MAXPQBinaryHeap
- HeapSort
- Elementary Efficient Implementation
- FrequencyCounter
- Binary Search Tree
- Time Driven Simulation
- Event Driven Simulation
- CubeSum
- EquationSolve
- PowerNumber
Slider Puzzle(Using A* search)
Slider puzzle can be solved using IDA* algorithm which is much faster.Though I haven't implemented it yet.But I have added some resources.
- RedBlackBST
- RandomizedBST
- MemoryOfBST
- Merge Of Two RandomizedBST to one RandomizedBST
- BTree
- AVLTreeST
- SplayTreeST
- RangeSearch for BST and RedBlackBST
- IntervalSearchfor1D
- IntervalSearchTree
- IntervalSearchfor2D
- LineSegment Intersection
- Rectangle Intersection(VLSI)
- SeparateChainingHashST
- LinearProbingHashST
- ExceptionFilterUsingSET
- FileIndex finding
- LookUpCSV
- Concordance(Book Index)
- Sparse Vector
- Sparse Matrix
- Graph
- Adjoint Matrix Graph
- Graph Client
- Graph Measurement(Diameter,Center,Radius etc..)
- Depth First Search
- Depth First Path
- Breadth First Path
- All Paths
- Connected Component
- Cycle
- Bipartite
- Bridge
- BiConnected or Articulation Vertices
- Symbol Graph
- Degrees of Separation
- Bacon Histogram
- Eulerian Cycle
- Eulerian Path
- Index SET
- Maze Game
- Word Ladder
- Weiner Index
- Directed Graph
- Adjoint Matrix Directed Graph
- Directed Depth First Search
- Directed Depth First Path
- Directed Breadth First Path
- Directed Cycle
- Depth First Order
- Topological Sort
- Directed Eulerian Cycle
- Directed Eulerian Path
- Shortest Directed Cycle
- Brute-force strong components algorithm
- Strongly Connected Component (Kosaraju Sharir Algorithm)
- Tarjan's strong components algorithm
- Gabow's strong components algorithm
- Hamiltonian Path at Directed Acyclic Graph
- Kernel DAG
- Reachable Vertex
- Transitive Closure
- Warshall's transitive closure algorithm
- Symbol Directed Graph
- Bare Bones Web Crawler
- Undirected Edge
- EdgeWeighted Graph
- Prim's MST Algorithm (Lazy Implementation)
- Prim's MST Algorithm (Eager Implementation)
- Kruskal MST Algorithm
- Boruvka MST Algorithm
- Edge in MST
- Minimum bottleneck spanning tree
- Minimum median spanning tree
- Minimum Weight Edge Feedback Set (using Prim Algorithm)
- Minimum Weight Edge Feedback Set (using Kruskal Algorithm)
- Single Link Clustering
- Single Link Clustering (using Prim Algorithm)
- Directed Edge
- EdgeWeighted Directed Graph
- Dijkstra Undirected Shortest Path Algorithm
- Dijkstra Shortest Path Algorithm (Lazy Version)
- Dijkstra Shortest Path Algorithm (Eager Version)
- ACyclic Shortest Path
- ACyclic Longest Path
- EdgeWeighted Directed Cycle
- BellMan Ford Shortest Path Algorithm
- FloydMarshall All Pairs Shortest Path
- Fattest Path
- Monotonic Shortest Path
- Second Shortest Path
- Skippable Edge
- Parallel precedence-constrained job scheduling problem (Critical path method)
- Arbitrage Detection
- Flow Edge
- Flow Network
- Ford Fulkerson Algorithm
- Fattest Path (using Ford Fulkerson Algorithm)
- Bipartite Matching
- Bipartite Matching using MaxFlow
- Bipartite Matching (Hopcroft Algorithm)
- Perfect Matching for K Bipartite
- Global MinCut (Stoer-Wagner's algorithm)
- Maximum Weight Closure
- Key Indexed Counting
- LSD Sort
- MSD Sort
- Quick 3 Way Radix Sort
- American Flag Sort
- Longest Common Prefix
- Two Sum
- Suffix Array
- Suffix Array using 3 Way Quick Sort
- Manber's algorithm
- Kasai's algorithm
- Keyword in context (KWIC)
- Longest repeated substring
- Longest common substring
- Cyclic Rotation
- R-Way Trie
- Ternary Search Trie.
- Suffix Tree
- Patricia Trie/Radix tree
- Prefix Free Code
- Spell Checker
- T9 Texting
- Brute Force String Search
- Rabin-Karp Algorithm
- Knuth-Morris-Pratt algorithm
- Knuth-Morris-Pratt algorithm (Improved Version)
- Boyer-Moore Algorithm
- Longest Pallindrome (Linearithmic Algorithm)
- Longest Pallindrome (Manacher's Algorithm)
- Cyclic Rotation
- Tandem Repeat
- Screen Scraping
- Regex Practice(3 files)
- Challenging Regex Finder
- NFA
- Extended NFA
- Exponential Size DFA
- GREP
- Harvester
- Crossword Puzzle
- Comment Stripper( for C++ and Java code)
- Tokenizer
- Binary DUMP
- Hex DUMP
- Picture DUMP
- Genome (Fixed Length Encoding & Decoding)
- RunLength (Run Length Encoding & Decoding)
- Huffman Compression Algorithm (Binary Version)
- Huffman Compression Algorithm (Ternary Version)
- LZW(Lempel–Ziv–Welch) Compression Algorithm
- MoveToFront Compression Algorithm
- Bipartite Matching
- Bipartite Matching using MaxFlow
- Bipartite Matching (Hopcroft Algorithm)
- Longest Path
- Convex Hull
- Three Sum using Four Sum
- Three Linear using Three Sum
- Simplex Algorithm
- TwoPhase Simplex Algorithm
- Assignment Problem using LP
- Hangarian Algorithm
- Two Person ZeroSum Game
- Hamiltonian Path
- Hamiltonian Path at Directed Acyclic Graph
- Assignment Problem Using Bitmask
- BinaryCounter
- Euler Conjecture
- Karatsuba Multiplication
- Subset Sum
- Traveling Salesman Problem