DS4007 Design and Analysis of Computer Algorithms Syllabus:
DS4007 Design and Analysis of Computer Algorithms Syllabus – Anna University PG Syllabus Regulation 2021
COURSE OBJECTIVES:
To understand the usage of algorithms in computing.
To learn the usage of graphs and its applications.
To select and design data structures and algorithms that is appropriate for problems.
To study the main classes of fundamental parallel algorithms.
To study the design of algorithms.
UNIT I ROLE OF ALGORITHMS IN COMPUTING
Basics of algorithm: Writing – Analysis – Design, Mathematical analysis of recursive algorithm – Growth of Functions: Asymptotic Notation – Standard Notations and Common Functions- Recurrences: The Substitution Method – The Recursion-Tree Method
UNIT II DATA STRUCTURE FOR SET MANIPULATION
Binary Search Trees: Basics – Querying a Binary search tree – Insertion and Deletion – Red-Black trees: Properties of Red-Black Trees – Rotations – Insertion – Deletion -B- Trees: Definition of B Trees – Basic operations on B-Trees – Deleting a key from a B-Tree- Fibonacci Heaps: structure – Mergeable-heap operations- Decreasing a key and deleting a node-Bounding The Maximum Degree.
UNIT III GRAPHS
Elementary Graph Algorithms: Representations of Graphs – Breadth-First Search – Depth-First Search – Topological Sort – Strongly Connected Components- Minimum Spanning Trees: Growing a Minimum Spanning Tree – Kruskal and Prim- Single-Source Shortest Paths: The Bellman-Ford algorithm – Single-Source Shortest paths in Directed Acyclic Graphs – Dijkstra‘s Algorithm; All Pairs Shortest Paths: Shortest Paths and Matrix Multiplication – The Floyd Warshall Algorithm.
UNIT IV INTRODUCTION TO PARALLEL ALGORITHMS
Introduction – Models of computation – Selection – Merging on EREW and CREW – Median of two sorted sequence – Fast Merging on EREW – Analyzing Parallel Algorithms
UNIT V ALGORITHM DESIGN TECHNIQUES
Dynamic Programming: Matrix-Chain Multiplication – Elements of Dynamic Programming – Longest Common Subsequence- Greedy Algorithms: An Activity-Selection Problem – Elements of the Greedy Strategy- Huffman Codes.
COURSE OUTCOMES:
CO1:Design data structures and algorithms to solve computing problems.
CO2:Design algorithms using graph structure and various string matching algorithms to solve real-life problems.
CO3:Understand the difference between sequential and parallel algorithms.
CO4:Design parallel algorithms in various models of parallel computation.
CO5:Apply suitable design strategy for problem solving.
TOTAL:45 PERIODS
REFERENCES
1. Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman, “Data Structures and Algorithms”, Pearson Education, Reprint 2006.
2. Robert Sedgewick and Kevin Wayne, “ALGORITHMS”, Fourth Edition, Pearson Education.
3. S.Sridhar,”Design and Analysis of Algorithms”, First Edition, Oxford University Press. 2014.
4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”, Third Edition, Prentice-Hall, 2011.
5. Selim G. Akl, “The Design and Analysis of Parallel Algorithms”, Prentice Hall, New Jersey,1989.
6. Michael J. Quinn, “Parallel Computing: Theory & Practice”, Tata McGraw Hill Edition, 2003.
7. Joseph JaJa, “Introduction to Parallel Algorithms”, Addison-Wesley, 1992