Design and Analysis of Algorithms

Course Title: Design and Analysis of Algorithms

Course No: CSIT.311

Nature of the Course: Theory + Lab

Semester: 5

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 10 + 10

Credit Hours: 3

Course Description

This course introduces basic elements of the design and analysis of computer algorithms. Topics include asymptotic notations and analysis, divide and conquer strategy, greedy methods, dynamic programming, basic graph algorithms, NP-completeness, and approximation algorithms.

Course Objectives

Analyze the asymptotic performance of algorithms. Demonstrate a familiarity with major algorithms and data structures. Apply important algorithmic design paradigms and methods of analysis. Solve simple to moderately difficult algorithmic problems arising in applications. Be able to demonstrate the hardness of simple NP-complete problems.

Course Contents

1. Foundation of Algorithm Analysis

4 hrs

1.1. Algorithm Analysis Introduction

Algorithm and its properties

RAM model

Time and Space Complexity

Detailed analysis of factorial algorithm

1.2. Asymptotic Notations

Big-O Notation, Geometrical Interpretation and Examples

Big-Ω Notation, Geometrical Interpretation and Examples

Big-Ө Notation, Geometrical Interpretation and Examples

1.3. Recurrences

Recursive Algorithms and Recurrence Relations

Recursion Tree Method

Substitution Method

Application of Masters Theorem

2. Iterative Algorithms

4 hrs

2.1. Basic Algorithms

Algorithm for GCD

Fibonacci Number and analysis of their time and space complexity

2.2. Searching Algorithms

Sequential Search and its analysis

2.3. Sorting Algorithms

Bubble Sort and Analysis

Selection Sort and Analysis

Insertion Sort and Analysis

3. Divide and Conquer Algorithms

10 hrs

3.1. Searching Algorithms

Binary Search and Analysis

Min-Max Finding and Analysis

3.2. Sorting Algorithms

Merge Sort and Analysis

Quick Sort and Analysis (Best Case, Worst Case and Average Case)

Heap Sort (Heapify, Build Heap and Heap Sort Algorithms and their Analysis)

Randomized Quick sort and its Analysis

3.3. Order Statistics

Selection in Expected Linear Time and their Analysis

Selection in Worst Case Linear Time and their Analysis

4. Greedy Algorithms

4 hrs

4.1. Optimization Problems and Optimal Solution, Introduction of Greedy Algorithms, Elements of Greedy Strategy.

4.2. Greedy Algorithms

Fractional Knapsack

Job sequencing with Deadlines

Task Scheduling Algorithms able to designd their Time Complexity

4.3. Huffman Coding

Purpose of Huffman Coding

Prefix Codes

Huffman Coding Algorithm and its Analysis

5. Dynamic Programming

6 hrs

5.1. Greedy Algorithms vs Dynamic Programming, Recursion vs Dynamic Programming, Elements of DP Strategy

5.2. DP Algorithms

Matrix Chain Multiplication and Analysis

String Editing and Analysis

Zero-One Knapsack Problem and Analysis

Travelling Salesman Problem and Analysis

5.3. Memoization Strategy, Dynamic Programming vs Memoization

6. Graph Algorithms

8 hrs

6.1. Graph Representation

Adjacency List

Incidence Matrix

Efficiency Comparison

6.2. Graph Traversal

Breadth First Search and Analysis

Depth First Search and Analysis

6.3. Spanning Trees

Definition of MST

Kruskals Algorithm and Analysis

Prims Algorithm and Analysis

6.4. Shortest Path Algorithms

Bellman Ford Algorithm and Analysis

Dijkstra Algorithm and Analysis

Floyd Warshwall Algorithm and Analysis

7. Number Theoretic Algorithms

4 hrs

7.1. Number Theoretic Notations, GCD, Euclid's and Extended Euclid's Algorithms and their Analysis.

7.2. Definition of x modulo n, Solving Modular Linear Equations, Chinese Remainder Theorem

7.3. Primility Testing

Miller-Rabin Randomized Primility Test

8. NP Completeness

5 hrs

8.1. Tractable and Intractable Problems, Concept of Polynomial Time and Super Polynomial Time Complexity

8.2. Complexity Classes

NP-Hard

NP-Complete and NP Complete Problems

8.3. NP Completeness and Reducibility, Cooks Theorem, Proofs of NP Completeness (CNF-SAT, Vertex Cover and Subset Sum)

8.4. Approximation Algorithms

Concept

Vertex Cover Problem

Subset Sum Problem

Laboratory Works

Student should write programs, prepare lab sheet for each of the topics discussed in classes. Minimum 3 lab hour per week in required. In laboratory students should perform empirical analysis of different searching and sorting algorithms. Besides this students should implement greedy algorithms, DP algorithms and graph algorithms. Lab sheet of around 15 moderately large programming problems is recommended.

1.Empirical Analysis
2.Greedy Algorithms
3.Dynamic Programming
4.Graph Algorithms

Text Books

1.Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, 'Introduction to algorithms', Third Edition.. The MIT Press, 2009.

Reference Books

1.Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekiaran, 'Computer Algorithms', Second Edition, Silicon Press, 2007.
2.Kleinberg, Jon, and Eva Tardos, 'Algorithm Design', Addison-Wesley, First Edition, 2005

Notes:

This syllabus follows the official CSIT curriculum of Far Western University. In case of any doubt or revision, the university's published syllabus shall be considered authoritative. https://cdc.fwu.edu.np/faculties.html

Design and Analysis of Algorithm

Design and Analysis of Algorithm

Select University

Select Program

TabFlux . Design and Analysis of Algorithms . FWU . BSc. CSIT