Data Structure with Python#
Course Code: 4331601
Data Structure with Python Course Code: 4331601
GUJARAT TECHNOLOGICAL UNIVERSITY (GTU)
Competency-focused Outcome-based Green Curriculum-2021 (COGC-2021) Semester-III
Course Title: Data Structure with Python (Course Code: 4331601)
Diploma programme in which this course is offered Semester in which offered Information Technology Third
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. As far as data structures are concerned, the course covers Python dictionaries as well as classes and objects for defining user defined data types such as linked lists and binary search trees. This course is designed to develop an integrated ability to efficient software development and apply the knowledge to various application systems; hence this course is very important for IT diploma engineers.
2. Competency#
The purpose of this course is to help the student to attain the following industry identified competency through various teaching learning experiences:
- Implement various types of data structures algorithms using python.
3. Course Outcomes#
The practical exercises, the underpinning knowledge and the relevant soft skills associated with the identified competency are to be developed in the student for theachievement of the following COs: a. Understand linear and non-linear data structures. b. Implement Object Oriented Programming concepts in Python. c. Implement basic data structures such as stacks, queues and linked lists. d. Apply Algorithms for solving problems like searching and sorting of data. e. Implement nonlinear data structures like trees.
4. Teaching And Examination Scheme#
Teaching and Examination Scheme#
Teaching Scheme Total Credits Examination Scheme
(In Hours) (L+T+P/2) Theory Marks Practical Marks Total
L T P C 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.
Data Structure with Python Course Code: 4331601
Legends: L-Lecture; T – Tutorial/Teacher Guided Theory Practice; P -Practical; C – Credit,
CA - Continuous Assessment; ESE -End Semester Examination.
5. Suggested Practical Exercises#
Practical Outcomes#
The following practical outcomes (PrOs) are the sub-components of the 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. Unit Approx. Hrs.
Practical Outcomes (PrOs) required
No. No.
Write a program to read a list of elements. Modify this list so I 02
that it does not contain any duplicate elements, i.e., all
1.
elements occurring multiple times in the list should appear
only once.
Build a program to count the frequency of words appearing in I 02
2. .
a string using a dictionary.
Implement a Program for two matrix multiplication using I 02
3.
simple nested loop and numpy module.
- Implement basic operations on arrays. I 02 Design an employee class for reading and displaying the II 02 employee information, the getInfo() and displayInfo() methods will be used respectively. Where getInfo() will be a private method. Design a class Complex for adding the two complex numbers II 02
4
and also show the use of constructor. Design a class for single level inheritance using public and II 02 private type derivation. 8. Implement multiple and hierarchical inheritance. II 02 Write a Python program to demonstrate method overriding II 02 using inheritance. 10. Implement push and pop algorithms of stack using list. III 02 Implement a program to convert infix notation to postfix III 02 notation using stack. 12. Implement recursive functions. III 02 Implement a program to implement QUEUE using list that III 04 performs following operations: ENQUEUE, DEQUEUE, DISPLAY Implement program to perform following operation on singly IV 08 linked list: a. Insert a node at the beginning of a singly linked list. 14. 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.
Data Structure with Python Course Code: 4331601
Teaching and Examination Scheme#
S. Unit Approx. Hrs.
Practical Outcomes (PrOs) required
No. No.
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
Implement a python program to search a particular element V 04
15.
from list using Linear and Binary Search.
- Implement Bubble sort algorithm. V 02
- Implement Selection sort and Insertion sort algorithm. V 02
- Implement Merge sort algorithm. V 02
- Implement construction of binary search trees. VI 02 Write a menu driven program to perform following VI 08 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 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. 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.
Practical Outcomes#
S.No. Sample Performance Indicators for the PrOs Weightage in %
1 Identify suitable approach to implement logic 25
2 Correctness of data structure representation 20
3 Use python concepts to implement efficient program 25
4 Follow different input test cases to check output 10
5 Identify and mend coding errors in a program / Interpret the 20
result and conclude
Total 100
- MAJOR EQUIPMENT/ INSTRUMENTS REQUIRED
Practical Outcomes#
These major equipment with broad specifications for the PrOs is a guide to procure them by
the administrators to usher in uniformity of practicals in all institutions across the state.
S. PrO. No.
Equipment Name with Broad Specifications
No.
GTU - COGC-2021 Curriculum
Page 3 of 9
Data Structure with Python Course Code: 4331601
S. PrO. No.
Equipment Name with Broad Specifications
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
7. Affective Domain Outcomes#
The following sample Affective Domain Outcomes (ADOs) are embedded in many of the
Practical Outcomes#
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.
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.
Teaching and Examination Scheme#
Unit Unit Outcomes (UOs) Topics and Sub-topics
(4 to 6 UOs at different levels)
Unit – I 1a. Define linear and non-linear data 1.1 Data Structure Basic Concepts
structures. 1.2Types of data structures
Basic 1b. Define time complexity and space 1.3 Analysis Terms (for the
Concepts of complexity. definitions purpose only) :
Data 1c. Explain python specific - list, tuple, Time Complexity
Structures set, Dictionary and tuple data Space Complexity
structures. Asymptotic Notations ,Big ‘O’,
1d. Describe the Operations on arrays. Notation , Best case Time
1e. Differentiate array and list. Complexity, Average case
Time Complexity, Worst case
Time Complexity
1.4 Python Specific Data
Structures-List, Tuple,
Set, Dictionary
1.5 Array in Python
import array
Data Structure with Python Course Code: 4331601
Teaching and Examination Scheme#
Unit Unit Outcomes (UOs) Topics and Sub-topics
(4 to 6 UOs at different levels)
import numpy
Operations on Arrays
Arrays vs List
Unit – II 2a. Explain concepts of Object 2.1 Oops Concepts
Oriented programming. 2.2 Class and Object
Basics of 2b. Explain the concept of class and 2.3 Constructors
Object 2.4 Types of methods
object.
Oriented Instance method
Programming 2c. Use a constructor to initialize an
Class method
object.
static method
2d. List the types of Inheritance. 2.5 Data Encapsulation
2e. Use Inheritance to create re-usable 2.6 Inheritance - single, multiple,
codes in Python. multi-level, hierarchical,
2f. Understand Polymorphism. hybrid
2.7 Polymorphism through
2g. Describe Abstract class.
inheritance 2.8 Abstraction - abstract class
Teaching and Examination Scheme#
Unit– III 3a. Implement Stack Operations using 3.1 Overview of Stack
List. 3.2 Operations on Stack - Push,
Stack and Pop
3b. List applications of Stack.
Queues 3.3 Implementation of Stack
3c. Convert the given expression from using List
Infix to Prefix/Postfix using stack. 3.4 Application of Stack - Infix,
3d. Evaluate the postfix expression Prefix and Postfix Forms of
using stack. Expressions, Evaluations of
postfix expression, Recursive
3e. Implement Queue Operations
Functions (factorial, Fibonacci
using List. series)
3f. Explain concepts of Circular queue. 3.5 Overview of Queue
3g. List applications of Queue. 3.6 Operations on Queue -
3h. Differentiate circular and simple Enqueue and Dequeue
3.7 Implementation of Queue
queues.
using List
3.8 Limitation of Single Queue
3.9 Concepts of Circular Queue
3.10 Application of queue 3.11 Differentiate circular queue and simple queue
Data Structure with Python Course Code: 4331601
Teaching and Examination Scheme#
Unit Unit Outcomes (UOs) Topics and Sub-topics
(4 to 6 UOs at different levels)
Unit– IV 4a. Define a linked list. 4.1 Overview of Linked list
4b. List types of Linked List. 4.2 Types of Linked List
Linked List 4.3 Basic operations on singly
4c. Implement basic operations on
linked list :
singly linked lists.
Insertion of a new node in
4d. Explain concepts of circular linked the beginning of the list, at
lists. the end of the list, after a
4e. Differentiate between circular given node, before a given
linked list and singly linked list. node, Deleting the first and
last node from a linked list,
4f. Explain concepts of doubly linked
Count the number of nodes in
lists.
linked list.
4g. List applications of Linked List. 4.4 Overview of circular linked list
4.5 Difference between circular
linked list and singly linked list
4.6 Overview of doubly linked list 4.7 Applications of linked list
Teaching and Examination Scheme#
Unit– V 5a. Design and Implement search 5.1 Searching an element into
algorithms. List:
Searching and 5b. Arrange data in ascending and Linear Search, Binary Search
Sorting 5.2 Sorting Methods:
descending orders using
Bubble Sort, Selection Sort,
appropriate sorting algorithms. Quick Sort, Insertion Sort,
5c. Explain the working of the given Merge Sort
sorting method step-by-step with
an example and small data set.
Unit– VI 6a. Describe a binary tree. 6.1 Binary trees: Complete
6b. Draw binary search tree for the Binary Tree, Basic Terms:
Trees given data set. level number, degree,
in-degree and out-degree,
6c. Write algorithms to traverse the
leaf node
tree using the given method. 6.2 Binary Search Tree:
6d. List applications of trees. Insertion of a node in binary
tree, Deletion of a node in
binary tree, Searching a node
in binary tree
6.3 Tree Traversal : Inorder, Preorder, Postorder 6.4 Applications of binary tree
9. Suggested Specification Table For Questionpaper Design#
Data Structure with Python Course Code: 4331601
Teaching and Examination Scheme#
Unit Unit Title Teaching Distribution of Theory Marks
No. Hours R U A Total
Level Level Level Marks
I Basic Concepts of Data Structures 04 04 02 00 06
II Basics of Object Oriented
08 04 04 04 12
Programming
III Stack and Queues 08 02 06 06 14
IV Linked List 08 04 08 02 14
V Searching and Sorting 08 02 06 06 14
VI Trees 06 02 04 04 10
Total 42 18 30 22 70
Legends: R=Remember, U=Understand, A=Apply and above (Revised Bloom’s taxonomy)
Note: This specification table provides general guidelines to assist students for their learning and to teachers to teach and question paper designers/setters to formulate test items/questions to assess the attainment of the UOs. The actual distribution of marks at different taxonomy levels (of R, U and A) in the question paper may slightly vary from above table.
10. Suggested Student Activities#
Other than the classroom and laboratory learning, following are the suggested student- related co-curricular activities which can be undertaken to accelerate the attainment of the various outcomes in this course: Students should perform following activities in group and prepare reports of about 5 pages for each activity. They should also collect/record physical evidences for their (student’s) portfolio which may be useful for their placement interviews: a. Prepare a practical journal. b. Undertake micro-projects in teams. c. Give a seminar on any relevant topics. d. Prepare a chart to classify Data structures. e. Explore different python data structure modules. 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/subtopics. b. Guide student(s) in undertaking micro-projects. c. ‘L’ in section No. 4 means different types of teaching methods that are to be employed by teachers to develop the outcomes. d. 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. e. With respect to section No.10, teachers need to ensure to create opportunities and provisions for co-curricular activities. f. Guide students for finding suitable data structures to solve given problems. 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
Data Structure with Python Course Code: 4331601
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
Practical Outcomes#
which are in fact, an integration of PrOs, UOs and ADOs. Each student will have to maintain a
dated work diary consisting of individual contributions in the project work and give a
seminar presentation of it before submission. The duration of the micro project should be
about 14-16 (fourteen to sixteen) student engagement hours during the course. The
students ought to submit micro-project by the end of the semester to develop the industry-
oriented COs.
A suggestive list of micro-projects is given here. This has to match the competency and the
COs. Similar micro-projects could be added by the concerned course teacher:
a) 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.
b) Hangman Game: The Hangman program randomly selects a secret word from a list of
secret words. A random word (Eg. 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.
c) 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. Author Publication with place, year and Title of Book No. ISBN 1 Data structures and M.Goodrich Wiley, 2013 ISBN: 978-1-118- algorithms in python 29027-9 2 Data Structures and N.Karumanchi Career Monk Publications, 2016 Algorithmic Thinking with ISBN:978-81-921075-9-2 Python 3 Core Python Programming Wesley J. Chun Prentice Hall, ISBN: 978-0-13- 226993-3 4 Data Structures And R. Necaise John Wiley & Sons, 2011 Algorithms Using Python ISBN: 978-0470618295 5 Python Programming N.Fatak,S.Chavd Mahajan Publication,2021 a 978-93-93218-00-1 6 Advanced Python S.Chawda,P.Cha Mahajan Publication,2022 Programming vda 978-93-93218-22-3
- SOFTWARE/LEARNING WEBSITES
Data Structure with Python Course Code: 4331601
- Hands-On Data Structures and Algorithms with Python: Write complex and powerful code using the latest features of Python 3.7, 2nd Edition by Dr. Basant Agarwal, Benjamin Baka
- Data Structures and Algorithms with Python by Kent D. Lee and Steve Hubbard
- Problem Solving with Algorithms and Data Structures Using Python by Bradley N Miller and David L. Ranum
- https://nptel.ac.in/courses/106106145
- PO-COMPETENCY-CO MAPPING Semester III Data Structures Using Python(Course Code: 4331601) Competency PO 1 PO 2 PO 3 PO 4 PO 5 PO 6 PO 7 & Course Outcomes Basic & Problem Design/ Engineering Engineering Project Life- Discipline Analysis developmen Tools, practices for Management long specific t of solutions Experimenta society, learnin knowledg tion & sustainability & g e Testing environment Competency Implement various types of data structures algorithms using python
Course Outcomes CO a) Understand linear and non-linear data 3 1 1 2 - 1 1 structures. CO b) Implement Object Oriented Programming 3 2 2 1 concepts in Python. 3 - 2 CO c) Implement basic data structures such as stacks, queues and 3 2 2 3 - 2 1 linked lists. CO d) Apply Algorithms for solving problems like 2 1 searching and sorting of 3 2 2 3 - data. CO e) Implement non linear data structures like 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 Email 1 Prof. Nandu A. Fatak HOD-I.T. nandu_fatak@yahoo.com LEC Poly Morbi 2 Ms. Ayesha S. Shaikh RCTI,Sola, shaikh.ayesha0014@gmail.com Ahmedabad 3 Mr. Hardik Mandora RCTI,Sola, hmandora@gmail.com Ahmedabad 4 Mr. Pradipsinh K. LECP Morbi pradipchavda.it@gmail.com Chavda