Assignment for C Programming - Recursion and Sorting

1 | P a g e    

National University of Singapore  School of Continuing and Lifelong Education 

TIC1002: Introduction to Computing and Programming II  Semester II, 2017/2018 

Problem Set 2  Recursion and Sorting 

    Release date: 3 Feb 2018  Due: 19 Feb 2018, 23:59    Task 1: Memoisation…. Did you just misspelled memorization? [6 marks] 

The  Fibonacci()  example  from  lecture  illustrated  that  a)  Recursion  is  indeed  simpler  /  elegant  to code, but also b) Precious  time may be wasted due  to  the  recalculation of known  results. Let us learn a powerful technique to get the best of both worlds in this task.  

Memoization (not a typo!) is a problem solving technique where we keep previously calculated  results for future use. Combining memoization with recursion give you a very powerful problem  solving tool!  

Let us use factorial() to illustrate the technique: 

int factorial_m( int N, int known_result[])  { 

if (known_result[N] == 0) {          //Cannot rely on known calculation, have to work       if (N == 0){           //Fill in the result for future use           known_result[0] = 1;       } else {           //Same, record result for future use           known_result[N] = N * factorial_m( N‐1, known_result);       }  }    //At this point, known_result[N] should have N!  // Either it is previously known (i.e. failed the if condition) OR // It has just been calculated in the recursive portion above.  return known_result[N]; 

}   

The factorial function now takes in an array known_result[] which keeps track of previously  calculated result, known_result[K] stores the answer for K!.  

2 | P a g e    

At the beginning, the known_result[] should be initialized to all zeroes to indicate no known  answers (zero is chosen because factorial(N) cannot be zero). You can see that as answers are  calculated,  the  respective  elements  in  the  known_result  array will  be  filled.  If  the  same  known_result[] array is used again, we can cut down some of the unnecessary calculations. 

For example: 

int known[20] = {0};   //support up to factorial(19).    factorial_m( 3, known );   // Call ONE  factorial_m( 3, known );   // Call TWO  factorial_m( 5, known );   // Call Three

 

For Call ONE, each of  the  recursive  calls  (f(3)  f(2)  f(1)  f(0)) will  find  that  the respective element in known[3], known[2], known[1] and known[0] are all "0", i.e. no  known  result.  The  normal  recursion  will  kick  in  and  fill  up  the  answers  in    known[0],  known[1], known[2] and known[3]. In this example, there is no saving at all. 

However, at Call TWO, fac(3) will find that known[3] already has an answer and proceed to  return it without any recursive call!   

For Call THREE, fac(5) will only calculates two values at known[5] and known[4]. As soon as  the recursion hits fac(3), the known result will be used instead of recursion. 

 

Observations:  1. Memoisation is not only applicable to recursive functions. You can use it for non‐

recursive processing too, especially if the calculation takes a long time.  2. Factorial() can only benefit  from memorization  if we call  factorial() multiple 

times  for different  inputs.  i.e.  if we  stop  the example after call one,  there  is no  benefit gained as fac(3), fac(2), fac(1) and fac(0) are calculated and used  once only. 

 

Point (2) above should give you a hint that memorization will help functions like Fibonacci()  greatly as multiple redundant calculations are performed even in the same Fibonacci call. 

 

Your task  is to utilize memorization technique for the recursive Fibonacci() function. Note  that in the template code, we gave the original Fibonacci function with a small addition. There  is a global variable "call_count" which will be incremented every time the Fibonacci function  is called. This  is  just a simple way  for us to check whether your memoization  is  implemented 

3 | P a g e    

properly. For actual usage outside of this task, you can just remove this global variable safely. In  the original recursive Fibonacci() function: 

Fibonacci 20 30 40  Result  6765 832040 102334155 

Call Count  13529  1664079  204668309   

With memoization, the call count reduces drastically: 

Fibonacci  20  30  40  Result  6765  832040  102334155 

Call Count  20  30  40   

Note  that  the  results  reported are  from  independent  single Fibonacci()  function  call, not  consecutive ones. Once  the memorization  is properly  implemented, you  should  find  that  the  recursive function's execution speed is comparable to the iterative version! 

 

Task 2: Pretty Tiles [6 marks] 

Nemo has  just moved  in  to his new HDB  flat! He hired you as  the  interior designer with  the  main focus to tile his floor with beautiful patterns. Being a typical choosy person, Nemo asked  you to show him all possible designs so that he can decide on the best pattern. 

To simplify the problem,  let us consider only one strip of the floor area, represented by a 1D  character  string. Each  type of  tile pattern  is  represented by a character and has a  size  (how  many units of floor area it can cover). For example, we have 4 different tiles below: 

Index  0  1  2  3  Pattern  '*'  '%'  '#'  '$'  Size  3  1  2  2 

 

For example, the tile pattern 0 is a size 3 tile with '*', i.e. "***".  

If we use the above tile set to fill a floor area of 3 units, the possible patterns are: 

***  %%%  %##  %$$  ##%  $$% 

One tile 0 Three tile 1  One tile 1 and One tile 2  etc….. 

Note that a valid pattern must fully filled the floor (i.e. has 3 characters in this example). 

4 | P a g e    

Write a recursive function to generate all the possible design patterns. The recursive function  has the following header: 

void tile_floor(char floor[], int loc,                   struct Tile tileArray[], int numTiles)  floor[] is the character array representing the floor. Should be used as a string.  loc is the current location (index) to place a tile on.  tileArrray[] is an array of Tile structure (see below).  numTiles is the number of tiles in the tileArray  This function print all possible design patterns to fully fill the floor from loc onwards. 

 

We use a Tile structure to capture the information about a tile: 

struct Tile {      int size;      char pattern;  }; 

 

In addition, we have written the following helper functions for you: 

void put_tile(char floor[], int loc, struct Tile* tilePtr);  Fill in a tile on the floor at location loc. The tile information is passed in via the structure  pointer tilePtr. 

 

void remove_tile(char floor[], int loc, struct Tile* tilePtr);  Remove a tile on the floor at location loc. The tile information is passed in via the structure  pointer tilePtr. 

 

void remove_tile(char floor[], int loc, struct Tile* tilePtr);  Remove a tile on the floor at location loc. The tile information is passed in via the structure  pointer tilePtr. 

 

void init_floor(char floor[], int size); Empty the floor of any tile. In this program, we represent empty floor locations as '‐'. 

 

Hints: 

1. Think of the 3 key ingredients of recursive solution!  2. The solution needs only ~10 lines of code.  3. In this case, there can be a loop in the recursive function.  4. Don’t forget to make use of the provided helper functions. 

5 | P a g e    

Two sample output for floor length of 3 and 5, named as "sample_length_3.txt" and  "sample_length_5.txt" are provided for your reference.  Ensure your output is exactly the same as the sample output (including the sequence of  designs). 

 

Task 3: There is no point in sorting! [6 marks] 

 

Sorting algorithm can be easily expanded to any other comparable items. As long as there is a  way to say "item A is before item B", then a collection of such items can be sorted.  

In this task, we will try to sort an array of 2D points, i.e. reusing the Point structure covered in  lecture 2: 

struct Point {      int X, Y;  }; 

 

The ordering we want to achieve is "sort by X‐ coordinate, tie breaks by Y‐coordinate". Below is  an example of sorted array of points: 

Point Index  0  1  2  3  4  X  5  11  11  11  13  Y  73  19  34  68  5 

 

Note the interesting example of Point 1, 2 and 3: Since they have the same X‐ coordinates,  these points are ordered by the Y coordinate ("Tie breaks by Y‐coordinate"). 

You can implement any of the 3 sorting algorithms taught in this course: Insertion, Selection or  Bubble Sort. However, the restriction is that you can only call sort() ONCE to achieve the final  result. 

Note: The auto‐grader can only confirm the sorting order (i.e. is it sorted properly), but not the  further requirements (sorting algorithm, cannot use sort more than once etc). Hence, the  further requirements will be manually verified after submission deadline. 

 

 

 

6 | P a g e    

Task 4: Tada! Magic Sort. [6 marks] 

This task looks at a very interesting sorting that works on a 2D array. Don’t panic! The core logic  is already written in the magic_sort() function. You only need to provide two helper  functions that are quite straightforward to write: 

 

void bidirection_bbsort( int a[], int N, bool ascending);  Adapt the given bubble sort function so that it can sort either in ascending order (from  small item to large) or descending order (from large item to small). Note that the bubble  sort function can already sort in ascending order.    The parameter ascending indicates the sorting order:  true: ascending order OR  false: descending order 

 

void column_sort( int matrix[][MAXCOL], int col); Sort the col column in the matrix[][] in ascending order.   Restriction: Find a way to reuse the bidirection_bbsort(), i.e. you do not need to  write the sorting logic at all. 

 

Once the functions are implemented, the magic_sort() function should have the following  output: 

 2  5  9 13  15 10  1  0   3  7 11 14  12  8  6  4 

   0  1  2  3    7  6  4  5    8  9 11 10   15 14 12 13  

  2  5  1  0   3  7  6  4  12  8  9 13  15 10 11 14 

   0  1  2  3    7  6  5  4    8  9 10 11   15 14 13 12 

 0  1  2  5   7  6  4  3   8  9 12 13  15 14 11 10 

   

 

See anything special for the final output? (hint: the matrix is now sorted in a specific way… ) 

For your exploration: Try placing other values in the original matrix in main() and verify that  the "magic sort" always work. This sorting algorithm is known as "shear sort".