Fundamental Data Structures & Algorithms using C language.
You will learn the following in this course: (All implemented using C programming)
Fundamental of Data Structure concept
Why we need Data Structures
Stack – Idea, definition, algorithm, implementations.
Using Stack – Parenthesis checking, Polish Notation, Infix to postfix conversion and evaluation.
FIFO Queue – Idea, definition, algorithm, implementation.
Circular Queue using array – Idea, definition, algorithm, implementation.
Double ended queue using array – Idea, definition, algorithm, implementation.
Linked List – Idea, definition, why we need linked list. Comparison with array.
Singly Linked List – Development of algorithm for various operations and then Implementation of each of them
Creating Stack and Queue using Singly Linked list – Implementation.
Doubly Linked List – Idea, definition, algorithm of various operations and implementations.
Circular Linked List – Idea, definition, algorithm and implementations.
14. Calculating efficiency of algorithms, Worst Case (Big Oh), Average Case (Big Theta) and Best case (Big omega) complexities. How to calculate them for different algorithms.
15. Binary Searching
16. Recursion in detail. Example program using recursion and the critical comparison between Recursive approach and Iterative approach of problem solving.
17. Binary Tree, definition, traversal (In, Pre and Post Order), Binary Search Tree implementation.
18. Heap data structure, definition, heap insertion, deletion, heap adjust, Heapify and heap sort.
Introduction to the course.
All about Stack
Introduction to stack data structure. Definition and description, how it works. Understanding Push and Pop operations along with overflow and underflow state of a Stack.
Evaluation of your basic understanding of Stack Data Structuure.
Real life applications where Stack has been used, just to help student understand how stack can be used for practical purposes.
Understanding and development of basic algorithms for Push and Pop operations of Stack.
This quiz will tests your understanding about the Stack operations.
Implementing Stack operations using C programming language.
Explanations and clarifications how the pointers works for implementing Stack operations, why we should pass the address of Stack object to the functions.
Building a console based menu system for the Stack operations so that one can call and test the different Stack operations and see how they works.
The stack we developed was fixed in size, now let us improve the implementation using dynamic memory allocation technique so that the stack can be allocated with custom size.
Improve the stack implementation by adding more dynamic mechanism to it, when the stack is overflow grow the stack to double in size dynamically retaining the existing content.
Using the stack data structure in solving a problem. If you try to develop a program for converting an unsigned integer to it's binary equivalent then you will need a Stack. See how stack helps to develop a program to solve a problem.
Another programming example where we can use Stack data structure.
Step-by-step developing a parenthesis checking program using Stack.
Let us understand the problem and how we can approach for a solution using stack. How stack can be useful for developing a solution.
The algorithm for solving the problem of parenthesis checking.
Detail explanation of algorithm for checking parenthesis, whether the parenthesis are well formed in a mathematical expression or not.
Starting the implementation of the parenthesis checking program using the C language.
Completing the implementation and executing the program.
Polish notation and Reverse Polish Notation.
How expressions could be represented. Introduction to Polish and Reverse Polish Notation.
Understand how the default precedence works, how we can use the precedence to convert from infix to prefix or postfix. Learn how to manually convert infix to prefix/ postfix.
Check your skill on converting infix to pre/post fix and how you have understood the functionality of precedence of operator.
Understand how we can evaluate Polish or Reverse Polish Notations using Stack.
Developing algorithm for evaluating Postfix expression using Stack.
You will follow how the evaluation of Postfix expression could be implemented using C Programming language. It will be best if you can try to write the code just after watching the algorithm and cross check with your implementation with the one that is done in this video lecture.
Understand how we should proceed to convert an Infix expression into it's equivalent Postfix expression using a Stack.
Another example, a more complex one, that will help you to understand the procedure for converting infix to postfix, clearly explains how precedence function should work in such a routine.
To help you understand better, just added this lecture which explains in details again about the procedure that converts the infix expression to postfix. Since, the procedure is little bit tricky, this lecture will help you to ease the complexity involved.
This lecture develops the algorithm for converting Infix expression to it's equivalent Postfix step-by-step. It is strongly recommended that you complete the previous lectures of this section and then start with this. The previous 3 lectures specially discussed the procedure that I am going to use here for developing the algorithm.
Let us dry run the algorithm, that we developed in the last lecture, with some input infix expression to convert it to Postfix. Take your Pen and Paper and do the dry run with me.
In this lecture I will show you how to develop the PRCD function that takes care of comparing the precedence of 2 operators. We need this for implementing the infix to postfix conversion implementation.
Finally, let us write the C Function to convert infix to postfix. The best way for you will be to write the code along with me side-by-side.
Finally combine the functions written to convert from infix to postfix and postfix evaluation into a single program. This is your task to put them together, I am just giving the proposal ;).
All about Queue
Understanding Queue data structure - definition, operations on a Queue, various types of Queue data structure.
Understand how we can build a FIFO queue using one dimensional array. The description and the animation will help you the understand the core concept of how front and rear marker used for building a FIFO queue.
Developing algorithm for insert and delete operations for a FIFO Queue.
Take your pen and paper and proceed with me for dry running the algorithm for FIFO queue operation - this is the best way to understand how any algorithm works.
Implementation of FIFO queue operations using C Language. Open your favourite IDE and start writing with me.
A simple console based menu is added to call different Queue operations.
Understanding what went wrong with our implementation of FIFO Queue.
Explanation about the flaw in the FIFO algorithm.
Introduction to Circular Queue data structure for implementing FIFO queue. Idea of how we can move the rear and front circularly over the array.
Conception on how to perform enqueue and dequeue operations for a circular queue. The conditions for overflow and underflow.
The algorithm for enqueue and dequeue operations for a Circular Queue.
This lecture shows how we can implement Circular queue concept using C Programming language.
Introduction to the concept of double ended queue.
Development and understanding of the algorithm for Double Ended Queue data structure.
Let us do the dry run of the algorithm of various operations on Double Ended Queue.
Implementing operations for a double ended queue using C programming language.
Introduction to LinkedList Data structure, drawbacks of Arrays and facilities of having LinkedList. When we should use LinkedList.
Understanding the definition of Linked List, conception of Node in a Linked List, how the link works. The external pointers for accessing linked list.
Idea of different categories of linked list, when and how they are beneficial.
Singly Linked List
Declare and understand the 'struct' types we need for representing a Node and a Linked List. First step for building various operations on Linked List.
Understanding various functions and their prototypes which we will implement for abstracting various operations on Linked List. Understanding how we should pass the linked list object to various functions.
This lecture describes and simultaneously develops a function to add a new node at the end of singly linked list.
Let us now understand and develop a function to dynamically add a new node as the first node of the singly linked list.
Let us understand how we can traverse the entire linked list node by node starting from the first node until we access the last node. Then we build a print function that traverses the entire linked list to print the content of each node.
To understand clearly how nodes of the linked list resides in memory developing a function that will print the content of next pointer field of each node, address of the node and the content of the node. When we execute this, you can see how addresses are used to build the linked list.
Just compiling and running the programme written so far.
A practice exercise for Singly Linked List.
How we can search for a target data in linked list.
This lectures shows how we can build a function that reads data from a text file and builds the linked list using those data.
This lecture shows how we can generate random numbers and use them to build the linked list using insert at tail operation.
This lecture describes and implements how we can implement a function that deletes the first node of the linked list.
In this lecture you will get the way to develop delete last operation to delete the last node of the linked list.
Let us develop a function that deletes a node containing target data (if that exists).
Understanding and implementing the idea of reversing a singly linked list. This lecture shows you how you can reverse the linked list physically, on calling the reverse function twice in a row, the linked list will remain same.
Let us try to develop function that uses recursive technique to traverse the linked list.
Let us now build a Stack using Linked List. Implementation of Push and Pop operation when we use linked list as data structure for building a Stack.
Lets us build a queue using Linked List data structure.
Doubly Linked List
Introduction to the Doubly Linked List data structure. Each node contains two pointer this time - traversal in both the ways are possible with doubly linked list.
You will get to know what is the new stuff that we need in the Node to make the linked list doubly. You will learn about the various operations on Doubly Linked List.
Understand and Implement of AddFirst operation that will add a new node as the first node of doubly linked list.
This lecture describes and shows how you can add a new node as the last node of the linked list.
This lecture describes various delete operations for a doubly linked list - delete first to delete the first node, delete last to delete the last node, delete target - to delete a node that contains the target data.
How we can develop a double ended queue using doubly linked list.
Circular Linked List.
The definition and structure of Circular Linked List. Understanding the basics of Circular Linked List.
How we can develop a function that inserts a new node into the Circular Linked List.
How we can delete a node from the Circular Linked List.
Lets understand how we can traverse a circular linked list. Idea of how we can build a Circular Queue using a Circular Linked List data structure.