Design and Analysis of algorithms

By Dr. Faheem Syeed Masoodi | University of Kashmir

Learners enrolled: 6392

Algorithms are essential in solving large scale problems and there may exist one or more than one algorithm for a specific problem. It is always desirous to reduce the time and maximize the performance while solving a problem and as such, we need to analyze these algorithms for correctness and efficiency in terms of time and space.

The “design” part of this course shall lay more emphasis on the key aspects in the development of new algorithms and the “analysis” part shall help you to better understand what resources an algorithm may use to reach a solution.

We have structured this course in four units within which the topics that shall be broadly covered include: Introduction to algorithm, asymptotic complexity, sorting and searching using divide and conquer, greedy method, dynamic programming, backtracking, branch and bound. Lower bound theory and approximation algorithms

Summary

Course Status :	Completed
Course Type :	Core
Language for course content :	English
Duration :	12 weeks
Category :	Computer Science and Engineering
Credit Points :	4
Level :	Undergraduate
Start Date :	27 Jan 2020
End Date :	04 Apr 2020
Enrollment Ends :	08 Mar 2020
Exam Date :	10 May 2020 IST

Note: This exam date is subject to change based on seat availability. You can check final exam date on your hall ticket.

Page Visits

Course layout

WEEK 1

01 - Introduction to Algorithms

02 - Analysis of algorithms

03 - Growth of functions

04 - Asymptotic notations

WEEK 2

05 - Operations and properties of asymptotic notations

06 - Recurrences (Substitution method)

07 - Iteration method & Recursion trees

08 - Solving Recurrences (Decreasing Functions)

WEEK 3

09 - Solving recurrences (Dividing functions)

10 - The Master Method

11 - Divide and Conquer: Binary Search

12 - MAX MIN.

WEEK 4

13 - Quick Sort

14 - Merge Sort

15 - Greedy Method: Job sequencing

16 - Fractional Knapsack method

WEEK 5

17 - Huffman codes

18 - Optimal storage on tapes

19 - Dynamic programming (General method)

20 - Multistage graphs

WEEK 6

21 - Longest common subsequences

22 - Dynamic Programming (All Pairs Shortest Paths)

23 - Backtracking (General methods)

24 - N-Queens Problem

WEEK 7

25 - Sum of subsets

26 - 0/1 Knapsack problem

27 - Branch and Bound (General method)

28 - Least Cost Branch and Bound

WEEK 8

29 - Traveling salesperson problem Using LCBB

30 - Lower bound theory through reductions

31 - P, NP, NP hard and NP complete problems _ basic concepts.

32 – Approximate Algorithms

WEEK 9

33 – The set veering problem

34 - The traveling salesman problem

35 - The Vertex Cover Problem

36 - The subset sum problem

WEEK 10

37 - Parallel Algorithms, Parallelism_ PRAM and other Models

Books and references

• Computer Algorithms by Horowitz & Sahni

• Introduction to Algorithms by Thomas H. Cormen

• Algorithm Design by Jon Kleinberg and Éva Tardos

• Computer Algorithms by Sara Base and Allen Van Gelder

• Fundamentals of Algorithms by Gilles Brassard and Paul Bratley

• Data Structure and Algorithms by G A V PAI

Instructor bio

Dr. Faheem Syeed Masoodi

University of Kashmir

Dr. Faheem Syeed Masoodi is currently working as an Assistant Professor in the Department of Computer Science, Kashmir University. Earlier, he served College of Computer Science, University of Jizan, Saudi Arabia as an Assistant Professor. Prior to that, he performed his duties as a Research Scientist at NMEICT-Edrp project sponsored by Ministry of HRD, Govt. of India in 2015.

He was awarded PhD in the domain of Network Security & cryptography by the Department of Computer Science, Aligarh Muslim University India in year 2014 and did his masters in computer sciences from university of Kashmir. His basic research interests include Cryptography & Network Security; and Internet of things (IOT). He is a Professional member of many Cryptology Associations and has published nine research papers in reputed journals and conferences. He has been Awarded fellowship for Summer Training “Conference effective moduli spaces and application to cryptography” organized by CENTRE HENRI LEBESGUE, Rennes, France in 2014 and was also awarded fellowship for Summer School “SP-ASCRYPTO-2011 Advance School of Cryptography” at University of Campinas, Sao Paulo, Brazil in 2011. He was also awarded Maulana Azad National Fellowship for his Doctorate programme by UGC New Delhi.