Course Objectives

This course aims to:

• Introduce the fundamental concepts of data structures and algorithms.
• Enable students to analyze the efficiency of algorithms.
• Teach students to select appropriate data structures for specific problems.
• Equip students with the skills to design and implement efficient algorithms.

Course Outcomes

Upon completion of this course, students will be able to:

1. Understand and implement various data structures like arrays, linked lists, stacks, queues, trees, and graphs.
2. Analyze the time and space complexity of algorithms.
3. Apply appropriate searching and sorting algorithms to solve problems efficiently.
4. Design and implement algorithms for various applications.
5. Choose suitable data structures and algorithms for specific problem scenarios.

Detailed Syllabus

Module 1: Introduction

Basic Terminology, Elementary Data Organization, Built-in Data Types, Abstract Data Types, Algorithms, Complexity of Algorithms, Asymptotic Notations, Time-Space tradeoff.

Module 2: Arrays and Structures

Arrays: Representation of Arrays, Single and Multidimensional Arrays, Address Calculation, Application of arrays, Sparse Matrices and their representations.

Structures: Declaration, initialization, accessing structures, operations on structures, nested structures, arrays of structures, structures and functions, unions.

Module 3: Stacks & Queues

Stacks: Array Representation and Implementation of Stacks, Operations on Stacks, Applications of Stacks: Expression Conversion and evaluation, Recursion, Linked representation of Stack

Queues: Array and linked representation and implementation of queues, various queue structures (circular queue, dequeue, priority queue), Operations on Queues, Applications of Queues.

Module 4: Linked Lists

Linked Lists: Representation of linked lists in memory, Operations on Linked Lists (Insertion, Deletion, Search), Types of Linked Lists (Singly Linked List, Doubly Linked List, Circular Linked List), Applications of linked lists.

Module 5: Trees

Basic terminology, Binary trees, Binary tree representation, Binary Search Trees, Tree traversal algorithms, Threaded binary trees, AVL Trees, Applications of trees.

Module 6: Sorting and Searching

Sorting: Selection Sort, Bubble Sort, Insertion Sort, Quick Sort, Merge Sort, Heap Sort, Radix Sort.

Searching: Linear Search, Binary Search.

Module 7: Graphs

Basic terminology, Graph representations (adjacency matrix, adjacency list), Graph Traversals (BFS, DFS), Applications of Graphs, Minimum Spanning Trees (Kruskal's and Prim's algorithms), Shortest Path Algorithms (Dijkstra's algorithm).

Module 8: Hashing

Hash tables, Hash functions, Collision resolution techniques (chaining, open addressing), Applications of hashing.

Suggested Readings/Books

• Data Structures using C by A.M. Tenenbaum, Langsam, Moshe J. Augentem
• Data Structures and Algorithm Analysis in C++ by Mark Allen Weiss
• Data Structures and Algorithms in Java by Adam Drozdek, Pearson Education
• Data Structures and Program Design in C by Robert Kruse, PHI
• Fundamentals of Data Structures by Ellis Horowitz & Sartaj Sahni
• Fundamentals of Computer Algorithms by Ellis Horowitz, Sartaj Sahni, and S. Rajasekaran

List of Experiments (Expandable)

1. Write a program to search an element from a list. Give user the option to perform Linear or Binary search.
2. Write a program to sort a list in ascending order. Give user the option to perform Selection sort, Bubble sort or Insertion sort.
3. Implement stack using array and linked-list. Give user the option to perform various operations on stack like push, pop, display.
4. Implement queue using array and linked-list. Give user the option to perform various operations on queue like enqueue, dequeue, display.
5. Write a program to convert infix expression to postfix expression and evaluate postfix expression.
6. Write a program to implement singly linked list. Give user the option to perform various operations on the linked list like create, insert, delete, display.
7. Write a program to implement doubly linked list. Give user the option to perform various operations on the doubly linked list like create, insert, delete, display.
8. Write a program to implement circular linked list. Give user the option to perform various operations on the circular linked list like create, insert, delete, display.
9. Write a program to implement Binary Search Tree. Give user the option to perform various operations on the binary search tree like insert, delete, inorder traversal, preorder traversal, postorder traversal.
10. Write a program to implement various graph traversal techniques like Breadth-First Search and Depth-First Search.

Course Outcomes

Upon completion of this lab, students will be able to:

1. Implement and experiment with different data structures in C/C++.
2. Implement various searching and sorting algorithms.
3. Analyze the performance of different algorithms.
4. Apply data structures and algorithms to solve real-world problems.