WEEK #8

Assignment #2 was due the Monday of this week and all of the questions were challenging, with some more than others. Yet the first question seemed much harder than the rest which was surprising since it was postponed from the previous assignment to this one. The topics in this week's lectures is a build-up on last week's introduction to program-correctness. Loop invariants were explained in more depth and it is seen that they are key for determining the termination of a loop or in other words getting closer to the main goal after each iteration. The problems became more challenging with trickier loop conditions and double/nested loops. No problem set for this Friday and no assignment for the coming Monday so some time to sit down and review for next Friday's term test.

WEEK #7

The week started with a different professor than usual and he began the topic of program-correctness which was reviewed and continued in the following lectures by Professor Danny Heap. This procedure seems very obvious at the moment for the reason that it is being performed on functions that we know will terminate and return the expected result, however it is probably one of the most important aspects of software/algorithm testing. One of the main problems with functions and programs is that they would go into an infinite loop and which could solved by checking them with program-correctness methods. Problem Set #4 was also postponed to the following Monday which is a relief from the heavy workload of the past couple of weeks.

WEEK #6

Time-complexity of search/sort algorithms were revisited this week with an analysis of the merge-sort algorithm. However, in this case we had to deal with powers of 2 within the derived time-complexity function which needed a different process in order to prove that the function will work for any natural number n. We had to first start by proving for numbers that are powers of two and then prove that the function is monotonic which will result in a proof that the function holds for numbers between powers of 2. This method is very flexible since it can be used for functions that contain powers of any number which is very common in divide-and-conquer algorithms.

WEEK #5

We started learning about the closed-form of recursive functions. This seems like a very useful tool (and probably is) since it transforms a quite tedious type of function into a more familiar and simpler one. This process will come in handy when testing recursive functions or needing a less memory-intensive function that will achieve the same or at least a very similar result. For example, in order to find a specific Fibonacci number, one had to find all the previous Fibonacci numbers in order to come up with the original number that was needed or one could have used a computer program which would do the same process a little faster. With a closed-form of the Fibonacci function, to find a specific number in the sequence, one just has to plug-in and do a couple simple mathematical operations.