Data Structures

Introduction to Data Structures: Information and Meaning – Representation of Multi- Dimensional Arrays _
Review of C Programming.
The Stack: Primitive operations – As an Abstract Data Type – Implementing the Stack operations in C.
Infix, Postfix and Prefix: Definitions, Evaluation and Conversions using C.
Recursion: Recursive Definition and Processes, Recursion in C and Recursive Implementation of Applications.
Simulation of Recursion – Efficiency of Recursion.
Queues and Lists: The Queue as Abstract Data Type – Sequential Representation _Types of Queues – Operations
– Implementation in C.
Linked List: Operations – Implementation of Stacks, Queues and priority Queues in C. Circular Lists: Insertion,
Deletion and Concatenation Operations _ Stacks and Queues as Circular Lists _ Doubly Linked Lists
_Applications.
Trees: Binary Trees Operations and Applications.
Binary Tree Representation: Node Representation – Implicit array Representation – Choice of Representation –
Binary Tree Traversal – Threaded Binary Trees and their Traversal – Trees and their Applications
Sorting: General Background: Efficiency – The big 0 Notation – Efficiency of Sorting. Bubble Sort and Quick
Sort and their Efficiency – Selection Sorting – Binary Tree Sort – Heap Sort – Insertion Sorts – Shell Sort –
Address calculation Sort – Merge and Radix Sorts.
Searching: Basic Searching Techniques: Dictionary as an Abstract Data Type – Algorithmic
Notation – Sequential Searching and its Efficiency – Binary Search – Interpolation Search.
Tree Searching: Insertion into a Binary Search Tree – Deleting from a Binary Search Tree – Efficiency of Binary
Search Tree operation
Graphs and Their Application: Graphs: Application of Graphs – Representation of Graphs in
C – Transitive closure – Warshall’s Algorithm – Shortest Path Algorithm.
Linked Representation of Graphs: Dijikstra’s Algorithm – Organizing the set of Graph
Nodes – Application to Scheduling and its implication.
Graph Traversal and Spanning Forests – Undirected Graph and their Traversals, Applications and Efficiency –
Minimal Spanning Trees –Prim’s and Kruskal’s Algorithms.