By: Sarfraz Raza
TAs: Kashmal, Shuja and Sara
(Images taken from Jeff Erickson Algorithms...!!!)
Other related courses:
ITC: https://sites.google.com/view/itc-ucp-2017
PF/OOP: https://sites.google.com/view/pf-ucp-2018/
DSA: https://sites.google.com/view/dsa-ucp2017/home
DS: https://sites.google.com/view/ds-ucp-2017/home
Algo-2019: https://sites.google.com/view/algo-ucp-2019
Geometric Sequence (logarithm function)
Prune and Search
Geometric Series - Proof of 1+2+4+8+...+N/2+N = N+N/2+N/4+...+ 8+4+2+1 <=2N = O(N)
THE PROBLEM: Given an N-1- element array, Finding an element from within a range of 1-N.
N^2 Algorithm - Finding each value from within the range into the array.
N log N + N log N - Sorting + binary Searching.
N log N + N - Sorting + One Scan Algorithm.
N (reading) + N(Boolean array filling, with respect to each value) + N(Searching a value which one is missing by scanning Boolean array).
N (reading) + Summing from 1-N + Subtracting each value from Sum variable.
Bit Complexity and analysis of the above 5 solutions
2N Bit reading Algorithm finding the missing element.
Binary Search Overflow Handling
Loop Invariant Property
Initialization, Maintenance, and Terminal Condition
Bubble Sort
Selection Sort
Insertions Sort
Which algorithm is faster
Big-O (Upper Bound)
Limit Definition, Set Definition
Logarithmic function
Little o
Limit Definition, Set Definition
Big Omega
Limit Definition, Set Definition
Little Omega
Limit Definition, Set Definition
Big Theta
Limit Definition, Set Definition
Many Examples and their proofs
Ω(N) = | {1, 1+k, 1+2k, 1+3k, 1+4k, 1+5k, .... , N}| N/k i.e. O(N) if k is a constan for(int i=1; i<=N; i+=k)
Ω(N/log N) = |{1, 1+log N, 1+2 log N, 1+3 log N, 1+4log N, 1+5 log N, .... , N}| N/log N i.e. O(N/log N)
for(int i=1; i<=N; i+=k);
| {1, 1+N, 1+2N, 1+3 N, 1+4N, 1+5N, .... , N }| N/N = O(N) i.e. O(N) if k is
for(int i=1; i<=N; i+=10); N/10 times Similarly for(int i=1; i<=N; i+=20); N/20 times
for(int i=1; i<=N; i+=sqrt(N) ); N/sqrt(N) = sqrt(N)
Ω(N2) <= 1+2+3+4+5+6+ ....N-3+ N-2+ N-1+ N <= O(N2) ====> Θ(N2)
Ω(N4) <= 1+2+3+4+5+6+ .... + N2 <= O(N4) ====> Θ(N4)
Ω(N2k) <=1+2+3+4+5+6+ .... +Nk <= O(NkxNk)
Ω(N3) ------ 12+22+32+42+52+62+ .... + N2 --------- O(N3) ===> Θ (N3)
Geometric Sequence Size
GEOMETRIC SERIES
Fibonacci Numbers
Recursive Formulation
Fn = n n=[0,1] //F0 =0, F1=1
Fn = Fn-1+Fn-2 n>=2
Memoized Implementation
TriSum Series
Recursive Formulation
T(N) = 0 (N==0)
T(N) = 1 (N==1)
T(N) = 2 (N==2)
T(N) = T(N-1)+T(N-2)+T(N-3) (N>=3)
Slow Power
Recursive Formulation
Power(N, K) = 1 K = 0
Power(N, K) = N * Power(N, K-1) K !=0
Fast Power
Recursive Formulation
Power(N, K) = 1 K = 0
Power(N, K) = N * Power(N, K/2) * Power(N, K/2) K%2 == 1
Power(N, K) = Power(N, K/2) * Power(N, K/2) K%2 == 0
Slow Multiplication
Recursive Formulation
Mult(A, B) = 0 B = 0
Mult(A, B) = A + Mult(A, B-1) B!=0
Fast Multiplication
Recursive Formulation
T= A , C=0
T+=T , C+=C
Mult(A,B)=0 B = 0
Mult(A,B) = T+Mult(A,B-C)
BubbleSort Recursive Algorithm
Lecture 5 - Recording (Recursion Begins)
Homework 3 Part 1 (Revision of Recursion) - Document
Solving Recurrence of this type - T(N) = a T(N/b) + Nc
If the cost remain constant over each level then the total cost is O(one level cost) x # of levels (Nc x logb N)
Its Proof and several examples
If the cost is decreasing over each level geometrically then the total cost is the cost of 1st step. O(Nc)
Its Proof and several examples
If the cost is increasing over each level geometrically then the total cost is the cost of the last step (alogbN ) .
Its Proof and several examples
Tower of Hanoi
Recursive Formulation
with 3 recursive calls
2 recursive calls
Analysis of Recursive implementations
Quick Sort
Partition Function
Implementation of QuickSort (with extreme left as pivot element)
Lecture 6 - Recording (Solving Recurrence & Master Theorem)
Homework 3 Part 2 (Solve Recurrences) - Document
int LargestSumAtBeginning(int si, int ei, int A [ ], int &ssi, int &sei)
O(N) time complexity
int LargestSumAtEnd(int si, int ei, int A [ ], int &ssi, int &sei)
O(N) time complexity
Investing in the Stock Exchange
Connection with computing the change and finding the Maximum Contiguous Subarray
Divide and Conquer idea
Finding Maximum Crossing Contiguous Sub-array
Finding the Divide and Conquer approach solution
Time Complexity Analysis and discovering the recurrence T(N) = 2 T(N/2) + O(N)
Iterative Merge Sort with Recursive Merge
Lecture 7 - Recording (Divide and Conquer - Stock Investment Problem, Merge Sort)
Karatsuba's Multiplication Algorithm
Classical Slow Multiplication
Its analysis
Divide and Conquer based Multiplication Algorithm over bits
Divide and Conquer based FAST Karatsuba's Algorithm based upon Gauss's simplification
Lower Bound of Comparison based Sorting Algorithm
Lecture 8 - Recording (Divide and Conquer + Sorting Algo Lower Bound + Karatsuba)
Quick Sort
Talking partition (which takes the left/rightmost element as pivot element and partitions
Best/Worst Cases and their time complexities and their solutions
What if QuickSort does skew proportional partitioning.
Its recurrence and its impact
Randomized Partition and its recurrence
How can we do Deterministic QuickSort
Finding the median in the linear time???
Finding the Kth Smallest element in linear time.
Lecture Recording - Divide and Conquer + Quick Sort - Randomized & Deterministic)
Homework 4 (Divide and Conquer) - Document
Homework 4 - Tutorial Recording I
Homework 4 - Tutorial Recording II
Counting Sort
Its application - Range Search
Stable Count Sort
Radix Sort
Sorting numbers from 1 to N^2 in linear time
Bucket Sort
Computing Skyline (O(NlogN))
Finding Closest Pair (O(NlogN))
Reachability Problem for Robot
How to design Maze Solver problem to realistic representation?
Introduction to Graph notation
Adjacency List
Adjacency Matrix
Exploration of Graph
Explore function DFSVisit
Depth First Searching
Application of DFS
Finding Connected Components in the graph
Finding Reachability problem in the graph (in O(1) time with O(N) time pre-processing)
DFS for Directed Graphs
Types of Edges
Tree-Cross-Forward-Back Edges
Identifying all the types of edges in DFS
Directed Acyclic Graph
How to find the Source Vertex and Sink Vertex Inefficient solution by looking into the matrix
Efficient Solution using DFS ordering???
Directed Acyclic Graph
How to find the Source Vertex and Sink Vertex Inefficient solution by looking into the matrix
Efficient Solution using DFS ordering???
Topological Sorting
Inefficient Algorithm (Finding Source/Sink and removing it)
Efficient Implementation using DFS
Breadth-First Search Traversal and Shortest Paths in the labyrinth
Finding Strongly Connected Components
Kosaraju's Algorithm
Heap Data Structures
Complete Tree
Why pointers are not needed
Parent(i), Left(i), Right(i)
HeapifyUp
HeapifyDown
ExtractMin
Lecture 14 - Recording (DFS, Strongly Connected Components, Heap)
Finding Shortest Paths
Adding New Vertices Idea and its problems
Alarm Clock Algorithm
Dijkstra Algorithm
Bellman-Ford Algorithm
Dijkstra Algorithm - Handling the Negative Edges
The Relaxing Algorithm
Universal Sink
Lecture 15 - Recording (Graphs Shortest Path + Dijkstra + Bellman-Ford + Universal Sink)
Paths in Directed Acyclic Graph
Shortest Path in DAG
Longest Path in DAG
Why Dijkstra does not give a minimum spanning tree
Safe Edges
Prim's Algorithm for finding Minimum Spanning Tree
Kruskal Algorithm for finding Minimum Spanning Tree
Complete Trees and their space efficiency
Parent(i), Left(i), Right(i)
Height of the Complete Tree
How to Compute the first Parent with lowest depth
Given an array if it is a Binary Max Heaps
MaxHeapify
Its Time Complexity
BuildHeap
Its Time Complexity analysis
HeapSort
In place sorting algorithm
Disk External Sort: Problem Discussion - Sorting 10 GB data with 1 GB RAM
Recalling
Sorting K sorted arrays in O(KN*log(KN)) - Merging K SortedArrays
Sorting K sorted arrays in O(KN*log K) - using Heap (Priority Queue)
(building Min-Heap with K sorted arrays' ith sub-indices (with K elements)
ExtractMin() value from Min-Heap
Update Min-Heap
Insert next value of ith sub-index of minimum extracted Kith array) - repeat
Sorting 10 GB data with 1 GB RAM - Idea Discussion
Dividing 10 GB data into 10 files of 1 GB
Use Sorting K sorted arrays technique with files
O(KN*log(KN)) - Inefficient because of Disk Accesses
Disk Sort Implementation Discussion with geeks for geeks
Disk Sorting article: https://www.geeksforgeeks.org/external-sorting/
Homework 6 Disk Sort - problem Discussion
Calculate the time taken to complete the Disk-Sort algorithm for 4GB data?
Union-Find
Implementing DataStructure "SetsCollection" - Union(s1, s2)
Find(C): returns the representative IDs for set C belonging to ith set
Update IDs // costly operation
Maximum Unions for n sets (nC2)
Maximum IDs update (n)
Approach 1
Union(S1,S2,....,Sn) - MergeAllSets O(N^2)
Change IDs (parents) of all sets
Find(C) - O(1)
Minimize the gap between Union(..) and Find(..) complexity
Approach 2
Union - O(1)
Change ID (parent) of a set with a smaller size
Find(C) - O(logN) - check recursively C's parent, until reach to null and return
Path Compression technique will study, Find(C) becomes approx O(1)
Lecture 18 Recording - Disk External Sort and Union-Find
Lecture 18 Slides
Finding the Shortest Path in DAG
formulation
connection with Longest Path in DAG
Catalan Numbers
Catalan Numbers Applications
possible Binary Search trees of N vertices
possible Parenthesization {} ordering of size N
Computing Catalan Number with Top-Down Approach
solution1 with simple Recursive Pattern
solution 2 - incorporating Memoization technique
Why need a shift from Top-down to Bottom-up (Dynamic Programming)?
Computing Catalan Number with Bottom-up DP Approach (Table Look-up)
DAG representation
Time Complexity Analysis
Fibonacci Numbers
Computing Fibonacci Number with Top-Down Approach
Computing Fibonacci Number with Bottom-up DP Approach
Time Complexity Analysis
Lecture 19 Recording - DP with Catalan and Fibonacci Numbers
Largest Sum Contiguous Subarray
Kadane's Algorithm | Stock Exchange Problem
Making Recurrence
Bottom-Up Tabulation Method
Book Keeping and Solution printing
Longest Increasing Sub-sequence
Recurrence
Reduction to Finding Longest Path in DAG
Bottom-Up Tabulation Method
Book Keeping and Solution printing
Lecture 20 Recording - Longest Sum Subarray + Longest Increasing Subsequence
What is Rod Cutting Problem?
Making Recurrence
Top-Down Recursive Approach
without Memoization Method
with Memoization Method
Time Complexity Analysis
Bottom-Up Tabular Approach
Mapping on DAG
Time Complexity Analysis
Printing Solution with Book Keeping
Longest/Shortest Distance in a DAG Grid
Making Recurrence
Top-Down + Bottom-Up Approach
Edit Distance Problem
Recursive Definition
Reduction to 2D-Grid DAG (Shortest and Longest Path Finder)
Implementation of Edit Distance
Bottom-Up Approach
Longest Common Sequence
Recursive Definition
Reduction to 2D-Grid DAG (Shortest and Longest Path Finder)
Implementation of Longest Common Subsequence
Bottom-Up Approach
Lecture 22 Recording - Distance in DAG Grid + Edit Distance + Longest Common Sequence
Knapsack Problem Family Set of Problems
Discussion on slides by Dr. Ashraf Iqbal
Lecture 23 Recording - Knapsack Family Set of Problems (Starting from 1:04:00)
Lecture 23 - Slides and notes by Dr. Ashraf Iqbal Knapsack and its relatives
Knapsack Problem Types (with Repetition and without Repetition)
Recursive Problem definition
Its Implementation and Analysis
Matrix Chain Multiplication
Recursive Problem definition
Its Implementation and Analysis
Applications
Lecture 24 Recording - Knapsack Problem Types + Matrix Chain Multiplication
Lecture 24 - Slides
Matrix Chain Multiplication - Revision
Recursive Problem definition
Its Implementation and Analysis
Applications
Graphs Review
DFS Algorithm
Its Applications
Topological Ordering
Finding Strongly Connected Components
BFS Algorithm
Finding the shortest path in the unweighted graphs
Dijkstra Algorithm
How to Handle Weighted edges
When Dijkstra Fails?
Bellman-Ford Algorithm
Shortest path in DAG
All Pair Shortest Path
Why we need it
How we can Use BFS, Dijkstra, Bellmanford for computing APSP
Their complexity analysis
First DP-Solution
Its Complexity analysis
Connection with Matrices - How path finding is equivalent to matrix multiplications
Its complexity analysis
How FAST powering can help???
FAST APSP Algorithm (by using FAST Matrix chain Multiplication - power squaring idea)
Lecture 25 Recording - Matrix Chain Multiplication - Graphs Review + SSSP and APSP
P class - Problem (Efficient Problems)
Some Feasible Algorithms
Sorting
Minimum Spanning Trees
Eulerian Cycle Existence
Comparisons of Algorithms - Running Time (in 2008)
NP class - Problem (Intractable Problems)
P ⊆ NP or NP ⊆ P?
Factorization Problem
Satisfiability SAT
Conjunctive Normal form (CNF)
Disjunctive Normal form (CNF)
Travelling Salesman Problem
Hamiltonian Cycle/Path Problem
Rudrata Cycle Problem
NP-Complete Problem (Hard Problems)
Polynomial Time Reductions
Reducibility Idea
3-SAT problem => Independent Set problem
Independent Set problem => Clique problem
Lecture 26 Recording - P vs NP and Introduction to Reductions
3SAT is as hard as SAT Problem
[Yes - No] 3SAT is as hard as 3SAT
Further Reductions
TSP is harder then HAM-Path
Lecture 27 Recording - P vs NP and Reductions - II
Homework 9 Part 1 - Complexity Classes and Sweep-Line - Document
Find 2D Maxima Point Set
O(N^2) Solution
Divide and Conquer O(NlogN) Solution
Sweep Line Algorithm and its Analysis
Convex Hull
Finding Convex Hull points using
anti-clockwise test with Jarvis's Algorithm
Divide and Conquer Idea
Sweep-line Algorithm
Complexity Analysis
Counting Segment Intersections
using Sweep-line Algorithm
Complexity Analysis
Lecture 28 Recording - Geometric Algorithms - Sweep Line Algorithm and its Applications
Homework 9 Part 2 - Complexity Classes and Sweep-Line - Document
Random Variable, Expectation, PDF, Indicator Random Variable
Hiring Problem
Randomizing an array of n size
Its analysis
Harmonic Series
Its lower bound
Its upper bound
Analysis of Randomized Quicksort
Its analysis
Lecture 29 Recording - Randomized Algorithms - Hiring Problem +Randomized Quicksort
Homework 9 Part 3 - Complexity Classes and Sweep-Line - Document
GOAL : What is Public Key Cryptography ?
Divisibility
Related Theorems
Euclidean GCD - and Division theorem
Modular Arithmetic
Related Theorems
Fields and finite fields based mathematics
FAST - Powering
Calculating Inverse
Generators/Primitive roots
Diffie Hellman Key exchange algorithm
ElGamal Crypto System
Lecture 30a: Number Theoretic Algorithms
Lecture 30b: Number Theoretic Algorithms
Homework 9 Part 3 - Complexity Classes and Sweep-Line - Document