A5-R5- Data Structure Through Object Oriented Programming Language
Good knowledge of data
structures and algorithms is the foundation of writing good code. Having good
knowledge of essential Data structures like array, string, linked list, stack,
queue, tree, graph etc makes one understand when to use which Data Structure
and accordingly reduce the space and time complexity of the algorithm. Using
the right data structure can drastically improve the performance of an
algorithm. In depth understanding of Data Structures, enables one to understand
how computer gets things done. Everything from memory allocation in the depths
of operating system, to the inner workings of an RDBMS, to how networking stack
manages to send data from one place to another, all computers rely on
fundamental data structures and algorithms, so understanding them better makes
one understand the computer better.
In this course, the Data Structures and algorithms have been implemented using Object Oriented Approach with C++.Object-oriented programming (OOP) is a programming language model in which programs are organized around data, or objects, rather than functions and logic. An object can be defined as a data field that has unique attributes and behaviour. OOP approach enables a programmer to deal with real world entities. This opposes the historical approach to programming where emphasis was placed on how the logic was written rather than how to define the data within the logic.
Objective
The course is designed to impart knowledge and develop skills required to solve real world problems using Object Oriented Approach, Python constructs. The focus will also be on fundamentals of Data Structures, Abstract concepts and how these are useful in problem solving. After completing the module, the student will be able to understand:
The course is designed to impart knowledge and develop skills required to solve real world problems using Object Oriented Approach, Python constructs. The focus will also be on fundamentals of Data Structures, Abstract concepts and how these are useful in problem solving. After completing the module, the student will be able to understand:
i. Basics of Object-oriented
Programming
ii. Understand the OOP concepts- bstraction, Objects, Classes, Polymorphism, Inheritance
iii. Implementation of Object-Oriented concepts using C++ classes
iv. Analyze step by step and develop algorithms to solve real world problems
v. Implementation of Data Structures like Linked List, Stack, queue, Trees, Graphs
vi. Sorting and Searching Techniques with focus on space and time complexity of algorithms
1. Object Oriented Concepts:
ii. Understand the OOP concepts- bstraction, Objects, Classes, Polymorphism, Inheritance
iii. Implementation of Object-Oriented concepts using C++ classes
iv. Analyze step by step and develop algorithms to solve real world problems
v. Implementation of Data Structures like Linked List, Stack, queue, Trees, Graphs
vi. Sorting and Searching Techniques with focus on space and time complexity of algorithms
1. Object Oriented Concepts:
i. Have an understanding
of Basic concepts of Object- Oriented approach of programming and how it is
different from traditional procedural approach
2. Bsics of C++ and C++ classes nd Objects
i. Basics of C++, Data types, Operators,control structures, arrays, pointers, Functions, Basic input/output and will be able to solve simple problems in C++
ii. Use of C++ language to create classes and objects
iii. Implementation of all OOPs concepts- Polymorphism, Data Abstraction, Inheritance
iv. Understand the concept of Operator Overloading
3. Analysis of Algorithm
i. Analysis of various algorithms in terms of space and time complexity
ii. Concept of Big- O notation.
4. Searchin and Sorting
iii. Various Searching techniques and their comparison in terms of time complexity
iv. Various sorting techniques and their comparison in terms of time complexity
5. Elementary Data Types- Arrays, Linked
Lists and Types
i. Implementation of 1-D and 2-D arrays and various operations to be performed on arrays
ii. Creation of new structures like- Linked list, double Link List, Circular Link List and all the operations related to same
6. Stacks and Queues
i. Implementation of stacks and queues
ii. Understand the use of the two data structures.
7. Trees
i. Nonlinear Data Structure- trees and different modes of traversals
ii. Implement different types of trees-BST, Threaded Binary Tree, B tree and practical use of the same
8. Graphs
i. The concept of Graph and its implementation through Adjacency Matrix and various traversal techniques of graphs:
2. Basics of C++, classes and objects 20
3. Analysis of algorithms 8
4. Sorting and Searching 12
5. Elementary Data Structures- Arrays, Linked Lists 15
6. Stack and Queue 15
7. Trees 15
8. Graphs 10
Total 100
Object Oriented Programming- a new paradigm, Abstraction, forms of Abstraction, OOP concepts- Classes, Objects, Polymorphism, Data Encapsulation, Data Hiding, Inheritance,
i. Basics of C++, Data types, Operators,control structures, arrays, pointers, Functions, Basic input/output and will be able to solve simple problems in C++
ii. Use of C++ language to create classes and objects
iii. Implementation of all OOPs concepts- Polymorphism, Data Abstraction, Inheritance
iv. Understand the concept of Operator Overloading
i. Analysis of various algorithms in terms of space and time complexity
ii. Concept of Big- O notation.
iii. Various Searching techniques and their comparison in terms of time complexity
iv. Various sorting techniques and their comparison in terms of time complexity
i. Implementation of 1-D and 2-D arrays and various operations to be performed on arrays
ii. Creation of new structures like- Linked list, double Link List, Circular Link List and all the operations related to same
i. Implementation of stacks and queues
ii. Understand the use of the two data structures.
i. Nonlinear Data Structure- trees and different modes of traversals
ii. Implement different types of trees-BST, Threaded Binary Tree, B tree and practical use of the same
i. The concept of Graph and its implementation through Adjacency Matrix and various traversal techniques of graphs:
2. Basics of C++, classes and objects 20
3. Analysis of algorithms 8
4. Sorting and Searching 12
5. Elementary Data Structures- Arrays, Linked Lists 15
6. Stack and Queue 15
7. Trees 15
8. Graphs 10
Total 100
Detailed Syllabus
(i) Object Oriented ConceptsObject Oriented Programming- a new paradigm, Abstraction, forms of Abstraction, OOP concepts- Classes, Objects, Polymorphism, Data Encapsulation, Data Hiding, Inheritance,
(ii) Basics of C++, Classes and Objects
Features of C++, Tokens, keywords, Data types, Operators, Manipulators, Console input, output, Control statements (conditional and loops), Functions, Classes, Instantiation, Destructor, constructor, Polymorphism - Operator Overloading, Function Overloading, Inheritance-Single, Multiple, Multilevel, Pointers
Features of C++, Tokens, keywords, Data types, Operators, Manipulators, Console input, output, Control statements (conditional and loops), Functions, Classes, Instantiation, Destructor, constructor, Polymorphism - Operator Overloading, Function Overloading, Inheritance-Single, Multiple, Multilevel, Pointers
(iii) Analysis of Algorithm
Introduction to algorithm design and Data structures, Comparison of Algorithms, Complexity in terms of space and time, Calculation of O- notation. Abstract Data type and its implementation with a Rational number example
Introduction to algorithm design and Data structures, Comparison of Algorithms, Complexity in terms of space and time, Calculation of O- notation. Abstract Data type and its implementation with a Rational number example
(iv) Searching and Sorting
Searching- Linear and Binary Search, Sorting- Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Merge Sort, Comparison of various searching and sorting techniques in terms of time complexity
Searching- Linear and Binary Search, Sorting- Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Merge Sort, Comparison of various searching and sorting techniques in terms of time complexity
(v)
Elementary Data Structures: Arrays, Linked Lists
Representation of arrays-single and multidimensional, Address calculation using row major ordering, Various operations on arrays, Linked Lists-Singly Linked List, Double linked List, Circular Linked List- traversing, deleting, inserting, searching, counting, reversing, printing of nodes.
Representation of arrays-single and multidimensional, Address calculation using row major ordering, Various operations on arrays, Linked Lists-Singly Linked List, Double linked List, Circular Linked List- traversing, deleting, inserting, searching, counting, reversing, printing of nodes.
(vi) Stacks and Queues
Stack ADT, Implementation of stack using array and linked list, Application of Stack- Evaluation of postfix/prefix expression, Queue ADT, Implementation of queue using Array and Linked List
Stack ADT, Implementation of stack using array and linked list, Application of Stack- Evaluation of postfix/prefix expression, Queue ADT, Implementation of queue using Array and Linked List
(vii) Trees
Definition and notations, Binary Search Trees Implementation. Traversals using stacks and recursion - In-order, post-order, pre-order techniques, Threaded binary tree, B-trees with implementation of 2-3 trees.
Definition and notations, Binary Search Trees Implementation. Traversals using stacks and recursion - In-order, post-order, pre-order techniques, Threaded binary tree, B-trees with implementation of 2-3 trees.
(viii) Graphs
Definition and notations, Components of Graphs, Types of Graphs, Graph Implementation using Adjacency Matrix and Adjacency List algorithms and programs, Graph Traversal Methods: Depth First Search and Breadth First Search.
Reference Books/Study Material
1. Object Oriented Programming with C++ by Robert Lafore
2. Object Oriented Programming with C++ by E Balaguruswamy
Definition and notations, Components of Graphs, Types of Graphs, Graph Implementation using Adjacency Matrix and Adjacency List algorithms and programs, Graph Traversal Methods: Depth First Search and Breadth First Search.
Reference Books/Study Material
1. Object Oriented Programming with C++ by Robert Lafore
2. Object Oriented Programming with C++ by E Balaguruswamy
3. Data Structures through C++ by Yashwant Kanetkar
4. Schaum’s Outlines Data Structures Seymour Lipschutz
4. Schaum’s Outlines Data Structures Seymour Lipschutz