Data Structures and Algorithms

Syllabus

1. Concept of data structure
   1. Introduction: data types, data structures and abstract data types
   2. Introduction to algorithms
2. The Stack and Queue
   1. Stack operation
   2. Stack application: Evaluation of Infix, Postfix and Prefix expressions
   3. Operations in queue, Enqueue and Dequeue
   4. Linear and circular queue
   5. Priority queue
3. List
   1. Definition
      1. Static and dynamic list structure
      2. Array implementation of lists
      3. Queues as list
4. Linked lists
   1. Dynamic implementation
   2. Operations in linked list
   3. Linked stacks and queues
   4. Doubly linked lists and its applications
5. Recursion
   1. Principle of recursion
   2. TOH and Fibonacci sequence
   3. Applications of recursion
6. Trees
   1. Concept
   2. Operation in Binary tree
   3. Tree search, insertion/deletions
   4. Tree traversals (pre-order, post-order and in-order)
   5. Height, level and depth of a tree
   6. AVL balanced trees and Balancing algorithm
   7. The Huffman algorithm
   8. B-Tree
   9. Red Black Tree
7. Sorting
   1. Types of sorting: internal and external
   2. Insertion and selection sort
   3. Exchange sort
   4. Merge and Redix sort
   5. Shell sort
   6. Heap sort as a priority queue
   7. Big ‘O’ notation and Efficiency of sorting
8. Searching
   1. Search technique
   2. Sequential, Binary and Tree search
   3. General search tree
   4. Hashing
      1. Hash function and hash tables
      2. Collision resolution technique
9. Growth Functions
   • Asymptotic notations: notations and their properties
10. Graphs
    1. Representation and applications
    2. Transitive closure
    3. Warshall’s algorithm
    4. Graphs type
    5. Graph traversal and Spanning forests
       1. Depth First Traversal and Breadth First Traversal
       2. Topological sorting: Depth first, Breadth first topological sorting
       3. Minimum spanning trees, Prim’s, Kruskal’s and Round-Robin algorithms
    6. Shortest-path algorithm
       1. Greedy algorithm
       2. Dijkstra’s Algorithm