CS702 Official Handouts

Contents

Lecture 01 Lecture 02 Mathematical Tools for Design and Analysis of Algorithms ........................................... 5 Lecture 03 Logic and Proving Techniques ....................................................................................... 10 Lecture 04 Mathematical Induction ................................................................................................ 16 Lecture 05 Strong Mathematical Induction .................................................................................... 22 Lecture 06 Fibonacci Sequences ..................................................................................................... 27 Lecture 07 Recurrence Relations .................................................................................................... 37 Lecture 08 Recurrence Relations .................................................................................................... 45 Lecture 09 Further Techniques Solving Recurrence Relations ....................................................... 52 Lecture 10 Time Complexity of Algorithms (Asymptotic Notations) .............................................. 64 Lecture 11 Relations Over Asymptotic Notations ........................................................................... 73 Lecture 12 Design of Algorithms using Brute Force Approach ....................................................... 80 Lecture 13 Designing Algorithms using Brute Force and Divide & Conquer Approaches .............. 88 Lecture 14 Designing Algorithms using Divide & Conquer Approach ............................................. 92 Lecture 15 Dynamic Programming for Solving Optimization Problems ....................................... 103 Lecture 16 Chain Matrix Multiplication Problem using Dynamic Programming .......................... 110 Lecture 17 Assembly‐Line Scheduling Problem ............................................................................ 116 Lecture 18 2‐Line Assembly Scheduling Problem ......................................................................... 123 Lecture 19 0‐1 Knapsack Problem using Dynamic Programming ................................................. 127 Lecture 20 0‐1 Knapsack Problem’s Algorithm (using Dynamic Programming) and Optimal Weight Triangulation ....................................................................................................................................... 135 Lecture 21 Optimal Weight Triangulation .................................................................................... 146 Lecture 22 Lecture 23 Longest Common Subsequence (Dynamic Algorithm) & Optimal Binary Search Trees

Lecture 24 Optimal Binary Search Trees (Constructing Dynamic Programming) ......................... 160 Lecture 25 Greedy Algorithms ...................................................................................................... 166 Lecture 26 Huffman Coding .......................................................................................................... 176 Lecture 27 Huffman Coding Problem and Graph Theory ............................................................. 186 Lecture 28 Breadth First Search .................................................................................................... 197 Lecture 29 Proof (Breadth First Search Algorithm) and Depth First Search ................................. 205 Lecture 30 Proof (White Path Theorem) & Applications of Depth First Search ........................... 216 Lecture 31 Backtracking and Branch & Bound Algorithms ........................................................... 221 Lecture 32 Minimal Spanning Tree Problem ................................................................................. 227 Lecture 33 Single‐Source Shortest Path ........................................................................................ 242 Lecture 34 Proof: Bellman‐Ford Algorithm & Shortest Paths in Directed Acyclic Graphs .................. 252 Lecture 35 Dijkstra’s Algorithm ..................................................................................................... 257 Lecture 36 All Pairs Shortest Paths ............................................................................................... 266 Lecture 37 The Floyd‐Warshall Algorithm and Johnson’s Algorithm ............................................ 272 Lecture 38 Number Theoretic Algorithms .................................................................................... 283 Lecture 39 Number Theoretic Algorithms .................................................................................... 293 Lecture 40 Chinese Remainder Theorem and RSA Cryptosystem ................................................ 302 Lecture 41 RSA Cryptosystem and String Matching ..................................................................... 309 Lecture 42 String Matching ........................................................................................................... 314 Lecture 43 Polynomials and Fast Fourier Transform .................................................................... 323 Lecture 44 NP Completeness ........................................................................................................ 333 Lecture 45

Lecture 01

What is algorithm?

•  A computer algorithm is a detailed step-by-step method for solving a problem by using a computer.
•  An algorithm is a sequence of unambiguous instructions for solving a problem in a finite amount of time.
•  An Algorithm is well defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values as output.
•  More generally, an Algorithm is any well defined computational procedure that takes collection of elements as input and produces a collection of elements as output.

Popular Algorithms, Factors of Dependence

Most basic and popular algorithms are sorting algorithms & Searching algorithms

Which algorithm is best?

•  Mainly, it depends upon various factors, for example in case of sorting
•  The number of items to be sorted
•  The extent to which the items are already sorted
•  Possible restrictions on the item values
•  The kind of storage device to be used etc.

One Problem, Many Algorithms

Problem: The statement of the problem specifies, in general terms, the desired input/output relationship. Algorithm: The algorithm describes a specific computational procedure for achieving input/output relationship. Example: One might need to sort a sequence of numbers into non-decreasing order. Algorithms: Various algorithms e.g. merge sort, quick sort, heap sorts etc.

Important Designing Techniques

•  Brute Force: Straightforward, naive approach, mostly expensive
•  Divide-and-Conquer: Divide into smaller sub-problems
•  Iterative Improvement: Improve one change at a time

Algorithm · Input · output