## Pre-requisite(s)

Data Structures (CS-2143)

Discrete Mathematics (MTC-2053)

Computer Programming (CS-1123)

## Recommended Book(s)

Introduction To Design & Analysis Of Algorithms By Anany Levitin 3rd Edition

Foundations Of Algorithms  By Richard E. Neapolitan, Kumarss Naimipour, Northeastern Illinois University D. C. Heath And Company Lexington, Massachusetts Toronto

## Reference Book(s)

Data Structures And Algorithm Analysis In C++ By Mark Allen Weiss Benjamin/Cummings Publishing Company, Inc.

## COURSE OBJECTIVES

Design algorithms using different algorithms design techniques i.e. Divide and Conquer, Dynamic Programming, Greedy Algorithms & Backtracking. Analyze Algorithms (estimate upper & lower bounds without coding and running the algorithms) and compare the efficiency of different algorithms for a problem. Implement and test algorithms. Logically think and develop problem solving skills.

### COURSE LEARNING OUTCOMES (CLO)

Course Objectives

## COURSE CONTENTS

### Introduction to the course and course objectives

What is an algorithm?
Fundamental of the Algorithmic Problem Solving
Important Problem Types
Fundamental Data structures

### Fundamentals of the Analysis of Algorithm Efficiency

The analysis framework
Asymptotic Notations and Basic Efficiency Classes
Mathematical Analysis of Nonrecursive Algorithms
Mathematical Analysis of Recursive Algorithms
Substitution method
Iteration method

### Brute Force / Exhaustive Search / Decrease-and-Conquer

Selection Sort and Bubble Sort
Sequential Search and Brute-Force String Matching
Exhaustive Search
Depth first search
Insertion Sort

### Design and Optimization Example

Maximum Subsequence Sum Problem

### Divide and Conquer algorithm design strategy

Recursive Algorithm Analysis
Merge Sort
Quick Sort
Multiplication of Matrices  / Strassen’s  Algorithm

### Dynamic Programming

Development of a Recursive Algorithm
Elimination of Redundant Work from a Recursive Algorithm
Transform into a memoized recursive algorithm
Transform into an iterative algorithm
Optimized Algorithm
Development of a recursive definition to solve a problem with examples
Coin row problem
Coin collection problem
Knapsack problem
Optimal Binary Search Tree
Warshall Algorithm
Flyod Algorithm

### Greedy Technique

Prim’s Algorithm
Kruskal’s Algorithm
Dijkstra’s Algorithm
Huffman Trees and Codes

### Coping with the Limitations of Algorithm Power

Backtracking (n-Queen Problem, Hamiltonian Circuit Problem, Subset-Sum Problem)
Branch & Bound (Assignment Problem, knapsack Problem)

## MAPPING OF CLOs TO ASSESSMENT MODULES

 Final Exam Assignments Surprise Tests/Quizzes Project Midterm Exam