ANONYMOUS wrote:

Hi there! I have a few questions after watching the lecture today.

Question 9, how is the time complexity for the brute force O(n^(2k)) does it come from us having a total of n^2 total combinations and choosing subarrays is Subarray^k ? Also, I didn't really understand when it was mentioned an easier to prove time complexity of O(2^n)

This comes from that we can define a set of k subarrays as a set of pairs of start and end indices {(l1, r1), (l2, r2), ..., (lk, rk)}. Each index in this representation has O(N) options, and there are 2k of them, so that gives O(N^(2k)) representations we can enumerate. As part of our enumeration this would require us to discard invalid solutions, however, such as if one of the ranges ends before it starts, or if two ranges overlap. O(N^(2k)) is just the number of representable options, and we would then need to check if it represents a valid set of disjoint subarrays. The complexity of doing this check makes the algorithm a little less naive and fiddlier to think about, but we can just compare all pairs of ranges and test if they intersect. So the overall time complexity of this approach would be O(N^(2k) k^2).

I consider the O(2^N) one representation easier to reason about because it is simply each element in the list either being included or not, and then you just need to check if that subset can be covered by at most k subarrays by scanning over and seeing how many contiguous blocks are formed in O(N) for O(2^N N) overall.

The reason I always tell people to start with a naive or brute force is because it is good to start with the logically simplest, most obviously correct algorithm. This ensures that we actually understand the problem before we start trying to do clever things to solve it faster. Therefore I would consider the second of these options preferable as it is more obvious and simpler to prove correct and prove its complexity, in my opinion. There isn't really an objective measure of how simple something is to explain, though.

There were a few questions that were not answered in the lecture, (e.g. Question 9 efficient method, Question 5 efficient method) will there be a sample answer so that we can see how we should answer ?

I believe that students will have better outcomes if not (immediately, at least) given sample answers. My experience is that many students, intentionally or not, start trying to imitate the sample answers rather than thinking about how to actually answer the problem. For this reason, if I do choose to release sample answers, it will not be until after there has been ample opportunity for students to have properly thought about the questions. For example I am quite confident that Max and myself would give very different looking answers to most of these questions (even if we found the same algorithm), but that both of our answers would easily qualify for full marks.

Given that the skills we want you to develop in this unit are all about the ability to solve problems you have not seen before, the best thing we can do for you is give you problems you have not seen before and not give you the solutions. In the lecture I deliberately did not give example written answers or attempt to answer the written questions directly, but rather discussed the content of the questions and how we thought about them. This was a very deliberate decision.

So at this time it is intentional that you do not have answers for everything, but you should have everything you need to be able to think about these problems and get the benefit from studying them. If I choose to release sample answers at a later date it will basically be as a rough rubric so students can self-assess their answers, rather than using the sample answers as a guide for how to answer.

Cheers, Gozz