CS702 Handouts

Advanced Algorithms Analysis and Design · Table of Contents · Chapter 1: Model of Computation

Lecture No 1: Introduction of Algorithms ............................................................................ 03

Chapter 2: Mathematical Tools

Lecture No 2: Fundamentals of Algorithms ........................................................................ 08 Lecture No 3: Logic and Proving Techniques ..................................................................... 13 Lecture No 4: Mathematical Induction ................................................................................ 19 Lecture No 5: Strong Mathematical Induction ..................................................................... 25

Chapter 3: Recursion

Lecture No 6: Fibonacci Sequences ................................................................................... 29 Lecture No 7: Recurrence Relations I ........................................................................................ 39 Lecture No 8: Recurrence Relations II ....................................................................................... 49 Lecture No 9: Algorithms Analysis Techniques ................................................................... 55

Chapter 4: Asymptotic Notations

Lecture No 10: Time Complexity of Algorithms................................................................... 67 Lecture No 11: Relations over Asymptotic Notations .......................................................... 76

Chapter 5: Brute Force Approach, Divide and Conquer

Lecture No 12: Design of Algorithms using Brute Force Approach .................................... 83 Lecture No 13: Design of Algorithms using Brute Force, Divide & Conquer Approaches .... 91 Lecture No 14: Design of Algorithms using Divide & Conquer Approaches ....................... 95

Chapter 6: Dynamic Programming

Lecture No 15: Chain Matrix Multiplication using Brute Force .............................................. 106 Lecture No 16: Chain Matrix Multiplication using Dynamic Programming ......................... 113 Lecture No 17: Assembly-Line Scheduling Problem ......................................................... 119 Lecture No 18: 2-Line Assembly Scheduling Problem ...................................................... 126 Lecture No 19: 0-1 Knapsack Problem using Dynamic Programming .............................. 133 Lecture No 20: Optimal Weight Triangulation I ...................................................................... 142 Lecture No 21: Optimal Weight Triangulation II ..................................................................... 152 Lecture No 22: Review Lectures 1-21 .............................................................................. 159

Mid-Term 2015 Exam Questions .................................................................................... 166

Lecture No 23: Longest Common Subsequence ............................................................... 167 Lecture No 24: Optimal Binary Search Trees .................................................................... 177

Chapter 7: Greedy Algorithms

Lecture No 25: Greedy Algorithm ...................................................................................... 181 Lecture No 26: Huffman Coding ........................................................................................ 190

Chapter 8: Graph Theoretic Algorithms

Lecture No 27: Huffman Coding Problem and Graph Theory ............................................. 197 Lecture No 28: Breadth First Search .................................................................................. 207 Lecture No 29: Depth First Search ..................................................................................... 217 Lecture No 30: White Path Theorem .................................................................................. 225 Lecture No 31: Backtracking and Branch & Bound Algorithms ........................................... 233 Lecture No 32: Minimal Spanning Tree Problem ................................................................236 Lecture No 33: Single-Source Shortest Path ...................................................................... 249 Lecture No 34: Bellman-Ford Algorithm ............................................................................. 258 Lecture No 35: Dijkstra‟s Algorithm ........................................................................................... 264 Lecture No 36: All Pairs Shortest Paths ............................................................................. 272 Lecture No 37: Floyd-Warshall Algorithm & Johnson‟s Algorithm ...........................................278

Chapter 9: Number Theoretic Algorithms

Lecture No 38: Number Theoretic Algorithms .....................................................................290 Lecture No 39: Theorems and Algorithms .......................................................................... 300 Lecture No 40: Chinese Remainder Theorem .................................................................... 310

Chapter 10: Further Topics

Lecture No 41: RSA Cryptosystem ..................................................................................... 317 Lecture No 42: String Matching .......................................................................................... 322 Lecture No 43: Polynomials and Fast Fourier Transform .....................................................331 Lecture No 44: NP Completeness ...................................................................................... 340 Lecture No 45: Review Lecture .......................................................................................... 350

Final-Term 2015 Exam Questions .................................................................................... 358

Presented By: · Dr. Nazir Ahmad Zafar · Virtual University of Pakistan · Published by: Safi Khan · Introduction of Algorithms · (What, Why and Where) · Major objective of this course is:

Design and analysis of modern

Different variants Accuracy Efficiency Comparing efficiencies Motivation thinking new algorithms Advanced designing techniques Real world problems will be taken as examples To create feelings about usefulness of this course

Major objective of this course is:

Design and analysis of modern

Different variants Accuracy Efficiency Comparing efficiencies Motivation thinking new algorithms Advanced designing techniques Real world problems will be taken as examples To create feelings about usefulness of this course

Expected Results

On successful completion, students will be able to Argue and prove correctness of algorithms Derive and solve mathematical models of problems Reasoning when an algorithm calls certain approach Analyze average and worst-case running times Integrating approaches in dynamic and greedy algos. Use of graph theory in problems solving Advanced topics such as Computational geometry, number theory etc. Several other algorithms such as String matching, NP completeness, approximate algorithms etc.

In this lecture we will cover the following

What is Algorithm?

Algorithms as a technology Algorithms and other technologies Importance of algorithms Difference in Users and Developers Kinds of problems solved by algorithms