Design and Analysis of Algorithms, a very important subject introduced in the 6th semester of Information Technology Engineering and 7th Semester of Computer Engineering of Pune University. The syllabus for Computer and IT is not same, Computer Engineering Syllabus is a bit more than IT. Infact , Computer's syllabus is a strict superset of the IT syllabus.
The subject is really interesting and logical. Totally conceptual but time consuming subject. Too many algorithms in the subject make the course a bit confusing. Relatively easy to score and easy to learn subject. Scoring 65+ in this subject is not a difficult task.
Books Recommended :
Foreign Authors :
Fundamentals of computer Algorithms - Horowitz and Sahani
Local Authors : DAA - (Technical Publications)
Algorithms are relatively easy to understand from Nirali.
Techmax would not be good choice for DAA.
Syllabus for Computer Engineering.
Unit I
Asymptotic notations, necessary mathematical foundation, introduction to Algorithm, Algorithm specifications, Performance analysis, Review of proof techniques: Contradiction and Mathematical induction, Solving Recurrence Equations. Introduction to NP-Hard And NP-Complete Problems, Divide And Conquer And Greedy Strategy, Performance analysis of Algorithmic Strategies Divide and Conquer: General Strategy, Exponentiation, Quick Sort and Merge Sort. Greedy Method: General Strategy, Knapsack problem, Job sequencing with Deadlines, Optimal merge patterns, Minimal Spanning Trees and Dijkstra's algorithm.
Unit II
Dynamic Programming, Study of different ways to implement Knapsack Problem. Implementation of OBST, Traveling Salesperson Problem. General Strategy, Multistage graphs, OBST, 0/1 Knapsack, Traveling Salesperson Problem, Flow Shop Scheduling.
6 Unit III Backtracking: General Strategy, 8 Queen's problem, Graph Coloring, Hamiltonian Cycles, 0/1 Knapsack. Branch and Bound: General Strategy, 0/1 Knapsack, Traveling Salesperson Problem. Design of N Queen's problem, Hamiltonian Cycles
Unit IV
Basic Concepts: Non deterministic algorithms, The classes NP Hard and NP Complete, Cook's Theorem, NP Hard graph problems: Clique Decision problem, Node cover Decision problem, Chromatic number decision problem, Directed Hamiltonian Cycle Problem, TSP Decision problem, AND/OR Graph decision problem, NP-Hard Scheduling problems: Scheduling Identical processors, Flow shop scheduling, Job shop scheduling. NP-Hard Scheduling. Study of NP-Hard and NP-COMPLETE problems. Solving NP-COMPLETE problem.
Unit V
Parallel Algorithms, Study of different graph problems. Implementation of different sorting problems on multiprocessor system. Computational Model, Basic Techniques and Algorithms, Complete Binary Tree, Pointer Doubling, Prefix Computation, Selection, Merging, Sorting, Graph Problems.
Unit VI
Case Studies of Algorithmic Designs & Applications, Implementation of Huffman Problem. Deadlock detection and avoidance implementation. Image edge detection algorithms, Resource allocation algorithm with deadlock avoidance, Heuristic search algorithm, Coding theory algorithm (Huffman coding), Sorting & Convex hulls algorithm. Review and interactive discussions on home tutorials, classroom tutorials and students presentation. Review of recent advances in the subject
Syllabus for IT Engineering
Unit I Introduction
Analysis of Algorithm Efficiency:- Analysis framework – Asymptotic notations – Analysis of Non-recursive and recursive algorithms. Amortized Analysis, Writing characteristic Polynomial equations, Solving Recurrence Equations, Proof Techniques: by Contradiction, by Mathematical Induction, direct proofs, proof by counterexample, proof by contraposition.
Unit II Divide and Conquer and The Greedy Method
Characteristic; Analysis Methodology:- Merge sort – Quick Sort – Binary search – Large integer Multiplication and Strassen’s Matrix multiplicationclosest pair and convex Hull problems The Greedy Method : General characteristics of greedy algorithms, Prim’s and kruskal’s Algorithms, Dijkstra’s Algorithm, Huffman Trees.
Unit III Dynamic Programming
General strategy, Principle of optimality, Warshall’s and Floyd’s Algorithm – Optimal Binary Search Trees – knapsack Problem
Unit IV Backtracking
General method— Recursive backtracking algorithm, iterative backtracking method. 8-queens problem, sum of subsets and Graph coloring, Hamiltonian cycle and Knapsack Problem.
Unit V Branch-Bound
The method, Least Cost Search, FIFO branch and bound, LC branch and bound. 0/1 Kanpsack problem –LC branch and bound and FIFO branch and bound solution. Traveling sales person problem.
Unit VI NP-Hard and NP-Complete Problems
Basic concepts, Non deterministic Algorithms, The classes of NP hard and NP complete, Cooks Theorem.
NP-Complete problems- Satisfiability problem, vertex cover problem. NP-Hard problems-graph, scheduling, code generation problems, Simplified NP hard Problems.
Books for Download
The subject is really interesting and logical. Totally conceptual but time consuming subject. Too many algorithms in the subject make the course a bit confusing. Relatively easy to score and easy to learn subject. Scoring 65+ in this subject is not a difficult task.
Books Recommended :
Foreign Authors :
Fundamentals of computer Algorithms - Horowitz and Sahani
Local Authors : DAA - (Technical Publications)
Algorithms are relatively easy to understand from Nirali.
Techmax would not be good choice for DAA.
Syllabus for Computer Engineering.
Unit I
Asymptotic notations, necessary mathematical foundation, introduction to Algorithm, Algorithm specifications, Performance analysis, Review of proof techniques: Contradiction and Mathematical induction, Solving Recurrence Equations. Introduction to NP-Hard And NP-Complete Problems, Divide And Conquer And Greedy Strategy, Performance analysis of Algorithmic Strategies Divide and Conquer: General Strategy, Exponentiation, Quick Sort and Merge Sort. Greedy Method: General Strategy, Knapsack problem, Job sequencing with Deadlines, Optimal merge patterns, Minimal Spanning Trees and Dijkstra's algorithm.
Unit II
Dynamic Programming, Study of different ways to implement Knapsack Problem. Implementation of OBST, Traveling Salesperson Problem. General Strategy, Multistage graphs, OBST, 0/1 Knapsack, Traveling Salesperson Problem, Flow Shop Scheduling.
6 Unit III Backtracking: General Strategy, 8 Queen's problem, Graph Coloring, Hamiltonian Cycles, 0/1 Knapsack. Branch and Bound: General Strategy, 0/1 Knapsack, Traveling Salesperson Problem. Design of N Queen's problem, Hamiltonian Cycles
Unit IV
Basic Concepts: Non deterministic algorithms, The classes NP Hard and NP Complete, Cook's Theorem, NP Hard graph problems: Clique Decision problem, Node cover Decision problem, Chromatic number decision problem, Directed Hamiltonian Cycle Problem, TSP Decision problem, AND/OR Graph decision problem, NP-Hard Scheduling problems: Scheduling Identical processors, Flow shop scheduling, Job shop scheduling. NP-Hard Scheduling. Study of NP-Hard and NP-COMPLETE problems. Solving NP-COMPLETE problem.
Unit V
Parallel Algorithms, Study of different graph problems. Implementation of different sorting problems on multiprocessor system. Computational Model, Basic Techniques and Algorithms, Complete Binary Tree, Pointer Doubling, Prefix Computation, Selection, Merging, Sorting, Graph Problems.
Unit VI
Case Studies of Algorithmic Designs & Applications, Implementation of Huffman Problem. Deadlock detection and avoidance implementation. Image edge detection algorithms, Resource allocation algorithm with deadlock avoidance, Heuristic search algorithm, Coding theory algorithm (Huffman coding), Sorting & Convex hulls algorithm. Review and interactive discussions on home tutorials, classroom tutorials and students presentation. Review of recent advances in the subject
Syllabus for IT Engineering
Unit I Introduction
Analysis of Algorithm Efficiency:- Analysis framework – Asymptotic notations – Analysis of Non-recursive and recursive algorithms. Amortized Analysis, Writing characteristic Polynomial equations, Solving Recurrence Equations, Proof Techniques: by Contradiction, by Mathematical Induction, direct proofs, proof by counterexample, proof by contraposition.
Unit II Divide and Conquer and The Greedy Method
Characteristic; Analysis Methodology:- Merge sort – Quick Sort – Binary search – Large integer Multiplication and Strassen’s Matrix multiplicationclosest pair and convex Hull problems The Greedy Method : General characteristics of greedy algorithms, Prim’s and kruskal’s Algorithms, Dijkstra’s Algorithm, Huffman Trees.
Unit III Dynamic Programming
General strategy, Principle of optimality, Warshall’s and Floyd’s Algorithm – Optimal Binary Search Trees – knapsack Problem
Unit IV Backtracking
General method— Recursive backtracking algorithm, iterative backtracking method. 8-queens problem, sum of subsets and Graph coloring, Hamiltonian cycle and Knapsack Problem.
Unit V Branch-Bound
The method, Least Cost Search, FIFO branch and bound, LC branch and bound. 0/1 Kanpsack problem –LC branch and bound and FIFO branch and bound solution. Traveling sales person problem.
Unit VI NP-Hard and NP-Complete Problems
Basic concepts, Non deterministic Algorithms, The classes of NP hard and NP complete, Cooks Theorem.
NP-Complete problems- Satisfiability problem, vertex cover problem. NP-Hard problems-graph, scheduling, code generation problems, Simplified NP hard Problems.
Books for Download
Fundamentals of Computer Algorithms
(Software to view DJVU Files)
Introduction to Algorithms - Cormen
-------------------------------------------------
Video Lectures
Introduction to Algorithms ( MIT)
Dynamic Programming , Knapsack
Binary, Selection Sort Analysis
Average Case Analysis of Quick Sort
Quick Sort
Bubble Sort - Analysis
=============================
