Skip to content

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

Notifications You must be signed in to change notification settings

hishamcse/Algorithms-Princeton-Combined

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 

Repository files navigation

Algorithms-Princeton

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

Overview of Implemented Codes:

[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]

Part I

Week 1

UNION FIND:

  • Quick Find
  • Quick Union
  • Weighted Quick Union
  • Weighted Quick Union With Path Compression

Analysis Of Algorithms:

  • ThreeSum Problem

Assignment:

Percolation

Quiz:

Interview Questions

Week 2

Stacks and Queues:

  • Stacks
  • FixedCapacityStackOfStrings
  • ResizingArrayStackOfStrings
  • LinkedStackOfStrings
  • LinkedStackIterable
  • ResizingArrayQueueOfStrings
  • LinkedQueueOfStrings
  • ArrayQueueIterable
  • Dijkstra Algorithm
  • Parenthesis Problem

Elementary Sorts:

  • Selection Sort
  • Insertion Sort
  • Shell Sort
  • Shuffle
  • SortingUsingCustomDatatype
  • Some Visualization Code

Assignment:

Queues

Quiz:

Interview Questions

Week 3

Merge Sort:

  • Merge Sort
  • BottomUp Merge Sort
  • MergeSort Performance Improvement

Quick Sort:

  • Quick Sort
  • QuickSort Improvement
  • QuickSort Space Improvement
  • Randomized QuickSort
  • QuickSelect
  • Dihkstra3wayPartition For DuplicateKeys
  • Dihkstra3wayPartition For Randomized QuickSort
  • BentleyMcIlroy3wayPartition
  • KedallTau Distance
  • YaroslavskiyDualPivot Quicksort

Extra Credit:

  • Convex Hull
  • CountSort

Assignment:

Collinear Points

Additional Assignment:

Autocomplete

Quiz:

Interview Questions

Week 4

Priority Queues:

  • UnorderedArray Implementation
  • OrderedArray Implementation
  • MINPQBinaryHeap
  • MAXPQBinaryHeap
  • HeapSort

Elementary Symbol Tables:

  • Elementary Efficient Implementation
  • FrequencyCounter
  • Binary Search Tree

Extra Credit:

  • Time Driven Simulation
  • Event Driven Simulation
  • CubeSum
  • EquationSolve
  • PowerNumber

Assignment:

Slider Puzzle(Using A* search)

Assignment Enrichment:

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.

Quiz:

Interview Questions

Week 5

Balanced Search Trees:

  • RedBlackBST
  • RandomizedBST
  • MemoryOfBST
  • Merge Of Two RandomizedBST to one RandomizedBST
  • BTree
  • AVLTreeST
  • SplayTreeST

Geometric Applications of BST:

  • RangeSearch for BST and RedBlackBST
  • IntervalSearchfor1D
  • IntervalSearchTree
  • IntervalSearchfor2D
  • LineSegment Intersection
  • Rectangle Intersection(VLSI)

Assignment:

KDTree

Quiz:

Interview Questions

Week 6

Hash Table:

  • SeparateChainingHashST
  • LinearProbingHashST

Searching Applications:

  • ExceptionFilterUsingSET
  • FileIndex finding
  • LookUpCSV
  • Concordance(Book Index)
  • Sparse Vector
  • Sparse Matrix

Quiz:

Interview Questions


Part II

Week 1

UNDIRECTED GRAPHS:

  • 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 GRAPHS:

  • 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

Assignment:

Wordnet

Quiz:

Interview Questions

Week 2

Minimum Spanning Tree:

  • 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)

Shortest Paths:

  • 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

Assignment:

Seam Carving

Quiz:

Interview Questions

Week 3

MaxFlow Mincut:

  • 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

Radix Sort:

  • Key Indexed Counting
  • LSD Sort
  • MSD Sort
  • Quick 3 Way Radix Sort
  • American Flag Sort
  • Longest Common Prefix
  • Two Sum

Suffix Arrays:

  • 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

Assignment:

Baseball Elimination

Quiz:

Interview Questions

Week 4

Trie:

  • R-Way Trie
  • Ternary Search Trie.
  • Suffix Tree
  • Patricia Trie/Radix tree
  • Prefix Free Code
  • Spell Checker
  • T9 Texting

SubString Search:

  • 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

Assignment:

Boggle

Quiz:

Interview Questions

Week 5

Regular Expression:

  • 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

Data Compression:

  • 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

Assignment:

Burrows-Wheeler

Quiz:

Interview Questions

Week 6

Reduction:

  • Bipartite Matching
  • Bipartite Matching using MaxFlow
  • Bipartite Matching (Hopcroft Algorithm)
  • Longest Path
  • Convex Hull
  • Three Sum using Four Sum
  • Three Linear using Three Sum

Linear Programming:

  • Simplex Algorithm
  • TwoPhase Simplex Algorithm
  • Assignment Problem using LP
  • Hangarian Algorithm
  • Two Person ZeroSum Game

Intractibility / NP:

  • Hamiltonian Path
  • Hamiltonian Path at Directed Acyclic Graph

Quiz:

Interview Questions

Xtra_Advanced Concepts

Extra Codes:

  • Assignment Problem Using Bitmask
  • BinaryCounter
  • Euler Conjecture
  • Karatsuba Multiplication
  • Subset Sum
  • Traveling Salesman Problem

For various Puzzle Solvers,you can visit my another repository Puzzle Solver

I will be updating the repository whenever I will implement something new related to these courses

About

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

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published