B.Tech. I - II Sem. (CSE) SYLLABUS FOR DATA STRUCTURES

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY ANANTAPUR

ANANTHAPURAMU

B.Tech. I - II Sem. (CSE)                                                T      Tu     C

                                                                     3       1      3

(15A05201) DATA STRUCTURES

(Common to CSE and IT branches of Engineering)

                            

                                   

Objectives:

·        Understand different Data Structures

·        Understand Searching and Sorting techniques

Unit-1

Introduction and overview: Asymptotic Notations, One Dimensional array- Multi Dimensional array- pointer arrays.

Linked lists: Definition- Single linked list- Circular linked list- Double linked list- Circular Double linked list- Application of linked lists.

Unit-2

Stacks: Introduction-Definition-Representation of Stack-Operations on Stacks- Applications of Stacks.

Queues:  Introduction, Definition- Representations of Queues- Various Queue Structures- Applications of Queues. Tables: Hash tables.

Unit-3

Trees: Basic Terminologies- Definition and Concepts- Representations of Binary Tree- Operation on a Binary Tree- Types of Binary Trees-Binary Search Tree, Heap Trees, Height Balanced Trees, B. Trees, Red Black Trees.

Graphs: Introduction- Graph terminologies- Representation of graphs- Operations on Graphs- Application of Graph Structures: Shortest path problem- topological sorting.

Unit-4

Sorting : Sorting Techniques- Sorting by Insertion: Straight Insertion sort- List insertion sort- Binary insertion sort- Sorting by selection: Straight selection sort- Heap Sort- Sorting by Exchange- Bubble Sort- Shell Sort-Quick Sort-External Sorts: Merging Order Files-Merging Unorder Files- Sorting Process.

Unit-5

Searching: List Searches- Sequential Search- Variations on Sequential Searches- Binary Search- Analyzing Search Algorithm- Hashed List Searches- Basic Concepts- Hashing Methods- Collision Resolutions- Open Addressing- Linked List Collision Resolution- Bucket Hashing.

 Text Books:

1. “Classic Data Structures”, Second Edition by Debasis Samanta, PHI.

2. “Data Structures A Pseudo code Approach with C”, Second Edition by  

     Richard F. Gilberg, Behrouz A. Forouzan, Cengage Learning.

Reference Books:

1. Fundamentals of Data Structures in C – Horowitz, Sahni, Anderson-

    Freed, Universities Press, Second Edition.

2. Schaum’ Outlines – Data Structures – Seymour Lipschutz – McGrawHill-

    Revised First Edition.

3. Data structures and Algorithms using C++, Ananda Rao Akepogu and

    Radhika Raju Palagiri, Pearson Education.

JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY ANANTAPUR

ANANTHAPURAMU

B.Tech. I - II Sem. (CSE)                                                                 P        C

                                                                                                           4      2

(15A05202) DATA STRUCTURES LAB

(Common to CSE & IT Branches of Engineering)

Course Objectives:

• To strengthen the ability to identify and apply the suitable data structure for the given real  world problem

Course Outcomes: 

• Apply problem solving techniques to find solutions to problems
• Able to identify the appropriate data structure for a given problem or application.
• Improve logical skills

List of Experiments/Tasks

1.   Write a program to sort the elements of an array using sorting by exchange.

2.   Write a program to sort the elements of an array using Selection Sort.

3.   Write a program to implement heap sort.

4.   Write a program to perform Linear Search on the elements of a given array.

5.   Write a program to perform Binary Search on the elements of a given array.

6.   Write a program to convert infix expression to postfix expression and evaluate postfix expression.

7.   Write a program to implement stack, queue, circular queue using arrays and linked lists.

8.   Write a program to perform the operations creation, insertion, deletion, and traversing a singly linked list.

9.   Write a program to perform the operations creation, insertion, deletion, and traversing a Doubly linked list.

10. Write a program to remove duplicates from ordered and unordered

      arrays.

11.Write a program to sort numbers using insertion sort.

12.Write a program to implement quick sort using non-recursive and recursive approaches. Use randomized element as partitioning element.

13.Write a program to search a word in a given file and display all its positions.

14.Write a program for tic-tac-toe game.

15.Write a program to perform operations creation, insertion, deletion and traversing on a binary search tree.

16.Write a program to implement depth first search and breadth first search on graphs.

17.Write a program to perform different operations on Red Black trees.

18. Write a program to implement external sorting.

19.Write a program to perform different operations of B Tree.

Note:

1. Instructors are advised to conduct the lab in LINUX/UNIX environment
2. The above list consists of only sample programs. Instructors may choose other programs to illustrate certain concepts, wherever is necessary. Programs should be there on all the concepts studied in Theory. Instructors are advised to change atleast 25% of the programs every year until the next syllabus revision.

References:

1.   Fundamentals of Data Structures in C”, Horowitz, Sahni, Anderson-freed, Second Edition, Universities Press.

2.      Data structures and Algorithms using C++, Ananda Rao Akepogu and Radhika Raju Palagiri, Pearson Education.