Data Structures Lab (2-1-1)

 

SPRING 2021-2022
Lecture: Wednesday (9:00 AM-11:00 PM); Lab : Monday (11:00 AM - 1:00 PM); Tut: Monday (3:00 PM - 5:00 PM)

Lectures/ Tut and Lab evaluation will be held physically

Announcements, Assignment submissions via Google Classroom

 

 

 

 

Course Objective:

The Data Structure lab class intends to provide the students a practical knowledge of data structures so that the abstractions discussed in lecture classes are made concerete. For all the data structures, the course follows a three step procedure - conceptualization, explaination and implementation using the C programming language as an implementation tool.

Course Outline:


Component / Unit Topics
C1 / Unit 1 Introduction - Basic Terminology, Elementary Data Organization, Algorithm, Efficiency of an Algorithm, Time and Space Complexity;
Asymptotic notations - Theta, Big-O, and Omega, Time-Space trade-off.
Arrays - Definition, Single and Multidimensional Arrays, Representation of Arrays: Row Major Order, and Column Major Order, Application of arrays, Sparse Matrices and their representations. Linked Lists - Array Implementation and Dynamic Implementation of Singly Linked Lists, Doubly Linked List, Circularly Linked List, Header node based Linked List, Operations on a Linked List. Insertion, Deletion, Traversal, Polynomial Representation and Addition, Generalized Linked List
Abstract Data Types (ADT) Stacks: Abstract Data Type, Primitive Stack operations: Push & Pop, Array and Linked Implementation of Stack in C, Application of stack: Prefix and Postfix Expressions, Evaluation of postfix expression, Recursion, Tower of Hanoi Problem, Simulating Recursion, Principles of recursion, Tail recursion, Removal of recursion Queues: Abstract Data Type, Operations on Queue: Create, Add, Delete, Full and Empty, Circular queues, Array and linked implementation of queues in C, Doubly Ended Queue.;
C1 / Unit 2 Searching - Sequential search, Binary Search, Comparison and Analysis;
Sorting - Internal Sorting: Bubble Sort, Selection Sort, Insertion Sort, Two Way Merge Sort, Heap Sort (to be discussed after Heaps), Quick Sort
C2 / Unit 1 Trees: Basic terminology, k-ary trees, Binary Trees, Binary Tree Representation: Array Representation and Linked Representation, Skew Binary Tree, Strict Binary Tree, Complete Binary Tree, Full Binary Tree, Binary Tree Traversals: In order, Preorder and Post order, Binary Search Trees, Threaded Binary trees, Traversing Threaded Binary trees, Forest, Expression Tree, Heaps, AVL tree, B Tree and B+ Tree. Priority Queues: Array based and Heap based
C2 / Unit 2 Hashing: Hash table, hash function, collison, collision resolution strategies - Direct Chaining, Open Addressing - Linear Probing and Quadratic Probing Graphs: Basic Terminology, Sequential and linked Representations of Graphs: Adjacency Matrix, Adjacency List, Graph Traversals: Depth First Search and Breadth First Search, Connected Components. Spanning Trees, Minimum Cost Spanning Trees: Prims and Kruskal algorithm, single source shortest path-Dijkstra algorithm, Topological Sort.


Tools and Language

The vehicular language used for the course will be "C". All codes, assignments and lab exercises will be implemented in C language only.
The computer systems for the course are the machines in Lab 5042.
The preferred operating system for the tutorials and lab would be Ubuntu and the prefered editor would be Gedit or Emacs

Linux Distribution

It is a good idea to have linux installed on your machine. The 'C' compiler comes as default with the distribution. Be sure to choose it, if it is not selected by defaults, from the 'Development' items during installation. If you forget to install and desired package at the time of installation then use sudo apt-get install to select and install new packages. You need to be a root (super) user to do this (sudo gives you temporary root user permission).
Linux can co-exist with windows, if you have that already installed. Otherwise, if you like to have both then you should install windows first and linux next. Windows sometimes disturbs other installed systems.
A recent Ubuntu distribution is available [here]

Compiler

Most students prefer using non-ANSI-compliant compilers such as Turbo C while working at home. We strongly discourage doing so. Microsoft's Visual C++ compiler is good and recommended for use. But this compiler is proprietary and free copies of it cannot be obtained. The GNU range of compilers and the emacs editor can, however, be freely downloaded from the Internet. You are encouraged to download and install them in your machines, and use these software instead of non-standard software.

Editor

The preferred editors for the tutorial and lab sessions would be either Emacs , Gedit or vi
Gedit and vi are pre-installed with any Ubutu distribution.
To install Emacs in the Ubuntu environment : Open a terminal and type sudo apt-get install emacs

Working in the Windows environment

Students preferring to work in the Windows environment are encouraged to try ANSI-C compliant Compilers only and are asked to visit the this page to know how to download and install GCC compiler in the Windows environment. They may also want to visit the page to know about downloading and installing Emacs

 

 

Textbooks:

 

1.      Ellis Horowitz, Satraj Sahni and Susan Anderson-Freed, Fundamentals of Data Structures in C, W. H. Freeman and Company.

2.      Seymour Lipschutz , Data Structures, Schaum's Outlines Series, Tata McGraw-Hill.

3.      Aaron M. Tenenbaum, Yedidyah Langsam and Moshe J. Augenstein , Data Structures Using C and C++, Prentice Hall of India.

4.      R. Kruse et al. , Data Structures and Program Design in C, Pearson Education.

References:

 

1.      Donald Knuth, The Art of Computer Programming, Volume 1 and 3, Addison-Wesley, Reading, Mass., 1973.

2.      Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, MIT Press.

3.      Ritchie and Kerningham, The C Programming Language,

4.      R. G. Dromey, How to Solve it by Computer, Prentice-Hall of India. .

5.      PDS notes @IIT KGP

 

 

 

 

Important Instructions:

1.         The lab classes will mainly consist of implementation of programming concepts discussed in class and the assignments covered in tutorial sessions. of the course website for details. .

2.         Every student is expected to have access to at least one of the text books .

3.         Attendance in the classes is mandatory. If the attendance of a student falls below 75%, he/she may will be dropped from the course after Component 2

4.         The course will consist of laboratory and take-home assignments, which has to be done very seriously. If a student does not submit the assignments, his/her grade will remain as incomplete.

5.         The vehicular language for the course will be "C". All codes, assignments and lab exercises will be implemented in C language only.
.

6.         The laboratory assignments will be mainly implementation-oriented which have to coded in C and will be based the topics discussed in theoretical lectures.

7.         Grading Policy :

o   Component 1 -Lab assignments and a lab test will form the 10% of this component.

o   Component 2 - Lab assignments and lab test will form the 10% of this component.

o   Component 3 - Group Project evalution

Lab Related Instructions:

1. Submission : All submissions must be made using Google Classroom . You will be notified about mode and way to submit in the tutorial classes. E-mail submission is strongly discouraged and if submitted will be ignored.  Submissions after the deadline will not be considered.

2. Programming Language : All programs must be written in the C programming language. algorithms. Although we will initially help you to debug your codes, the debugging support will be slowly withdrawn as time progresses. For C syntax, look at the lecture slides, or bring with you any textbook on ANSI C.

3. Plagiarism :  We have a zero tolerance policy towards plagiarism. Any case of cheating or stealing codes would result in imposition of “ Unfair Means “ charge on you and you will have to face the disciplinary committee of the Department leading to probable de-registration from the course. The person who allowed his program to be copied and the one who copied it will face same consequences.  If you copy parts of your code from the Internet, you must mention that clearly in your code. Failure to do that will lead to your entire submission being invalid. 

4. Comments and Indentation : We want your programs to follow a proper indentation style as instructed in the lab

         

 

 

 

 

Sl. No.

Topic

Tutorial / Reference Codes / Helpful Resources

Tutorial/Assignments

1.

Setting Up your Linux environment to compile a C code

Working with Arrays and Structures

C Programming on Unix Systems

Tut-0

my_first_program.c


File Handling in C


Reading from a file in C


Writing a file in C


Assignment on Arrays


Assignment on Structures


2.

Working with Linked List

Tut-1





Assignment on Linked List


3.

Abstract Data Type - Stack

Tut-2


Assignment on Abstract Data Type - Stack


4.

Abstract Data Type - Queue

Assignment on Abstract Data Type - Queue


5.

Data Structuring - Tournament Sort

Assignment on Data Structuring


6.

Sorting Algorithms

Assignment on Sorting


7.

Trees

Assignment on Trees