CSE 3100 Systems Programming Fall 2018Lab #4Welcome to Lab 4! This lab assignment is due 36 hours after your lab session starts. For example,if your lab session starts at 8am on Friday, the assignment is due at 8pm on Saturday. Read each questioncarefully before beginning work. Start by executing git pull inside your Git repository on the virtualmachine. This will create a directory called lab4 which includes code provided for this lab as well as aMakefile. Do all your work inside the lab4 directory. Remember to add, commit, and push when youcomplete your work. Add ONLY *.c to the git repo. Do not add .o files, executables, or profiling outputfiles.Part 1: Cache-friendly matrix multiplication. Given two n × n matrices A and B, their product isdefined as the n × n matrix C whose elements areci,j=n−1Xk=0aikbkjComputing the elements of C can be done by using the above formula directly within three nested forloops (over i, j, and k). This yields a matrix multiplication algorithm that has O(n3) asymptotic runningtime. Note that the three loops can be arbitrarily reordered without affecting the correctness or the asymp-totic running time of the algorithm. However, different loop orders can have substantial impact on cacheperformance, and hence on the actual runnng time. Your task is to complete the implementation of themultiply() function in matmult.c. Use the time command and the cachegrind tool of valgrind to profilethe cache performance of your code (on large enough matrices) to find a loop order that results in fewestcache misses and fastest running time.Running the matmult executable takes two command line parameters: the matrix dimension n and thenumber of times the matrix multiplications should be repeated. Upon completing the implementation of themultiply function, the output from the program should look as in the following listing:$ ./matmult 100 1trace of AxB: 2470.000000trace of BxA: 2470.000000$ ./matmult 200 1trace of AxB: 9958.000000trace of BxA: 9958.000000$ ./matmult 300 1trace of AxB: 22338.000000trace of BxA: 22338.000000$ ./matmult 400 1trace of AxB: 39791.000000trace of BxA: 39791.000000$ ./matmult 500 1trace of AxB: 62489.000000trace of BxA: 62489.000000Note that the main function initializes the two matrices to be multiplied using a random pattern of 0’s and1’s, so overflow should not be a concern when performing the matrix multiplication.Part 2: Cycle length. A popular interview question is to describe an algorithm for testing if a singlylinked list contains a cycle. Note that you cannot simply set a pointer to the first node of the list andthen repeatedly advance it using “next” links while checking whether you’ve reached the end of the list orreturned to the first node. If the list contains a cycle not including the first node (as in the diagram below)1this algorithm would loop forever!An elegant solution that uses only a constant amount of memory besides the nodes of the list is Floyd’s“tortoise and hare” algorithm. In this algorithm two pointer variables are used, both initially pointing tothe first node of the list. In each iteration, one of the pointers (the “hare”) is advanced by two nodes (if thisis not possible because of a null pointer, we have found the end of the list and therefore the list is acyclic).The other pointer (the “tortoise”) is advanced by only one node in each iteration. If the tortoise and thehare point to the same node, then the list is cyclic, otherwise, the above steps are repeated.Your task is to implement the function cycle length() in the provided C program cycle.c, withoutmodifying the main function. This function receives as argument a pointer to the head node of a singly-linked list and returns the number of nodes in the cycle, if a cycle exists, and 0 otherwise. You may onlyuse a constant amount of additional memory in cycle length(). After you have implemented this function,compiling and running the program will call your function against a number of predefined linked lists, andshould print the following output:% ./cycleCycle_length: 0Cycle_length: 7Cycle_length: 4Cycle_length: 1Cycle_length: 0Cycle_length: