About the Project and Trees

It is extremely important that both the classes, BEE and BSE, give their project vivas before the end of this week, that is by 15th of Friday. Otherwise your marks will not be added as I will not be around during the exams.

Also, I have not provided any notes for Trees, especially binary trees. You are required to read about them from anywhere you wish but I do recommend your course book. Do not forget to read about them just because the notes are not available on this site

Minimum Spanning Trees

You can get the Dijkstra Algorithm from here. For those who are too lazy to search for the other MST algorithms, can get them from here:

Prim's
Kruskal's
Dijkstra

One IMPORTANT point. I have not given notes for trees anywhere. You are required about them (especially binary trees) from any book or online site. I recommend your course book to do the reading.

Graphs

The slides related to graphs can be obtained from here.

Project Details

The project details can be found here.

Tree traversal

There are two types of traversals when we are talking about trees. You can get the notes about both from these links:

Breadth First Traversal

Depth First Traversal

Trees

Before we can study Heap Sort or any of the searching algorithms, we need to understand the concept of trees and how do we go about them.

We start our discussion from binary trees. You can get the linked list implementation of binary trees from here. Keep in mind that all the pointers in this implementation are not deallocated at the end of the program, which causes it to crash sometimes.

In order to see the results, what you can do is to put a break point just before the program finishes so that you can see the results shown by it. If time allows, I will try to fix this problem.

Radix sort

Radix Sort Algorithm

The notes for the course can be obtained here.

Psuedocode for algorithms

I am not following any book when it comes to algorithms or psuedocode.

a good resource is wikipedia to get the details about the algorithms, for example, the psuedocode for merge sort that i explained in the class is present here. You can use whatever resource you find is good for your understanding.

Till now, we have covered:

merge sort
insertion sort
selection sort and
bubble sort

Algorithm animations

A very good animation of all the sorting algorithms can be found here.

Algorithms and Complexity Analysis

A very good document about complexity analysis can be obtained from here. You must read it as it is very well written.

The slides for the first lecture are present here

Assignment 2

The assignment 2 can be obtained from here.

Assignment 1 Solution

The solution for the first assignment can be obtained from here

Priority Queue

The code for the priority queue can be obtained from here.

Recursion

The code of all the recursion functions can be obtained from here:

Converting Infix Expression to Postfix

This is a pseudocode of the program that can covert an Infix expression to postfix expression. The same pseudocode is given in your course book as well, but I have written it in a way that it is more understandable. The code has a precedence() function that returns true or false, depending on the precedence of the operators. so if it is precedence('*', '+'), it will return true and also true for precedence('*', '*'). You must keep in mind that for precedence('$', '$'), the return value is false.

Get expression from user //Say A*B+C or A+B*C$D$E
initialize operatorStack as empty //A stack for only storing operators +,-,*,/,$
initialize postfixString //The created postfix string

char Symbol;
char topSymbol;

//While loop will run till the end is reached
while(!endOfExpression())
{
Symbol = getCharacterFromExpression()
if(SymbolIsOperand())
{
add Symbol to postfixString;
}
else
{
while(!operatorStack.isEmpty() && precedance(operatorStack.getTop(), Symbol))
{
topSymbol = operatorStack.pop();
add topSymbol to postfixString;
}
operatorStack.push(Symbol);
}
}

while(!operatorStack.isEmpty())
{
topSymbol = operatorStack.pop();
add topSymbol to postfixString;
}

One of the problems that came up during the assignment was the class redefinition error as both the stack and the queue classes were using the same Car.h header file. One way of avoiding that problem is to make 2 different projects and work in them. Another way is to do a bit of programming.

You can use macros to keep check of the files that might be redefined and thus you avoid the error altogether and do not need to make two separate projects. So, you will define your car.h file like this:

#ifndef CAR_H //This checks if the header file was defined
#define CAR_H //If it was not defined, it will define it

class Car
{
private:
int milage;
int passengers;
int model;
char* name;
public:
Car();
void setmilage(int);
int getmilage();

void setpassengers(int);
int getpassengers();

void setmodel(int);
int getmodel();

void setname(char* );
char* getname();
};


#endif /* CAR Seen */

Infix, Prefix and Postfix notations

The next lecture id going to be about infix, postfix and prefix notations. After explaining the three notations, I will go and explain the algorithm for implementing and calculating postfix notation while using a stack. You can read about the postfix notation here. you can also read about it in the book, Data Structures using C and C++ by Tenenbaum on page 95. I created a working program using the pseudo code as given in the Tenenbaum book in Visual C++. You can get it from here. You should see how I have created the entire project, declared the header files, the cpp files and how I used one of the classes as static, to use its functionality. I will be explaining this in class as well. The assignments that you submit should be similarly done. I also hope that you will get to learn Visual C++ IDE and debugging as you proceed.

Lab No. 3

A stack is exactly what it means, like a stack of books, a stack of cards and in such a stack, it is known that the item that is readily available is the top most item. Thus, when we add an item, we add it to the top and when we remove an item, we remove it from the top. This way of accessing data, earns it the name of a LIFO data structure. The implementation of the stack is as follows:
#include
class Stack
{
private:
char* data; //character pointer
int head; //index counter
int maxSize; //maximum array size
public:
Stack(int);
void push(char);
char pop();
};

Stack::Stack(int num)//Constructor
{
head = -1; //setting head to -1;
maxSize = num;
data = new char[maxSize]; //declaring the stack size
for(int i = 0; i < maxSize ;i++) //initialising all values to NULL
{
data[i] = '\0'; //putting NULL values in the data array
}
}

void Stack::push(char c)//Adding a value
{
if(head == -1)
{
head++;
data[head] = c;
}
else if(head < maxSize - 1)
{
head++;
data[head] = c;
}
else
{
cout<<"Stack is full.";
}
}
char Stack::pop()
{
char c;
if(head==-1)
{
cout<<"Stack is empty.";
}
else
{
c = data[head];
head--;
}
return c;
}

Circular Queue:
In a queue, the item that is added first is removed first, thus it is commonly known as a FIFO data structure. A common example of a queue is when you join a line in front of a cinema to buy tickets. Circular queue is a bounded queue. It is better than a normal queue because in this we can effectively utilize the memory space. The implementation of the circular queue is as following:

#include
typedef int bool;
const int false = 0;
const int true = 1;

class CircularQueue
{
private:
int head;
int tail;
int maxSize;
char* data;
public:
CircularQueue(int);
~CircularQueue();
bool isFull();
void push(char);
void pop();
};


CircularQueue::CircularQueue(int num)
{
head = tail = -1;
maxSize = num;
data = new char[num];
}
CircularQueue::~CircularQueue()
{
delete[] data;
}


bool CircularQueue::isFull()
{
return(head == tail+1 || (head == 0 && tail == maxSize-1) );
}


void CircularQueue::push(char c)
{
if(!isFull())
{
if(tail == -1 || tail == maxSize-1)
{
tail = 0;
data[tail] = c;
if(head == -1)
{
head = 0;
}
}
else
{
tail++;
data[tail] = c;
}
cout<<"\nPushed " ;}
else
{
cout<<"\nQueue is Full.\n";
}
}


void CircularQueue::pop()
{
char temp;
temp = data[head];


if(head == -1 && tail == -1)
{
cout<<"\nStack is Empty\n";
}
else
{
if(head == tail)
{
head = tail = -1;
}
else if(head == maxSize-1)
{
head = 0;
}
else
{
head++;
}
cout<<"\nPopped "; }
}

Lab Tasks:

1) Write a program to create a stack of books in a library. Modify the code of stack class given in the handout so that it works for strings and verify the methods of the stack class. (Hint: You can create a structure which stores the name of the book and then create an array of that structure to implement stack)

Linked lists and Stack

This is the place where all the pointers, objects and structures come together. A pointer can be used to point towards a memory location. That memory location can hold a pointer, a variable, a structure an array of structure and so on. Once we have pointers that start pointing towards structures, the C++ starts to become both interesting and complicated. Again, if you do not forget how the pointers work, you will have no problem in understanding the concept of linked lists.

We start off by defining a very basic structure called "node" which holds the data that we want to store and a pointer that helps in pointing towards other nodes. This structure can be defined as this:

struct node

{

char data;

node* next;

};

Now, we define our interface for the stack class that we are going to create, like this:

class stack

{

private:

node* head;

public:

stack();

~stack();

void push(char c);

char pop();

};

if you remember the stack implementation through arrays, you will see that the class looks almost the same, with slight differences. The real differences come when you start to implement the various functions. In order to understand how these functions work, attending the classes should do you good. The code that lets you make a stack is as following:

stack::stack()

{

head = NULL;

}

stack::~stack()

{

}

void stack::push(char c)

{

if(head == NULL)

{

head = new node;

head->data = c;

head->next = NULL;

}

else

{

node* temp = new node;

temp->data = c;

temp->next = head;

head = temp;

temp = NULL;

}

}

char stack::pop()

{

char c = '\0';

if(head == NULL)

{

cout<<"\nStack Empty";

return c;

}

else

{

node* temp = head;

head = head->next;

c = temp->data;

delete temp;

temp = NULL;

}

return c;

}

I have made and performed this code myself, so there does not seem to be any problem. You can now try the code yourself and see how the stack works by using nodes. Once you learn this, going through queues and trees is going to be a lot of fun.

Today’s lecture is about circular queue. The problem with making a queue in an array is the right shifting of the data whenever we pop an element. One way to fix that problem is to run a for loop that shifts the elements one step back in the array after every pop.

Another way to fix this problem is to treat the array as a circular queue. In that case, The array gives the illusion of continuing in a circular way. What we actually do is that, we start using the old locations in the stack that had been popped. This brings us to the important task of finding out the conditions when the queue will be full, which is defined by the isFull() function.

bool CircularQueue::isFull()

{

return(head == tail+1 || (head == 0 && tail == maxSize-1) );

}

According to this code, there are two conditions by which a queue can be full.

1. head is greater than tail by one place. This means that the user started popping values and while doing so, as we increment head, after popping the last value, the head becomes greater than tail.

2. The second condition becomes true if head was at the zero location and the tail was at the last place possible in the array.

If any of these two conditions are met, the queue is considered to be full.

In case of pushing, we need to check first if the array is full or not. Then we push to the appropriate place:

void CircularQueue::push(char c)

{

if(!isFull())

{

if(tail == -1 || tail == maxSize-1)

{

tail = 0;

data[tail] = c;

if(head == -1)

{

head = 0;

}

}

else

{

tail++;

data[tail] = c;

}

cout<<"\nPushed "<

}

else

{

cout<<"\nQueue is Full.\n";

}

}

If you look at the code, after checking if the Queue is Full, we check if tail was either at the final position or -1. It then increments tail and puts the element to the appropriate spot. It also checks if the head was -1 or not and increments it if it was.

Otherwise, it just increments tail and puts the element at the appropriate place.

void CircularQueue::pop()

{

char temp;

temp = data[head];

if(head == -1 && tail == -1)

{

cout<<"\nStack is Empty\n";

}

else

{

if(head == tail)

{

head = tail = -1;

}

else if(head == maxSize-1)

{

head = 0;

}

else

{

head++;

}

cout<<"\nPopped "<

}

}

For popping, it first checks if both head and tail are -1, this tells the user that queue is empty. Otherwise, it first checks if the array has the last value, then if the head was at the last value of the array and if these conditions are not met, it simply increments head and puts the data at the appropriate place. The complete code for the circular queue is as following:

class CircularQueue

{

private:

int head;

int tail;

int maxSize;

char* data;

public:

CircularQueue(int);

~CircularQueue();

bool isFull();

void push(char);

void pop();

};

CircularQueue::CircularQueue(int num)

{

head = tail = -1;

maxSize = num;

data = new char[num];

}

CircularQueue::~CircularQueue()

{

delete[] data;

}

bool CircularQueue::isFull()

{

return(head == tail+1 || (head == 0 && tail == maxSize-1) );

}

void CircularQueue::push(char c)

{

if(!isFull())

{

if(tail == -1 || tail == maxSize-1)

{

tail = 0;

data[tail] = c;

if(head == -1)

{

head = 0;

}

}

else

{

tail++;

data[tail] = c;

}

cout<<"\nPushed "<

}

else

{

cout<<"\nQueue is Full.\n";

}

}

void CircularQueue::pop()

{

char temp;

temp = data[head];

if(head == -1 && tail == -1)

{

cout<<"\nStack is Empty\n";

}

else

{

if(head == tail)

{

head = tail = -1;

}

else if(head == maxSize-1)

{

head = 0;

}

else

{

head++;

}

cout<<"\nPopped "<

}

}