Syllabus of Andhra University BTech Computer Science Engineering - CSE 3.2.2 - Design and Analysis of Algorithms

Third year - Second Semester

Instruction: 3 Periods & 1 Tut /week
Univ. Exam : 3 Hours

Sessional Marks: 30
Univ-Exam-Marks:70

Introduction – Fundamentals of algorithmic problem solving – important problem types –fundamental data structures.

Fundamentals of analysis of algorithms and efficiency – Analysis framework – AsymptoticNotations and Basic Efficiency classes – Mathematical Analysis of Non-recursive Algorithms –Mathematical Analysis of recursive Algorithms – Empirical Analysis of Algorithms – Algorithm Visualization
Brute Force – Selection Sort and Bubble sort – Sequential Search and Brute – Force StringMatching – Closest Pair and Convex-Hull Problems by Brute Force – Exhaustive Search

Divide-and-Conquer – Mergesort – Quicksort – Binary Search – Binary Tree Traversals and Related Properties – Multiplication of large integers and Strassen’s Matrix Multiplication –Closest- Pair Convex-Hull Problems by Divide- and – Conquer

Decrease – and – Conquer – Insertion Sort – Depth-First Search and Breadth-First Search-Topological Sorting – Algorithms for Generating Combinatorial Objects – Decrease-by-a-Constant-Factor Algorithms – Variable-Size-Decrease Algorithms

Transform-and-Conquer – Presorting – Gaussian Elimination – Balanced Search Trees – Heapsand Heapsort – Horner’s Rule and Binary Exponentiation – Problem Reduction

Space and Time Tradeoffs – Sorting by Counting – Input Enhancement in string Matching –Hashing – B-Trees

Dynamic Programming – Computing a Binomial Coefficient – Warshall’s and Floyd’s Algorithm– Optimal Binary Search Trees - The Knapsack Problem and Memory Functions.

Greedy Technique – Prim’s Algorithm – Kruskal’s Algorithm – Dijkstra’s Algorithm – Huffman Trees Limitations of Algorithm Power – Lower-Bound Arguments – Decision Trees – P, NP and NP – completeproblems – Challenges of Numerical Algorithms

Coping with the Limitations of Algorithms Power – Backtracking – Branch-and-Bound –Approximation Algorithms for NP-hard Problems – Algorithms for solving Nonlinear Equations.

Text Book:

Introduction to Design & Analysis of Algorithms by Anany Levitin, Pearson Education, NewDelhi, 2003

Reference Books:

1. Introduction to Algorithms by Thomas H. Corman, Charles E. Leiserson, Ronald R. Rivest &Clifford Stein, Prentice Hall of India, New Delhi, New Delhi

2. The Design and Analysis of computer Algorithms, Aho, Hopcroft & Ullman, PearsonEducation, New Delhi, 2003

3. Fundamentals of algorithmics, Gilles Brassard & Paul Bratley, Prentice Hall of India, New Delhi