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