Search This Blog

Simplicity is the ultimate sophistication.” — Leonardo da Vinci
Contact me: sreramk360@gmail.com

Wednesday, 1 April 2015

CS6212 lab manual programs

- By

CS6212 lab manual programs (complete solutions - C programs).

The following programs are written for the subject CS6212 (only the first ten out of twelve are given here). These programs or based on BE- CSE semester 2 lab syllabus. I am a student doing my second semester BE CSE currently while writing down these record programs. So please excuse me for any mistakes that might have crept in the programs (but I have made sure that the following programs are error free and warning free and also works as expected).

I have written these programs in a format I believe to be standard.The IDE I had used to test the programs was Code Blocks and had used the open source gcc compiler for compiling the source. All the programs that follow are free from errors and warnings. In this post I have categorized them in a user-friendly manner to make download easier; all my programs are uploaded in PDF format and DOCX format and each files contain just one program with the program's aim written right above it. I haven't written down the algorithms yet; they will be uploaded under its respective program as I write them down.

I would soon be writing a documentation for these programs. And about the programs, I had written each of them with care that they don't deviate from the standard procedure. Each program I wrote was a challenge to me. The common run-time error I had been getting while coding the linked list was, "access violation"or "segmentation fault" which arises when the program tries to read a memory storage locations that does not belong to that program and the other common mistake one would make (and the one I made extensively before I spent hours correcting it) is loosing the list in the process of its operations.

The programs I really enjoyed programming were, the program that computes combinations and runs in time $O(M^{N+1})$, the polynomial multiplication program which runs in time $O(M(M+N))$ and were the process of checking if $M<N$ runs in time complexity $O(M+N)$ so finally $T(M+N)+T(M(M+N)) = O(M(M+N))$, the infix to prefix conversion program (I had initially wasted a lot of time in it because I had forgotten that this implementation should run in $O(N)$ time and space), the sorting algorithms and the linked list single and circular implementation.

In the linked list implementation, I had written down one module that's actually not commonly used (but still used). The position vice deletion operation is what was a new implementation. Usually one would prefer to delete an element by matching its data with the data to delete, but here the unique address that points to the node is passed on as an argument and is deleted. Lets say we simulate 'Enqueue' and 'Dequeue' queue operations using the standard linked list operations 'Insert', 'DeleteEment', 'DeleteNode' and 'Find' (its obvious that the Dequeue operation cannot be made $O(1)$ with just these operations). We need one variable to have a track of the front end. Now this variable could either be a variable that stores the element that's stored in the front of the list or the address value pointing to the front of the list. If it stores the element and the operation 'DeleteElement' is used to delete the node on the front end, this is going to set an undesirable limitation for our queue implementation. If the same element present else were in the list is present in the front end, then the 'DeleteElement' would delete the first element it finds. So the limitation will be that each element should be unique. So instead the 'DeleteNode' operation can be used and the value returned by 'Find' to be used to update the variable pointing to the front end.

And I guess my introduction is enough and proceed viewing the programs.

Yours,
K Sreram

(These programs are written and tested by K Sreram)

The programs:

Program 1:

Aim

To write a program to obtain all the possible prime numbers from one till the given limit.
Program 2:

Aim
Let $A$ be a set of values passed on by the user. The aim of this program to determine the number of ways by which we may add a particular number of terms that are chosen from $A$ randomly, to obtain a given value as its summation. A value in $A$ can be chosen more than once.

Program 3:

Aim
To read, write and modify employee records using a program written in C and to thereby implement file random access and file handling concepts in C.
Program 4:

Aim
To create, store, find and delete employee records using singly linked list in C.

Program 5:

Aim
To implement set union and intersection of set of integers using linked list, where the sets are represented as doubly linked lists

Program 6:

Aim
To implement Josephus problem in the form of a game using circular linked list in C

Program 7:

Aim
To represent a polynomial as a singly linked list and to implement addition and multiplication of the polynomials in C.

Program 8 a:

Aim
To implement infix to post-fix expression conversion using dynamic stacks in C.
(wrong version)
NOTE: I found a bug in the above program. The algorithm it implements is not correct. the corrected version is also uploaded along with the wrong version. I have summarized  the mistake along with the details of correction in this post's footer.
(corrected version)

Program 8 b:

Aim
To write a C program to evaluate the result of a simple infix expression using stacks.

Program 9a:

Aim
To write a program that imitates function recursion by manually creating an imitation function stack and implement recursion within an infinite loop.
Program 9b:

Aim
To obtain employment application forms and to either accept or reject it, with the higher priority in verification given to applications that arrived earlier than the ones that arrived later, using queue in C.

Program 10 a:

Aim
To implement insertion sorting algorithm in C, where the elements to be sorted are stored in a singly linked list

Program 10b:

Aim
To implement selection sorting algorithm in C, where the elements to be sorted are stored in a singly linked list.

Program 10c:

Aim
To implement bubble sorting algorithm in C, where the elements to be sorted are stored and sorted in a singly linked list.

Please give me reviews on the programs I wrote and inform me if you spot any errors in the program (I have tested it enough to make sure that no errors have crept. But you can never be sure about it!). I'll write down the algorithms (or with my friends help) and upload them as soon as possible. Good Luck!!!

Note: Let me describe the game I had written in the 6th program. The players are to sit along a circle and pass on an object to their neighbor as they get that object from their other neighbor. As they pass-on, they count the number of passes made. Before the start of the game, the number of passes after which a player would be eliminated from the game would be agreed upon. Let that value be $n$. Now after $n$ passes, the person next to the one holding the object gets eliminated. So this continues until just one person remains. The person who remains becomes the winner. Now this program gets the names of the players and gets the value $n$ as run-time inputs; then it evaluates (using circular linked list. Refer the program for the functionality of this algorithm) the next person to be eliminated and displays their name. This goes on until the last player remains.

There is a problem with the algorithm (for question 8 a) I had initially thought was right; but now I have solved it.
Changes summery.

// else if(symbol == '/')
//           return 9;
//else if (symbol == '*')
//          return 8;
// else if (symbol == '+')
//           return 7;
//else if(symbol == '-')
//           return 6;
//else return 0;

is changed to,
if(symbol == '(' || symbol == ')')
return 10;
else if ((symbol == '/') || (symbol == '*'))
return 8;
else if ((symbol == '+') || (symbol == '-'))
return 6;
else return 0;

I first thought that treating the priority of symbol '/' to be greater than '*' was of no issues, but a detailed analysis has showed that this could be a problem. So I have changed it to such a way that operators with similar priority is given equal priority.
/**********************************************************
void infixToPostfix(Stack infix) /// B, D, M, A, S
{
Stack symbolStack = NewStack();
DataType temp;
while(!IsEmpty(infix))
{
temp = Top(infix);
if(temp == '(')
{
Push(symbolStack, temp);
Pop(infix);
}
else if(IsOperator(temp))
{
/// --- if(FindPriority(temp) <= FindPriority(Top(symbolStack)))
/// ---    {
while((Top(symbolStack)!='(') &&/// +++  change: while((Top(symbolStack)!='(') && --- while(Top(symbolStack)!='(')
(FindPriority(temp) <= FindPriority(Top(symbolStack)))) /// +++ change: (FindPriority(temp) <= FindPriority(Top(symbolStack)))
evaluate(symbolStack);
Push(symbolStack, temp);
///---  }
/// --- else // if a more prior symbol is read
/// ---   Push(symbolStack, temp);
Pop(infix);
}
else if( IsVar(temp))
{
printf("%c", temp);
Pop(infix);
}
else if(temp == ')')
{
if(Top(symbolStack) == '(')
{
Pop(symbolStack);
Pop(infix);
}
else evaluate(symbolStack);
}
}
DisposeStack(&symbolStack);
}

The algorithm initially used checks for the symbol priority and applies the evaluation operation once it reads a lower priority symbol compared to the one that's at the top of the symbol stack until it reaches a '(' symbol. But the actual working algorithm needs to apply the 'evaluate' operation until it either reaches the symbol '(' or a symbol of lower priority.

The reason for this is, the operations with a higher priority need to be applied first; so the algorithm does not do the operation once it reads an operator but instead waits for a second operator to compare its priority with the the previously read operator.

And one more thing, this still deviates from the standard procedure because of its poor error reporting methods. And these methods can be incorporated by making the following changes:
1. The algorithm needs to check if the stack is empty after evaluation.
2. The algorithm needs to check if there is a close bracket symbol without an open bracket symbol.
3. The algorithm needs to check if there are successive operators one after the other in the expression, where the succeeding character is not an open bracket or a close bracket.

The reason I have both the corrected version and the wrong version online is, I believe that sometimes a mistake in a solution to a problem teaches us something more than the solution itself! So I like talking about my mistakes.

A comment or two regarding the programs will be nice.

1. nice job, sreram !! :) but, r these programs going to come for ur practicals ??

1. and thanks !! :)

2. Thanks Sudha. I was given a set of 10 abstract questions based on our computer practical syllabus. Rather than calling them "questions" its better to call them "syllabus". For example, one of the questions just said: "implement single linked list" so I chose a more specific problem (employee records insertion, deletion, searching and displaying) that demonstrates the use of linked list by solving that problem. And about the large size of the programs, I tried my best to reduce the number of lines while coding (though I insisted on not deviating from the standard procedure).

3. the program could have started after two or three lines so that we neednt edit !! its a big fuss to edit !! :/

4. You can just open it as WORD 2003 Document Sudha or adjust ruler accordingly it'll remain the same for every other docs ...
By The Way, A Great job Sre Ram ...
I can't find a word in English (or any other language) to appreciate you ...

5. Thanks Sri Vineeth

Featured post

Why increasing complexity is not good?

“ Simplicity is the ultimate sophistication.” — Leonardo da Vinci Why is complicating things wrong ? - K Sr...