Write an algorithm for the implementation of a Stack.
Showing posts with label mcs021. Show all posts
Showing posts with label mcs021. Show all posts
Write a note of not more than 5 pages summarizing the latest research in the area
of “Trees”. Refer to various journals and other online resources. Indicate them in your
assignment.
of “Trees”. Refer to various journals and other online resources. Indicate them in your
assignment.
Write an algorithm that accepts a Binary Tree as input and prints the number of leaf
nodes to standard output.
nodes to standard output.
Trace the
algorithm for the following set of data :
10
25, 0, 8, 78, 6, 34, 56, 90, 100
Sequential access file organization
In computer science, sequential access means that a group of elements (such as data in a memory array or a disk file or on magnetic tape data storage) is accessed in a predetermined, ordered sequence. Sequential access is sometimes the only way of accessing the data, for example if it is on a tape.
Direct File Organization
Hash/Direct File Organization. In this method of file organization, hash function is used to calculate the address of the block to store the records. ... Hence each record is stored randomly irrespective of the order they come. Hence this method is also known asDirect or Random file organization.Download Solutions
Ignou MCA Solved Question Paper
A red-black tree is a binary search tree which has the following red-black properties: Every node is either red or black. Every leaf (NULL) is black. If a node is red, then both its children are black. Every simple path from a node to a descendant leaf contains the same number of black nodes.
Download Solutions
Ignou MCA Solved Question Paper
Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component). Kruskal's algorithm is an example of a greedy algorithm.
Download Solutions
Ignou MCA Solved Question Paper
Download Solutions
Ignou MCA Solved Question Paper
B-trees are balanced trees that are optimized for situations when part or all of the tree must be maintained in secondary storage such as a magnetic disk.
Download Solutions
Ignou MCA Solved Question Paper
Download Solutions
Ignou MCA Solved Question Paper
We extend the concept of linked data structures to structure containing nodes with more than one self-referenced field. A binary tree is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. The topmost node in the tree is called the root.
Download Solutions
Ignou MCA Solved Question Paper
Download Solutions
Ignou MCA Solved Question Paper
In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes.
Read More: https://en.wikipedia.org/wiki/Doubly_linked_list
Download SolutionsRead More: https://en.wikipedia.org/wiki/Doubly_linked_list
Ignou MCA Solved Question Paper
A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time.
Read more: https://en.wikipedia.org/wiki/Splay_tree
Download NotesRead more: https://en.wikipedia.org/wiki/Splay_tree
Ignou MCA Solved Question Paper
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors.
Read more : https://en.wikipedia.org/wiki/Breadth-first_search
MCS021 Decemeber 2015 Solved Question Paper
Ignou MCA Solved Question Paper
Read more : https://en.wikipedia.org/wiki/Breadth-first_search
MCS021 Decemeber 2015 Solved Question Paper
Ignou MCA Solved Question Paper
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.
Read More: https://en.wikipedia.org/wiki/Depth-first_search
Read More: https://en.wikipedia.org/wiki/Depth-first_search
Download Notes
Ignou MCA Solved Question Paper
Stack
Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack, the only element that can be removed is the element that was at the top of the stack, just like a pile of objects.
Download Notes
Ignou MCA Solved Question Paper
Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack, the only element that can be removed is the element that was at the top of the stack, just like a pile of objects.
Download Notes
Ignou MCA Solved Question Paper
This is a sort of edit-distance question, and is very easy. I am just quite brain dead on this subject and can't figure it out so far.
Given a series of numbers, e.g.
[3, 1, 1, 1] In the above example, the most efficient moves would be:
[1, 1, 1, 1] I can't figure out the best way to find this out, given much larger arrays of hundreds of numbers.
I originally tried computing the rounded average number (sum of all divided by length), and then reducing them to the computed average, but the above example broke this, requiring 4 moves instead of 2.
I suppose I could figure:
- The average,
- The mode,
- The median
Asked By : dthree
Answered By : mhum
The answer is to take the median. One of the properties of the median is that it minimizes the L1 distance to each element. (To make sense of the Wikipedia article, take the probability distribution to be the uniform distribution over your original series of numbers).
This is the algorithm which solves the problem (originally written by dc2):
This is the algorithm which solves the problem (originally written by dc2):
function median(arr) { arr.sort(function(a, b) { return a - b; }); var half = floor(arr.length/2); if ( arr.length % 2 ) { return arr[half]; } else { return (arr[half-1] + arr[half]) / 2.0; } } function minl1(arr) { var moves = 0; var mdn = median(arr); for ( var i = 0; i < arr.length; ++i ) { moves += Math.abs(mdn - arr[i]); } return moves; } minl1([3, 1, 1, 1]); // -> 2 Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/24469
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#define MAX1 3
#define MAX2 3
#define MAXSIZE 20
#define TRUE 1
#define FALSE 2
struct sparse
{
int *sp ;
int row ;
int *result ;
} ;
void initsparse ( struct sparse * ) ;
void create_array ( struct sparse * ) ;
int count ( struct sparse ) ;
void display ( struct sparse ) ;
void create_tuple ( struct sparse*, struct sparse ) ;
void display_tuple ( struct sparse ) ;
void prodmat ( struct sparse *, struct sparse, struct sparse ) ;
void searchina ( int *sp, int ii, int*p, int*flag ) ;
void searchinb ( int *sp, int jj, int colofa, int*p, int*flag ) ;
void display_result ( struct sparse ) ;
void delsparse ( struct sparse * ) ;
void main( )
{
struct sparse s[5] ;
int i ;
clrscr( ) ;
for ( i = 0 ; i <= 3 ; i++ )
initsparse ( &s[i] ) ;
create_array ( &s[0] ) ;
create_tuple ( &s[1], s[0] ) ;
display_tuple ( s[1] ) ;
create_array ( &s[2] ) ;
create_tuple ( &s[3], s[2] ) ;
display_tuple ( s[3] ) ;
prodmat ( &s[4], s[1], s[3] ) ;
printf ( "\nResult of multiplication of two matrices: " ) ;
display_result ( s[4] ) ;
for ( i = 0 ; i <= 3 ; i++ )
delsparse ( &s[i] ) ;
getch( ) ;
}
/* initialises elements of structure */
void initsparse ( struct sparse *p )
{
p -> sp = NULL ;
p -> result = NULL ;
}
/* dynamically creates the matrix */
void create_array ( struct sparse *p )
{
int n, i ;
/* allocate memory */
p -> sp = ( int * ) malloc ( MAX1 * MAX2 * sizeof ( int ) ) ;
/* add elements to the array */
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
printf ( "Enter element no. %d: ", i ) ;
scanf ( "%d", &n ) ;
* ( p -> sp + i ) = n ;
}
}
/* displays the contents of the matrix */
void display ( struct sparse s )
{
int i ;
/* traverses the entire matrix */
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
/* positions the cursor to the new line for every new row */
if ( i % 3 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( s.sp + i ) ) ;
}
}
/* counts the number of non-zero elements */
int count ( struct sparse s )
{
int cnt = 0, i ;
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
if ( * ( s.sp + i ) != 0 )
cnt++ ;
}
return cnt ;
}
/* creates an array that stores information about non-zero elements */
void create_tuple ( struct sparse *p, struct sparse s )
{
int r = 0 , c = -1, l = -1, i ;
/* get the total number of non-zero elements */
p -> row = count ( s ) + 1 ;
/* allocate memory */
p -> sp = ( int * ) malloc ( p -> row * 3 * sizeof ( int ) ) ;
/* store information about
total no. of rows, cols, and non-zero values */
* ( p -> sp + 0 ) = MAX1 ;
* ( p -> sp + 1 ) = MAX2 ;
* ( p -> sp + 2 ) = p -> row - 1 ;
l = 2 ;
/* scan the array and store info. about non-zero values
in the 3-tuple */
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
c++ ;
/* sets the row and column values */
if ( ( ( i % 3 ) == 0 ) && ( i != 0 ) )
{
r++ ;
c = 0 ;
}
/* checks for non-zero element,
row, column and non-zero value
is assigned to the matrix */
if ( * ( s.sp + i ) != 0 )
{
l++ ;
* ( p -> sp + l ) = r ;
l++ ;
* ( p -> sp + l ) = c ;
l++ ;
* ( p -> sp + l ) = * ( s.sp + i ) ;
}
}
}
/* displays the contents of the matrix */
void display_tuple ( struct sparse s )
{
int i, j ;
/* traverses the entire matrix */
printf ( "\nElements in a 3-tuple: " ) ;
j = ( * ( s.sp + 2 ) * 3 ) + 3 ;
for ( i = 0 ; i < j ; i++ )
{
/* positions the cursor to the new line for every new row */
if ( i % 3 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( s.sp + i ) ) ;
}
printf ( "\n" ) ;
}
/* performs multiplication of sparse matrices */
void prodmat ( struct sparse *p, struct sparse a, struct sparse b )
{
int sum, k, position, posi, flaga, flagb, i , j ;
k = 1 ;
p -> result = ( int * ) malloc ( MAXSIZE * 3 * sizeof ( int ) ) ;
for ( i = 0 ; i < * ( a.sp + 0 * 3 + 0 ) ; i++ )
{
for ( j = 0 ; j < * ( b.sp + 0 * 3 + 1 ) ; j++ )
{
/* search if an element present at ith row */
searchina ( a.sp, i, &position, &flaga ) ;
if ( flaga == TRUE )
{
sum = 0 ;
/* run loop till there are element at ith row
in first 3-tuple */
while ( * ( a.sp + position * 3 + 0 ) == i )
{
/* search if an element present at ith col.
in second 3-tuple */
searchinb ( b.sp, j, * ( a.sp + position * 3 + 1 ),
&posi, &flagb ) ;
/* if found then multiply */
if ( flagb == TRUE )
sum = sum + * ( a.sp + position * 3 + 2 ) *
* ( b.sp + posi * 3 + 2 ) ;
position = position + 1 ;
}
/* add result */
if ( sum != 0 )
{
* ( p -> result + k * 3 + 0 ) = i ;
* ( p -> result + k * 3 + 1 ) = j ;
* ( p -> result + k * 3 + 2 ) = sum ;
k = k + 1 ;
}
}
}
}
/* add total no. of rows, cols and non-zero values */
* ( p -> result + 0 * 3 + 0 ) = * ( a.sp + 0 * 3 + 0 ) ;
* ( p -> result + 0 * 3 + 1 ) = * ( b.sp + 0 * 3 + 1 ) ;
* ( p -> result + 0 * 3 + 2 ) = k - 1 ;
}
/* searches if an element present at iith row */
void searchina ( int *sp, int ii, int *p, int *flag )
{
int j ;
*flag = FALSE ;
for ( j = 1 ; j <= * ( sp + 0 * 3 + 2 ) ; j++ )
{
if ( * ( sp + j * 3 + 0 ) == ii )
{
*p = j ;
*flag = TRUE ;
return ;
}
}
}
/* searches if an element where col. of first 3-tuple
is equal to row of second 3-tuple */
void searchinb ( int *sp, int jj, int colofa, int *p, int *flag )
{
int j ;
*flag = FALSE ;
for ( j = 1 ; j <= * ( sp + 0 * 3 + 2 ) ; j++ )
{
if ( * ( sp + j * 3 + 1 ) == jj && * ( sp + j * 3 + 0 ) == colofa )
{
*p = j ;
*flag = TRUE ;
return ;
}
}
}
/* displays the contents of the matrix */
void display_result ( struct sparse s )
{
int i ;
/* traverses the entire matrix */
for ( i = 0 ; i < ( * ( s.result + 0 + 2 ) + 1 ) * 3 ; i++ )
{
/* positions the cursor to the new line for every new row */
if ( i % 3 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( s.result + i ) ) ;
}
}
/* deallocates memory */
void delsparse ( struct sparse *s )
{
if ( s -> sp != NULL )
free ( s -> sp ) ;
if ( s -> result != NULL )
free ( s -> result ) ;
}
#include <stdio.h> #include <conio.h> #include <alloc.h> #define MAX1 3 #define MAX2 3 #define MAXSIZE 20 #define TRUE 1 #define FALSE 2 struct sparse { int *sp ; int row ; int *result ; } ; void initsparse ( struct sparse * ) ; void create_array ( struct sparse * ) ; int count ( struct sparse ) ; void display ( struct sparse ) ; void create_tuple ( struct sparse*, struct sparse ) ; void display_tuple ( struct sparse ) ; void prodmat ( struct sparse *, struct sparse, struct sparse ) ; void searchina ( int *sp, int ii, int*p, int*flag ) ; void searchinb ( int *sp, int jj, int colofa, int*p, int*flag ) ; void display_result ( struct sparse ) ; void delsparse ( struct sparse * ) ; void main( ) { struct sparse s[5] ; int i ; clrscr( ) ; for ( i = 0 ; i <= 3 ; i++ ) initsparse ( &s[i] ) ; create_array ( &s[0] ) ; create_tuple ( &s[1], s[0] ) ; display_tuple ( s[1] ) ; create_array ( &s[2] ) ; create_tuple ( &s[3], s[2] ) ; display_tuple ( s[3] ) ; prodmat ( &s[4], s[1], s[3] ) ; printf ( "\nResult of multiplication of two matrices: " ) ; display_result ( s[4] ) ; for ( i = 0 ; i <= 3 ; i++ ) delsparse ( &s[i] ) ; getch( ) ; } /* initialises elements of structure */ void initsparse ( struct sparse *p ) { p -> sp = NULL ; p -> result = NULL ; } /* dynamically creates the matrix */ void create_array ( struct sparse *p ) { int n, i ; /* allocate memory */ p -> sp = ( int * ) malloc ( MAX1 * MAX2 * sizeof ( int ) ) ; /* add elements to the array */ for ( i = 0 ; i < MAX1 * MAX2 ; i++ ) { printf ( "Enter element no. %d: ", i ) ; scanf ( "%d", &n ) ; * ( p -> sp + i ) = n ; } } /* displays the contents of the matrix */ void display ( struct sparse s ) { int i ; /* traverses the entire matrix */ for ( i = 0 ; i < MAX1 * MAX2 ; i++ ) { /* positions the cursor to the new line for every new row */ if ( i % 3 == 0 ) printf ( "\n" ) ; printf ( "%d\t", * ( s.sp + i ) ) ; } } /* counts the number of non-zero elements */ int count ( struct sparse s ) { int cnt = 0, i ; for ( i = 0 ; i < MAX1 * MAX2 ; i++ ) { if ( * ( s.sp + i ) != 0 ) cnt++ ; } return cnt ; } /* creates an array that stores information about non-zero elements */ void create_tuple ( struct sparse *p, struct sparse s ) { int r = 0 , c = -1, l = -1, i ; /* get the total number of non-zero elements */ p -> row = count ( s ) + 1 ; /* allocate memory */ p -> sp = ( int * ) malloc ( p -> row * 3 * sizeof ( int ) ) ; /* store information about total no. of rows, cols, and non-zero values */ * ( p -> sp + 0 ) = MAX1 ; * ( p -> sp + 1 ) = MAX2 ; * ( p -> sp + 2 ) = p -> row - 1 ; l = 2 ; /* scan the array and store info. about non-zero values in the 3-tuple */ for ( i = 0 ; i < MAX1 * MAX2 ; i++ ) { c++ ; /* sets the row and column values */ if ( ( ( i % 3 ) == 0 ) && ( i != 0 ) ) { r++ ; c = 0 ; } /* checks for non-zero element, row, column and non-zero value is assigned to the matrix */ if ( * ( s.sp + i ) != 0 ) { l++ ; * ( p -> sp + l ) = r ; l++ ; * ( p -> sp + l ) = c ; l++ ; * ( p -> sp + l ) = * ( s.sp + i ) ; } } } /* displays the contents of the matrix */ void display_tuple ( struct sparse s ) { int i, j ; /* traverses the entire matrix */ printf ( "\nElements in a 3-tuple: " ) ; j = ( * ( s.sp + 2 ) * 3 ) + 3 ; for ( i = 0 ; i < j ; i++ ) { /* positions the cursor to the new line for every new row */ if ( i % 3 == 0 ) printf ( "\n" ) ; printf ( "%d\t", * ( s.sp + i ) ) ; } printf ( "\n" ) ; } /* performs multiplication of sparse matrices */ void prodmat ( struct sparse *p, struct sparse a, struct sparse b ) { int sum, k, position, posi, flaga, flagb, i , j ; k = 1 ; p -> result = ( int * ) malloc ( MAXSIZE * 3 * sizeof ( int ) ) ; for ( i = 0 ; i < * ( a.sp + 0 * 3 + 0 ) ; i++ ) { for ( j = 0 ; j < * ( b.sp + 0 * 3 + 1 ) ; j++ ) { /* search if an element present at ith row */ searchina ( a.sp, i, &position, &flaga ) ; if ( flaga == TRUE ) { sum = 0 ; /* run loop till there are element at ith row in first 3-tuple */ while ( * ( a.sp + position * 3 + 0 ) == i ) { /* search if an element present at ith col. in second 3-tuple */ searchinb ( b.sp, j, * ( a.sp + position * 3 + 1 ), &posi, &flagb ) ; /* if found then multiply */ if ( flagb == TRUE ) sum = sum + * ( a.sp + position * 3 + 2 ) * * ( b.sp + posi * 3 + 2 ) ; position = position + 1 ; } /* add result */ if ( sum != 0 ) { * ( p -> result + k * 3 + 0 ) = i ; * ( p -> result + k * 3 + 1 ) = j ; * ( p -> result + k * 3 + 2 ) = sum ; k = k + 1 ; } } } } /* add total no. of rows, cols and non-zero values */ * ( p -> result + 0 * 3 + 0 ) = * ( a.sp + 0 * 3 + 0 ) ; * ( p -> result + 0 * 3 + 1 ) = * ( b.sp + 0 * 3 + 1 ) ; * ( p -> result + 0 * 3 + 2 ) = k - 1 ; } /* searches if an element present at iith row */ void searchina ( int *sp, int ii, int *p, int *flag ) { int j ; *flag = FALSE ; for ( j = 1 ; j <= * ( sp + 0 * 3 + 2 ) ; j++ ) { if ( * ( sp + j * 3 + 0 ) == ii ) { *p = j ; *flag = TRUE ; return ; } } } /* searches if an element where col. of first 3-tuple is equal to row of second 3-tuple */ void searchinb ( int *sp, int jj, int colofa, int *p, int *flag ) { int j ; *flag = FALSE ; for ( j = 1 ; j <= * ( sp + 0 * 3 + 2 ) ; j++ ) { if ( * ( sp + j * 3 + 1 ) == jj && * ( sp + j * 3 + 0 ) == colofa ) { *p = j ; *flag = TRUE ; return ; } } } /* displays the contents of the matrix */ void display_result ( struct sparse s ) { int i ; /* traverses the entire matrix */ for ( i = 0 ; i < ( * ( s.result + 0 + 2 ) + 1 ) * 3 ; i++ ) { /* positions the cursor to the new line for every new row */ if ( i % 3 == 0 ) printf ( "\n" ) ; printf ( "%d\t", * ( s.result + i ) ) ; } } /* deallocates memory */ void delsparse ( struct sparse *s ) { if ( s -> sp != NULL ) free ( s -> sp ) ; if ( s -> result != NULL ) free ( s -> result ) ; }
