Main navigation | Main content
In today's lab we'll work on concepts related to the Project 1, mostly on file formatting and quicksort, and a little bit on binary trees.
In this exercise, our goal is to complete a C program c_fmt, which changes all spaces in a slurped file into new lines, and vice versa.
Get a copy of the program with:
cp /web/classes/Spring-2020/csci2021/labs/0x3/lab3-format.c .
This program can be compiled using the command gcc -g -Wall -o c_fmt lab3-format.c .
The executable can be run using the command line c_fmt <file_name> <fmt_type>
The first argument is the name of the file that needs to be slurped and formatted. The second argument
is a string which indicates format conversion, which could be "space_to_newline"
or " newline_to_space ".
Your implementation can be done completely inside the format_file function, as indicated by the TODO comment in the function. One way to do it is to loop through the file buffer buf, and replace any spaces with new lines and vice versa. Subsequently, the contents of buf can overwrite the contents of the file.
For this question you are going to complete a program that performs in-place quicksort on an array of strings.
Get a copy of the program with:
cp /web/classes/Spring-2020/csci2021/labs/0x3/lab3-quicksort.c .
The main idea of this quicksort implementation is to select a pivot value. All values less than the pivot are moved to the left of the array, and all values more than the pivot are moved to the right of the array, whereas the pivot is between these values. This step is often called partitioning. Then, quicksort is invoked recursively on the left and right subarrays. There are several implementations of quicksorts readily available online, which can be a useful resource, such as here.
An optimization for this implementation of quicksort is to choose the pivot in a clever manner, so that it is rare to have worst case performance scenario (eg: pivot is the largest or smallest number in the array). One such strategy is called median of three, or MoD. In this approach, one compares the first, middle and last elements of the array, and picks the median one to be the pivot.
An implementation of quicksort , qsort, is provided by the C std library.
You can use the command man qsort on the terminal to learn about this function.
qsort is polymorphic, i.e. it can be applied to an arbitrary type array, eg int, char, float, char*, etc.
To facilitate this polymorphic behavior, in addition to the array pointer, qsort has the number and size
of the array elements and a function pointer as inputs. The function is user-defined and is supposed
to compare two array elements of the array.
For uniformity, we implement the same function definition as the C std library. As indicated by TODOs in the code, you need to complete the partitioning and the recursive calls to quicksort, the cmpInt function, which compares two integers, and is used as a function pointer input to qsort, and lastly an MoT function, which computes the median-of-three index.
Once done with your implementation, you can compile the program using the command gcc -g -Wall -o qsort lab3-quicksort.c Upon successful compilation, the program can be executed using the command line qsort <filename> . The input file should contain a sequence of integers, one integer per line. The output should print the sorted result to stdout in the same way i.e. one integer per line.
In this exercise, you will be completing a program which reverses the contents of a file, both the order of the lines (similar to the tac utility), and the order of the characters in each line, similar to the rev utility, both commonly installed on linux systems.
Get a copy of the program with:
cp /web/classes/Spring-2020/csci2021/labs/0x3/lab3-reverser.c .
This program can be compiled using the command gcc -g -Wall -o reverser lab3-reverser.c .
The executable can be run using the command line ./reverser <file_name>
The first argument is the name of the file that needs to be reversed.
The main idea of the implementation is to store the lines of the file into an array of strings, and then call a polymorphic string array manipulation function, called array_manipulate_polymorphic, which will invoke a manipulate function on each of the strings of the string array. Note that the function definition is quite similar to qsort discussed in the previous problem. Lastly, another function print_string_array_rev writes the contents of the string array in reverse order into the file. You need to complete these three functions, as indicated by TODOs in the provided code.
In this exercise, you are given a program which converts a given binary number to its integer value, using a binary tree datastructure. The leaves of the binary tree store the decimal values. Each edge of the binary tree represents a zero or a one, therefore, each path from the root to the leaf is a sequence of zeros and ones, which represents a binary number. A zero corresponds to the left child and a one corresponds to the right child. Thus each unique binary number corresponds to a unique path through the binary tree, to a unique child and value. The number of leaves of this datastructure depends on the size of the binary number. A 3 bit binary number requires 8 leaves, a 4-bit number 16 leaves and so on.
Get a copy of the program with:
cp /web/classes/Spring-2020/csci2021/labs/0x3/lab3-bin2dec.c .
This program can be compiled using the command gcc -g -Wall -o bin2dec lab3-reverser.c .
The executable can be run using the command line ./bin2dec <binary_number>
The first argument is a string composed using bits 0 and 1 only, thus representing a binary number.
You'll notice that the program segfaults instead of returning a value. Use gdb to run the program and figure out why this is happening.