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.

WEEK #4

The first lecture of week 4 was about proving recursive functions which was accompanied by a proof of the Fibonacci Sequence. This was interesting because the Fibonacci sequence had appeared in so many courses before (and I'm guessing there is more to come) yet a formal proof was never given. In the second lecture of the week we talked more about recursive functions as well as their time complexities. We also started looking at the Recursive Binary Search function and analyzed its time complexity. I think that the approximate time complexity for the recBinSearch(x,A,b,e) is :
T(n) = (e-b)*4 + T(1)

WEEK #3

We started the week with the round-robin problem which was confusing for me during the lecture and I think I still do not fully get it, probably because I haven't taken the time to look over it again. When it's actually proven it makes sense and might look easy but it is quite the opposite when you start from scratch, which is probably the case for many other problems as well. It was also interesting to see how one principle linked to another, where PWO => PSI => PCI => PWO. It was nice to see some problems similar to those in 165 when doing "Bases larger than zero". Problem set #2 was straight-forward with a similar structure to that of problem set #1 with the first part like a problem done in lectures and the second part being a follow-up of the first yet without resemblance to lecture problems.