Course

Lab Component:

Topic 1: Sorting – Searching
1.1 Write a program to implement Bubble Sort.
1.2 Write a program to implement selection sort.
1.3 Write a program to implement Quick Sort.
1.4 Write a program to implement Insertion Sort.
1.5 Write a program to implement Merge Sort.
1.6 Write a program to implement Binary Search.

Topic 2: Arrays –Stacks-Recursion
1.7 Write and test a function that transposes a square matrix.
1.8 Write and test a recursive function that prints all the permutations of the first n characters of a string.
1.9 Write and test a recursive function that returns the power xn
1.10 Write a program to implement a stack of strings (illustrate the operations push (), pop(),size(), empty() and top()).
1.11 Write a program to show the linked implementation of the Stack class.
1.12 Write a program to covert infix to postfix.
1.13 Write a program to implement Towers of Hanoi using Stack. Queues-Linked-Lists
1.14 Write a program to implement a linear list and perform the operation such as insert(),search() and delete().
1.15 Write a program to implement a queue by adding the functions such as
1.15.i Determine the size
1.15.ii input queue
1.15.iii output a queue
1.15.iv split a queue into two queues
1.16 Write a program to search a circular linked list with a header node.

Topic 3: Binary Trees – Binary Tree Traversal
1 Write a program to implement Binary Search Tree.
2 Priority queue implementation.
3 Write a program to create a binary tree and find the height of a binary tree.
4 Write a program to perform the binary tree traversals.
5 Write a program to perform a deletion from a Binary Tree (using a delete () function).

Topic 4: Graphs
6 Matrix representation of graphs
7 DFS traversal
8 BFS traversal

Unit I

Algorithm Analysis

Mathematical preliminaries; Efficiency of algorithms – notion of time and space complexity, Basic Complexity Analysis – Worst case, Average case and Best cases, Asymptotic Analysis- notations, analysing iterative programs– Simple examples; Recurrences, Analysis of Divide and conquer algorithms – Merge sort, Substitution Method, Master method.

Unit II

Searching and Sorting

Linear Search, Binary Search – Analysis

Bubble Sort, Insertion Sort, Merge sort, Quick Sort – Analysis

Unit III

Linear Data Structures

Abstract Data Type, List ADT: Singly linked lists, Doubly linked lists, Circular Linked Lists, Stack ADT implementation and applications, Queue ADT: Implementation and Application. Circular Queue, Priority Queue

Unit IV

Non-Linear Data Structures

Basic concepts of trees, Implementation of trees, Traversal, Binary tree, Expression tree, Binary search tree, AVL tree, Heaps.

Unit V

Graphs

Adjacency matrix, Adjacency list, Breadth First Search, Depth First Search, Minimum Spanning Tree- Prim’s and Kruskal’s Algorithm, Dijkstra’s algorithm

Course Outcomes

Textbooks:

1) Mark Allen Weiss, “Data Structures and Algorithm Analysis in C”, Second Edition, Pearson Education
References:

1) Samanta, Debasis. Classic Data Structures. PHI Learning Pvt. Ltd., 2004.
2) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rdedition, MIT Press, 2009