Goals for this homework

  • Practice the C development cycle
  • Practice using control, iteration, and recursion

You are expected to complete this assignment individually. If you need help, you are invited to come to office hours and/or ask questions on piazza. Clarification questions about the assignments may be asked publicly. Once you have specific bugs related to your code, make the posts private.

This homework has several exercises. We are also providing you with some resources on printf and error handling for this assignment.

You should submit five files for this assignment (hw2.h, hw2.c, hw2_main.c, and Makefile) in your subversion repository as directed below.

Set Up

If you participated in duet programming, make sure you copy over your files from your duet svn account to this account!!

Because you are adding a second set of files to your directory, you need to add a second target to your Makefile. In your makefile, add another two lines (with a space between these and the ones already there). 

hw2: hw2.h hw2.c hw2_main.c
	clang -Wall -o hw2 hw2.c hw2_main.c

Now you need to make the skeleton code so that your program will minimally execute.

  • Step 1: Create hw2.h. I have written this for you. Copy and paste the text.
  • Step 2: Create hw2.c. I have written it partially for you. There are some missing functions - look at the hw2.h file and add in the stubs / skeletons for any missing functions. The project will not compile until you do so.

    For each function, implement the function with a single line - return with the right type. For example: 

    double surface_area_cylinder(double height, double radius)
{
	return 0.0;
}
  • Step 3: Create hw2_main.c. I have provided this for you in order to show you how to allocate and initialize arrays.

    First get this compiling and running. It won't print out anything, but this will mean that your code will compile and execute with our infrastructure. This must work in order to get any points in this course. Do this first, not last.

    Note: The array of exercises are chosen for several reasons. First, they build up in difficulty as they move forward. Second, they exercise all of the different skills you have learned so far. As simple as these functions seem, they have multiple ways they could be solved. You will be graded on choosing a solution that is efficient.

    How do you decide, you ask? If you can solve it by calculation rather than by conditionals, then do so. Also, different conditionals have different efficiencies. A disconnected set of if's is slower than a coordinated set of if/else if/else if's, which is slower than a single switch statement. However, not all code can be implemented with the faster control structure. Therefore, it is your job to think about whether what you are writing could be structured in such a way as to use a switch or if/else if/else if or if. We cover proper usage, not just correctness of control structures in class, so make sure to pay attention. If we haven't covered it in lecture, then I do not expect you to apply it in your assignments.

Exercise 1: Print numbers

In this exercise, you will write a function that takes a number betweem 0 and 99, and print the English word(s) of that number, like following:

  • 0: zero
  • 7: seven
  • 12: twelve
  • 32: thirty-two
  • 98: ninety-eight

First write a function that takes an integer between 0 and 99 and prints out the written version of the number.

In addition, this function returns 0 if it prints out the English version of the number successfully.

If the user enters any number out of the range between 0 and 99, print out an error "error (print_number): [description of error]". Remember, as described in hw1, to use fprintf rather than printf and send the output to stderr. Return -1 to indicate that an improper input was received.

Note: You may not use an array for this exercise. This is an exercise in choosing proper control structures, not choosing proper data structures. That will come later!

The function header must be as follows: 

void print_number(int number);

Don't forget to complete this portion, test it, and commit it before moving on!

Exercise 2: Convert decimal to hexadecimal

Context: We are used to a decimal number system, i.e., a number system with base 10. However, there are other number systems as well. For example, binary numbers (numbers with base 2) are commonly used in computers. Hexadecimals are numbers that based on number 16.

Read this post to learn hexadecimal numbers.

To summarize what a hexadecimal number system is, instead of using digits 0 to 9, it uses digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. A hexadecimal number 10 is decimal number 16

In this exercise, you will write a function that converts a decimal number to a hexadecimal number. There is a nice recursive algorithm for this purpose.

Read this page to learn the algorithm converting decimal numbers to hexadecimal numbers.

To summarize, the algorithm works as follows:

  1. Given a decimal number n, you divide this number by 16, and write down the result as well as the remainder.
  2. Now the result becomes n, and you repeat step 1, until the result becomes 0.
  3. Output the remainders in the reverse order, this will be the hexadecimal number representation of the decimal number n.

For example, decimal number 31 is hexadecimal number 1F, decimal number 145 is hexadecimal number 91, etc. Verify this is true with the algorithm we provide.

The function skeleton is provided as follows: 

void print_hex(unsigned int number);

You may assume that the input number is non negative.

Note: You may not use arrays or loops for this exercise. You must use recusion. Remember that recursion is a problem-solving technique, not just a solution. This is the key to this problem. If you can't figure it out, please come into to office hours! I'm happy to help you!

You must clearly label your base case, smaller case, and general case in comments

Don't forget to complete this portion, test it, and commit it before moving on! If you get stuck, you may move on. Otherwise, make sure you go through all steps.

Exercise 3: print_asterisk_word

It is pretty limiting to only print one letter per line. We want to support writing words, as such: 
****  *   * ***** 
*   * *   *   *   
****  *   *   *   
*  *  *   *   *   
*   *  ***    *
There is a single space between each letter (or column of spaces, to be more accurate).
The function prototype is as follows: 
void print_asterisk_word(char word[], unsigned int length);

You already wrote a print_asterisk_letter function in the warmup. You are now using an array, which you saw in class on Friday. I have provided skeleton code for you to test it. Think about whether or not you can use that function for this part. At its heart, this an exercise in function decomposition, not coding. The way you break down this exercise is going to greatly influence the readability of your solution. Think about how the computer is going to print it out, then think about giving that information in such a way that divides nicely into functions. You should have helper functions, but not necessarily the ones you think.

Exercise 4: print_asterisk_shape

Write a function to print the following asterisk shape with parameter h = 5. 

*        *
**      **
***    ***
****  ****
**********
**********
**********
**********
**********
**********
**********
 ******** 
  ******  
   ****   
    **

At the top are two isosceles right triangles, with side height and width of h. In the middle is a rectangle with height h and width 2h. At the bottom is an upside-down isosceles triangle with base width 2h and height h. You can view it as "moving" a triangle from the top to the bottom.

Please write the function with the following function signature. 

void print_asterisk_shape(unsigned int h);

When we change the value of h, your function should be able to print shapes with corresponding length of h. Accept any intput between 1 and 40, inclusive.

Don't forget to complete this portion, test it, and commit it before moving on!

Exercise 5: Sort

Sorting is an algorithm that puts elements of an array in order. It is one of the most fundamental algorithms we will learn in an algorithm course. People have invented many good sorting algorithms, some of which are very efficient.

In this exercise, we will implement one of the less efficient, but simple, sorting algorithms. The most efficient algorithms are "quick sort" and "merge sort", which we will learn later in the course. However, the purpose of this exercise is to get you familiar with array operations, so efficiency is not a big concern here.

This sort we are doing takes a set of unordered numbers and inserts them, one at a time, into an array in sorted order. That is, after 1 iteration, 1 item is in the array. After 2 iterations, 2 items are in the array, and they are sorted. After 3 iterations, 3 items are in the array, and they are sorted. This continues until all n items have been inserted into the array, leaving us with a sorted array. More specifically, the algorithm is decomposed as follows: 

            void sort(int source_array[], 
                int dest_array[], unsigned int size);
  1. We maintain two arrays, one source_array contains a random sequence of numbers to be sorted, and another dest_array is empty initially, and will be filled with sorted array numbers.
  2. Loop over each element of source_array from the beginning, and insert that number to dest_array, gradually building a larger sorted array.
We need a helper function to perform that insertion of a single value into the array. 
	   void insert_into_array(int array[], unsigned int cur_size,
			unsigned int total_size, int value)
You may assume that array currently holds cur_size items, stored in locations 0 through cur_size-1, in it in sorted order. Furthermore, it is large enough to hold total_size items. To perform the insertion, cur_size must be less than total_size. At the end of this function, there are now cur_size+1 items in sorted order - the original ones and value.

Submit

At this point, you should have done the following:
  • Created four files and filled in the proper information: hw2.h, hw2.c, hw2_main.c inside your hw2 directory. 
  • $ svn add hw2.h hw2.c hw2_main.c
  • Implemented all of your functions in hw2.c. If not, you at least need skeletons of your functions so that our automated tests will compile for the functions you did write.
  • Compiled your executable manually (typing the clang line directly into the terminal) and with the Makefile
  • Implemented your test cases in the main function.
  • Executed your code
  • Debugged your code 
  • $ svn commit -m "hw2 complete"