# Python 🐍 Plots

A plot is a visual representation of the data and is especially valuable to analyze data graphically. You can plot with the matplotlib package. In the incubator example, we may want to see how the temperature changes with time. The x-axis may be time and y-axis may be the data. In an incubator, graphs could be used for a number of things. Some could be heater percentage, egg temperature, and much more.

IPython Notebooks on Github: https://github.com/APMonitor/begin_py...

# Begin Python 🐍 for and while loops

There are two basic types of loops including for and while. A for loop is to repeat code a predetermined number of times. A while loop is to repeat code but where the stopping condition may not be known before the loop starts.

Source code: https://github.com/APMonitor/begin_py...

# Begin Python 🐍 Course Introduction

Welcome to this introductory course on Python! This course is intended to help you start programming in Python from little or no prior experience. There are video tutorials for each exercise if you have questions along the way. One of the unique things about this course is that you work on basic elements to help you with a temperature control project. You will see your Python code have a real effect by adjusting heaters to maintain a target temperature, just like a thermostat in a home or office.

One of the best ways to start or review a programming language is to work on a simple project. These exercises are designed to teach basic Python programming skills to help you design a temperature controller. Temperature control is found in many applications such as home or office HVAC, manufacturing processes, transportation, and life sciences. Even our bodies regulate temperature to a specific set point. This project is to regulate the temperature of the TCLab. Each TCLab has thermochromic (changes color with temperature) paint that turns from black to purple when the temperature reaches the target temperature of 37°C (99°F).

Final Project Objective: Program the TCLab to maintain the temperature at 37°C. Display the heater level with an LED indicator as the program is adjusting the temperature. Create a plot of the temperature and heater values over a 10 minute evaluation period.

To make the problem more concrete, suppose that you are designing a chicken egg incubator. Temperature, humidity, and egg rotation are all important to help the chicks develop. For this exercise, you will only focus on temperature control by adjusting the heater.

There are 12 lessons to help you with the objective of designing the temperature control for the incubator. The first thing that you will need is to install Anaconda to open and run the IPython notebook files in Jupyter. Any Python distribution or Integrated Development Environment (IDE) can be used (IDLE (python.org), Spyder, PyCharm, and others) but Jupyter notebook is required to open and run the IPython notebook (.ipynb) files.

Install Anaconda (Python): https://www.anaconda.com/distribution/

All of the IPython notebook (.ipynb) files can be downloaded at this link. Don't forget to unzip the folder (extract the archive) and copy it to a convenient location before starting. The course is freely available for download with course files on Github: https://github.com/APMonitor/begin_py...

1. Overview
2. Debugging
3. Variables
4. Printing
5. Classes and Objects
6. Functions
7. Loops
8. Input
9. If Statements
10. Lists and Tuples
11. Dictionaries
12. Plotting

You will also need a TCLab kit to complete the exercises and they are available for purchase on Amazon: https://www.amazon.com/gp/product/B07...

# Begin Python 🐍 Overview and pip install

This introductory course uses the TCLab package that can be installed with:

pip install tclab

or:

!pip install tclab --user

if you are running in a Jupyter notebook and do not have administrative privilege. The 12 modules of this course are intended to help you complete the final project.

Final Project: You have eggs that need to hatch in an incubator. One option is to constantly check the temperature and adjust the heaters manually. Another way is to automate the temperature control by constantly checking the temperature and adjusting the heaters with Python. Unfortunately, you only get three eggs for the test and one attempt to get it right. You do have a simulator of the incubator (TCLab) so you can practice Python, without having to worry about mistakes. The purpose of this lab is to develop a temperature controller (like a thermostat) that could be used for an egg incubator. There are other factors such as humidity and turning the eggs that are important with incubators but we'll only focus on the temperature for this project.

Source files: https://github.com/APMonitor/begin_py...

# Begin Python 🐍 Pseudo-Code and Debugging

One of the biggest time consuming parts of programming is debugging, or resolving mistakes in the program. This is true for every language because the computer needs exact commands, which is very important for precise measurements and control for incubating. A few steps can limit the time you are searching for mistakes, instead of completing the project.

1. Start with understanding the big picture. It seems silly, but once you start going over the whole thing you find a lot of gaps. Do this in whichever way suits you best, we’ll leave it up to you. For the egg incubator, it would be understanding what you actually need to do to help an egg hatch.

2. Start by outlining your code, writing **high-level instructions (pseudo-code)** what you want each section of the code to do. Break it into more specific tasks. You can do this even without understanding the basics of Python. Once you learn Python basics, you can translate these high level instructions into code. Organizing the outline helps to make sure your programming isn't more complex than it needs to be.

3. Program the specific tasks and connect them together. Direct tasks make it significantly easier to program because the program is modular. It’s a lot harder to program something if the program is large and complex. For the incubator, this may be programming something specific like how hard the heater should work, based on a low temperature reading.

4. Test and fix problems. This is basically debugging, but don’t only test the whole project all in one go. It’s much easier to find a problem if you test every once in a while, when you are programming smaller parts. A good way to do this is grab a specific piece of code, run it on a seperate file, and see if it does the job you want. An example would be fixing when the heater should stop working, so the egg doesn't go over temperature.

The better you follow these steps the less time you will have to spend fixing problems in your code for your incubator, or just Python programs in general.

# Begin Python 🐍 integer, string, float

Variables store information and are objects in Python. For example, if you wanted to keep a set temperature for an egg, you would type egg = 37.5 for °C or egg = 99.5 for °F. The first part tells what the variable will be called, and the value after the = tells what is being stored.

See https://github.com/APMonitor/begin_py... for source files.

# Begin Python 🐍 print

Printing is displaying values to the screen. The word print comes from the time when programs previously put ink on paper. You use the built in python function print() to output values. You could use this to tell you what is the current temperature from a temperature sensor.

See https://github.com/APMonitor/begin_py... for source files.

# Begin Python 🐍 Classes and Objects

Classes are collections of objects and functions. Many Python packages such as time, tclab, numpy, scipy, gekko, and others are distributed as classes. A class is imported with the import statement such as import time. Time is a package that has timing functions that we will use to pause the program for a specified amount of time. TCLab package has functions created with tclab.TCLab(). The next lesson shows how to use the tclab functions.

Source files: https://github.com/APMonitor/begin_py...

# Begin Python🐍 functions

Functions create modular code that can do the same task repeatedly without you having to type out the same code each time. Functions make complex code accessible with a single statement. You also can create your own function, but there are also some are built in to Python or in many packages. One built in function you have already seen is the print() function.

Source code: https://github.com/APMonitor/begin_py...

# Python Vs R for Data Science - One Clear Winner

This video titled "Python Vs R for Data Science One Clear Winner" explains and compare both R and Python language on seven parameters when it comes to machine learning. Although both of these languages have their own strengths and weakness yet we will choose a clear winner based on these parameters.

# 1 Introduction to Python | Hindi

This is the first lecture of Python tutorial in Hindi.

# Data Structures- Leture 4

Data Structures
Lecture 4

Stack Representation

Pointed to original stack top. And now change the stack top pointed to the new pointer implement top to the point to the new node. And increment the count of the stack by one. And return one. And Return one this is indicated. So this is what we do for insertion into a stack. As we consider to this is very similar to the insertion into the front of the linked list. Now let us look at the next operation of stack. Which is pop. Pop is to delete the element and as you know you can only the delete element from top of the stack. That is the constraint that you have on stack. So this is the same as the removing first element from a linked list. So what you have to do is. This is an original stack. Now the only element you can delete or remove from the stack from and do the pop operation. In this element. No other element can remove. So what you do is. You make the pop. Now point to blue. Ok. That is it. So now you can access the stack. Only. Throw this. Now you have a node which is short of bankling. So this can be recycled. So you make a pointer to Point to this node. So that it can be recycled. So this is the pop operation. So the code for the pop operation. As follows. So you have a pointer to point to the node. Which you want to the return. And if the stack already discussed you want to a deletion and what do you want we consume must. First ensure that the data structure from which you want do the deletion. Is not empty. So that is what is doing here. Just checking the count what whether equal to zero. You saying that will return zero. Which means that is an underflow. That is no element. To be delete it. Otherwise you make this pointer to point to the original stack. This is for recycling purposes. And then what you do is. Make the stack top. Point to the new stack. Top and if free, dlt pointer. What do you going to doing here is, string is the node. That has been deleted. And decrement the stack count and return the value of stack. This is code for the pop stack. Both these cases the stack is represented using a linked list and these particular data structure is very useful. When we are doing for organizing the nodes in an allocated list. It is called allocation list. And these represented linked list. Who store all the nodes are has been deleted are when you want to delete. You store for recycling take allocated list. Which is represented as stack. When you want to insert to take a node from same allocated list. So the next stack top is already discussed before stack top doesn’t change stack at all. Just access the top element of the stack. So again if the count is only greater than zero. That mean stack doesn’t contain anything. Then just take out the pointer to the top element. Make that data to be returned in data pointer and return 1. If it is less than 0. That means no stack. So you return. So that is top. Know hearing to change of the list, this is can normal thing. And empty stack a stack count. So what you do here in. if the count is equal to zero then the return value. Otherwise the stack is not empty. This is a code for Boolean function. This is an empty stack. Which
is return value from the stack is empty. Which is value is false. The stack is not empty. This is return a count. So already maintain the count. There are implementation do not maintain count of the stack. Certain implementation you maintain count .so return stack. That is it. So the count can be equal to zero. The stack is empty. You can also check for full stack. This is assuming that u have decided that only so many nodes going to give for the stack. This is a stack. If you have stack full condition then malloc is failed. If malloc is failed, it means, you cannot there is no temporary node to be given to for the operation. In which case you have a return 1. So this is a full stack. Where you cannot, remember that in full stack condition checking whether there are nodes available for putting into the stack. If there are not saying full otherwise putting full. This is not like an array implementation already allocated the size of the stack. This is the destroying stack Destroying complete stack. So you want to delete all the nodes in the stack. So if the stack top is null it means already stack is empty. You don’t have after do any destroying. So if it is not null. Then you make delete pointer to point to the top of the stack top of the point to the next node and free delete pointer. You keep doing this. Till the stacks it will come. Come to the last node in the stack. The Stack is now empty then the destroy the head node. So free that and you return null. So this here having a by loop. Here this is the logic. Where you keep on deleting nodes of push. Popping of the nodes. Till start becomes. Now what you seen upto now is the some of the implementation of stacks. Where we look at linked list implementation of the stack. In this particular implementation of the stack. What you done is we are assume that you have a count. Also it is not necessary. So in case you don’t have a count the code has to be appropriately modified. Stack Applications Now let us go to next some of the application. Using stack. Very interesting applications. I said used in no.of places in computer science itself. For example, the stack is a particular specific data structure that is used for quick sort algorithm is a difficult data structure. It also used in other applications. Like very important application where you have to maintain the program counter and return address in the case of recursive calls in function calls. So this is very important data structure as well as computer science.is concerned. We are looking at 2 very different application. One is the depth first search. And one is the N_Queens problem. So let us first look at the depth first search. The depth first search actually backtracking type of concept. That it uses. And this backtracking type of concept we do use stack. Stack is a difficult data structure that is used for doing back tracking. So this problem as follows discover a part from start to goal and
the solution you have to go deep. If there is an unvisited neighbour go there then you retreat along the path to find an unvisited neighbour. The outcome is if there is a path from the stack to goal. DFs very finds such a path. So that is going to go deep and cannot enough to do. Go to DFS wise. That is an idea. So this is a difficult application of a stack. So let us soon given a tree and if you want to find the goal. So initialize to start at 1. That is pushed on to the stack. Then you go to two depth number. To get to the child. So push 2. When you push 5. 5 has no children so you go to the sibling with 6. Then Go to child 9. After then you don’t have anything. So Pop it up. Pop is 6 out. Then pop 5 out. Pop 2 out. When you go to the next child which is 3. Then you go to 7. Then you go to 10. That is depth first we go to 10. Now you have identifying the value. So that the path followed 1,2,5,6,9. Then back tracking up and then go to 1. Find the next child go down. Ok. That is the path followed by the depth first search. So let us algorithm for the DFS. So the stack is first initialized. And you stack the operation look at push start. Now while the stack is a not empty. This is keep track. You data in the top element. If it is the goal you just put access. If T has a unvisited neighbour. Choose an unvisited neighbour n. Mark N as visited and push n into the stack. Otherwise that is if doesn’t have a unvisited neighbour. When you backtrack take in the next node from the stack. Keep doing this. Till stack is empty. Are you reach the goal? So this is the DFS algorithm. Of course you searching the node in a algorithm you can also happen that here may be a failure. So this is a difficult application of stack. Where the stack is used to maintain the node. When we want to do the DFS algorithm. As specially backtracking algorithm. This is a difficult data structure that used many concept used back tracking. Also used stack is a basic data structure. For implementation purpose. N-Queens Problem
Now you going to look at what is the N_Queens problem? This is a difficult problem in artificial intelligence and the N_Queens problem is actually problem associated with the chess board. So in this lecture I will explain the problem and then how it is solved using the stack. OK. So first let us see what the problem is the NQueens problem can be defined as follows. It is a backtracking problem to solve the NQueens. Suppose you have 8 chess queens & and a chess board. Can the queens be placed on the board? So that no two queens are attacking each other? Now what do you mean by attacking. We will see that as we go long. So the problem is this. Two queens are not allowed in the same row, or in the same column. Or along the same diagonal. So that is the idea. So 2 queens are not allowed on the same row, and the same column, or along the same diagonal, the no.of queens and the size of the board can vary.
Normally use all this problem for the NQueens problem. We are going to take it can simple example and show you. But basically solve it for any queen. It after all chess board is the square. So you can 64 * 64. Where N = 64 and so on. So basically NQueens can be represented this way you consist of NQueens. And chess board that you have consist of N rows and N columns. So your aim is placed NQueens on the boards. Such that if you have a queen here. We don’t have queen anywhere here and also don’t have anywhere queen here. So you gone queen same diagonal on the same row, same columns, along this same row. That’s the problem so are idea is to try to find solution to this problem. The computer program to solve this problem. Program tries to find a way to place N queens on the N * N chess board. Following the instruction we already seen. Now comes the application of stack. We going to uses a stack to keep track of where each queen as already been placed. So first place a queen on the board. The position of the new queen is stored in a record which is placed in the stack. And also you have an integer variable to keep track of how many rows have been filled so for. So these are two things that a going to use keep track of how to place the NQueens. So the is how the program works you have take 4 */ 4 board in very simple example to show the how the program works and this is the no. of queens to be filed. Which is 4 and this is stack to be used. Stack contains record. Which gives the position of the queen. Which is 1,1 is the position 1,2 mean this 1, 4 means first row , 4th column and so on. And this is the variable. Which keeps track of how many queens have already been placed. OK. This is the way. This is the complete show. You have a N * N board. You have NQueens, you have a stack. Which give the position of queen and you have the no. of queens that mean placed directly as the program. Now let us start the program. So first you place 1 here. Then you come do this what happen so that is 1,1 has been placed here. Then you come here. Now can you placed queen here, you can’t the queen placed here. Because along it a same diagonal so the logic uses that you shift it once to the right and see whether breaks it in a rules now that is no queen along the column, that is no queen along the row, that is no queen along the diagonal. So this is allowed. Now you have a queen at 1,1 you have a queen at 2,3 and 2 have been filled. Now we are to place this. N row you can place it here. Can’t place it here. Because if it is in the diagonal. So what you do is? Go up here and place it here. can you place it here 3, 4 so 3 rd row, 4 Th column you can’t place it here. Because of the fact at that along diagonal. How the program works? When we run out of remove in or row, pop the stack,
reduce filled by 1 and continue working on the previous row. Let us look at that. What is mean these? When you can’t place, pop it off. Go to the previous row and you see whether place it along that. Along the right or left. You will see the logical as we see go long. Again I tell you. When we run out of room in a row, pop the stack, reduced filled by 1 and continue working on the previous row. Whatever you placed in the previous row, here are having so ok. That is what is happened here. This is r th position. We still have to queens 2. And reduced filled by 1. Now we continue working on row 2, shifting the queen to the right. Now instant have it here. We pop it up. And shifting the queen here. Now thus has to been incremented this position has no conflicts, so we can increase filled by 1, and move to row 3. So now we move to row 3. Ion row 3 what happens, we can’t place it here. Because diagonal. So placed it here. And then we go to 3 one. And this is the conflicts. We stack again first column conflicts. Second column that is no conflicts. So that is how we so along to the problem. You can work it on row. You see how 4 queens are filled. So the logical basically to be repeat. That is you take the row placed a queen there. Then you go to the next row place the queen there. When conflict arises. What you do is? You tried to push the queen to right. If it is possible and you know no conflicts arises. If you come across a conflict then you pop the top element from the stack. That’s you are a backtracking. You are not using that. Already placed it, removing from the stack. Which remove it. And try again to reworks on the previous row and that’s how you do the queen. Nqueens problem. So for are nqueens problem. Let us see this is slightly different from the problem. That mean normally used. We are going to first talk about the pseudo code.so here what we do is. We first initialize the stack. Which is date structure. We want to use. Keep track of artificians and we also place the first queen. Pushing its position onto the stack and setting filled it equal to be 0. This is pseudo code repeat these steps. If there are no conflicts in the queen then we do else if there is a conflict and there is room to shift the current queen right ward do it. Else if there is a conflict and there is no room to shift the current queen right ward then what we do. You have do keep on doing this. Repeat these steps. There are no conflicts increase filled by 1. If filled is now what then doing here and take this each of the steps and giving the details. If there are no conflicts with the queen what we do increase filled by 1. If filled row is now N. That means filled all the queens then the algorithm is over. Otherwise, move to the next row and place a queen in the first column. So that this steps is over. So what we and done is. We done this. If you take one queen ok. We are placed it the first in the row. We see there is a conflict. Then there is a conflict moving a right. If there is a conflict and
there is a room to shift the current queen rightward. Move the current queen rightward adjusting the record on top of the stack to indicate the new position. So, this is in the same row. Even that you can’t do. Position where you have can’t fill the there is conflict. Can’t move rightward and fill. Because there is a conflict again. If there is a conflict and there is a room to shift the current queen right ward. This is place to have do a back. So what you do. You keep popping the stack and reducing filled by 1. Until you reach a row where the queen can be shifted rightward. When you shift this queen right. Then what you doing is. What ever done before you backtracking. Can backtracking till you reach the position? Where you can have another alternative. Which is not placing that. But moving it to the right. If it is possible. So the movement to the right once step of the time. But you move one also. So that is the NQueen problem. By the NQueens problem is very challenging is that. We are actually redoing the work. We already done. So that we get the choice of what we doing actually in the algorithm is we first start with the easiest method. Placed the first row that we see. Then we keep on doing it till the and the second we can take is every ok. When I placed in that place there is a conflict. So I will let move right to see. If you move to right and see, fill a conflicts. So I will let more right to se. If you move to right and see, fill a conflicts. Only then I go back. And I check whether. What I will done can be changed so that’s can be accompanied. You can properly try thus for 6 * 6 or 4*4 on your own on. Similarly act how it works. That will be a good exercise for you. When you for you do understand. How the stack works and how backtracking algorithm work also. That is explain both the concept of backtracking as well as the application of stack to backtracking. Now let us look at some problems. Associated with stacks. There is know up to implementation of stack.

# Data Structures - Lecture 3

Data Structures - Lecture 3
Data Structure
Lecture 3
from the stack has been remove the stack is empty now if you give pop operation there is error in the condition because the stack has is empty .so let us look at stack as an abstract data type so that means we are not bother about the implementation we going to using this stack so basically for any stack. Whatever the implementation the following at the operation of function that associated with the stack so one is create this means you just create an a empty stack for the implementation then the push you seen in of about the push. Push means added an element top of the stack then you have pop which means pop an element from the top of the stack you don’t have to specify the element because only think at pop from the stack is top element then stack top which you already defined that is you are accessing the top element of the stack no changing in the stack that is the top remains in the same number of element in the stack remains the same then you can also have full condition the question mark that we put here is you cannot check a full condition when you do a link list implementation of a stack because you can keep an adding notes dynamically but fill make sense in the stack is implemented as an a array and then empty is when the stack is element that is does not contain any element so this is the stack in empty condition so you can just look at this small data structure of this so you have a external interface you have a data structure and can have the data here so this is the data you want to input in to the stack this is just giving feeling of what is available outside. The outside is when you doing push you have indicate which element it is X. which stack you want to put it and similarly when you defining the stack you have to also know the access point that is top of the stack so one typical application of a stack is the famous parenthesis matching or matching of brackets so what it do here this you don’t have a matching parenthesis here so what it do you input when you see the traverses list from this corner when you see the bracket you put it in the stack then you see the other bracket . Put it the stack then you see an a just pass it don’t be anything you see plus B don’t be anything then you see the closing bracket. So you look at this stack and C whether whatever you have top of the stack matches this if it matches you removed that so now you left with is one bracket one that we put here then you see a divide sign don’t be anything just pass it C. don’t be anything then you finished you come to the end of the expression when you come to the end of the expression if it was matching expression. You should have add the stack is empty unfortunately now the stack is contain the single bracket so you know that the equation has not brackets have not been matched if you look at this same think you can do it surffency you see that this you will put on the stack. Then here you will you put on the stack again are left with closing bracket that is not matching so here are matching we a put in this on the stack then you putting a open parenthesis and the stack then you have a matching closing parenthesis which will cancel each other that will left with in
open parenthesis here you will left with the closing parenthesis but however you do that always you should have the stack is empty then only it’s matched now in this example you take on simple example there is only one type of bracket you can have any type you can have square bracket and check the corresponding matching.

So you can actually do parenthesis matching automatically using the stack data structure for any type of complex expression so as we already saw the stack ADT can have several implementations. Implementations may be different but implementation details are be hidden and the interface function have to be the same and most application programmes should not see any difference just because using array implementation arm using a stack implementation. So let us first look at the stack implementation using an array so stack is stored as an array when you stored stack is an array immediately it means that the number of element has to be allocated that is how many element this stack in cold so I can here constantly look at the stack as we done before so I have defined something called as defined stack array and then have a something called as stack max. Stack max is maximum number of elements that I can store is physical array and top tells be the top element you can actually not have the count also the doesn’t matter but stack array, stack max, and top has to be defined. If you want to define a stack using array so implementing stack using array. It’s a simple implementation. The size of the stack must be determined when a stack object is declared space is wasted if we use less elements suppose you have a stack you declared it have hundred elements and usually the stack within ten and fifteen then you wasting the space and we cannot push the more element and then the array can hold. So this is the typical definition of stack of integers in an array implementation. So what you doing here is we are declaring the array call stack array and then this is the number of element at count then stack max this is equivalent to what we saw before for this . We are defining the structure so this is the maximum element and this top is the index of the top element. So all of them are integers in this case so first step here is creating a stack so you will say the create a stack with maximum elements ok so if the stack is equal to null check as stack is empty you return a null otherwise you going to now you going to allocate the stack. So first what we do you initialize the top of the stack to be minas one and count is equal to zero remember this is stack which is empty. So doesn’t have anything. So you can defined the top of many way in this implementation have a initialize. The stack to be minas one and stack count be equal to zero that is same and then stack max has been initialize to the maximum. Number of elements that we want the stack hold and the stack array that is the complete array defined as allocate maximum element into size of the element size. So if stacks stack array is equal to null. Then that means free all free the stacks always return the null so it done here this you creates at a stack which called stack array which has top is equal to minas one
count is equal to zero and the stack max equal maximum number of element. So next let as look at the push operation so the push stack you have when you remember when I told you told that you have a push stack operation you have two think as to define one is the stack array which is the array in which you want to push into the next is data element that we want to push so first for any push operation infect this is two five any in session operation you have first check whether there is place to instant the element in other words. So for that we are doing a stack check full stack check. So here what you doing is if the count of the number of elements is equal to the maximum number of elements is stack can hold then we are returning zero let us it is over flow and the number of elements in this stack equal to the maximum number you can hold and you cannot add any more elements otherwise when you come out this it means that you have to place the hold elements but in case what you do is you increment the count so the number of elements in the stack increases by one you increment pop by one because now want to create to a place pointed at to this top, there you want to inset the element and then what you do you with array at the position calls top you inset the elements that you want to inset and you return one . just this indicate that the push operation has been success if it already full then you did have return zero which means that there is the problem there is an error and this condition the error is a overfull. So this is how you do please note here we are first incrementing talk to create place and then we are putting the element into the top position so next let look at pop operation again as you know in any deletion operation you should have something to delete so in deletion operation you will get an under flow the same is true for stack. So here what you do you given a stack given data output pointer this is the data you going to output and given a stack you can you did not have the as in input parameter you can gives the stack and you can delete from that but here want to get out what is top on the stack for that’s why having the extra parameter some pop operation implementation do not look at this is a separate parameter inside the pop operation. One of the example. We saw people we did not have to parameters for the pop – operation. So here what you do this please remember this is array implementations? So what you do is you first. Check whether stack is empty if it is empty then you cannot do a deletion operation, became you don’t know anything to delete. So you getting underflow condition otherwise what you do is you have to take out the them the list of the stack so what you do the access is top element of the stack and take it out is the variable call data output points and decrement the count by one because round in the count number of element is decreased and decrement top also by one because previously whatever top is pointing to is now a empty so end don’t want to access is you will decrement all and return one indicate one it is successful operation this is the top operation this function retrieve the data is the top of the stack without
changing the stack so again as we already saw pre-conditions stack is pointer to the stack and post return one its success zero is under flow so have what you do is we have the stack again and this is the output pointer as we did in the pop operation so it the count is greater than zero than only you can do the operation. If it is can then zero you don’t have to access at all because these stack in empty you don’t have a element so it is next zero that this then element greater than zero that is element so you just take out the elements not take out you just access the element but remember no top changing nothing change is the count does not decrease nothing happens only think is accessing the top element so hear after the top operation this stack remain same is as already told you and returning zero this return zero is if not able to do the operation because of count being not greater than zero which mean that’s the stack is this is the condition check whether the stack is empty as next so the pre-condition is stack is pointer to the stack and post condition is if returns one its empty and zero is there is data is this stack so here what you do is again the input the stack and you that’s the structure stack. If the count is equal to zero that means is an empty stack. You just Boolean you will return the value that is true value similarly full this function determine the stack is full so fully detained as heat full ok heap full for latter so pre stack is pointed to the stack head note suppose if return one heap for stack is full and zero is heap as room what you do here is this is full stack condition again we have the complete structure now here because its and array implementation then you know the stack is full then the count is equal to these stack max so if count is equal to these stack max so if the count is equal to the maximum element the stack in held then we know that the stack hen full then you return the value now Growable tray – based stack this is the slightly difference diversion of what will apposing to say In a push operation, when the array is full, instead of throwing an exception, we can replace the array with a larger one. How large should the new array be? Incremental strategy: increase the size by a constant C. doubling strategy, double the size, what you mean by here is we docent usually know cannot predict how much the size of stack will be now the problem here is that you have if you put stack is 1000 elements are using one 10 or 15 eliminating wasting are memory resources are then have you put is or 10 elements you against to 20 or 30 elements then you concisely you will getting a stack full condition. So one we doing this is have global array stating what will you do is if you get stack full condition that point you reallocated larger array and then put all the stack elements is to that array so this is not a very simple operation. This is changing of elements from one array to other bus assume that you can do that but two strategists of how the largers array allocated how much of how much should be one think you going to suppose the original stack size is 10 and you a have stack full condition you can increased by constancy size 5 and every time to get a stack full condition keep
top immediately stack not accessible all so disturbed the stack. So here you have two data structure that we using two modes that using one this is stack head other this stack node so this stack will have a count and top which is count an integer and top is a doubt pointer this will have a data type and this will be a link which is again note point this is similar to structure that we used for this but here the operation are restricted I already told you that again this data type can be a single data type or have a large record whatever so the key data structure of this structure that used this CR again a node with key integer data and struck node which is an address and you can also have stack and the stack is represented by a count and the stack node pointing to the top so let us look at operation a stack so when you create a stack you have a pointer to the stack and you have allocate this equal to be size of the stack. So if stack equal to null then you initialize the top and have you going to this is creation of the stack remember and you already seeing here how do you create a stack what do you this to put the count equal to zero and top equal to null that is exactly what you a doing here putting the top equal to null and count is equal to zero and the address of the stack is return this is the allocating the size of the I mean allocating stack to be dynamic allocation of a node.

# Data Structures - Lecture 2

Data structure Lecture -2

Arrays We are going to look at two implementation of list. Two important implementation of list. One is array and another is using linked list. So first let us look at implementation of list using arrays. Before we are going to that we have to know what an arrays? Array is usually associated with pair of values an index and a value. An array is a sequence of indexed items. For example when I say the first element it is the index is one. And then the element is also fix as five are something other. If I say 10, A it means that the 10th index is 10 and the element value of the whatever the element there will come out. So associated with each index there is a value, and normally an important constraint of arrays is that the length of the array has to be fixed. Before the array is created and it is implemented using consecutive memory. Now one important thing that we have do known is that when we represent list using arrays, the list is logically continuous as well as physically continuous in other words the elements of the array are stored in consecutive memory location. When an array is created consecutive memory blocks is allocated dynamically to store the values of the element of the array. So if we take an example.

Let us assume that the array consist of 0,1,2,3,4. You will see that, here we assume that 2 address location are used represent one element of the array. So 1 to 2 it’s contains 0. 1,2,3,0 contains 1. The index will be 1,2,3,4,5. This is contiguous memory location that allocated. Normally, we talk about an array. The indices an array range from the lower index bound normally 0 most programming languages. Through the higher index bound n-1. It means that you can represent N element using the particular array. Any items of the array can be access directly by just giving its index. So when you say A you can access the first element. When you say A, you can access the fifth element and time complexity of accessing an element is 0 of the order of 1, which means error if its 1000th the element array. If you say A you can access directly to the 1000th element. So operation you do create and initialize the length is a find the number of elements in the array and insertion & deletion. So given an array like a left to right. You can insert of a value and a particular location. If necessary we have to shift the elements. Insertion and deletion is most time consuming and inefficient operations. When you represent list using an array. Now search on the other hand is the most efficient operation that we do.

# Data Structures - Lecture 1

Data Structure

Lecture 1

Data structure is a systematic way of manipulating data. A data structure structures data. Usually more than one piece of data and we have to provide legal operations on the data and the data can also be joined together. That is it can be collection. Basically data structure talks about two aspects. One aspect is data organization and other is manipulating data. In fact manipulation of data, how we want to manipulate the data and how do we organize the data. Results in different data structure that we going to talk about. All of you are some of you have done computer programming and they you have used programming languages and there are some data types that are called primitive data types. For example and this holds a single piece of data in java are may be in ‘C’ most programming languages built in data types called int means integer, char means character ,long stand for long integer and Boolean means Boolean values. There are some Legal operations which is stress for this built in data types like for example for integer: +,-,*, /. Because of the coming of object oriented programming languages abstract data types are get a lot of importance .We talk about data types we also talk about abstract data types. Abstract data types are like a black box. An abstract data type (ADT) is a data type together with the operations, whose properties are specified user of the abstract data type does not have to know what particular implementation used for implementing that particular data type. When we look from data to data structures actually the machine store only binary data. So that what we can see the figure and then you have primitive data types. For example 23 which is an integer 3.1415 which is a decimal and ‘A’ is a character and then you have some basic data structures like arrays and structures used to store the data types and then have a high level data structure like stack, queue and list. Stack, queue and list are data structures that define so that does particular operations these types of data structures. We talk about data to data structures actually as we all of you know data stored in a machine in the form of binary bits and that’s what machine level data storage and then we have primitive data types that are provided most programming languages like integers, floating point 3.145 and character like A and then have basic data structures that are also provided in programming languages like arrays and structures in addition to this we have high level data structure which are special type of list and structures like stack, queue and list. When you talk about data structures there are two types of data structures one is linear data structure and another one is non-linear data
structures.
Linear structures
Array is common linear data structure. Most important concept of array is that the size of array is fixed. Linked list is a variable size. Then you have a stack is very common data structures. It is a restricted form of list where we can add and delete from one point on top of the list. Then we have queue add to back and remove from front. These are ordinary queue. Priority queue add anywhere remove the highest priority. Other important types of data structures which is very necessary for many application of computer science and one such as a hash table .The hash table commonly used for compilers , storing of variables names compilers and so on. Hash tables: unordered list which use a 'hash function' to insert and delete. A tree is a very important data structures. It is unlike most of the data structure since it is a non-linear data structure because it has a branching structure. Graph: Graph is a more linear type of data structure than the Tree. Tree has no loops. Graph has less stringent connection conditions there can be loops in that. When we talk about data structures talk about the data organizations then addition to the data organizations what manipulation you can do with this data types its very important concept. Necessarily to some of the operations you normally do in data structures one is creating an empty data structures. Create an empty list. Give a list we have Determine whether a list is empty. Determine the number of items on a list. Add an item at a given position in a list. Remove the item at a given position in a list. Remove all the items from a list. Now actually what are the actions doing have a half a do depends on the application. Some applications just we do look at only addition and deletion. Certain application you do have to find a list is empty. So operation and combination of operations depends on a particular application that you want to a data structure to have and another important operations are data structures. Another important operation of data structure is to get the item from a given position in a list. Accessing on elements in a list very important operation so in a sorting and searching in any application. For example counseling that you have in Anna University and certain other application. Sorting of the ranks and searching for a particular student then list is a very important operation and mostly all these occupied searching and sorting frequently used operations of data structure. Some time you need the capacity of the list data structure what is the total count of the elements in list. Some time you have needed to modify, update, delete and insert in list. Generally you say that for most applications. This type of modification is not accessed common as action. If we look at the data
structure you can also think of a matrix as a data structures. Linked list as a data structures, a tree and network as a data structures. How this is implemented in how this is represented. LIST: This is the fundamental data structure in computer science and this processing is considered as one of the most important data structures. Infract has been the inspiration for the particular type of programming and language called Lisp. List of integers is the most widely used kind of list and that can also be set or collection of instance. Examples of list are 0,+1,-1,+2,-2,+3,-3 is an example of integer list. We can also have the Days of week = { s,m,t,w,th,f,sa} and sometimes it is not necessary that all elements need to be same type. Instances may or may not be related. {Apple, chair, 2,5.2, red, green, jack}. There is no connection between elements of the list back but tree still that also a list. In many ways list can be classified. But most important classification is unordered and ordered list. Unordered list means insertion list are not in any particular order. Sorted order it could be an alphabetical, numerically but the way in unordered list. Ordered lists are very similar to alphabetical list of employee names. E.g.: The rank of student exam and so on. Difficult example of ordered list. These ordered lists keep items in a specific order and so most manipulation depends on one this order list. When ever an item added to a list. That has to be placed in correct order and similarly when you remove an element from the list. Still have to remain in sorted order. Linear list: Example of linear list. It is a sequence of elements. There is something called as a first element and last element and if you take an every element it has a previous and next element is obliviously there is no element before first another is no element in after the last element. So for an example you can represent list. Linear (or ordered lists) It could be a linear list or ordered list of the form of each row to e0,e1,e2,..en-1 and assigning that n is finite. And size of the list is obliviously n. e0 is the zero. Here if we look e0 is the front e0 is the zeroth element of the list. En-1 is the last element and ei always precedes ei+1 succeeds en. So there is definite relation between elements of the list. Especially in the case of order list. Example of linear list is Student in some particular course. Jack, Jill, tree, henry, Mary and Judy. Please note that this is not an ordered list. Linear list examples Students in comp 2210 = (jack, Jill, able, Hendry, Mary, Judy). OPERATIONS ON LIST:
First create an empty list. We go and look at each operation in detail as we go long. So create an empty list. Determine whether a list is empty. Get the item at a given position is a list that is normally called as retrieval. Determine the no.of items on a list that is count the item of list. Then given an element finite index of an element. Then traverse the list you want to find the all element in the list. Add as item at a given position in a list. Remove the item at a given position in a list. Remove all the items from a list. You can thing a may such operation depending on an application. But which are discussed some of the very common operation do on any list. So first we look at create an empty list. First look at a create (list). Create (list)
In description is creates a new empty list and the inputs are either it can be no inputs are and i want to create an integer list. Types of elements are list integers are character list or character and output as an only empty list no specific output is given. If we look at this result is a new creating an empty list? You have specified in size. You may have specific the type and you may have want to specify something else also. Is empty () .You have found whether list is empty or not. So input is obliviously in the list. Output is it a Boolean output. True if one list is empty and gives false if the list is not empty and the result is after still list is remain unchanged. Important operation of the list or linear list is getting an index. Get an element the input is getting in element which has specific an index. L=(a,b,c,d,e), this an example list if you give get(0). Remember that list is start from 0 to n-1. When you say get(0) you get a. when you say get(2) you get c and so on. If you give index that are not valid like -1 you get an error and 9 though it is a valid integer. It is not a index of the list. Maximum of the index list is e0 to e4. Here so that gives an error. The index is given an index want to get an item from the list. So the input is an index. The item to be got that an index. Output is return to the items at the specified index and it throws an exception if index is not valid. But here result for list is unchanged. Throws an exception if index is out of range. The result is remaining in unchanged. Retrieval means which we just discuss. Suppose i give this and i want to retrieval the element called dog. I don’t know for examples are given index is one. It retrieval dog for me. List at the top and the bottom do not change. Only for that particular index taking are data element and showing it the use. Size and indexof: Size means determine list size. For example if given L is a,b,c,d,e the size of the list is 5. Important one is index of the element. Here unlike the previous one. When for example given a list a,b,c,d,e given the index of d is 2. Given the index of a is 0. The index of z is -1. Because is not there. The index of d is actually here 3.
Traverse