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

Introduction to the DP Paradigm
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

Limitations of Algorithm Power

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