Design and Analysis of Algorithms

Lecture 1: Algorithmic Problem solving and Analysis of Algorithms

• • • Discussion on Course Outline

    • Geometric Sequence (logrithm function)

    • Prune and Search

      • • Finding the heaviest ball from 8 balls in 3 tries, using a balance

          • • Its generalization and connection with $\log_2 N$

        • Finding the heaviest ball from 8 balls in 2 tries, using a balance.

          • • Its generalization and connection with $\log_3 N$

        • Binary Searching

    • 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 + Subtracing each value from Sum variable.

        • Bit Complexity and analysis of the above 5 solutions

          • • 2N Bit reading Algorithm finding the missing element.

Lecture 2: N^2 Sorts

• • • Bubble Sort

      • • • BubbleUp function

          • Its Time Complexity analysis

          • 3 Implentations of BubbleSort

    • Selection Sort

      • • • • SelectMinIndexWithinRange function

            • Its Time Complexity analysis

            • SelectionSort using SelectMinIndexWithinRange function

    • Insertions Sort

      • • • • QUIZ - InsertInSortedSubarray

            • InsertionsSort using InsertInSortedSubarray method.

            • Its Time Complexity Analysis

    • Vector Implementations of the above codes

Lecture 3: Recursion I and analyzing Time recurrences

• • • Recursive Formulation

      • • • Factorial function

            • • N! = N * (N-1)! and 0! = 1

              • Recursive code

              • Recursive Time equation T(N) = T(N-1) + 2 , and its derivation

          • Fibonacci Numbers

            • • • Fn = Fn-1 + Fn-2 and F0 = 0 and F1 = 1

                • Recursive code

                • T(N) = T(N-1) + T(N-2) + 2

                • Bounding lower by comparing it with T(N) = T(N-2) + T(N-2) + 2

                • Why it is taking so long time?

                • Why Stack overflow is not happening on F(55)???

• • • • • • • Memoization (Memory saving and recursive codes)

              • vector<int> implementation for memory saving version of fibonacci.

              • Time complexity of the memoized version? T(N) = T(N-1) + 2 the second call will be cut due to memory.

• • • • • • Trisum Number

            • • • its recurrence, recursive formulation and code

          • Many Series recurrences and their formulations?

            • • • Various versions of Arithmetic, geometric sequences and series

                • Their mathematical formulations and their recurrences and their solutions

          • Power(X,Y)

            • • • Its mathematical formulation and recurrence time complexity analysis.

          • Linear Searching

            • • • Its two variants

Lecture 4: Recursion II

• • • • • Recursive Searching Algorithm

          • • • • With Size shrinking idea (What will it return if more than one time the value is present?)

                • With si (starting index) increasing and making a helping function for Searching

        • Recursive BubbleUp program

          • • • • Its two implementations

        • BubbleSort Program

          • • • • Why Recursive BubbleSort is not recommended? Its limitation of Stackover flow?

        • Recursive MinimumIndexSearch

• • • • • • • • Recursive SelectionSort?

• • • • • Multiplication Using Addition and Comparison

• • • • • • • • SlowMultiplication(A, B) with recurrence of T(B) = T(B-1) + 1 ===> O(B) Time complexity

              • LighteningFASTMultiplication(A, B) with recurrence of O(log B) Time complexity

• • • • • Division using Addition and Subtraction/Comparison

• • • • • • • • SlowDivision(A, B, & Rem) with recurrence of T(B) = T(B-1) + 1 ===> O(B) Time complexity

              • LighteningFASTDivisionA, B, & Rem) with recurrence of O(log B) Time complexity

• • • • • Power(X, Y) function

• • • • • • • • Slow Powering recurrence function

              • FAST Powering recursive function and coding details

• • • • • Merging two Single Dimensional sorted arrays

• • • • • • • • Point to ponder - How to use this to do Sorting?

Lecture 5: Divide and Conquer I

• • • • • Merging two Single Dimensional sorted arrays

          • • • Arrays Implentation

              • Vector Implementation

              • Point to ponder - How to use this to do Sorting?

        • MergSort

          • • • Array Implementation

              • Vector Implementation

        • Time Complexity Analysis of the MergeSort recurrence : T(N) = 2 T(N/2) + 2N

          • • • Why O(N)

              • Comparison of BubbleSort VS MergeSort

Lecture 6: Divide and Conquer II

• • • • • MergeSort revisited on Linked Lists

          • • • Merging two Singly linked lists

              • Its comparison with array based implementations

        • Finding in a sorted matrix (given Row and Column - wise sorted in decreasing order)

          • • • O(N log N) implementation

              • O(N) Time implementation

        • Shrinking Range Pruning Technique O(N) Time Algorithm

          • • • Sorting a 0/1 array

              • Segregating/partitioning Evens and Odds

              • Segregating/partitioning All on the basis of a value

        • QuickSort Algorithm

          • • • Its recursive implementation

Lecture 7: Time Complexity (Big O, Ω , Little o, ω)

• • • • • Lower Bounds and Upper bounds

          • • • Little o VS Big O

              • Little ω VS Ω

        • Combining Bounds with limit test

          • • • How to compare the efficiency of two algorithms by taking help from Calculus

        • Randomized QuickSort (Revisited)

          • • • Its Randomized analysis

Lecture 8: Tricks of finding Upper and Lower bounds and Solving Recurrences

• • • • • How to bound the Arithematic series and relatives?

          • How to do upper bound in Arithematic Series and relatives cases

            • • • by adding some fraction and trying to ease out the bounding?

                • Replacing with highest value trick....

          • How to find strong lower bounds in case of arithematic series case???

            • • • by ignoring some of the parts to ease out the bounding process.

                • Fractional removing technique/Halving or some part of the size of input.

        • How to deal with Geometric Series cases

          • Finding Upper bound?

• • • • • • • • Why the same trick of fraction removal didnt work?

              • By taking two unit boxes and fitting in the fractions into boxes.

• • • • • • Finding lower bound of Geometric Case

• • • • • • • • By taking just the largest term.

• • • • • Solving recurrences (Recursion Tree method + Discovery of Master Theorem)

• • • • • • • • Solving recurrences which expand in the form gemetric series and its three cases

Lecture 9: Investing in the Stock Exchange

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

Tutorial 1: Homework 5

• • • • • Basics of Sequences and Series

        • Loops based Time Complexities

          • Functions calls based time complexity analysis

        • Solving Recurrences

          • Geometrically Increasing sequences

          • Geometrically decreasing sequences

        • Recurrences with different branch out factors

Lecture 10: Lower Bounds of Sorting + Karatsuba's Algorithm of Multiplication

• • • • • Revision of Maximum Contiguous Sub-array

        • Revision of Iterative Version of Merge-Sort

        • Balanced Tree and discovery of Red-BlackTreeSort

          • Set Implementation

          • Analysis of BalancedTreeSort

        • Lower Bounds on Comparison based Sorting Algorithms Ω(N log N)

        • Gauss note complex numbers multiplication

        • Classical Multiplication Algorithm

          • • Its recurrence and analysis

        • Discovery of Divide and Conquer Algorithm for multiplication

          • • Its recurrence and analysis

        • Karatsuba's Algorithm based on Gauss Notes

          • • Its recurrence and analysis

Lecture 11: Several Examples of Time complexities

• • • • • • • 1. int f1(int N)

              2. {

              3. int Count=0;

              4. for(int i=0; i<=N^8; i++)

              5. count++;

              6. 
                 

              7. return Count^(1/8); // runs in constant times.

              8. }

              9. 
                 

              10. int main()

              11. {

              12. int N;

              13. .

              14. .

              15. for(int i=0; i<=f1(N); i++)

              16. for(int j=0; j<=i; j++) // We covered various variants

              17. ........

              18. }

• • • • • T(N) = T(N-4) + N^3

        • T(N) = 2T(N-4) + N^3 its BIG O and Ω

        • T(N) = T(N/2) + 5T(N/5)+ T(N/8) + N and several other variants

        • T(N) = T(N^0.5) + N and comparison with Geometric Series and finding its BIG O and Ω

        • T(N) =4 T(N/2) + N log N

        • T(N) = 3T(N/3) + n^0.5

Lecture 12: Prune and Search Revisited (Randomized Algorithm)

• • • • • QuickSort Revisited

          • • Randomized Partitioning

            • BEST and WORST cases.

            • What will happen if the partition doesn't divide into Equal-partitions (rather skewed one)

              • • e.g. T(N) = T(9N/10) + T(N/10) + O(N).

                • OR T(N) = T(3N/4) + T(N/4) + O(N)

                • Average Case of QUICKSORT

        • Prune and Search in ACTION

• • • • • • • • Randomized-Select: Finding the Kth smallest element in an array in expected lienar time.

              • Deterministic-Select in action.

Lecture 13: Linear Sorting and relatives

• • • • • Implementation of BalancedTreeSort

          • Using MAP of STL

        • Lowerbound of Sorting

        • Sorting Elements with 1-K values

          • • • Counting Sort idea

              • Practical Details (Bucketing Idea)

        • Range Count Problem

          • • • Count Sort Algorithm

        • Radix Sort

          • • • Sorting N elements from 1-N^2 range elements in linear time

        • Bucket Sort

Lecture 14: Discussion on Homework 6

• • • • • TowerOfHanoi (2 ideas and their complexities)

        • Pair Sum Search

        • Finding Disjoint or Intersection Sets

        • Minimum and Second Minimum Searching

        • Sorting N - records Data with K distinct values only

        • Rotated Sorted Array relatives

        • Contiguous Subset Sum(linear time idea)

        • Exponential Searching

        • Prune and Searching Revisited

Lecture 15: Discussion II on Homework 6

• • • • • Contiguous Subset Sum(linear time idea)

        • Sachhay and Jhottay

        • and Popular Image Searching

        • Nuts and Bolts

Lecture 16: Binary Heaps and HeapSort

• • • • • Complete Tree and Array Based Implementation of Complete Tree

        • Detecting an array if it is a Heap

        • Inserting and Extracting operation in Binary Heap

          • • • • HeapifyUP

                • HeapifyDown

        • BUILD-HEAP

        • HEAPSORT

Lecture 17: Priority Queues and Binary Heap

• • • • • How to implement priority queue using simple array

          • • Problem of searching maximum priority element

        • How to implement priority queue using sorted array

          • • Problem of inserting while maintaining sorted array

            • Circular Queues in case of avoiding the isFull function.

        • Moving to Linked List

          • • Searching is a problem now... Insertion problem is resolved

        • Moving to Binary Search Tree

          • • Skewed tree is the problem

        • Moving to Balanced Binary Search tree (AVL or Red Black tree)

          • • Problem - Space inefficient

        • Complete Binary tree and its array based implementation

        • Detecting an array if it is a Heap

        • Inserting and Extracting operation in Binary Heap

          • • • • HeapifyUP

                • HeapifyDown

        • BUILD-HEAP

          • • O(n log n) implementation

            • O(n) implementation

        • HEAPSORT

Lecture 18: Introduction to Graphs

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

Lecture 19: Implementation of Graphs

• • • • • Implementation of Graphs and its usage in DFS

          • • AdjacencyMatrix implementation of Graph

            • AdjacencyList implementation of Graph

              • • How it will be used in DFS

        • DFS for Directed Graphs

          • • • • Types of Edges

                • Tree-Cross-Forward-Back Edges

                • Identifying all the types of edges in DFS

        • Directed Acyclic Graph

Lecture 20: Application of DFS

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

        • Finding Topological Ordering

          • • • • Topological Sort

Lecture 21: Graphs Traversal and Application

• • • • • DFS for Directed Graphs

          • • Finding Strongly Connected Components

        • Finding Shortest Path

          • • Breadth First Search and its implementation

            • Prison Break Using DFS

Lecture 22: Grid Graph and Implementation of DFS and BFS

• • • • • Grid Graph

        • Recursive Implementation of DFS

Lecture 23 and 24: Dijkstra, Bellman Ford, Shortest/Longest Path in DAG, Finding MSTs

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

        • Minimum Spanning Tree

          • • • Prims Algorithm

              • Kruskal Algorithm

Lecture 25 : Dynamic Programming I

• • • • • Finding Shortest Path in DAG

          • • • Two Approaches (Top Down order path finder and Bottom Up, in topological order)

        • Finding Longest Path in DAG

          • • • The Changes we have to make in our upper solution

        • Catalan Numbers

          • • • Designing Recurrence

              • Implementing Top Down Memoization Code

              • Implementing Bottom Up Tabulation Method

        • Fibonacci Numbers

          • • • Designing Recurrence

              • Implementing Top Down Memoization Code

              • Implementing Bottom Up Tabulation Method

        • Longest Increasing Sub-sequence

          • • • Reduction to Finding Longest Path in DAG

Lecture 26 : Dynamic Programming II

• • • • • Longest Increasing Sub-sequence

          • • • Recurrence

              • Reduction to Finding Longest Path in DAG

              • Bottom Up Tabulation Method

              • Book Keeping and Solution printing

        • Maximum Sum Subarray (Kadane's Algorithm)

          • • • Making Recurrence

              • Bottom Up Tabulation Method

              • Book Keeping and Solution printing

        • Rod Cutting Problem

          • • • Making Recurrence

Lecture 27 : Dynamic Programming III

• • • • • Rod Cutting Problem

          • • • Making Recurrence

              • Top Down Memoization Method

              • Bottom Up Tabular Approach

              • Book Keeping and Solution printing

        • Longest/Shortest Path in the 2D - GRID DAG

          • • • Its recurrence

              • Its Bottom Up approach

        • Edit Distance Problem

          • • • Recursive Problem definition

              • Its reduction to 2D-Grid DAG (Shortest and Longest Path Finder)

              • Implementation of Edit Distance, Bottom Up Approach (from DPV)

Lecture 28 : Edit Distance and Longest Common Subsequence

• • • • • Longest/Shortest Path in the 2D - GRID DAG

          • • • Its recurrence

              • Its Bottom Up approach

        • Edit Distance Problem

          • • • Recursive Problem definition

              • Its reduction to 2D-Grid DAG (Shortest and Longest Path Finder)

              • Implementation of Edit Distance, Bottom Up Approach (from DPV)

        • Longest Common Sub-sequence

          • • • Recursive Problem definition

              • Its reduction to 2D-Grid DAG (Shortest and Longest Path Finder)

              • Implementation of Edit Distance, Bottom Up Approach (from DPV)

Lecture 29 - Knapsack Problem and Matrix Chain Multiplication

• • • • • Longest/Shortest Path in the 2D - GRID DAG, Edit Distance Problem, Longest Common Sub-sequence

          • • • Recursive Problem definition

              • Its reduction to 2D-Grid DAG (Shortest and Longest Path Finder)

              • Implementation of Edit Distance, Bottom Up Approach (from DPV)

        • Knapsack Problem (Unbounded and Bounded Versions)

          • • • Recursive Problem definition

              • Its implementation

        • Matrix Chain Multiplication

          • • • Recursive Problem definition

              • Its implementation

Lecture 30- Knapsack Problem(Its variants) and Matrix Chain Multiplication

• • • • • • • • Longest/Shortest Path in the 2D - GRID DAG, Edit Distance Problem, Longest Common Sub-sequence

              • Recursive Problem definition

              • Its reduction to 2D-Grid DAG (Shortest and Longest Path Finder)

              • Implementation of Edit Distance, Bottom Up Approach (from DPV)

• • • • • Knapsack Problem (Unbounded and Bounded Versions)

          • • • Recursive Problem definition

              • Its implementation

              • Discussion on slides by Dr. Ashraf Iqbal

        • Matrix Chain Multiplication

          • • • Recursive Problem definition

              • Its implementation

              • Discussion on slides by Dr. Ashraf Iqbal

Lecture 31- Graphs Review + Single Source (SSSP) and All Pair Shortest Paths(APSP)

• • • • • Review of Graphs

          • • • DFS Algorithm

                • Its Applications

                • Topological Ordering

                • Finding Strongly Connected Components

              • BFS Algorithm

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

              • FLOYD WARSHAL Algorithm

Talk 1- by Dr. Mudassir

• • • • • Sweep line Algorithm

        • Greedy Algorithm

        • Real Life Problem of Control System and connection with Coin Picking Game

Talk 2- by Sarim Baig - Parrallel Algorithms

• • • • • Parrallel Fibonacci Recursive Problem

          • • • Its Connection with Stranded DAG problem

              • Bounds on Parallel Processing

        • MergeSort Parrallelized

        • Designing Greedy Scheduler and its approximation bound