Problem 1 Order the following list of functions by the bigOh notation. Group together (for example, by underlining) those functions that are bigTheta of one another. 4\" n3 n2logn 4'09\" W 22" [m \"0.01 1/71 4n3/2 3n0'5 5n [211109sz 2\" nlog4n Gnlogn 2100 loglogn logzn 2W\" Hint: When in doubt about two functions f (n) and g(n), consider log f (n) and log g(n) or 21%\") and 29(n)_ Problem 2 Matrix multiplication. Write pseudocode for computing 0 = A X B, where A, B, C are matrices of integers of size n X m, m X k, and n x k respectively. Analyze the running time of your algorithm. Problem 3 You are given a tree represented by the following data structure. Nodes have three elds: element, left-child, and right-child. The element is a integer. Write a procedure (pseudocode) with input parameter the location of the root node (or pointer to the root node), and that computes the average value of the elements in the tree. However, do not use recursion. Use a stack instead. Analyze the running time of your algorithm. As proven in CS 331, stack operations are 0(1). Problem 4 Give pseudocode for the following problem: given an array A[1. . .71] containing the numbers 1, 2, . . . ,n and representing a permutation, modify A to represent the next lexicographic permutation. Analyse running time (which should not exceed O(n)) and argue correctness (why the output is lexicographically bigger than the input? why other permutations lexicographically bigger than the input are bigger than the output?)