Operating Systems Assignment-

1. Binary Record Sorting in Ascending Order| You will write a simple sorting program. This program should be invoked as follows:

shell% ./fastsort -i inputfile -o outputfile

The above line means the users typed in the name of the sorting program ./fastsort and gave it two inputs: an input file to sort called input file and an output file to put the sorted results into called outputfile.

Input files are generated by a program we give you called generate.c (this file will be provided to you).

After running generate, you will have a file that needs to be sorted. It will be filled with binary data, of the following form: a series of 100-byte records, the first four bytes of which are an unsigned integer key, and the remaining 96 bytes of which are integers that form the rest of the record.

Something like this (where each letter represents two bytes):

kkRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR

See the following figure for details.

Your goal: to build a sorting program called fastsort that takes in one of these generated files and sorts it based on the 4-byte key (the remainder of the record should of course be kept with the same key). The output is written to the specified output file.

2. Big Integer Addition- As we have seen in the class, int datatype can hold an integer of size 4 bytes. We have also seen the type long long int which can hold up to 8-byte integer. Often times, while performing cryptographic operations (e.g., encryption, decryption) you require to add or multiply integers that are 1000 digits long. Your goal is to implement the addition operation of such big integers. Note that, these integers will not fit in a typical primitive data type. We are required to store these big integers in some other form. For instance, one can store them in a char array where each digit of such numbers occupy one position in that array. You will be given a skelton C file which will deal with taking such a pair of big integers as input.

Your objective is to implement the addition function and the print function to output the result. You can safely assume that the number of digits in these big integers are less than 10000. You can also safely assume the numbers are positive.

3. Big Integer Multiplication- In this problem, you will extend the previous problem by implementing the multiplication operation of big integers. Note that, these integers will not fit in a typical primitive data type. We are required to store these big integers in some other form. For instance, one can store them in a char array where each digit of such numbers occupy one position in that array. You will be given a skelton C file which will deal with taking such a pair of big integers as input. Your objective is to implement the multiplication function and the print function to output the result. You can safely assume that the number of digits in these big integers are less than 10000. You can also safely assume the numbers are positive.

4. Dictionary Search - A lot of times we are required to search for words in a large dictionary. This problem requires you to implement the insert and search functionality in a large dictionary. In this problem, you will be given a large dictionary file. Each input line of this dictionary will contain a word whose length will be maximum 64 characters. To make search efficient (i.e., O(log n)), you will require to order the dictionary as a binary search tree. You will need to implement the function responsible for creating a binary search tree from a given dictionary file. You do not have to be worried about taking inputs because you will be provided a skeleton file that reads words from the dictionary file. You will then be required to implement a function that takes a word as input and searches the tree to see whether the word can found in the dictionary. Your function should return true if the word can be found in the dictionary or else it should return false. In addition, you will need to implement 3 functions to print the binary search tree in a pre-, in-, and post-order form. You can consult a data-structure textbook to determine how to add and search in a binary search tree.

Attachment:- Assignment.zip