OCS751 - DATA STRUCTURES AND ALGORITHMS (Syllabus) 2017-regulation - Open Elective | Anna University

Title

OCS751	DATA STRUCTURES AND ALGORITHMS	LPTC

3003

OBJECTIVES:

• To understand the various algorithm design and analysis techniques
• To learn linear data structures – lists, stacks, and queues
• To learn different sorting and searching algorithms
• To understand Tree and Graph data structures

UNIT I	ALGORITHM ANALYSIS, LIST ADT	11

Algorithms: Notation - analysis – running time calculations. Abstract Data Types (ADTs): List ADT – array-based implementation – linked list implementation – singly linked lists- applications of lists: Polynomial Manipulation. Implementation of List ADT using an array and using a linked list in C.

UNIT II	STACKS AND QUEUES	7

Stack ADT - Applications - Evaluating arithmetic expressions- Conversion of Infix to Postfix- Recursion. Queue ADT – Priority Queue - applications of queues. Implementation of Stack ADT and palindrome checking using C. Implementation of Queue operations using arrays in C.

UNIT III	SEARCHING AND SORTING ALGORITHMS	10

Divide and conquer methodology - Searching: Linear Search - Binary Search. Sorting: Insertion sort – Merge sort – Quick sort – Heap sort. Analysis of searching and sorting techniques. Implementation of linear search, binary search, insertion sort, merge sort and quick sort algorithms in C.

UNIT IV	TREES	9

Tree ADT – tree traversals - Binary Tree ADT – expression trees – binary search tree ADT – applications of trees. Heap – applications of heap. Implementation of Binary search tree and its operations, tree traversal methods, finding height of the tree using C. Implementation of heap and heap sorting using arrays in C.

UNIT V	GRAPHS	8

Definition – Representation of Graph – Breadth-first traversal - Depth-first traversal – Dynamic programming Technique – Warshall’s and Floyd’s algorithm – Greedy method - Dijkstra’s algorithm – applications of graphs. Implementation of graph, graph traversal methods, finding shortest path using Dijkstra’s algorithm in C

TOTAL : 45 PERIODS

OUTCOMES: At the end of this course, the students should be able to:

• Implement linear data structures and solve problems using them.
• Implement and apply trees and graphs to solve problems.
• Implement the various searching and sorting algorithms.

TEXT BOOKS:

1. Mark Allen Weiss, “Data Structures and Algorithm Analysis in C”, 2nd Edition, Pearson Education,1997.
2. Brian W. Kernighan and Dennis M. Ritchie, “The C Programming Language”, 2nd Edition, Pearson Education, 1988.

REFERENCES:

1. Aho, Hopcroft and Ullman, “Data Structures and Algorithms”, Pearson Education,1983.
2. S.Sridhar, “Design and Analysis of Algorithms”, First Edition, Oxford University Press. 2014
3. Byron Gottfried, Jitender Chhabra, “Programming with C” (Schaum’s Outlines Series), Mcgraw Hill Higher Ed., III Edition, 2010
4. Yashvant Kanetkar, “Data Structures Through C”, BPB publications, II edition, 2003