The Complete 18CS42  Design and Analysis of Algorithms. Notes
 4.9

2018 Scheme  CSE Department
 Created by AcquireHowTo
 5 Modules
Description
Important Topics Covered
What is an Algorithm? Algorithm Specification, Analysis Framework. Performance Analysis such as Space complexity, Time complexity. Asymptotic Notations such as BigOh notation (O), Omega notation (?), Theta notation (?), and Littleoh notation (o).
Mathematical analysis of NonRecursive and recursive Algorithms with Examples. Important Problem Types: Sorting, Searching, String processing, Graph Problems, Combinatorial Problems. Fundamental Data Structures, Stacks, Queues, Graphs, Trees, Sets, and Dictionaries.
Divide and Conquer, A general method, Binary search, Recurrence equation for divide and conquer, Finding the maximum and minimum. Merge sort, Quicksort, Strassen’s matrix multiplication. Advantages and Disadvantages of divide and conquer.
Greedy Method:General method, Coin Change Problem, Knapsack Problem, Job sequencing with deadlines. Optimal Tree problem and Transform and Conquer Approach.
The general method with Examples, Multistage Graphs of Dynamic Programming. Floyd’s Algorithm, Optimal Binary Search Trees, Knapsack problem. Backtracking, Branch and Bound, and NPComplete and NPHard problems.
Powered by Froala Editor
What You’ll Learn
Module 1
Introduction:What is an Algorithm? (T2:1.1), Algorithm Specification (T2:1.2), Analysis Framework (T1:2.1), Performance Analysis: Space complexity, Time complexity (T2:1.3). Asymptotic Notations: BigOh notation (O), Omega notation (?), Theta notation (?), and Littleoh notation (o), Mathematical analysis of NonRecursive and recursive Algorithms with Examples (T1:2.2, 2.3, 2.4). Important Problem Types: Sorting, Searching, String processing, Graph Problems, Combinatorial Problems. Fundamental Data Structures: Stacks, Queues, Graphs, Trees, Sets and Dictionaries. (T1:1.3,1.4).
Module 2
Divide and Conquer:A general method, Binary search, Recurrence equation for divide and conquer, Finding the maximum and minimum (T2:3.1, 3.3, 3.4), Merge sort, Quicksort (T1:4.1, 4.2), Strassen’s matrix multiplication (T2:3.8), Advantages and Disadvantages of divide and conquer.
Decrease and Conquer Approach: Topological Sort. (T1:5.3).
Module 3
Greedy Method:General method, Coin Change Problem, Knapsack Problem, Job sequencing with deadlines (T2:4.1, 4.3, 4.5).Minimum cost spanning trees: Prim’s Algorithm, Kruskal’s Algorithm (T1:9.1, 9.2).
Single source shortest paths: Dijkstra's Algorithm (T1:9.3).
Optimal Tree problem: Huffman Trees and Codes (T1:9.4).
Transform and Conquer Approach: Heaps and Heap Sort (T1:6.4).
Module 4
Dynamic Programming: General method with Examples, Multistage Graphs (T2:5.1, 5.2).Transitive Closure: Warshall’s Algorithm, All Pairs Shortest Paths: Floyd's Algorithm, Optimal Binary Search Trees, Knapsack problem ((T1:8.2, 8.3, 8.4), BellmanFord Algorithm (T2:5.4), Travelling Sales Person problem (T2:5.9), Reliability design (T2:5.8).
Module 5
Backtracking: General method (T2:7.1), NQueens problem (T1:12.1), Sum of subsets problem (T1:12.1), Graph coloring (T2:7.4), Hamiltonian cycles (T2:7.5). Branch and Bound: Assignment Problem, Travelling Sales Person problem (T1:12.2), 0/1 Knapsack problem (T2:8.2, T1:12.2): LC Branch and Bound solution (T2:8.2), FIFO Branch andBound solution (T2:8.2). NPComplete and NPHard problems: Basic concepts, nondeterministic algorithms, P, NP, NPComplete, and NPHard classes (T2:11.1).
Powered by Froala Editor
Course Curriculum & Downloads Module Wise
Course Faq
 Can we download the notes?
Yes, you can download the notes by going to the Module Topics and clicking on the View/Download Module Notes.
 How often notes are updated on AcquireHowTo?
We try our best to provide update notes to our users, so we keep updating them once a week.
 Do you provide only one specific university note?
No, Our team tries to work hard to provide notes from multiple universities like VTU, IP, DTU, Amity, etc, and from multiple courses like B.E, B.Tech, BBA, MBA, BCA, etc.
 Do the Notes you provide belongs to you?
No, the notes we provide belong to the only creator of that notes. May some note belongs to us but not all. AcquireHowTo is a notes providing platform that provide notes from different sources at one place to help the students.
Announcement
AcquireHowTo
Admin 1 year agoUpcomming Updates of the AcquireHowTo
  CGPA/SGPA Calculator with University Filter.
  Student Projects Guide and Download.
  Article Publishing platform for different categories.
  Courses for students on different topics.
  Student Dashboard for AcquireHowTo Products.
  Online Portal to buy Minor Projects and Major Projects.
  Last year Exams Question paper .
These all updates are comming soon on our portal. Once the updates roll out you will be notified.
COURSE INCLUDES
CSE Deptartment  4th Sem
CSE Deptartment  4th Sem
CSE Deptartment  4th Sem
CSE Deptartment  4th Sem
CSE Deptartment  4th Sem