PDS LAB Test(Supplementary)

(16.04.2007)

(Section : 2)

Submission deadline time: 3 p.m.

1. Generate a random sequence of birthdays and store the birthdays in an array. As soon as a match is found, report that and stop generating the birthdays and exit.. Also report how many birthdays were generated to get the first match.

Note:
 

•  Encode a day in the year by an integer between 0 and 364, where 0 refers to January 1, 1 to January   2,     ..., 364 to December 31.

• Generate a random sequence of integers (between 0 and 364) one by one and store the integers in an array. Every time a new random day is generated, it is compared against the entries currently stored in the array. If a match is found, report and exit.

•  Print the birthdays in the standard format (MonthName Date). Don't bother about leap years, i.e., assume that every February has 28 days and every year 365 days. In case you are not sure about the numbers of days in the months, use the following array:
  
  int nDays[12] = {31,28,31,30,31,30,31,31,30,31,30,31};

• Use rand function to generate randon numbers.
   

 In order to generate random numbers between 0 and a bound B use the following:
 

#include<stdlib.h>
......

.....

int main()

{

...

int Date[365] // In this array store the date

int randInt;
int B = 364;

srand((unsigned int)time(NULL)); //Do this only once at the beginning of main.

....

....
randInt = rand() % (B+1); // do as many time as needed to generate random number
 

[MARKS :08]

Sample output

 1. March 12
 2. November 27
 3. May 27
 4. July 2
 5. April 18
 6. September 11
 7. February 13
 8. October 27
 9. September 15
10. January 11
11. October 29
12. December 23
13. January 5
14. February 1
15. June 13
16. December 28
17. November 12
18. October 15
19. January 5
Match found among 19 birthdays.
Birthdays no. 13 and 19 are the same...

2. Recall that the insertion sort algorithm on an array iteratively considers array elements one-by-one starting from the beginning and inserts that element in the proper position in the part of the array before this element.
 

You are given an unsorted linked list (instead of an array) of integers. Your task is to sort the linked list ( Non decreasing order ) using the insertion sort algorithm.
 

1. Write a function that creates a linked list of integers of  a specified size.

2. Write a function that takes as input a linked list of arbitrary size and sorts the list using the insertion sort algorithm.

3. Write a function that neatly prints a linked list from beginning to end.

4. Write a main function that calls the above three functions in order to do the following:  Create a
   linked list  integers, print this list, then call the sorting function and finally print the sorted list.

                [MARKS :12]

        Use the following structure & the following functions

        struct linked_list {
        int  value;
        struct linked_list *next
        } ;

        struct linked_list * Create_Linked_List(int N); // Create a linked list of  N  integers

        struct linked_list * Sort_Linked_List(struct linked_list *node); // Sort the linked list using insertion    sort

        void Print_linked_List(struct linked_list node); // Prints a linked list from beginning to end

 Sample output

        Input : Size of list (N) = 7

        List of elements (L) = 21 8 4 19 30 25 15

        Output: (Sorted List) =  4-> 8-> 15-> 19 -> 21 -> 25 -> 30