[SOLVED] CSE102 Assignment 8-Pointers, recursions and an interesting mathematical conjecture

In this assignment, you will experiment with pointers, recursions and an interesting mathematical conjecture, namely Collatz.

Collatz conjecture has not been proven yet even though it is seemingly a simple problem. Consider the following function:

𝑓(𝑥)= {3𝑥+1 𝑖𝑓𝑥𝑖𝑠𝑜𝑑𝑑 𝑥/2 𝑖𝑓 𝑥 𝑖𝑠 𝑒𝑣𝑒𝑛

Starting with an integer 𝑥0 the sequence 𝑥1 = 𝑓( 𝑥0), 𝑥2 = 𝑓( 𝑥1), … tends end up with a loop 4, 2, 1, 4, 2, 1… Conjecture says that any starting integer should send this sequence to the same loop. (See https://www.youtube.com/watch?v=094y1Z2wpJg for an overview of this conjecture).

Towards the analysis of this conjecture, you are asked to write a few C functions:

1. (25 pts) Write a recursive function to generate and return the sequence.void generate_sequence (int xs, int currentlen, int seqlen, int *seq)

   Where xs is the first element of the sequence, seqlen is the length of the sequence, currentlen is the length of the sequence in the time of the function called, *seq is the array of the sequence.

2. (30 pts) Write a recursive function such that given any function and a starting integer check if the sequence ends up in a loop.The first input is the function for which the sequence will be generated (fill its parameters declared with “?” above), starting from the first integer xs with a length of seqlen. The last two arguments will return the loop and its length. If no loop is found, the function will not update *loop array and return 0 with looplen variable.

   Note that the loop’s length can be n/2 at most and 2 at least, you should search for a loop with every possible length (until you find one) in descending order.

void check_loop_iterative(void (*f)(?), int xs, int seqlen, int *loop,

int *looplen)

CSE102 – Spring 2022 Assignment #8

3. (20 pts) To be used in the previous function, you are asked to write a function to check if a given sequence of numbers has a loop in it.int has_loop(int *arr, int n, int looplen, int *ls, int *le)

   Thefunctionwillreceiveasequencestartingfromarr[0]andendingatarr[n-1]. Itwill check if there are any loops with a length of looplen. The first occurrence of the loop will be output with parameters ls and le.

   This is not a void function, it will return 1 if a loop exists, 0 otherwise.

   For example,

   {15, 7, 4, 2, 1, 4, 2, 1}

   has a loop starting at arr[2] and ending at ar[4]. In this case ls=2 and le=4.

4. (25 pts) Write another recursive function that calculates the histogram of the first digits of thesequence generated by a given function.

   As before the first three parameters are for the generation of the sequence. h is the histogram of the first digits of the numbers that appear in the sequence. The size of this array will be 9 (you will ignore digit 0).

   For the following sequence:

   {340, 170, 85, 256, 128, 64, 32, 16, 8, 4, 2, 1, 4, 2, 1}

   The first digits of each integer:

   {3, 1, 8, 2, 1, 6, 3, 1, 8, 4, 2, 1, 4, 2, 1}

   The resulting histogram (*h) would be: {5,3,2,2,0,1,0,2,0}

   meaning that there are 0 numbers starting with digit 5 while there is only one number starting with digit 6.

   Every time this function is being called; it should find the total numbers of integers starting with digit.

void hist_of_firstdigits(void (*f)(?), int xs, int seqlen, int *h, int

digit)

CSE102 – Spring 2022 Assignment #8

Program flow:

• ❖  In main, take the first element and the size of the sequence as inputs from the user (assume that the inputs will be proper, i.e., positive integers).
• ❖  In main, call the check_loop_iterative function.
• ❖  In check_loop_iterative function, generate & print the sequence (print it only once). Also, checkif the sequence has a loop. If there is a loop, print its size and the indexes of its first occurrence.

  Do not print the loop itself in this function.

• ❖  In main, print the loop (if any). If there is no loop, print this information.
• ❖  In main, call the hist_of_firstdigits function.
• ❖  Print the histogram array in main.General Rules:
  • Obey the style guidelines.
  • Do not change the provided function prototypes (you will not get any credits).
  • The program must be developed on Ubuntu using GCC compiler (version provided in class),compilation problems due to the use of another OS or compiler is your responsibility (you will

    not get any credits).

  • Your program should work as expected. Do not expect partial credit if your code works only insome cases but not in all cases as expected.
  • Do not use any libraries other than stdio.h, stdlib.h and util.h. You can add new functions but donot change the structure of the functions given above. Parse the parameters by using pointers

    as shown above.

  • Use malloc/calloc functions from stdlib library, make sure your program won’t end up with asegmentation error.
  • Add comments to your code.
  • You can ask your questions about the homework by using the assignment post on Teams.Handing in your work:
    • Hand in your work using the appropriate class Teams assignment site.
    • No late submissions will be accepted.
    • Please pack your solution directory in the following way (assuming a student with number20180000001 andnameXYZissubmitting):

o A directory named 20180000001_X_Z is created
o Allthesolutionsfilesalongwithamakefilearecreatedaspartoftheassignment.For

example:

o Packthisdirectoryintoazipfilenamed20180000001_X_Z.zip
o WhenunpackedasaboveinUbuntu(versionprovidedinclass)itshouldallowexecuting

the following commands in a shell:

• ▪  “$makeclean”removeseverythingexceptmakefile,sourcecode(.cand.h)andother resource files (if any) – all compiling results and intermediate files should

  be removed.

• ▪  “$makecompile”shouldcompilethecode.
• ▪  “$makerun”shouldrunthecodealongwithanyparametersneeded.

CSE102 – Spring 2022 Assignment #8

Expected outputs (first two rows are inputs, the rest is output only)