ALGORITHMS & DATA STRUCTURES

Paper Code: 
MIT 221
Credits: 
04
Periods/week: 
04
Max. Marks: 
100.00
Objective: 

This course describes various structuring methods of data and their practical use.

 

 

12.00

Introduction to the Problem solving Aspect, Algorithm definition and its characteristics, Top down Design, implementation of Algorithms, Program Verification , The Efficiency of Algorithms., Abstract data types and concept of Data Structures, ADT for rational number, Sequence as value definition, ADT for varying length strings, Array as an ADT.

Data Structures: definition and classification, Data type in C, pointers in C, Data structure and C, Arrays (one, two and multi dimensional), Row major and column major form, representation of strings.

 

12.00

Stack: Definition, Primitive operations, Stack as an ADT, representing stack in C, implementing the push and pop operation, testing exceptional conditions, infix, postfix and prefix expression (definition and examples), evaluation of postfix expression and converting an expression from infix to postfix only (Algorithm and C implementation).

Recursion definition and processes, algorithms, recursion in C, Writing recursive programs ( Factorial, multiplication, Fibonacci sequence, Binary search, Towers of Hanoi Problem), Properties of recursive definition or Algorithms, Efficiency of recursion.

 

12.00

Queues: Introduction, Definition of Queue and its sequential representation, Queue as an ADT, C implementation of queues, insert and remove operation, Applications and Priority queues.

Linked list: Introduction to linked list, creation, insertion and deletion of nodes from a list, linked implementation of stacks, get node and free node operations, linked implementation of queues, linked list as a data structure, linked implementation of priority queue, concept of header nodes, array implementation of lists and its limitation, Allocating and freeing dynamic memory, comparing dynamic and array implementation of lists.

Definition and C implementation: Singly linked lists, Doubly Linked lists, Circular linked lists, Circular Double linked lists, Stack as Circular List, Queue as circular list.

 

12.00

Trees: Binary tree, Introduction and terminology, Operations on binary trees, applications of binary tree, Binary tree representations (node and implicit array representation), Recursive and Non - Recursive Tree Traversal Techniques ( Inorder, PostOrder and Preorder), Threaded binary trees.

Sorting: Exchange Sorts (Bubble sort, Quick sort), Straight Selection sort, Insertion sorts, Merge sort.

Searching: Linear and Binary Search.

 

12.00

Hashing: Concept, Resolve hash clashes by open addressing, coalesced Hashing and separate chaining.

Graphs and their Applications: Graphs, C representation of graphs, Transitive Closure, Warshall’s Algorithm, Shortest path algorithm, Graph Traversal (Depth First Traversal & Breadth First Traversal: Algorithm and application only).

 

ESSENTIAL READINGS: 

 

  1. Y. Langsam, M. J. Augenstein, A.M. Tanenbaum, “Data Structure using C, C++”, second edition, Prentice Hall of India, 1999.
REFERENCES: 

 

  1. E. Horowitz and S. Sahani, “Fundamentals of Data Structures”, Galgotia Book source Pvt. Ltd, 2000
  2. S. Lipschutz,  “Data Structures”, Schaum’s outline series, Tata McGraw Hill Edition, 2002
  3. Robert L.Kruse “Data Structures and Program Design”,  Third edition, PHI
  4. Weiss, “Data Structures and Algorithmic analysis in C", 2e, 2003, PEA.
  5. Trembley, Sorenson,” An introduction to Data Structure with Applications", 2e, TMH.
  6. Aho, Hopcroft, Ullman,” Data Structure and Algorithms", PEA.
  7. Nicholas Wirth, “Algorithms + Data Structure = Programs", PHI.
  8. Samanta, “Classic Data Structures", 1e, 2001, PHI.
  9. R.B.Patel, “Expert data structures with C”, Khanna Book Publishing Co(p). Ltd. Delhi
Academic Year: 
2016-17
  • Printer-friendly version