Design and Analysis of Algorithms 2020

Lecture 5: Time Complexity Big O, Omega, Little O and Omega, Big Theta Notation II

• Which algorithm is faster
  • Big-O (Upper Bound)
    • Logarithmic function
  • little o
  • Big Omega
  • Little Omega
  • Big Theta
• Many Examples and its 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)
  • Ω(N²) <= 1+2+3+4+5+6+ ....N-3+ N-2+ N-1+ N <= O(N²) ====> Θ(N²)
  • Ω(N⁴) <= 1+2+3+4+5+6+ .... + N² <= O(N⁴) ====> Θ(N⁴)
  • Ω(N^2k) <=1+2+3+4+5+6+ .... +N^k <= O(N^kxN^k)
  • Ω(N³) ------ 1²+2²+3²+4²+5²+6²+ .... + N² --------- O(N³) ===> Θ (N³)
  • Geometric Sequence Size
  • GEOMETRIC SERIES

Lecture Notes

Video Recordings

Homework 3

Lecture 5b(Tutorial):

Time Complexity analysis of Several examples

(Big O, Big Omega and Theta)

• Problem Set 1
• Problem Set 2
• Problem Set 3
• Problem Set 4

Problem Set Link

Lecture # 5b -Video Tutorial

Homework 3

Lecture 6 - Recursion Begins

• Recursive formulation of
  • 1+2+3+4+...+N
    • Sum(N) = N+Sum(N-1) , Sum(1) = 1
  • Let us say there is a frog living in a well, but now would like to leave the well. If the walls of the well are slippery, and the frog can jump on the wall with quantity J and it will slip with quantity S, find it will take how many steps for the frog to escape from the well, if the height of the well is H units. Keep this thing in mind that it is possible that the frog cannot escape from the well, in that case it must output that frog is imprisoned in the well. E.g. for H = 10 J = 12 S = 2. # 0f Jumps will be 10. floor(H/(j-S)) = ceil(H/(j-S)) Both will fail
  • int SearchFirstOccurence(vector<int>& Vs, int T)
  • int SearchRecLastOccurence(vector<int>& Vs, int si, int ei, int T);
  • int Power(int X, int Y)
    • X^Y = X . X^(Y-1) , X^0 = 1
  • int Mult(int A, int B) // 10x5 = 10 + Mult(10, 4) , Mult(10, 0) = 0;
    • Power(X, Y) = Power(X, Y-1), Power(X, 0) = 1

Notes(Codes written in the lecture)

Video Lecture

Homework 3

Lecture 7 - Recursion II

• Fibonacci Numbers
  • Recursive Formulation
    • Fn = n n={0, 1} // F0 = 0, F1 = 1
    • Fn = Fn-1 + Fn-2 n>=2
  • Memoized Implementation
  • BottomUp Implementation (Introduction to removing recursion with table looking)
• Slow Multiplication
• FAST Multiplication
• Slow Division
• FAST Division
• BubbleSort Recursive algorithm

Notes(Codes written in the lecture)

Video Lecture

Homework 3

Lecture 8 - Recursion III (Advanced Recursion)

1. Tower of Hanoi
   • Recursive Formulation
     • with 3 recursive calls
     • 2 recursive calls
     • Analysis of Recursive implementations
2. - All String of length K from made up of the characters from array in increasing order
3. - Permutations
4. - Merge Sort
   • Implementation of Merge
   • Implementation of MergeSort
5. - Quick Sort
   • Partition Function
   • Implementation of QuickSort (with extreme left as pivot element)

Video Lecture

Homework 4

Lecture 9 - Homework 3 and Analysis of Merge-Sort

• Time Complexity of functions calling functions
  • Some more examples
• Analysis of Merge Sort

Video Lecture

Homework 3

Lecture 10 - Solving Recurrences

• Solving Recurrences
  • Arithmetic Series
  • Arithmetic Sequence
  • Geometric Sequence
  • Geometric Series

Notes

Video Lecture

Homework 4

Lecture - Tutorial(Help Session on Homework 4)

Solving Recurrences and Master Theorem

Solving Recurrence of this type - T(N) = a T(N/b) + N^c

1. If the cost remain constant over each level then the total cost is O(one level cost) x # of levels (N^c x log_b N)
   • Its Proof and several examples
2. If the cost is decreasing over each level geometrically then the total cost is the cost of 1st step. O(N^c)
   • Its Proof and several examples
3. If the cost is increasing over each level geometrically then the total cost is the cost of the last step (a^logb^N ) .
   • Its Proof and several examples

Notes

Formal Reading

• Practice these recurrences... by making the recurrence tree.... all the recurrences has solution provided to you.... verify it..... http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf
• Another variant of Master Theorem https://www.geeksforgeeks.org/master-theorem-subtract-conquer-recurrences/

Video Lecture

Homework 4

Lecture - 11 Segregating values in an array, Partition, QuickSort

• Segregating 0,1 array
• Segregating Even and Odds
• Segregating smaller values to the left and greater to the right.
• Partition
• Quick-Sort with left corner as pivot
  • Its Time Complexity Analysis
  • Comparison with Merge-Sort
  • Its worst time complexity
• Randomized Partition
  • Its analysis
• Comparison with Merge-Sort

Video Lecture

Homework 4

Lecture - 12 Divide and Conquer

• Quiz (Finding Maximum Subarray Anchored to the left and Anchored to the right and middle)
• 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

Slides

Video Lecture

Tutorial - Homework 4

• Iterators and list
• vector<vector> Implementation of Matrix
• Prune Searching - Searching in Sorted Matrix(row and column wise decreasing order)
• Measuring Entropy - Divide and Conquer
• T(n) = n^1/2 T(n^1/2) + n

Codes

Video Lecture

Lecture 13 - Divide and Conquer (Karatsuba's Multiplication Algorithm)

• Review
  • 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
  • Lower Bound of Comparison based Sorting Algorithm
• 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

Slides

Video Lecture

Lecture 14 - Prune and Search (Deterministic QuickSort)

• Quick Sort
  • Talking partition (which takes the left/right most element as pivot element and paritions
  • Best/Worst Cases and their time complexities and their solutions
• What if QuickSort does skewed proportional paritioning.
  • 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.

Slides

Video Lecture

Lecture 15 - Review of Deterministic QuickSort and Counting Sort and Radix Sort

• Quick Sort and its instability
  • What if QuickSort does skewed proportional paritioning.
    • 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 Expected linear time
• Finding the Kth Smallest element in linear time
• Counting Sort
  • Its application - Range Search
• Radix Sort
  • Sorting numbers form 1-N^2 in linear time
• Bucket Sort

Slides

Video Lecture

Lecture 16 - Homework 5 (Discussion)

• Finding Pair(Pi, Pj) which has sum equal to X
  • in O(N log N) Time
  • Given Sorted array solving the above problem in linear time
• Finding Intersection Set
  • in O(N log N) Time
  • Given Sorted array solving the above problem in linear time
• Finding Minimum and 2nd Minimum in exact N + log N Time (Image Discussed)
• You have N elements array but you are given that there are only K distinct values which have been repeated again and again in any order. For example N could be 1000 and K could be 10 means that the array contains only 10 values which are being duplicated anywhere in the array. Now you want to sort that array. You must have to give appropriate implementation using vector, map or set (libraries in STL) or anything you like. Your algorithm should take O(N log K) time instead of O(N log N). Drive time complexity.

Codes Discussed

Video Lecture

Lecture 17 - Homework 5 (Discussion II)

• K Rotation in Linear Time and relatives
• FINDING MAXIMUM SUM SUBARRAY PROBLEM in linear time
• Finding the pair in two arrays, for swapping,such that sum becomes equal
• Finding Knight in the island
• Finding Majority Image
• Nuts and Bolts

Homework 5(Notes)

Video Lecture

Lecture 18 - Priority Queue (Heap Data Structure and Applications)

• Priority Queue and Heap
• Heap Recursive Definition
• Why Complete Tree?
  • Its connection with Array representation -
  • HeapiyDown
  • Build Heap and its Time Complexity proof (O(N))
  • Extract Max/Key -
• Application HeapSort
  • InsertKey
  • HeapifyUp Application
• Further Application
  • Merging K Arrays using MergeSort's merging technique
    • https://www.geeksforgeeks.org/merge-k-sorted-arrays/
  • External/Disk Sort
    • https://www.geeksforgeeks.org/external-sorting/

Notes

Video Lecture

Lecture 19 - Priority Queue Application (Heap Data Structure's Applications)

• Application
  • Merging K Arrays using MergeSort's merging technique
    • https://www.geeksforgeeks.org/merge-k-sorted-arrays/
  • External/Disk Sort
    • https://www.geeksforgeeks.org/external-sorting/

Notes

Video Lecture

Lecture 20 - Introduction To Graphs

• Introduction To Graphs
• Representations
• Applications
  • Directed vs Undirected Graphs
    • Facebook, Twitter, Collaboration Graph, Road network Graph
• Implementation of Graph
  • vector<vector<bool>>
  • Graph class using list representation
• Finding Connected Components, DFS

Notes

Slides

Video Lecture