DATA STRUCTURES AND ALGORITHMS (CST-003)

About Course

Course Objectives: The objectives of this course are to:

1. Introduce the fundamentals of Data Structures, Abstract concepts and how these concepts are useful in
   problem-solving.
2. Analyze step by step and develop algorithms to solve real-world problems.
3. Implement various data structures, viz. Stacks, Queues, Linked Lists, Trees and Graphs.
4. Understand various searching & sorting techniques

Course Outcomes: On successful completion of the course, the student will be able to:

1. Compare functions using asymptotic analysis and describe the relative merits of worst-case, average case, and best-case analysis.
2. Become familiar with a variety of sorting algorithms and their performance characteristics (e.g., running
   time, stability, and space usage) and be able to choose the best one under a variety of requirements.
3. Understand and identify the performance characteristics of fundamental algorithms and data structures
   and be able to trace their operations for problems such as sorting, searching, selection, and operations on
   numbers, and graphs.
4. Solve real-world problems using arrays, stacks, queues, and linked lists.
5. Become familiar with the major graph algorithms and their analyses. Employ graphs to model
   engineering problems when appropriate.

—–Course Content—-

Unit 1-Introduction: Basic Terminologies:

Elementary Data Organizations, Data Structure Operations: insertion, deletion, traversal etc.; Analysis of an Algorithm, Asymptotic Notations, Time-Space trade-off.Searching: Linear Search and Binary Search Techniques and their complexity analysis.

Unit 2-Stacks and Queues:

ADT Stack and its operations: Algorithms and their complexity analysis, Applications of Stacks: Expression Conversion and evaluation – corresponding algorithms and complexity analysis. ADT queue, Types of Queues: Simple Queue, Circular Queue, Priority Queue; Operations on each type of Queues: Algorithms and their analysis.

Unit 3-Linked Lists: Singly linked lists:

Representation in memory, Algorithms of several operations: Traversing, Searching, Insertion into, and Deletion from the linked list; Linked representation of Stack and Queue, Header nodes, Doubly linked list: operations on it and algorithmic analysis; Circular Linked Lists: all operations their algorithms and complexity analysis.

Unit 4-Trees and Graphs:

Basic Tree Terminologies, Different types of Trees: Binary Tree, Threaded Binary Tree, Binary Search Tree, AVL Tree; Tree operations on each of the trees and their algorithms with complexity analysis. Applications of Binary Trees. B Tree, B+ Tree: definitions, algorithms and analysis.
Graphs: Basic Terminologies and Representations, Graph search and traversal algorithms and complexity analysis.

Unit 5-Sorting and Hashing:

Objective and properties of different sorting algorithms: Selection Sort, Bubble Sort, Insertion Sort, Quick Sort, Merge Sort, Heap Sort; Performance and Comparison among all the methods.

Hashing: Symbol table, Hashing Functions, Collision-Resolution Techniques