Course Prerequisites: Introduction to Computer Programming, Fundamentals of Data Structure.

Course Objective:
This course will provide insights of advanced data structures and algorithms from which students will able to handle massive data by various algorithms and solve problems using linear and non-linear data structures.   

​

Course Outcome: After successful completion of the course, students will be able to:

CO1: Define the syntax of a programming language

CO2: Describe the functionalities of various data structures.

CO3: Develop programs to perform operations on data structures for a given task.

CO4: Examine the data structure programs for successful completion of the operation.

​

Course Contents:

UNIT-I: Introduction to C++ and Algorithms

Introduction to C++: Variables, Constants, Flow of control, Functions, Arrays, Strings, Pointer, Classes, Memory management. Algorithm Specification: Introduction to the algorithm, Algorithm Design, Analyzing an algorithm, Algorithm Design Approach, Pseudo code Conventions

​

UNIT-II: Sorting Algorithms

Types of sorting-Internal and external sorting, General sort concepts order, stability, number of passes, Sorting Algorithms: Merge Sort, Quick sort, Radix sort, Bucket sort, Heap sort, Shell sort.

 

UNIT-III: Linked List

​Concept of linked organization, comparison of sequential organization with linked organization, singly linked list, stack using linked list, queue using linked list, doubly linked list, circular linked list. Representation and manipulations of polynomials using linked lists.

 

UNIT-IV: Efficient Binary Trees

Binary Search Trees (BST): Basic Concepts, BST operations, Threaded Binary Tree, AVL Trees, M-way Search Trees, B-Trees, B+ Trees, Red-black Tree, Splay Tree.

 

UNIT-V: Graph

Graph theory, traversing a graph, Topological sorting, Spanning trees, Minimum Spanning tree, Kruskal’s Algorithm, Prim’s Algorithm, Dijkstra's Shortest Path Algorithm, Bellman-Ford, All-Pairs Shortest Paths: Floyd-Warshall’s Algorithm.

 

UNIT-VI: Hashing

General Idea, Hash Function, Separate Chaining, Hash Tables without linked lists: Linear Probing, Quadratic Probing, Double Hashing, Rehashing, Hash Tables in the Standard Library, Universal Hashing, Extendible Hashing.