Select Your Style

Choose your layout

Color scheme

Data Structure through C++

Data Structure through C++

INR₹4,237.00 + GST

Please login to purchase the course.

Clear
SKU: cid_253689 Category: Tags: , ,

 

This aim of this course is to introduce you to the fundamentals of Data Structures, abstract concepts, and how these concepts are useful in problem solving. This course covers in detail the design and analysis of algorithms along with the basics of C++ programming language including elementary data structures such as arrays and linked lists, abstract data types like stacks, queues, and trees. It also provides you an exposure to various searching and sorting techniques along with their performance analysis.

 

Learning Outcomes

After completing this course, you will be able to:

  • Understand the basics of C++ programming language
  • Understand the object oriented programming concepts like Inheritance, abstraction, polymorphism etc
  • Develop algorithms and analyze them step by step to solve real world problems
  • Implement various data structures such as arrays, linked lists, stacks, queues, trees and graphs in your programs
  • Perform search and sort operations to filter data by utilizing different searching and sorting techniques

Target Audience

The course can be taken by:

Students: All students who are pursuing any technical or professional degree courses in computer science or IT.
Teachers/Faculties: All computer Science or IT teachers/faculties who wish to acquire new skills or enhance their skills in data structures
Professionals: All working professionals, who wish to acquire new skills or who need to improve their efficiency in data structures.

Why learn data structures through C++?

Data structures and algorithms are some of the most essential topics for programmers, both to get a job and to do well on a job. Good knowledge of data structures and algorithms is the foundation of writing good code. If you are familiar with essential data structures like array, stack, queue, linked list, tree, graph, map etc, then you will know when to use which data structure and compute the CPU and memory cost of your code. Even though you don’t need to write your own array, linked list, or hashtable, given every major programming SDK provides them, e.g. JDK or C++ STL library, you will need to understand them so that you can use them in the right place.

Ideally, data structures and algorithms should be learned in schools and colleges, but it’s rarely ever covered. Most of the programmers, only get introduced to a data structure in our computer science courses, but they don’t really learn the real-world importance of them, and that’s why they don’t understand them better. For them, they are just the algorithms and data structures e.g. some concept, not a tool that you can use to write good programs. Do you know that Facebook use them to store our details and Google use them to store web pages and link to search queries. That is why it is very important to have working knowledge of data structures in order to become a successful IT/software professional.

 

Course Features

24X7 Access: You can view lectures as per your own convenience.
Online lectures: ~5  hours of online lectures with high-quality videos.
Updated Quality content: Content is latest and gets updated regularly to meet the current industry demands.

 

Test & Evaluation

There will be a final test containing a set of multiple choice questions. Your evaluation will include the scores achieved in the final test.

Note:
  1. The access to the course can be extended 3 months at a time (for upto 4 times) just by sending a mail requesting for an extension to the email id in the footer.
  2. The hard copy of the certificate shall be shipped to your registered address or your college
  3. There is no soft copy of the certificate.
  4. To get access to the certificate - you need to take the online exam at the end of the course

No prerequisites

 

Topics to be covered

Unit -1 Analysis of Algorithm
  • Learning objectives
  • Introduction
  • Goals of this courses
  • Need for Data Structures
  • Structure: how data is organized
  • ADT
  • Design and analysis of algorithm: Algorithms definition
  • Algorithm Properties
  • Big Oh Notation
  • Functions in order of increasing growth rate
  • Examples of Algorithm Running Times
  • Brute Force Algorithm
  • O(N2) algorithm
  • O(N) algorithm
  • General Big-Oh Rules
  • Mathematical Expression related to rate of growth
  • Various growth rates
  • Worst-case vs. Average-case
  • Static Searching problem
  • Limitations of Big-Oh Analysis
  • Statistics (function calls)
  • Top down vs. Bottom up
  • Examples of Dynamic Programming Algorithms
  • A framework to solve Optimization problems
  • Elements of Dynamic Programming
  • Development of a dynamic programming algorithm
  • Binomial Formulas
  • Frequency Count
  • Complexity Classes
  • Space Complexity
  • Structured Programming
  • Conclusion
Unit -2 Basic of C++, Elementary Data Structures: Arrays, Linked Lists
  • Learning objectives
  • Basics of C++
  • Basic Syntax
  • C++ Program Structure
  • Compile & Execute C++ Program
  • C++ Identifiers
  • Trigraphs
  • Whitespace in C++
  • Comments in C++
  • Data Types
  • Variables
  • Constants
  • Modifiers
  • Type Qualifiers in C++
  • Storage Classes in C++
  • Operators
  • C++ Basic Input & output
  • C++ Loop Types
  • C++ Decision Making
  • Functions
  • Arrays
  • Strings
  • Pointers
  • Object Oriented Programming - C++ Classes and Objects
  • Object Oriented Programming - Encapsulation
  • Object Oriented Programming - Abstraction
  • Object Oriented Programming - Inheritance
  • Object Oriented Programming - Polymorphism
  • Object Oriented Programming - Overloading
  • Representation of Array
  • Dimensional Arrays
  • Search
  • Insert
  • Remove
  • Sparse Polynomial Representation and Addition
  • Stack Implementation of Array
  • Queue Implementation using Array
  • Stack using Linked list in C++ and Implementation
  • Circular Linked List
  • Algorithm for Creating Circular Linked List
  • Using Array
  • Priority Queues
  • Application of Stack
  • Pointers - What Are Pointers?
  • Singly Linked List
  • Linked Stacks and Queues: Stack - What is Stack?
  • Polynomial Representation and Manipulation using Linked Lists
  • Circular Linked List
  • Doubly Linked Lists
  • Conclusion
Unit -3 Abstract Data types Stacks and Queues
  • Learning objectives
  • Definition of ADT
  • Stack ADT-Implementation
  • Stack
  • Array Implementation
  • Stack Class
  • Constructor and Destructor
  • Stack Header File
  • Stack ADT
  • STL Class Stack
  • C++ Run Time Stack
  • Array-based Stack
  • Stack Applications
  • FIFO queue ADT-Queue
  • Implementation of Queue
  • Circular Arrays
  • Empty Queue & Full Queue
  • Queue Class
  • Front & Rear
  • Constructor & Destructor
  • Priority Queue
  • Dequeue
  • Application of Queues
  • Designing a Queuing System
  • Customer
  • Server
  • Waiting Customers Queue
  • Conclusion
Unit -4 Trees
  • Learning objectives
  • Introduction
  • Copy Tree
  • Binary Tree Traversal
  • Tree Traversal Example
  • Sorting Values Using In-Order
  • Binary Search Tree: Operations on BST
  • Binary Search Trees
  • Searching for a key
  • The Maximum and the Minimum
  • The Successor and the Predecessor
  • Search
  • Insert
  • Delete
  • Non recursive Binary Tree Traversal Algorithms
  • Binary Tree Traversal and Functions as Parameters
  • Representations & Applications
  • A Class for Binary Tree Nodes
  • A More General BTNode
  • Binary Search Trees
  • Heaps
  • Trees Representation
  • AVL (Height-Balanced) Trees
  • Insertion
  • Conversion of Forest into Tree
  • AVL Tree Rotations
  • Deletion from AVL Trees
  • Analysis: AVL Trees
  • B-Trees
  • Conclusion
Unit -5 Searching, Sorting and Complexity
  • Learning objectives
  • Selection Sort
  • Insertion Sort
  • Bubble Sort
  • Quick Sort
  • Merge Sort
  • Heap Sort
  • Radix Sort
  • Binary Search
  • Binary search tree
  • Balanced Binary Tree
  • AVL tree
  • B Tree Searching operation
  • Index Searching
  • Search Algorithms
  • Hashing
  • Collision Resolution
  • Open Addressing
  • Separate Chaining
  • Comparisons of Sorting Algorithm
  • Conclusion
Unit -6 Graphs
  • Learning objectives
  • Graph representation-Introduction
  • Traversal Schemes
  • Spanning Tree: Definition
  • Conclusion

Assignment1:

  • Write a program that reads ten numbers from the user. These ten numbers represent the scores that a student has received in a class. Your program should create a nicely formatted report that displays all ten scores as well as the total score and average score that the student received.
  • Write a C++ program that reads ten numbers from the user. After reading all ten numbers, compute the sum of the odd-positioned numbers, multiply all of the even-positioned numbers together, and add these two numbers together. That is, you should add the first, third, fifth, seventh, and ninth numbers. You will then multiply the second, fourth, sixth, eighth, and tenth numbers. The sum of these two numbers is your final result.
  • The library circulation system will keep track of every book as well as library cardholders. Each time a book is checked out or returned, the system must keep track of it. Books can be added to the library’s collection and also removed. Due dates for books should be tracked, as well as notices sent out for materials that are more than a week overdue. Fines for overdue materials should be calculated, and a record kept of the amount owed by each cardholder. Design appropriate classes that keep records of book(book no, book name, author name), cardholders(member no, member name, age, address, city) and issue_return(book no, member no, date of issue, date of return, fine). Write appropriate functions
    • for keeping records of books, videos and audios in the library
    • for checking out or returning of book
    • for adding or removing of books in the library
    • for keeping track of fine due if the book is returned after due date
  • Write a program that can be used as a database of student’s information for a department. The program should be able to dynamically allocate or deallocate storage for the student’s records using linked lists. The database should have the following fields: the first and last names, a course code, and a grade for a student. The program should display the following menu: Welcome to the database menu! Press 1 to insert a new record  Press 2 to delete a record Press 3 to search the database (by last name) Press 4 to print a range in the database Press 9 to quit
  • Write a program for merging two sorted linked lists to form a third sorted linked list.

Assignment 2:

  • Given a linked list of integers sorted from smallest (at the head end) to largest, and a pointer to a  single node containing an integer, make appropriate function that insert the node in the linked list so that it remains sorted.
  • Implement a data structure that supports the following operations: insert, findMin, findMax, deleteMin, deleteMax, isEmpty, makeEmpty. You must use the following algorithm: maintain a sorted array. Insert new items into the correct position in the array, sliding elements over one position to the right, as  needed. findMin and findMax, and deleteMax are trivial. For deleteMin remove the item in position 0, and slide over all the other items one position to the left.
  • Companies and people often buy and sells stocks. Often they buy the same stock for different prices at different times. Say a person owns 1000 shares a certain stock (such as Checkpoint), she may have bought  the stock in amounts of 100 shares over 10 different times with 10 different prices.
    • In this assignment,  you will be using a stack for Lifo accounting. You should use an array based implementation for your  stack based implementation or a linked list for implementing your stack. Your stack should have records with the following fields:
      • The name of the stock (a string or int)
      • The number of shares of a stock (an int)
      • The purchase price (can be a decimal)
    • You can assume that the first element of the structure is the security bought first, the second was bought second, etc.
    • Create a program that should have the user  able to enter information about various stocks, the amount of shares, and the price. The user can then enter a query about a certain stock and the cost according to the Lifo accounting methods for a certain number of shares.
    • The following could be your menu:
      • Press 1 to enter a new stock.
      • Press 2 to find the Lifo price for a stock.
    • If 1 is pressed, the user needs to enter the stock symbol, and the number of shares, and the price.
    • If 2 is pressed, the user needs to enter the stock symbol being queried and the number of shares in question.

Assignment 3:

  • A deque is a data structure consisting of a list of items, on which the following operations are possible:
    • push x : Insert x on the front end of the deque.
    • pop : Remove the front item from the deque and return it.
    • inject x : Insert x on the rear end of the deque.
    • eject : Remove the rear item from the deque and return it.
    • Describe routines to support the deque that take constant number of steps for each operation. You may use array-based or pointer-based implementation.
  • Consider a database of student’s information for a department . The program should be able to dynamically allocate or deallocate storage for the student’s records. The database should have the following fields:
    • the first and last names,
    • a course code,
    • a grade for a student
    • Create a C++ function to search a particular student’s information from the database using:
      • linear search
      • binary search
  • Consider a database of patient’s information for a hospital. The program should be able to allocate and deallocate storage memory for the patient’s records. The database should have the following information field:
    • the first and last names,
    • patient id,
    • address ,
    • related disease ,
    • date of admission
    • Devise an appropriate C++ class and circular queue using arrays to implement the following functions:
      • creation of circular queue
      • accessing the element from the circular queue
      • searching element from the circular queue.

Assignment 4:

  • Create a Phone Book Data Store class. The requirements for this class are given below:
    • Create 2 String arrays for storing names and numbers, respectively.
    • Create class member variables for the capacity of the storage and the number of entries in use.
    • Use the constructor to initialize the arrays to a size specified by a parameter.
    • On this class, create and implement the following 4 methods:
      • storeNumber( ) should take two parameters, the name and the phone number to store; it will not return any value. It will iterate through the store, find the next open space, and store the name and number.
      • retrieveNumber( ) should take one parameter, the name, and return one parameter, the number. It will iterate through the store until it matches the name, and then return the number.
      • replaceNumber( ) should take two parameters, the name and the phone number to store; it will not return any value. It will iterate through the store until it matches the name, and then replace the number.
      • getAllNamesAndNumbers( ) does not take any parameters. It will return a list of all of the names and numbers stored in the store.
    • Use the PhoneBookDataStore.main( ) method to test the data structure. Create an instance that stores 5 numbers. Finally, create an instance of PhoneBookDataStore as a member of your PhoneBook class, and implement the user interface (e.g. prompting) using circular linked list to
      • collect names and phone numbers from the user and store them in the data store
      • print out a list of names and numbers.
  • Implement a class of your own: a priority queue for a hospital emergency room, for example, where it needs to schedule patients according to priority. A patient with a more critical problem will preempt others even if they have been waiting longer. This is a priority queue, where elements are prioritized relative to each other and when asked to dequeue one, it is the highest priority element in the queue that is removed. Write necessary functions on a priority queue as:
    • create an empty queue
    • whenever a more critical patient come, the system will preempt the queue and add patient in the queue depending on its priority
    • access all patients information from the queue

Assignment 5:

  • There are different sorting techniques used for arranging the values present in the list. Suppose we have a list of names of persons as: “Rajan”, “Rohit”, “Aman”, “Jinny”, “Sanjay”, “Bhatachariya”.
    • Write C++ programs arrange these names using:
      • Bubble Sort,
      • Selection Sort,
      • Insertion Sort,
      • Quicksort,
      • Heap Sort
      • Merge Sort
    • Differentiate between sorting Arrays vs sorting Linked Lists
  • A bank needs to maintain records of its customers. It is decided to create a database using B-Tree or any other data structure which you think is useful. The order is based on the key and the Social Security number of each Customer. Each record contains the following information.
    • Name
    • Social Security Number
    • Street Address
    • City
    • State
    • Pin code
    • Date of Birth
    • Marital Status
    • Account Number
    • Account Type (Fixed, Saving, etc.)
    • A DBMS needs to be designed to provide menu driven facility to its users. The facilities are :
      • I to insert the record for a new customer
      • F to find and display the record for a customer specified by name or by social security number
      • U to update the record
      • D to delete the record of a customer from the database.