Matrix Multiplication

1) Write a C++ program that creates matrices of different sizes and sparsity. Assume the matrices to be square and use them to compare the time to multiply two matrices using: - Standard Matrix Multiplication O(n3) -Strassen's Method. -Sparse Matrix Multiplication. Exercise 1. Change the matrix sizes as follows 20, 30, 100, 500, 1000 keeping sparsity=0 Exercise 2. For matrix size =20 change sparsity=0, 10, 50, 80 Exercise 3. For matrix size =500 change sparsity=0, 10, 50, 80 For each exercise test all the three methods, on the set of matrices and show your results as histograms. 2) Compare the performance of the three methods on non-square matrices (unequal number of rows and columns) Exercise 4. For matrix size =100X20, 100X25, 100X50, 100X80 sparsity=0 Exercise 5. For matrix size =100X20, 100X25, 100X50, 100X80 sparsity=80 Develop and implement an algorithm that can take in the matrix dimensions and sparsity and identify the best method to use. Test your algorithm for a subset of matrices from exercises 1-5. Remember that unlike the other exercises the two matrices can be different types (i.e. one sparse and the other not sparse). Explain your algorithm clearly in english and as a pseudocode. Provide some results of your algorithms and discuss the results in 1-2 paragraphs ---------------------------------------------------------------------------------------------------------------------------------------------------------------------- Balanced Binary Trees 1. Use BTrees.cpp. to test the performance of AVL and Red-Black trees. Exercise 1. Test the time to input new elements (a) For 3 different permuted orderings (b) For a sorted input Exercise 2. Using the tree is created in Exercise 1, search the tree to test whether the element exists (a) For 3 different permuted orderings (b) For a sorted input Execute the set of Exercise 1 and 2 for input sizes 10,000, 100,000, 1000,000. Each size corresponds to one run of exercise 1+2. 2. Change the code of the AVL tree such that the balance factor can be at most h, instead of 1. Rerun the exercises in part 1 to compare the timings for h=2,5,10,100 3. Write 1-2 paragraphs discussing the results you obtained and the inferences that you can make from them—such as when is it better to use an AVL tree rather than a R-B tree and vice-versa. How does the balance factor affect the performance of an AVL tree