Practice Exercises

Here are a few exercises that you might try to solve in getting ready to the exam. The questions presented here do not reflect in any way the questions that will appear in the exam.

Merger

Write a program that receives two input files as arguments. Those two files are assumed to be sorted text files (sorted by lexicograph ordering of the lines). The program should read the two files, and created a third file which is the sorted merge of those two files. The program should work by merging the two files in linear time.

Another Sort

Write a function that receives a pointer to a list of employees and sorts the list either by the employee name (lexicographic order) or by their ID. The type of sorting is defined by a parameter t.

Assume, of course, that the employee structure includes the fields of name and ID. The point to the list is passes to the function as a parameter:

void sort(employee *list, int t);

Binary Representation

Write a function that converts a given number into its binary representation in a string. For example

char * f(int d);

given d = 11, f() will return a pointer to the string "1011".

Trees

Write a function that reads a sequence of integers and creates a binary search tree. The program stores the numbers in the binary tree in ordered manner. Use dynamic memory, where a node in the tree is a structure with two pointers *left and *right.

Sum It Up

Write a program that reads a text file from a file (specified on the command line of the program using argv). The program should compute the total sum of the numbers written in the text. You can assume that a number is seperated from the numbers before it and after it by a space. Thus, for the following input file:

abcd 1000 100 10.1 1
2000 200 shalom 20 bogi 2

The program should output

3333.1

verify

Write a function:

bool  verify( char * line, double  * p_income )

The function return true if line is of the form:

"I earned -num- shekels"

Where -num- is a floating-point number. If the answer is true then the returned value should be stored into *p_income. Thus, for a line:

"I earned 1000 shekels"

the function should return true, and the vlaue 1000 will be stored into *p_income.

Script

Write a script big that output the total size (in K) of the largest subdirectory (of the current directory) that contains the file abc.txt. Hint :use the du command.

Primes

Write a program that outputs the first 1000 primes. The program should use Aristosenes sieve. Namely, you should allocate an appropriate array of flags (let say, an array with 1000000 entries), and initialize all its enteries to 1 (i.e., all the numbers are candidate to be prime). In each stage, you output the first entry k that is non-zero (this is a new prime). You should now pass over the flags array, and turn off all the entries that their index is a multiply of k (i.e., 2k, 3k, ... ). You repeate this process till 1000 primes are printed.

To make things interesting, you should implement the array of flags, so that each bit in memory contains one bit. Namely, you should allcoate an array of chars of size (1000000/8) to store the array of flags. To do so, use the bitwise operators &, |, < < > > .