click here to download: all units oss material
Friday, 7 November 2014
Thursday, 17 April 2014
NPTEL WEEK 5: IMPLEMENTATION OF HASH TABLE ADT
A hash table is a data structure that maps a set of keys to a given set of values. It uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found or to which a correct value can be inserted. A hash function will assign each key to a unique bucket or slot. In practice, however, there may be more than one key that will hash to the same bucket. Such an assignment is said to result in a collision.
In this assignment, you have to implement a Hash Table ADT using arrays and linked lists. The algorithm should accommodate the features described below:
-
Your program should take as input 10 non-negative integers as key values and insert them to a hash table.
-
The hash table has to be implemented using the hash function h(x) = x%10, where x is the input value.
-
Input values that return the same value for h(x) have to be properly accommodated such that if there is a collision, the index from the array to the appropriate bucket should point to a linked list that can take in all the values that hash to the same bucket. i.e., you can have an array of linked lists such that each entry of the array is a pointer to a bucket. For e.g., when h(x) returns 4, the input value should go into the linked list starting from A[4].
-
Your program should report when there is a collision and must specify the position (starting at 1 for the 1st element) in the input list of that key value where the collision occurred. It should also report the bucket number and the number of entries in each bucket
-
If there are no collisions, the program should report ‘NO’.
-
HashTable class has a printCollision function which you cannot re-write. The string you want to print has to be made available in the private data variable “collision” using listCollision function in class HashTable.
INPUT:
A list of 10 non-negative integers with a single space between the entries.
OUTPUT:
3-tuple indicating the position in the input list where the collision occurred, the corresponding bucket number and the number of elements in that bucket, each 3-tuple has to be separated by a single space.
CONSTRAINTS:
0 <= key <1000
Sample input:
77 23 231 785 900 345 287 16 5 234
Expected Output:
(6,5,2) (7,7,2) (9,5,3)#include <iostream>
#include <stdlib.h>
#include <string>
#include <sstream>
using namespace std;
/* Definitions as shown in the lecture */
typedef struct CellType* Position;
typedef int ElementType;
struct CellType{
ElementType value;
Position next;
};
/* *** Implements a List ADT with necessary functions.
You may make use of these functions (need not use all) to implement your HashTable ADT ***/
class List{
private:
Position listHead;
int count;
public:
//Initializes the number of nodes in the list
void setCount(int num){
count = num;
}
//Creates an empty list
void makeEmptyList(){
listHead = new CellType;
listHead->next = NULL;
}
//Inserts an element after Position p
int insertList(ElementType data, Position p){
Position temp;
temp = p->next;
p->next = new CellType;
p->next->next = temp;
p->next->value = data;
return ++count;
}
//Returns pointer to the last node
Position end(){
Position p;
p = listHead;
while (p->next != NULL){
p = p->next;
}
return p;
}
//Returns number of elements in the list
int getCount(){
return count;
}
};
/*UPTO THIS LINE, THE CODE WIL BE PREPENDED BEFORE YOUR FUNCTIONS*/
class HashTable
{
private:
List bucket[10];
int bucketIndex;
int numElemBucket;
Position posInsert;
string collision;
bool reportCol;
bool reportCol2; //Helps to print a NO for no collisions
public:
HashTable()
{ //constructor
int i;
for (i=0;i<10;i++)
{
bucket[i].setCount(0);
}
collision = "";
reportCol = false;
reportCol2=false;
numElemBucket=0;
}
int insert(int data)
{
/*Write your code here to insert data into
hash table and report collision*/
bucketIndex = data%10;
if(bucket[bucketIndex].getCount()==0)
{
bucket[bucketIndex].makeEmptyList();
}
else
{
reportCol=true;
reportCol2=true;
}
posInsert = bucket[bucketIndex].end();
bucket[bucketIndex].insertList(data,posInsert);
numElemBucket++;
if(reportCol2==true)
{
listCollision(bucket[bucketIndex].getCount());
reportCol2=false;
}
return numElemBucket;
}
void listCollision(int pos)
{
/*Write your code here to generate a properly formatted
string to report multiple collisions*/
if(collision.empty())
{
std::ostringstream oss;
oss << "(" << numElemBucket << "," << bucketIndex << "," << pos << ")"<<" " ;
collision += oss.str();
}
else
{
std::ostringstream oss;
oss << "(" << numElemBucket << "," << bucketIndex << "," << pos << ")"<<" " ;
collision += oss.str();
}
}
void printCollision();
};
int main()
{
HashTable ht;
int i, data;
for (i=0;i<10;i++)
{
cin>>data;
ht.insert(data);
}
/*Write your code here to call insert function of HashTable ADT and if there is a collision, use listCollision to generate the list of collisions*/
/* Warning: Do NOT edit the code below - it will be appended during compilation
//Prints the concatenated collision list
ht.printCollision();
}
void HashTable::printCollision(){
if (reportCol == false)
cout <<"NO";
else
cout<<collision;
}
*/WEEK 5 MATRIX ADT IMPLEMENTATION
YOU HAVE TO IMPLEMENT A MATRIX ADT USING CONCEPTS OF C++ CLASSES TAUGHT IN THE LECTURES. THE INPUT MATRICES WOULD BE SQUARE MATRICES. THE CLASS MUST SUPPORT THE FOLLOWING FUNCTIONS:
1. MATRIX ADDITION
2. MATRIX SUBTRACTION
3. MATRIX MULTIPLICATION
YOUR PROGRAM SHOULD TAKE AS INPUT: DIMENSION OF A SQUARE MATRIX N, TWO MATRICES OF SIZE N X N WITH INTEGER VALUES, AND ONE OPERATOR SYMBOL (+, - ,*). IT MUST PERFORM THE CORRESPONDING OPERATION USING MEMBER FUNCTIONS OF MATRIX CLASS.
INPUT:
IN THE FIRST LINE, ONE INTEGER WHICH IS THE DIMENSION OF THE MATRIX AND ONE OPERATOR (ONE OF +, - OR *)
TWO NXN MATRICES ONE AFTER THE OTHER, SUPPLIED ONE ROW AT A TIME.
OUTPUT:
RESULTANT MATRIX AFTER PERFORMING THE SPECIFIED OPERATION, ONE ROW AT A TIME. FOR SUBTRACTION, IF A IS THE FIRST MATRIX AND B IS THE SECOND MATRIX, PERFORM A-B.
CONSTRAINTS:
THE INPUTS WILL SATISFY THE FOLLOWING CONSTRAINTS:
1<=N<=10 THERE IS NO NEED TO VALIDATE THE VALUE OF N. THERE ARE NO CONSTRAINTS ON THE VALUES OF THE ENTRIES OF THE MATRICES.
#include <iostream>
#include <cstring>
using namespace std;
struct matrixType{
int matDimension;
int matValues[10][10];
};
class MatrixADT{
private:
matrixType resultMatrix;
public:
//Member function declarations
void intializeResultMatrix(int);
matrixType add(matrixType, matrixType);
matrixType subtract(matrixType,matrixType);
matrixType multiply(matrixType,matrixType);
void printResult();
};
//Member functions of Matrix class to be defined here
matrixType MatrixADT::add(matrixType M1, matrixType M2){
//Insert code here
int i,j,temp=0;
matrixType mat;
temp=resultMatrix.matDimension;
for(i=0;i<temp;i++){
for(j=0;j<temp;j++)
{
resultMatrix.matValues[i][j]=M1.matValues[i][j]+M2.matValues[i][j];
mat.matValues[i][j]=resultMatrix.matValues[i][j];
}
}
return mat;
}
matrixType MatrixADT::subtract(matrixType M1, matrixType M2){
//Insert code here
int i,j,temp=0;
matrixType mat;
temp=resultMatrix.matDimension;
for(i=0;i<temp;i++){
for(j=0;j<temp;j++)
{
resultMatrix.matValues[i][j]=M1.matValues[i][j]-M2.matValues[i][j];
mat.matValues[i][j]=resultMatrix.matValues[i][j];
}
}
return mat;
}
matrixType MatrixADT::multiply(matrixType M1, matrixType M2){
//Insert code here
int i,j,temp=0,k;
matrixType mat;
temp=resultMatrix.matDimension;
for(i=0;i<temp;i++){
for(j=0;j<temp;j++)
{
mat.matValues[i][j]=0;
for(k=0;k<temp;k++)
{
resultMatrix.matValues[i][j]=mat.matValues[i][j]+(M1.matValues[i][k]*M2.matValues[k][j]);
mat.matValues[i][j]=resultMatrix.matValues[i][j];
}
}
}
return mat;
}
void MatrixADT::intializeResultMatrix(int dim){
resultMatrix.matDimension=dim;
/*for(i=0;i<dim;i++){
for(j=0;j<dim;j++)
{
cin>>resultMatrix.matValues[i][j];
}
}*/
}
int main(){
MatrixADT maX;
matrixType M1, M2;
char op;
int dim,i,j;
cin>>dim>>op;
//intialize the dimension for the matrices
maX.intializeResultMatrix(dim);
//enter value for matrix M1
for(i=0;i<dim;i++){
for(j=0;j<dim;j++)
{
cin>>M1.matValues[i][j];
}
}
//enter value for matrix M2
for(i=0;i<dim;i++){
for(j=0;j<dim;j++)
{
cin>>M2.matValues[i][j];
}
}
switch(op)
{
case '+': maX.add(M1,M2);
break;
case '-': maX.subtract(M1,M2);
break;
case '*': maX.multiply(M1,M2);
break;
}
/*Enter your code here to accept two input matrices as instances of class Matrix and perform the operations using member functions, display the result matrix using member function*/
/* DO NOT EDIT the code below; if you edit it, your program will not give correct output
maX.printResult();
}
void MatrixADT::printResult(){
int i,j;
for (i=0;i<resultMatrix.matDimension;i++){
for (j=0; j<resultMatrix.matDimension-1;j++){
cout<<resultMatrix.matValues[i][j]<<" ";
}
cout <<resultMatrix.matValues[i][j]<<"\n";
}
cout <<”Done”;
}
*/NPTEL assignment week 5 BIG INT ADDITION
PRIMITIVE INT DATA TYPE HANDLES INTEGERS EACH OF WHICH CAN BE STORED USING 32 BITS. SIMILARLY LONG DATA TYPE ALSO HAS A LIMIT. IN THIS ASSIGNMENT YOU HAVE TO IMPLEMENT A DATA TYPE WHICH HANDLES NUMBERS LARGER THAN INT , LONG AND LONG LONG.
YOU ARE GIVEN A NUMBER IN DECIMAL FORM. YOU NEED TO BUILD A DATA STRUCTURE CALLED BIGINT WHICH CAN STORE THAT DATA, AND PERFORM THE FOLLOWING BASIC OPERATIONS ON THAT DATA TYPE:
1.BIGINT::ADD(BIGINT A ), RETURNS THE RESULT IN ANOTHER BIGINT, WITHOUT ALTERING THE NUMERICAL VALUE OF THE CALLER.
2.BIGINT::PRINT(), THIS FUNCTION MUST PRINT MOST SIGNIFICANT DIGIT AT THE BEGINNING AND MUST NOT PRINT ANY LEADING ZEROES.
EX: 123 (CORRECT )
0123 (INCORRECT)
3.POPULATE(BIGINT &A, CHAR * STR), POPULATES THE LIST IN BIGINT USING PUBLIC METHODS OF BIGINT.
NOTE THAT POPULATE(BIGINT &A, CHAR * STR) METHOD IS NOT A FUNCTION OF BIGINT.
INPUT:
INPUT WILL HAVE TWO LINES, EACH LINE CONTAINS A SINGLE BIGINT.
SAMPLE INPUT:
8132393963283
216396739263921391
OUTPUT:
OUTPUT CONTAINS THE RESULT OF THE ADDITION IN A SINGLE LINE.
OUTPUT OF THE ABOVE SAMPLE INPUT IS AS FOLLOWS.
SAMPLE OUTPUT:
216404871657884674
CONSTRAINTS:
1 ≤ INPUT LENGTH OF BIGINT ≤ 40 DIGITS.
INPUT FOR BIGINT IS ALWAYS POSITIVE
HINTS: (OPTIONAL)
STORE THE NUMBERS IN REVERSE ORDER, AS ADDITION IS PERFORMED FROM LEAST SIGNIFICANT DIGIT. FOR EXAMPLE STORE THE NUMBER 122 AS 2->2->1, INSTEAD OF 1->2->2.
/*
*THE BELOW CODE WILL BE PREPENDED BEFORE COMPILATION.
*ALL NECESSARY FUNCTIONS OF LIST, LISTNODE ARE IMPLEMENTED.
*
*/
#include <iostream>
#include <cstring>
using namespace std;
class ListNode{
private:
int data;
ListNode * next;
public:
ListNode(){}
ListNode(int num){
data=num;
next = NULL;
}
int getData();
void setData(int);
void setNext(ListNode *);
ListNode* getNext();
};
/*
*Implementation of Node Methods
*/
int ListNode::getData(){
return data;
}
void ListNode::setData(int x){
data = x;
}
ListNode * ListNode::getNext(){
return next;
}
void ListNode::setNext(ListNode * P){
next = P;
}
/***End Of Node Methods Implementation**/
class List{
private:
ListNode * Head;
public:
List(){
Head=NULL;
}
~List(){}
/*Already Implemented Methods.You can use them in your
*functions
**/
ListNode * getHead();
void setHead(ListNode *);
ListNode * last();
void append(int);
void prepend(int);
void popBack();
void print();
void copy(List);
void printReverse(); //prints the list from Tail to Head.
/*Implement the follwing if required. Not mandatory*/
ListNode * prevNode(ListNode* P);
void popFront();
};
/*
****List Methods Implementaion***
*/
ListNode * List::getHead(){
return Head;
}
ListNode * List::last(){
ListNode * temp=Head;
if(Head==NULL) return NULL;
while(temp->getNext()!=NULL){
temp=temp->getNext();
}
return temp;
}
void List::setHead(ListNode * P){
Head = P;
}
void List::append(int num){
ListNode * new_node = new ListNode(num);
ListNode * temp=Head;
if(temp==NULL){
Head = new_node;
return;
}
while(temp->getNext()!=NULL) temp=temp->getNext();
temp->setNext(new_node);
}
void List::prepend(int num){
ListNode * new_node = new ListNode(num);
new_node->setNext(Head);
Head = new_node;
}
/*
*Removes the Tail Node
*/
void List::popBack(){
ListNode * temp=Head,*prev=NULL;
//NULL list
if(Head==NULL){cout<<"List is Empty\n";}
//single element
if(Head->getNext()==NULL){
delete Head;
Head=NULL;
return;
}
while(temp->getNext()!=NULL){
prev = temp;
temp=temp->getNext();
}
delete temp;
prev->setNext(NULL);
}
void List::print(){
ListNode * temp=Head;
while(temp!=NULL){
cout<<temp->getData();
temp=temp->getNext();
}
}
//copy values of L into this list
void List::copy(List L){
Head = NULL;
ListNode * temp = L.Head;
while(temp!=NULL){
this->append(temp->getData());
temp=temp->getNext();
}
}
void List::printReverse(){
ListNode * curr=Head;
ListNode * prev_last=NULL;
while(Head!=NULL && prev_last!=Head){
curr = Head;
while(curr->getNext()!=prev_last){
curr = curr->getNext();
}
cout<<curr->getData();
prev_last = curr;
}
}
/*****End Of List Methods Implementation************************/
/* This is the data type you need to write the required methods*/
class BigInt{
private:
List L;
public:
BigInt(){}
~BigInt(){}
/*Must write code for append(),prepend(), add(), print() Methods*/
void append(int num);
void prepend(int num);
BigInt add(BigInt A);
void print();//mandatory
/*Helper Functions, not mandatory to implement
*Hint: Implement removeZeroes(), call it in print().
*/
void removeZeroes();
void copy(BigInt B);
};
/*UPTO THIS LINE, THE CODE WIL BE PREPENDED BEFORE YOUR FUNCTIONS*/
/**THESE ARE THE ONLY FUNCTIONS YOU ARE REQUIRED TO FILL
*You are allowed to define additional global functions.
*Note: Remove/Comment the helper functions, if you are not implementing them.
*/
int l1,l2,count=0;
void populate(BigInt &A, char * str){
/*write your code here**/
int i=0,k;
while(str[i]!=0)
{
k=(int)str[i]-48;
A.prepend(k);
i++;
}
if(count==0)
{l1=i;
count++;
}
else
l2=i;
}
void BigInt::append(int num){
/*write your code here**/
L.append(num);
}
void BigInt::prepend(int num){
/*write your code here**/
L.prepend(num);
}
BigInt BigInt::add(BigInt A){
/**write your code here*/
int t;
t=l1-l2;
if(t>0)
{
while(t!=0)
{
A.append(0);
t--;
}
}
else if(t<0)
{
while(t!=0)
{
append(0);
t++;
}
}
else
{
}
ListNode * temp1=L.getHead();
ListNode * temp2=A.L.getHead();
int x,carry=0;
while(temp1!=NULL)
{
x=temp1->getData()+temp2->getData()+carry;
carry=0;
if(x<10)
{
temp2->setData(x);
}
else
{
x=x%10;
temp2->setData(x);
carry=1;
}
temp1=temp1->getNext();
temp2=temp2->getNext();
}
if(carry==1)
{
A.L.append(1);
}
return A;
}
void BigInt::removeZeroes(){
/**write your code here
*Hint: Implement removeZeroes(), call it in print().
*/
ListNode * temp=L.getHead();
while(temp->getNext()!=0) temp=temp->getNext();
if(temp->getData()==0)
{
L.popBack();
}
}
void BigInt::print(){
/*write your code here*/
ListNode * temp=L.getHead();
removeZeroes();
removeZeroes();
while(temp->getNext()!=NULL) temp=temp->getNext();
L.printReverse();
}
/*Warning:: The following code given below will be appended
*at the end of your code before compilation.
*You must not write main function.
**/
/*
int main(){
char str[40];
BigInt A,B;
cin>>str;
populate(A,str);
cin>>str;
populate(B,str);
(A.add(B)).print();
return 0;
}*/Monday, 7 April 2014
nptel assignment week 4 for horner's rule
Horner's Rule
PROGRAM:You are given a polynomial of degree n. The polynomial is of the form P(x) = anxn + an-1xn-1 + … + a0. For given values k and m, You are required to find P(k) at the end of the mth iteration of Horner’s rule. The steps involved in the Horner’s rule are given below,
Pn (x) = an
Pn-1 (x) = an-1 + x * Pn (x) 1st iteration.
Pn-2 (x) = an-2 + x * Pn-1 (x) 2nd iteration.
.
.
P0 (x) = a0 + x * P1 (x) nth iteration.
In general, Pi (x) = ai + x * Pi + 1 (x) and P0(x) is the final result. The input to your program is as follows,
Line 1 contains the integers n, m and k separated by space.
Line 2 contains the coefficients an, an-1…, a0 separated by space.
INPUT: Integers n, m, k and the coefficients as described above.
OUTPUT: P(k) value at the end of the mth iteration.
Sample Input:
2 2 5
3 2 1
Sample Output:
86
Constraints:
1 <= n, k, m <= 10
0 <= ai <=10
PROGRAM:
#include<stdio.h>
int horner(int[],int,int);
int main()
{
int n,m,k,i;
int a[10];
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<=n;++i)
{
scanf("%d",&a[i]);
}
printf("%d",horner(a,m,k));
return 0;
}
int horner(int a[],int m,int k)
{
if(m==0){
return a[m];
}
else{
return a[m]+k*horner(a,m-1,k);
}}
NPTEL WEEK 4 ASSIGNMENT FOR MULTIPLYING POLYNOMIALS
Multiply Polynomials
A polynomial of degree n is of the form P(x) = anxn + an-1xn-1 + … + a0. Given two polynomials f(x) and g(x) of degrees n and m respectively, write a program to find the polynomial h(x) given by,
h(x) = f(x) * g(x)
INPUT: Line 1 contains n and m separated by space.
Line 2 contains the coefficients an, an-1…, a0 of f(x) separated by space.
Line 3 contains the coefficients bm, bm-1…, b0 of g(x) separated by space.
OUTPUT: The degree of h(x) followed by the coefficients ck, ck-1…, c0 of h(x) in next line separated by space.
Sample Input:
2 2
1 2 3
3 2 1
Sample Output:
4
3 8 14 8 3
Constraints:
1 <= n <= 10
1 <= ai <= 100
PROGRAM:
#include<stdio.h>
int main()
{
int n,m,i,j,k,a[10],b[10],sum=0;
scanf("%d%d",&n,&m);
for(i=n;i>=0;i--)
{
scanf("%d",&a[i]);
}
for(i=m;i>=0;i--)
{
scanf("%d",&b[i]);
}
printf("%d\n",n+m);
for(i=n+m;i>0;i--)
{
for(j=n;j>=0;j--)
{
for(k=m;k>=0;k--)
{
if(j+k==i)
{
sum=sum+a[j]*b[k];
}
}
}
if(i==0)
{
printf("%d ",sum);
}
else
{
printf("%d ",sum);
}
sum=0;
}
printf("%d",a[0]*b[0]);
return 0;
}
Subscribe to:
Comments (Atom)