Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
This article presents the detailed Syllabus of the subject "Design and Analysis of Algorithms (DAA)" also known as "Data Structure and Algorithms (DSA)". This subject is taught in Bachelor of Science or Bachelor of Technology course in Computer Science. This is the most important subject in Computer Science.
Table of contents:
- Syllabus of "Design and Analysis of Algorithms"
This article includes the complete list of Algorithm and Data Structure topics.
Syllabus of "Design and Analysis of Algorithms"
Data Structure and Algorithm (DSA) Syllabus | |
|---|---|
| 1. Introduction to Data Structure | |
| 1.1 | Introduction to Data Structures |
| 1.2 | Abstract Data Type (ADT) Definition, Examples |
| 1.3 | Introduction to Array ADT |
| 1.4 | Linked List ADT insert, delete, search, types of Linked List |
| 1.5 | Stack ADT push, pop, types of Stack |
| 1.6 | Queue ADT enqueue, deque, types of Queue |
| 2. Introduction to Algorithm + Sorting | |
| 2.1 | Introduction to Algorithms |
| 2.2 | Asymptotic analysis Big-O, Big-Theta and other notations, worst, average and best case analysis |
| 2.3 | Euclid's GCD Algorithm Basic and Extended Algorithms |
| 2.4 | Primality testing SQRT(N) test, Fermat primality test, Miller Rabin test, Sieve of Eratosthenes, Sieve of Atkin |
| 2.5 | Search Algorithms Linear Search, Binary Search, Interpolation Search |
| 2.6 | Basic Sorting Algorithms Selection Sort, Insertion Sort, Bubble Sort, Merge Sort, Quick Sort, Heap Sort, Time Complexity analysis of Sorting Counting Sort, Radix Sort, Bucket Sort |
| 3. Tree Data Structures | |
| 3.1 | Binary Tree ADT Basic terms: Complete BT, Balanced, Unbalanced BT, Insert, Delete, Traverse, Inorder, Postorder, Preorder |
| 3.2 | Self Balancing Binary Tree ADT AVL Tree, Red Black Tree, 2-3 Tree, AA Tree, Scapegoat Tree, Splay Tree, Treap |
| 3.3 | Trie ADT Applications to String problems |
| 3.4 | N-dimensional Tree ADT B Tree, B+ Tree |
| 3.5 | Heap Data Structures ADT Min Heap, Max Heap, Priority Heap, Fibonacci Heap |
| 3.6 | Advanced Data Structures ADT Segment Tree, Fenwick Tree, Cartesian Tree |
| 4. Analysis of Algorithms | |
| 4.1 | Complexity Notations Big-O, Big-Omega, Big-Theta and others |
| 4.2 | Complexity Analysis techniques Master theorem, Substitution Method, Iteration Method |
| 4.3 | Time Complexity Bound for Sorting Comparison Sort, Non-comparison sort |
| 4.4 | Time Complexity Bound for Searching Linear Search, Binary Search, Interpolation Search |
| 4.5 | Complexity Classes P class, NP-Complete, NP-Hard, P=NP problem |
| 5. Graph Algorithms | |
| 5.1 | Adjacency Matrix and Adjacency List |
| 5.2 | Shortest Path Algorithms Dijkstra's algorithm, Floyd-Warshall Algorithm, Bellman-Ford Algorithm, Johnson Algorithm |
| 5.3 | Minimum Spanning Tree Kruskal's Algorithm, Boruvka's Algorithm, Prim's Algorithm, Cheriton Tarjan's Algorithm |
| 5.4 | Graph Coloring Algorithm Greedy Algorithm, Welsh Powell Algorithm, Wigderson Algorithm |
| 5.5 | Cut edge, Cut node |
| 6. Other Algorithmic Techniques | |
| 6.1 | Dynamic Programming Dice Throw Problem, Assembly Line Scheduling, Subset Sum Problem, Longest Palindromic Subsequence, Word Break Problem, Word Wrap Problem |
| 6.2 | Greedy Algorithms Activity Selection Problem, Knapsack problem + variants, Bin Packing problem, Weighted Job scheduling |
| 6.3 | Backtracking 8 Queens Problem, Knight's Tour Problem |
| 6.4 | Divide and Conquer Closest Pair of Points, Karatsuba Algorithm, Median of Medians, Meet In Middle Technique |
With this detailed syllabus, you know that topics you must have a good hold on to ace your "Design and Analysis of Algorithms" examination in B. Tech/ B. Sc course work.
