GUJARAT TECHNOLOGICAL UNIVERSITY (GTU)
Competency-focused Outcome-based Green Curriculum-2021 (COGC-2021) Semester-III
Course Title: Data Structure and Application
Course Code: 1333203
| Diploma programme in which this course is offered | Semester in which offered |
|---|---|
| Information and Communication Technology | 3rd Semester |
1. RATIONALE
Development of application systems and software that use underlying architecture of machines efficiently and effectively requires the ability to use and manipulate various types of Data Structures and other constructs. This being a fundamental ability which is language neutral yet requires use of a language for its implementation. This is a basic course which goes along with other programming courses to develop an integrated ability to efficient software development, hence this course is very important for computer engineers.
2. COMPETENCY
The course content should be taught and implemented with the aim to develop various types of related skills leading to the achievement of the following competency:
- Implement various types of Data Structures algorithms using Python.
3. COURSE OUTCOMES (COs)
The practical exercises, the underpinning knowledge and the relevant soft skills associated with this competency are to be developed in the student to display the following COs:
The practical experiences and relevant soft skills associated with this course are to be taught and implemented, so that the student demonstrates the following industry-oriented COs associated with the above-mentioned competency:
a) Comprehend the basic concepts of data structures, analysis terms, OOPs concepts, and recursive functions.
b) Apply basic operations on stack, queue and linked list data structures.
c) Apply basic operations on linked list data structure.
d) Apply different sorting and searching algorithms to the small data sets.
e) Illustrate algorithms to insert, delete and searching a node in tree.
4. TEACHING AND EXAMINATION SCHEME
| Teaching Scheme | Total Credits | Examination Scheme | ||||||
|---|---|---|---|---|---|---|---|---|
| L | T | P | C | Theory | Practical | Total | ||
| (Hours) | (Hours) | (Hours) | (L+T+P/2) | CA | ESE | CA | ESE | Marks |
| 3 | - | 4 | 5 | 30* | 70 | 25 | 25 | 150 |
(*):Out of 30 marks under the theory CA, 10 marks are for assessment of the micro-project to facilitate integration of COs and the remaining 20 marks is the average of 2 tests to be taken during the semester for the assessing the attainment of the cognitive domain UOs required for the attainment of the COs.
Legends: L -Lecture; T - Tutorial/Teacher Guided Theory Practice; P -Practical; C - Credit, CA - Continuous Assessment; ESE -End Semester Examination.
5. SUGGESTED PRACTICAL EXERCISES
Following practical outcomes (PrOs) are the sub-components of the Course Outcomes (Cos). Some of the PrOs marked '*' are compulsory, as they are crucial for that particular CO at the 'Precision Level' of Dave's Taxonomy related to 'Psychomotor Domain'.
| S. No. | Practical Outcomes (PrOs) | Unit No. | Approx. Hrs. Required |
|---|---|---|---|
| 1 | Design an student class for reading and displaying the student information, the getInfo() and displayInfo() methods will be used respectively. Where getInfo() will be a private method. | I | 02 |
| 2 | Design a class Complex for adding the two complex numbers and show the use of constructor. | I | 02 |
| 3 | Write Python class to represent a bank account. The class contains account holder name, account number, type of account and balance amount as the data members. The member functions are as follows: to initialize the data members, to deposit an amount, to withdraw an amount after checking balance, and to display name and balance. | I | 02 |
| 4 | Write Python class to represent a Cricketer. The class contains name of cricketer, team name and run as the data members. The member functions are as follows: to initialize the data members, to set run and display run. | I | 04 |
| 5 | Implement push and pop algorithms of stack using list. | II | 02 |
| 6 | Implement a program to convert infix notation to postfix notation using stack. | II | 02 |
| 7 | Implement a program to implement queue using list that performs following operations: enqueue, dequeue, display | II | 04 |
| 8 | Implement program to perform following operation on singly linked list: a. Insert a node at the beginning of a singly linked list b. Insert a node at the end of a singly linked list c. Insert a node after the given node of a singly linked list d. Insert a node before the given node of singly linked list e. Delete a node from the beginning of a singly linked list f. Delete a node from the end of a singly linked list g. Count the number of nodes of a singly linked list h. Display content of singly linked list | III | 08 |
| 9 | Implement program to create and display circular linked list | III | 04 |
| 10 | Implement program to perform following operation on doubly linked list: traversal, searching, adding and removing node | III | 04 |
| 11 | Implement a python program to search a particular element from list using Linear and Binary Search | IV | 04 |
| 12 | Implement Bubble sort algorithm | IV | 02 |
| 13 | Implement Selection sort and Insertion sort algorithm | IV | 02 |
| 14 | Implement Merge sort algorithm | IV | 02 |
| 15 | Implement Quick sort algorithm | IV | 02 |
| 16 | Implement construction of binary search trees | V | 02 |
| 17 | Write a menu driven program to perform following operation on Binary Search Tree: a. Create a BST b. Insert an element in BST c. Pre-order traversal of BST d. In-order traversal of BST e. Post-order traversal of BST f. Delete an element from BST | V | 08 |
| Total | 56 Hrs |
Note
i. More Practical Exercises can be designed and offered by the respective course teacher to develop the industry relevant skills/outcomes to match the COs. The above table is only a suggestive list.
ii. Care must be taken in assigning and assessing study report as it is a first year study report. Study report, data collection and analysis report must be assigned in a group. Teacher has to discuss about type of data (which and why) before group start their market survey.
The following are some sample 'Process' and 'Product' related skills (more may be added/deleted depending on the course) that occur in the above listed Practical Exercises of this course required which are embedded in the COs and ultimately the competency.
| S.No. | Sample Performance Indicators for the PrOs | Weightage in % |
|---|---|---|
| 1 | Correctness of program & approach to implement logic | 30 |
| 2 | Readability and documentation of the program/Quality of input and output displayed (messaging and formatting) | 10 |
| 3 | Use python concepts to implement efficient program | 20 |
| 4 | Debugging ability | 20 |
| 5 | Program execution/answer to sample questions | 20 |
| Total | Total | 100 |
6. MAJOR EQUIPMENTS/ INSTRUMENTS REQUIRED
These major equipment's with broad specifications for the PrOs is a guide to procure them by the administrators to user in uniformity of practical's in all institutions across the state.
| S. No. | Equipment Name with Broad Specifications | PrO. No. |
|---|---|---|
| 1 | Computer system with operating system: Windows 7 or higher Ver., macOS, and Linux, with 4GB or higher RAM, Python versions: 2.7.X, 3.6.X or higher | All |
| 2 | Python IDEs and Code Editors Open Source : IDLE, Jupyter, Spyder (Anaconda) | All |
7. AFFECTIVE DOMAIN OUTCOMES
The following sample Affective Domain Outcomes (ADOs) are embedded in many of the above-mentioned COs and PrOs. More could be added to fulfill the development of this course competency.
a) Work as a leader/a team member.
b) Follow ethical practices.
c) Practice environment friendly methods and processes.
d) Follow safety precautions.
The ADOs are best developed through the laboratory/field based exercises. Moreover, the level of achievement of the ADOs according to Krathwohl's 'Affective Domain Taxonomy' should gradually increase as planned below:
i. 'Valuing Level' in 1st year
ii. 'Organization Level' in 2nd year
iii. 'Characterization Level' in 3rd year
8. UNDERPINNING THEORY
The major underpinning theory is given below based on the higher level UOs of Revised Bloom's taxonomy that are formulated for development of the COs and competency. If required, more such UOs could be included by the course teacher to focus on attainment of COs and competency.
| Unit | Unit Outcomes (UOs) | Topics and Sub-topics |
|---|---|---|
| Unit-I: Basic Concepts of Data Structures & OOP | 1a. Define linear and non-linear data structures 1b. Define time complexity and space complexity 1c. Explain concepts of Object Oriented programming 1d. Explain the concept of class and object 1e. Explain the concept of constructors and how they are used to initialize objects 1f. Describe the Operations on arrays 1g. Differentiate Array and List | 1.1 Data Structure Basic Concepts 1.2 Types of data structures 1.3 Analysis Terms (for the definitions purpose only): • Time Complexity • Space Complexity • Asymptotic Notations, Big 'O' Notation • Best case Time Complexity • Average case Time Complexity • Worst case Time Complexity 1.4 OOPs Concepts 1.5 Class and Object 1.6 Constructors 1.7 Types of methods: Instance method, Class method, static method 1.8 Overview of Abstract data types 1.9 Concept of Recursive functions |
| Unit-II: Stack and Queues | 2a. Implement Stack Operations using List 2b. List applications of Stack 2c. Convert the given expression from Infix to Prefix/Postfix using stack 2d. Evaluate the postfix expression using stack 2e. Implement Queue Operations using List 2f. Explain concepts of Circular queue 2g. List applications of Queue 2h. Differentiate circular and simple queues | 2.1 Overview of Stack 2.2 Operations on Stack - Push, Pop 2.3 Implementation of Stack using List 2.4 Application of Stack: • Infix, Prefix and Postfix Forms of Expressions • Evaluations of postfix expression • Recursive Functions (Factorial, Fibonacci series) 2.5 Overview of Queue 2.6 Operations on Queue - Enqueue and Dequeue 2.7 Implementation of Queue using List 2.8 Limitation of Single Queue 2.9 Concepts of Circular Queue 2.10 Application of queue 2.11 Differentiate circular queue and simple queue |
| Unit-III: Linked List | 3a. Define a linked list 3b. List types of Linked List 3c. Implement basic operations on singly linked lists 3d. Explain concepts of circular linked lists 3e. Differentiate between circular linked list and singly linked list 3f. Explain concepts of doubly linked lists 3g. List applications of Linked List | 3.1 Overview of Linked list 3.2 Types of Linked List 3.3 Basic operations on singly linked list: • Insertion of a new node in the beginning of the list • Insertion at the end of the list • Insertion after a given node • Insertion before a given node • Deleting the first and last node from a linked list • Count the number of nodes in linked list 3.4 Overview of circular linked list 3.5 Difference between circular linked list and singly linked list 3.6 Overview of doubly linked list 3.7 Applications of linked list |
| Unit-IV: Searching and Sorting | 4a. Design and Implement search algorithms 4b. Arrange data in ascending and descending orders using appropriate sorting algorithms 4c. Explain the working of the given sorting method step-by-step with an example and small data set | 4.1 Searching an element into List: • Linear Search • Binary Search 4.2 Sorting Methods: • Bubble Sort • Selection Sort • Quick Sort • Insertion Sort • Merge Sort |
| Unit-V: Trees | 5a. Describe a binary tree 5b. Draw binary search tree for the given data set 5c. Write algorithms to traverse the tree using the given method 5d. List applications of trees | 5.1 Binary trees: • Complete Binary Tree • Basic Terms: level number, degree, in-degree and out-degree, leaf node 5.2 Binary Search Tree: • Insertion of a node in binary tree • Deletion of a node in binary tree • Searching a node in binary tree 5.3 Tree Traversal: • Inorder • Preorder • Postorder 5.4 Applications of Binary tree |
9. SUGGESTED SPECIFICATION TABLE FOR QUESTION PAPER DESIGN
| Unit No. | Unit Title | Teaching Hours | R Level | U Level | A Level | Total Marks |
|---|---|---|---|---|---|---|
| I | Basic Concepts of Data Structures & OOP | 8 | 4 | 4 | 4 | 12 |
| II | Stack and Queues | 8 | 2 | 6 | 4 | 12 |
| III | Linked List | 10 | 4 | 8 | 6 | 18 |
| IV | Searching and Sorting | 8 | 2 | 7 | 4 | 13 |
| V | Trees | 8 | 2 | 7 | 6 | 15 |
| Total | Total | 42 | 14 | 32 | 24 | 70 |
Legends: R=Remember, U=Understand, A=Apply and above (Revised Bloom's taxonomy)
10. SUGGESTED STUDENT ACTIVITIES
Other than the classroom and laboratory learning, following are the suggested student-related cocurricular activities which can be undertaken to accelerate the attainment of the various outcomes in this course: Students should conduct following activities in group and prepare small reports (of 1 to 5 pages for each activity). For micro project report should be as per suggested format, for other activities students and teachers together can decide the format of the report. Students should also collect/record physical evidences such as photographs/videos of the activities for their (student's) portfolio which will be useful for their placement interviews:
a) Provide students with code snippets and ask them to identify the Big O notation for each one.
b) Undertake micro-projects in teams.
c) Code.org - An hour of code may be organized and students are encouraged to participate
d) Students are encouraged to register themselves in various MOOCs such as: Swayam, edX, Coursera, Udemy etc. to further enhance their learning.
e) List the applications which are developed using Python data structures
f) Encourage students to participate in different coding competitions like hackathon, online competitions on CodeChef etc.
g) Encourage students to form a coding club at institute level and can help the slow learners.
11. SUGGESTED SPECIAL INSTRUCTIONAL STRATEGIES (if any)
These are sample strategies, which the teacher can use to accelerate the attainment of the various outcomes in this course:
a) Massive open online courses (MOOCs) may be used to teach various topics/sub topics.
b) Guide student(s) in undertaking micro-projects.
c) Managing Learning Environment
d) Diagnosing Essential Missed Learning concepts that will help for students.
e) Guide Students to do Personalized learning so that students can understand the course material at his or her pace.
f) Encourage students to do Group learning by sharing so that teaching can easily be enhanced.
g) 'L' in section No. 4 means different types of teaching methods that are to be employed by teachers to develop the outcomes.
h) About 20% of the topics/sub-topics which are relatively simpler or descriptive in nature is to be given to the students for self-learning, but to be assessed using different assessment methods.
i) With respect to section No.10, teachers need to ensure to create opportunities and provisions for co-curricular activities.
j) Guide students on how to address issues on environment and sustainability using the knowledge of this course
12. SUGGESTED MICRO-PROJECTS
Only one micro-project is planned to be undertaken by a student that needs to be assigned to him/her in the beginning of the semester. In the first four semesters, the micro-project are group-based (group of 3 to 5). However, in the fifth and sixth semesters , the number of students in the group should not exceed three.
The micro-project could be industry application based, internet-based, workshop- based, laboratory-based or field-based. Each micro-project should encompass two or more COs which are in fact, an integration of PrOs, UOs and ADOs. Each student will have to maintain dated work diary consisting of individual contribution in the project work and give a seminar presentation of it before submission. The total work load on each student due to the micro-project should be about 16 (sixteen) student engagement hours (i.e., about one hour per week) during the course. The students ought to submit microproject by the end of the semester (so that they develop the industry-oriented COs).
A suggestive list of micro-projects is given here. This should relate highly with competency of the course and the COs. Similar micro-projects could be added by the concerned course teacher:
a) Develop a Python Program that evaluate the given arithmetic expression using stack.
b) Develop a Python Program that maintain a queue of persons. In this queue user can add a person, delete a person and search a person.
c) Develop a Python Program that perform banking operations like withdraw cash, deposit cash and mini statement using appropriate data structure.
d) Develop a Python Program for process management algorithm by using appropriate data structure.
e) Develop a Python Program for print spooler using appropriate Data structure.
f) Develop a Python Program for Telephone Directory system. In this user can adding, searching, modifying, listing, and deleting records through the use of appropriate data structure.
g) Phone directory application using doubly-linked lists: This project can demonstrate the working of contact book applications and also teach you about data structures like arrays, linked lists, stacks, and queues. Typically, phone book management encompasses searching, sorting, and deleting operations. A distinctive feature of the search queries here is that the user sees suggestions from the contact list after entering each character.
h) Hangman Game: The Hangman program randomly selects a secret word from a list of secret words. A random word (E.g. a fruit name) is picked up from our collection and the player gets limited chances to win the game. When a letter in that word is guessed correctly, that letter position in the word is made visible. In this way, all letters of the word are to be guessed before all the chances are over.
i) Stack and queue implementation using linked list: Develop a python program that implements stack and queue operations using linked list representation.
13. SUGGESTED LEARNING RESOURCES
| S. No. | Title of Book | Author | Publication with place, year and ISBN |
|---|---|---|---|
| 1 | Data structures and algorithms in python | Goodrich | Wiley, 2013 ISBN: 978-1- 118-29027-9 |
| 2 | Introduction to Programming using Python | Y Daniel Liang | Pearson, 2012, ISBN 978- 0132747189 |
| 3 | An Introduction to Data Structures with Applications | Jean-Paul Tremblay & Paul G. Sorenson | Tata McGraw Hill,2017, ISBN 978-0074624715 |
| 4 | Python Data Structures and Algorithms Benjamin Baka, David | Julian | Packt Publishing, 2017, ISBN 978-1-78646-735-5 |
| 5 | Data Structures and Algorithms using Python | Rance D. Necaise | Wiley, 2011, ISBN 978-0- 470-61829-5 |
| 6 | Python 3 Object oriented programming Dusty Phillips | Packt Publishing, 2015, ISBN 978-1-78439-878-1 |
14. SOFTWARE/LEARNING WEBSITES
- Python Data Structures Tutorial
- Interactive Python - Data Structures
- TutorialsPoint - Data Structures Algorithms
- GeeksforGeeks - Data Structures
- StudyTonight - Data Structures
- Coursera - Data Structures Algorithms Specialization
- NPTEL - Programming, Data Structures and Algorithms (IIT Madras)
- Codecademy - Linear Data Structures
- Udacity - Data Structures and Algorithms in Python
- edX - Learn Data Structures
- SoloLearn - Data Structures
15. PO-COMPETENCY-CO MAPPING
| Course Outcomes | PO1 Basic & Discipline Knowledge | PO2 Problem Analysis | PO3 Design/ Development Solutions | PO4 Engineering Tools & Testing | PO5 Engineering Practices & Environment | PO6 Project Management | PO7 Life-long Learning |
|---|---|---|---|---|---|---|---|
| Competency: Implement various types of data structures algorithms using Python | |||||||
| CO a) Comprehend the basic concepts of data structures, analysis terms, OOPs concepts, and recursive functions | 3 | 1 | 1 | 2 | - | 1 | 1 |
| CO b) Apply basic operations on stack, queue data structures | 3 | 2 | 2 | 3 | - | 2 | 1 |
| CO c) Apply basic operations on linked list data structures | 3 | 2 | 2 | 3 | - | 2 | 1 |
| CO d) Apply different sorting and searching algorithms to the small data sets | 3 | 2 | 2 | 3 | - | 2 | 1 |
| CO e) Illustrate algorithms to insert, delete and search nodes in trees | 3 | 2 | 2 | 3 | - | 2 | 1 |
Legend: ' 3' for high, ' 2 ' for medium, '1' for low and '-' for no correlation of each CO with PO.
16. COURSE CURRICULUM DEVELOPMENT COMMITTEE
GTU Resource Persons
| S. No. | Name and Designation | Institute | Contact No. | |
|---|---|---|---|---|
| 1 | Shri P. P. Kotak Principal | S & SS Gandhi College Surat | 8200601748 | kotakp2003@yahoo.com |
| 2 | Smt. M. P. Mehta Head of the Department | Government Polytechnic, Gandhinagar | 987958273 | manishamehtain@gm ail.com |
| 3 | Ms. Darshita S. Pathak | A.V.P.T.I. Rajkot | 9879251273 | dsp.pathak@gmail.com |
| 4 | Mr. Ashish Patel | Government Polytechnic for Girls, Surat | 992405023 9 | gpgsecamp@gm ail.com |