# 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 Duration : 12 weeks Start Date : 27 Jan 2020 End Date : 04 Apr 2020 Exam Date : 10 May 2020 IST Enrollment Ends : 08 Mar 2020 Category : Computer Science and Engineering Credit Points : 4 Level : Undergraduate

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

### 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.

### Course certificate

30% for internal Assessment & 70% for end term proctored exam.