Module Code and Title:       CSC102          Data Structures Using C

Programme:                          BCA

Credit Value:                         12

Module Tutor:                       Somnath Chaudhuri

General Objective: This module deals with how information is stored in a computer in order to minimize memory and data access times. The study of data structures such as linked lists and binary trees will increase the students’ understanding on how complex objects can be stored with appropriate data structures; essential manipulations such as searching and sorting are also incorporated in the module.

Learning Outcomes – On completion of the module, learners will be able to:

1. Explain the role and importance of data structures and the algorithms used to manipulate data structures.
2. Use algorithmic analysis in solving problems.
3. Calculate runtime values for different types of algorithms.
4. Use standard searching and elementary sorting algorithms.
5. Describe basic data structures such as link list, stack, queue, tree etc.
6. Apply recursion concepts to solve large and complex problems.
7. Develop small utilities using standard data structures and algorithms.
8. Explain the applications of data structures in different management levels of an operating system.

Learning and Teaching Approach:

Assessment Approach:

A. Individual Assignment: Portion of Final Mark: 10%

Students should submit two assignments related to algorithm theory, recursion technique, sorting, stack, queue and graph theory to obtain this 10%. The first one will be before the midterm and it constitutes half of the total 10% allocated. Students will be submitting an assignment based on algorithm theory and recursion technique. The next assignment, for the other half of the total marks, will be done after the midterm, on topics from sorting, stack, queue, graph theory. 2 analytical problems and 2 theoretical problems will be assigned to them to solve .40% will be awarded for solving the problem, 40% for analysing the problem and 20% for the overall report.

Activity: Problems relate to algorithm theory, recursion technique, sorting, stack, queue and graph theory will be assigned to the students. Students have to analyse those and solve them. Solutions should be submitted in hardcopy format with proper logical expressions.

B. Class Test: Portion of Final Mark: 20%

This is a written test conducted within the class for duration of 30-40 minutes. There will two such tests, one before midterm comprising of topics from the beginning to the quarter point of the subject matter and the other after the midterm comprising of topics from after the midterm to quarter pointer after midterm. Each class test will consist of 3-4 problems theoretical and generating codes in C. The students have to solve those problems in the class within predefined time.

C. Individual Presentation: Portion of Final Mark: 5%

The presentation will be conducted within the class hours. Students are expected present the topic assigned to them respectively. 30% will be awarded for content of the presentation, 30% for preparedness, 10% for timing, 15% for handling of Q&A session and 15% for presentation skill.  The presentation will be approximately 10-12 minutes, and include power points slides.

Activity: A few topics will be taught in the class. Then, when students have adequately grasped the concept of the topic, they have to prepare a presentation on its real-time application. The presentation will be evaluated by the contents of the presentation and individual presentation skill.

D. Lab Practical Exam: Portion of Final Mark: 20%

Students will be assessed on their program designing skills in solving problems relate to algorithm theory, recursion technique, sorting, stack, queue and graph theory in the lab.. 35% will be awarded sub tasks completed, 35% Techniques used for each sub task, 10% for timing and 30% for output. There will be one hour practical examination. 2-3 programs will be assigned to individual student. They have to solve it within predefined examination duration.

E. Midterm Exam: Portion of Final Marks: 20%

This a college wide examination conducted at the half-way into the semester. This examination is conducted for 1 hour and 30 Minutes and it includes all topics till the half-way point in the subject matter.

Prerequisites: CPR101, MAT101

Subject Matter:

1. Algorithm Design and Algorithm Analysis
   • Design algorithms
   • Algorithm Analysis
   • Concept of Big-Oh, Big Theta, Big Sigma notation
2. Searching and Sorting
   • Searching techniques: Linear, Binary. Algorithmic comparison between the searching techniques
   • Elementary Sorting Techniques: Selection Sort, Bubble Sort, Insertion Sort. Algorithmic analysis and coding in C.
   • Quick Sort, Radix Sort, Heap Sort, Merge Sort. Algorithmic analysis and comparison, without coding.
3. Recursion
   • Recursive algorithms
   • Divide and conquer technique
   • Comparison with dynamic programming
   • Problems with recursion
4. Stack
   • Definition and examples
   • Push and Pop functions
   • Example: infix, postfix and prefix
   • Stacks using Templates
   • Application of stack in Recursive program
5. Queue
   • Definition and examples
   • Insert and Delete Functions
   • Priority Queue
   • Double-ended Queue (without coding)
   • Circular Queue
6. Linklist
   • Inserting and Deleting of Nodes from a list
   • Inserting and Deleting at i-th position
   • Circular Linked list
   • Doubly Linked list
7. Non-planer data structures
   • Types of Binary Trees
   • Operations on Binary Trees
   • Binary Search Tree: Insertion, Deletion & Traversal
   • Threaded Binary Search Tree
   • Concept and advantage of AVL tree over BST
   • Application of Binary search tree and AVL tree
8. Matrix
   • Definitions and Operations
   • Special Matrices: Diagonal, Triangular, Symmetric
   • Adjacency matrix for Graph representation
9. Practical Components
   • Problems related to array
   • Linear & Binary Search
   • Bubble, Insertion and Selection Sort
   • Stack, Application of Stack
   • Queue, Application of Queue
   • Application of Stack & Queue in Process Management
   • Link List implementation
   • Application of Link List for Stack & Queue
   • Search & Sorting Operation Using Link List
   • Tree Using Link List
   • Recursion Problem and its application
   • Software to be used: Turbo

Reading List:

1. Essential Reading
   • Krishnamoorthy, Data Structures Using C, Tata McGraw-Hill Education, 2008
   • Kanetkar, P. Data Structure Through C, Latest Edition. BPB Publications
   • Sahni, S. (2005). Data Structures, Algorithms and Applications in C (2nd ed.). Universities Press.
   • Yedidyah, L. (1998). Data Structures Using C and C (2nd ed.). PHI.
2. Additional Reading
   • Aaro M. Tanenbum, Data Structures Using C. Pearson Education India
   • Seymour Lipschutz, Adapted by G A V Pai (2006). Tata McGraw-Hill Education
   • Yogish Sachdeva. (2011), Beginning Data Structures Using C,
   • K. Sharma. (2011), Data Structure Using C, Pearson Education India
   • Prabhakar Gupta, Vineet Agarwal, Manish Varshney (2007), Data Structure Using C, Firewall Media
   • A.Puntambekar. (2009), Data Structure Using ‘C’, Technical Publications

Date: May 30, 2015