Data Structures and Algorithms Syllabus | CT 552

Data Structures and Algorithms (CT 552)

Course Objectives

• To provide fundamental knowledge of various data structures and their implementation.
• To provide the fundamental knowledge of various algorithms and their analysis.

1. Concept of Data Structure (2 hours)

Topic	Sub-Topic
Introduction	Data types, data structures, and abstract data types
Introduction to Algorithms	Basic concepts of algorithms

2. The Stack and Queue (6 hours)

Topic	Sub-Topic
Stack Operations	Stack operations: Push, Pop, Top/Peek
Stack Applications	Evaluation of Infix, Postfix, and Prefix expressions
Queue Operations	Enqueue, Dequeue
Types of Queues	Linear queue, Circular queue, Priority queue

3. List (3 hours)

Topic	Sub-Topic
Definition of List	Static and dynamic list structures
Array Implementation	Array-based implementation of lists
Queues as List	Queues implemented as lists

4. Linked Lists (5 hours)

Topic	Sub-Topic
Dynamic Implementation	Linked list structure and its dynamic nature
Operations in Linked List	Insertion, deletion, traversal
Linked Stacks and Queues	Implementing stack and queue using linked lists
Doubly Linked Lists	Operations on doubly linked lists

5. Recursion (4 hours)

Topic	Sub-Topic
Principle of Recursion	Introduction to recursion
Applications of Recursion	TOH (Tower of Hanoi), Fibonacci sequence
General Applications	Use of recursion in problems solving

6. Trees (7 hours)

Topic	Sub-Topic
Binary Trees	Basic operations (insertion, deletion)
Tree Traversals	Pre-order, Post-order, In-order traversals
Tree Properties	Height, level, and depth of a tree
Balanced Trees	AVL Trees and balancing algorithms
Special Tree Algorithms	Huffman algorithm, B-Tree, Red-Black Tree

7. Sorting (5 hours)

Topic	Sub-Topic
Types of Sorting	Internal and external sorting
Basic Sorting Algorithms	Insertion sort, Selection sort, Exchange sort
Advanced Sorting	Merge sort, Radix sort, Shell sort, Heap sort
Sorting Efficiency	Big ‘O’ notation, Efficiency of sorting

8. Searching (5 hours)

Topic	Sub-Topic
Search Techniques	Sequential search, Binary search, Tree search
General Search Trees	Hashing and hash tables
Hash Functions	Hashing techniques and collision resolution

9. Growth Functions (2 hours)

Topic	Sub-Topic
Asymptotic Notations	O, O (big-O), o, and their properties

10. Graphs (6 hours)

Topic	Sub-Topic
Graph Representation	Matrix, adjacency list, and graph applications
Graph Algorithms	Transitive closure, Warshall’s algorithm
Graph Traversal	Depth-first search (DFS), Breadth-first search (BFS)
Minimum Spanning Trees	Prim’s and Kruskal’s algorithms
Shortest Path Algorithms	Dijkstra’s Algorithm, Greedy algorithm

---

Practical Lab Exercises

S.No	Exercise
1	Implementation of Stack
2	Implementation of Linear and Circular Queues
3	Solutions for TOH (Tower of Hanoi) and Fibonacci sequence using Recursion
4	Implementation of Linked Lists (Singly and Doubly Linked Lists)
5	Implementation of AVL Trees and balancing
6	Implementation of Merge Sort
7	Implementation of Search Algorithms (Sequential, Binary, and Tree Search)
8	Implementation of Graph Traversals (DFS, BFS)
9	Implementation of Hashing
10	Implementation of Heap

---

References

1. Y. Langsam, M. J. Augenstein, and A. M. Tenenbaum, Data Structures using C and C++, PHI. View Book

2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, PHI. View Book

3. G.W. Rowe, Introduction to Data Structure and Algorithms with C and C++, PHI. View Book

4. R. L. Kruse, B. P. Leung, C. L. Tondo, Data Structure and Program Design in C, PHI. View Book

5. G. Brassard and P. Bratley, Fundamentals of Algorithms, PHI. View Book