University of Allahabad Computer Science B.Sc.Part II Paper III Syllabus

Computer Science

B.Sc Part II Year

Paper III- Data Structures

Introduction:- 

 Data Structures, Representation and Implementation, Complexity calculation of algorithms, Linear & Non Linear Data Structures.

Linear Data Structures:- 

Arrays, Ordered List and their representations, List Operations- insertion deletion & transversal; Stack, Queues, Priority Queues, Linked lists, Doubly linked Lists, multi- channel lists and their variations; Algorithms for polynomial additions, sparse matrix representation, Infix and post fix expressions, Garbage collection.

Non Liner Data Structures:- 

 Binary trees &  their representations, Binary tree traversals,  Threaded binary trees, Height balancing and AVL tree, union and find algorithms, Decision tree, graphs, and their representations, Graphs and their representations. Graph search, Graph traversal, connected components and spanning trees; Shortest path.

Searching & Sorting:-

 Sequential search, binary search, hashing, Chaining and Symbol table, Collision processing, Indexed Search Techniques, Internal & External Sorting.

Read More

C program to calculate the difference of two dates in years, months and days.

Write a C program to calculate the difference of two dates in years, months and days.

Program:

#include<stdio.h>
#include<stdlib.h>
int valid_date(int date, int mon, int year);


int main(void)
{
    int day1, mon1, year1,
        day2, mon2, year2;

    int day_diff, mon_diff, year_diff;        

    printf("Enter start date (MM/DD/YYYY): ");
    scanf("%d/%d/%d", &mon1, &day1, &year1);
   
    printf("Enter end date (MM/DD/YYYY): ");
    scanf("%d/%d/%d", &mon2, &day2, &year2);
   
    if(!valid_date(day1, mon1, year1))
    {
        printf("First date is invalid.\n");       
    }
   
    if(!valid_date(day2, mon2, year2))
    {
        printf("Second date is invalid.\n");
        exit(0);
    }      
   
    if(day2 < day1)
    {     
        // borrow days from february
        if (mon2 == 3)
        {
            //  check whether year is a leap year
            if ((year2 % 4 == 0 && year2 % 100 != 0) || (year2 % 400 == 0))
            {
                day2 += 29;
            }
           
            else
            {
                day2 += 28;
            }                       
        }
       
        // borrow days from April or June or September or November
        else if (mon2 == 5 || mon2 == 7 || mon2 == 10 || mon2 == 12)
        {
           day2 += 30;
        }
               
        // borrow days from Jan or Mar or May or July or Aug or Oct or Dec
        else
        {
           day2 += 31;
        }
       
        mon2 = mon2 - 1;
    }
   
    if (mon2 < mon1)
    {
        mon2 += 12;
        year2 -= 1;
    }      
   
    day_diff = day2 - day1;
    mon_diff = mon2 - mon1;
    year_diff = year2 - year1;
   
    printf("Difference: %d years %02d months and %02d days.", year_diff, mon_diff, day_diff);
   
    return 0; // return 0 to operating system
}


// function to check whether a date is valid or not
   
int valid_date(int day, int mon, int year)   
{
    int is_valid = 1, is_leap = 0;
   
    if (year >= 1800 && year <= 9999)
    {

        //  check whether year is a leap year
        if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
        {
            is_leap = 1;
        }
       
        // check whether mon is between 1 and 12
        if(mon >= 1 && mon <= 12)
        {
            // check for days in feb
            if (mon == 2)
            {
                if (is_leap && day == 29)
                {
                    is_valid = 1;
                }
                else if(day > 28)
                {
                    is_valid = 0;
                }
            }
           
            // check for days in April, June, September and November
            else if (mon == 4 || mon == 6 || mon == 9 || mon == 11)
            {
                if (day > 30)
                {
                    is_valid = 0;
                }
            }

            // check for days in rest of the months
            // i.e Jan, Mar, May, July, Aug, Oct, Dec
            else if(day > 31)
            {           
                is_valid = 0;
            }       
        }
       
        else
        {
            is_valid = 0;
        }

    }
    else
    {
        is_valid = 0;
    }
   
    return is_valid;
       
}
--------------------------------------------------------------------------
Output:

Enter start date (MM/DD/YYYY): 7/10/2000
Enter end date (MM/DD/YYYY): 7/25/1998
Difference: -2 years 00 months and 15 days.
--------------------------------
Process exited after 35.3 seconds with return value 0
Press any key to continue . . .

Read More

C Program to Convert a Decimal Number to Roman Numerals

Write a C Program to Convert a Decimal Number to Roman Numerals

Program:

#include <stdio.h>

int main(void)
{  
    int num, rem;
   
    printf("Enter a number: ");
    scanf("%d", &num);
   
    printf("Roman numerals: ");       
   
    while(num != 0)
    {
   
        if (num >= 1000)       // 1000 - m
        {
           printf("m");
           num -= 1000;
        }

        else if (num >= 900)   // 900 -  cm
        {
           printf("cm");
           num -= 900;
        }       

        else if (num >= 500)   // 500 - d
        {          
           printf("d");
           num -= 500;
        }

        else if (num >= 400)   // 400 -  cd
        {
           printf("cd");
           num -= 400;
        }

        else if (num >= 100)   // 100 - c
        {
           printf("c");
           num -= 100;                      
        }

        else if (num >= 90)    // 90 - xc
        {
           printf("xc");
           num -= 90;                                             
        }

        else if (num >= 50)    // 50 - l
        {
           printf("l");
           num -= 50;                                                                    
        }

        else if (num >= 40)    // 40 - xl
        {
           printf("xl");          
           num -= 40;
        }

        else if (num >= 10)    // 10 - x
        {
           printf("x");
           num -= 10;          
        }

        else if (num >= 9)     // 9 - ix
        {
           printf("ix");
           num -= 9;                        
        }

        else if (num >= 5)     // 5 - v
        {
           printf("v");
           num -= 5;                                    
        }

        else if (num >= 4)     // 4 - iv
        {
           printf("iv");
           num -= 4;                                                           
        }

        else if (num >= 1)     // 1 - i
        {
           printf("i");
           num -= 1;                                                                                  
        }
   
    }

    return 0;
}
-----------------------------------------------------------------
Output:

Enter a number: 99
Roman numerals: xcix
--------------------------------
Process exited after 3.584 seconds with return value 0
Press any key to continue . . .

Read More

C Program to find the Sum of the Digits of a number

Write a C Program to find the Sum of the Digits of a Number

Program:

#include<stdio.h>

int main()
{
    int n, remainder, sum = 0;
   
    printf("Enter a number: ");
    scanf("%d", &n);
   
    while(n != 0)
    {
        remainder = n % 10;
        sum += remainder;
        n = n / 10;
    }
   
    printf("sum = %d", sum);
   
    return 0;
}
------------------------------------------------------------------------------------
Output:-
Enter a number: 12345
sum = 15
--------------------------------
Process exited after 8.671 seconds with return value 0
Press any key to continue . . .

Read More

C Program to Print the Date in Legal Format

Write a C Program to Print the Date in Legal Format:

PROGRAM:

#include<stdio.h>
int main(void)
{      
    int day, mon, year;

    char *months[] = {
                        "January", "February", "March", "April",
                        "May", "June", "July", "August",
                        "September", "October", "November", "December",
                      };
   
    printf("Enter date(MM/DD/YYYY): ");
    scanf("%d/%d/%d", &mon, &day, &year);
   
    printf("%d", day);
   
    // if day is 1 or 21 or 31, add the suffix "st"
    if(day == 1 || day == 21 || day == 31)
    {
        printf("st ");
    }
   
    // if day is 2 or 22, add the suffix "nd"
    else if(day == 2 || day == 22)
    {
        printf("nd ");
    }
   
    // if day is 3 or 23, add the suffix "rd"
    else if(day == 3 || day == 23)
    {
        printf("rd ");
    }
   
    // for everything else add the suffix "th"
    else
    {
        printf("th ");
    }   
   
    printf("%s, %d", months[mon - 1], year);
   
    return 0;
}

OUTPUT:

Enter date(MM/DD/YYYY): 10/5/1998
5th October, 1998
--------------------------------
Process exited after 23.59 seconds with return value 0
Press any key to continue . . .

Read More

C Program to calculate Permutation and Combination

Write a C Program to calculate Permutation and Combination

Program:

#include<stdio.h>
long permutation(int n, int r);
long combination(int n, int r);
long factorial(int num);


int main(void)
{   
    int n, r;
   
    printf("Enter n: ");
    scanf("%d", &n);
   
    printf("Enter r: ");
    scanf("%d", &r);
   
    printf("Permutation = %ld\n", permutation(n, r));   
    printf("Combination = %ld", combination(n, r));
   
    return 0;
}


long permutation(int n, int r)
{
    return factorial(n) / factorial(n-r);
}

long combination(int n, int r)
{
    return permutation(n, r) / factorial(r);
}

long factorial(int num)
{
    long long fact = 1;
   
    while(num > 0)
    {
        fact *= num;
        num--;
    }
   
    return fact;
}

Output:

Enter n: 10
Enter r: 5
Permutation = 30240
Combination = 252
--------------------------------
Process exited after 8.387 seconds with return value 0
Press any key to continue . . .

Read More

C Program to Print the Two Digit number in Words

Write a C Program to print the two digit number in words

PROGRAM:

# include<stdio.h> 

int main(void)
{
    int num1, num2;

    printf("Enter a two-digit number: ");
    scanf("%1d%1d", &num1, &num2);

    printf("You have entered: ");

    // print word for the first digit
    switch (num1)
    {
        case 1:
            // special case for numbers between 11-19
            switch (num2)
            {
                case 0:
                    printf("ten");
                    return 0;
                case 1:
                    printf("eleven");
                    return 0;
                case 2:
                    printf("twelve");
                    return 0;
                case 3:
                    printf("thirteen");
                    return 0;
                case 4:
                    printf("fourteen");
                    return 0;
                case 5:
                    printf("fifteen");
                    return 0;
                case 6:
                    printf("sixteen");
                    return 0;
                case 7:
                    printf("seventeen");
                    return 0;
                case 8:
                    printf("eigthteen");
                    return 0;
                case 9:
                    printf("nineteen");
                    return 0;
            }
        case 2:
            printf("twenty");
            break;
        case 3:
            printf("thirty");
            break;
        case 4:
            printf("forty");
            break;
        case 5:
            printf("fifty");
            break;
        case 6:
            printf("sixty");
            break;
        case 7:
            printf("seventy");
            break;
        case 8:
            printf("eighty");
            break;
        case 9:
            printf("ninety");
            break;
    }

    // print word for the second digit
    switch (num2)
    {
        case 1:
            printf("-one");
            break;
        case 2:
            printf("-two");
            break;
        case 3:
            printf("-three");
            break;
        case 4:
            printf("-four");
            break;
        case 5:
            printf("-five");
            break;
        case 6:
            printf("-six");
            break;
        case 7:
            printf("-seven");
            break;
        case 8:
            printf("-eight");
            break;
        case 9:
            printf("-nine");
            break;
    }

    return 0;
}

OUTPUT:-

Enter a two-digit number: 87
You have entered: eighty-seven
--------------------------------
Process exited after 10.21 seconds with return value 0
Press any key to continue . . .

Read More