Cs6515 - Algorithms- Exam 1 Complete Questions And Solutions

Consider ω_16. For what power k (ω_16)^-1 = ω_16^k? In other words, for what k is ω_16 * (ω_16)^k = 1? {Ans: k == 15 This is because (ω_16)^16 == (ω_16)^0}1.) what is the product of the roots of unity? 2.) What about the sum? 3.) What is the sum of Aeven? 4.) what is the sum of Aodd? {Ans: 1.) if it is even, then it is == 1 if it is odd, then it is == -1 2.) The sum is == 0. This is because (ω_n)^0 == 1 and (ω_n)^(n/2) == -1. These cancel each other out. So if you go through the whole sequence.. it eventually becomes 0. 3.) (n/2) * 1 4.) (n/2) * -1}WHat is the algorithm for merge sort? And what is its running time? {Ans: }what do you need to remember when it comes to lI subsequence? {Ans: - you are work with one array - you fill everything out with 1s first based on an array of same size - the value is compared as well as the index is compared that is why (a_}Why is omega squared? {Ans: }- What numbers can be used when