Responses to questions of February 12, 2020 ***************************************************************************** QUESTION (a) In a maximum subarray problem what is the answer if the array contains all non-negative numbers? (b) What's the run time difference in the subarray if the maximum subararray is already sorted? ANSWER (a) This is an excellent exam question---think about it! (b) If we add the condition that some numbers may be negative, this is also an excellent exam question. Run time for (a) O(1) for determining the endpoints, but O(n) to produce the total (why?). Run time for (b) O(lg n)---how? ***************************************************************************** QUESTION For the maximum subarray problem could you use a modified version of the algorithm you gave us in class if the subarray must be a given size n? As in, what if you were looking for the largest subarray of size 3. If so, what would be the modified algorithm. ANSWER Another good exam question. Just use a linear scan, "sliding window" approach. You would be calculating (using the size 3 example) of A[1..3], A[2..4], ... A[i-2..i] ... A[n-2..n] and choose the max. ***************************************************************************** QUESTION When doing divide and conquer, do subproblems always have the same complexity as the parent problem? For example, will a subproblem of a O(n^2) problem always be O(n^2) itself? ANSWER Whenever the subproblems are being solved by the same algorithm (i.e. a recursive call), then the time complexity function is the same T() with the base case normally being constant time. ***************************************************************************** QUESTION Is there a better alternative approach besides the divide and conquer and the the incremental approach that we will learn later in the semester or outside of this class? ANSWER For sequential processing environments, the incremental and divide and conquer approaches will carry us a long way. The challenge comes from ensuring that unnecessary computation is avoided. Parallel processing requires a different mindset and is outside the scope of this course. While one might think that divide and conquer is inherently the way to go with parallel processor (each core handles a different subproblem), remember that the actual processing overhead of the divide and combine steps may not be obviously parallelizable. ***************************************************************************** QUESTION What are the distinctions between the recurrence tree method vs the master theorem, given that the master theorem could be derived from the recurrence tree method? ANSWER As noted with our T(n) = T(n-1) + Theta(n) example, the recursion tree is a more general tool for solving recurrences as it can be used for this problem, but it does not fit the conditions of the master theorem. ***************************************************************************** QUESTION If we are more concerned about correctiveness why would we want to work with iteration when recursion is easier to write? ANSWER Sometimes the recursive definition leads to excessive redundant computation that must be avoided to have a practical solution. When every nanosecond counts, avoiding the overhead of function calls is a good strategy. However, if the asymptotic speed is sufficient, then recursion is just fine (so long as the redundant computation issue is avoided). We will be learning about techniques for avoiding redundant computation when we discuss dynamic programming algorithms. ***************************************************************************** QUESTION When will brute force ever be necessary to use other than the other algorithms? ANSWER Sometimes it's not obvious how to solve the problem other than brute force. For example The Traveling Salesman problem is a famous problem for which there is no other way known for computing the optimal answer other than by brute force. ***************************************************************************** QUESTION After developing an algorithm that you find to be too slow or not quite correct, how do you go about rethinking your solution? Does it help to step away? Start with the algorithm you have then tweak it? Etc. ANSWER It is almost invariably helpful to set something aside for 24 hours before going back to critique it. It's just how our minds work. With respect to efficiency analysis, you want to focus on identifying unnecessary computation. ***************************************************************************** QUESTION What is the worst case run time for bogosort? ANSWER I believe this is what I labeled as "stupid sort" in class! O(n!) ***************************************************************************** QUESTION What algorithms should we be familiar with before applying for a programming related job? ANSWER The flippant response is --- "as many as possible". If you are looking at a specific application area, then the classic algorithms of that area are a good place to start. Otherwise, folks will be looking to see if you have a solid background in computer science and will likely ask about problems similar and in some cases identical to the types of problems that which are presented in our curriculum. ***************************************************************************** QUESTION Generically: How does topic X,Y, or Z, relate the real world. ANSWER Either read or re-read http://www.cs.ecu.edu/~rws/realworld.txt Sometimes, a specific answer cannot be given. For maximum subarray, imagine any business with historical data about sales/costs/etc. Such data could be used to streamline business processes to engage in particular activities/promotions when they have been historically most successful. For more abstract topics the answer is less clear, but please understand that a primary (the primary?) purpose of this class is to help you develop a mindset of analysis that will carry forward in all your professional activities. To the extent that this mindset some day helps you to find a great solution to a hard problem (or at least a better solution than what your company currently had), then all of the topics where you were developing this mindset are relevant to the real world.