Course

Unit 1

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 2

Searching and Sorting

 Linear Search, Binary Search – Analysis

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

Unit 3

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 4

Non-Linear Data Structures

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

Unit 5

Graphs

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

Lab Component:

Topic 1: Sorting – Searching

• Write a program to implement Bubble
• Write a program to implement selection
• Write a program to implement Quick
• Write a program to implement Insertion
• Write a program to implement Merge
• Write a program to implement Binary

Topic 2: Arrays –Stacks-Recursion

• Write and test a function that transposes a square
• Write and test a recursive function that prints all the permutations of the first n characters of a
• Write and test a recursive function that returns the power xⁿ
• Write a program to implement a stack of strings (illustrate the operations push (), pop(),size(), empty() and top()).
• Write a program to show the linked implementation of the Stack
• Write a program to covert infix to
• Write a program to implement Towers of Hanoi using Stack

Queues-Linked-Lists

• Write a program to implement a linear list and perform the operation such as insert(),search() and delete().
• Write a program to implement a queue by adding the functions such as
  • Determine the size
  • input queue
  • output a queue
  • split a queue into two queues
• Write a program to search a circular linked list with a header

Topic 3: Binary Trees – Binary Tree Traversal

• Write a program to implement Binary Search
• Priority queue
• Write a program to create a binary tree and find the height of a binary
• Write a program to perform the binary tree traversals.
• Write a program to perform a deletion from a Binary Tree (using a delete () function).

Topic 4: Graphs

• Matrix representation of graphs
• DFS traversal
• BFS traversal

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, 3^rdedition, MIT Press, 2009