In the previous post I described the first week of "Data Structures and Algorithms" course on coursera. In this post I am going to describe the second week.
What's has been covered
Authors started the second week with Fibonacci numbers. 15th century Italian mathematician Leonardo Fibonacci found this sequence of numbers where every number in it is the sum of the two preceding ones. They presented two versions of Fibonacci numbers algorithm: exponential (recursive) and polynomial.
They introduced a couple of very important concepts, such as types of algorithms:
- Divide and Conquer
And levels of algorithm's design:
Then they continued with the greatest common divisor algorithms: naive GCD and Euclidian algorithm. Also they covered Big-O notation and how algorithm's runtime depends on input. There were few quizzes (nothing special) and after that I've started working on the assignment.
There are number of problems that has to be solved. The first three problems are very simple and covered in lectures. The other four were more complex and were not covered in lectures.
- Find Fibonacci number with given index - the classic approach to this problem is to use recursion, the problem is that the recursive algo is not as effective as other implementations, it simply won't pass tests. So it is required to come up with iterative version.
- Find last digit of Fibonacci number with given index - the trick is to store only the last digit of the number.
- Greatest common divisor - Euclidian algorithm - a very straightforward, but still useful algo.
- Least common multiple of two numbers - also, very common algo, that's not hard to implement, just check Least common multiple on wiki.
- Find Fibonacci number modulo m with given index - this one is more advanced, it requires understanding of Pisano period. But still, it is very simple once you understand how you can solve it in the way that you don't need to iterate through millions of numbers.
- Last digit of sum of Fibonacci numbers - very similar to the previous problem, you have to know about Pisano period for modulo 10 and apply it accordingly.
- Partial sum of Fibonacci numbers - a more advanced version of the previous problem.
Threre are couple of links that I have used to solve this week probles, if you don't want to get a complete solution but just looking for more info regarding outlined problems, you can check these:
- Big-O complexities of common algorithms
- Fibonacci visualizer
- Pisano period
- Chinese remainder theorem
- k-Fibonacci sequences modulo m
- Fast Computation of Pisano Period
- Compute the Period, Rank, and Order of F(mod m)
- The Fibonacci Sequence Modulo m
- The period of F(mod m) for 1 < m < 2002
- Last digits of Fibonacci numbers
In this post I have described the second week of "Data Structures and Algorithms" course on Coursera. This week wasn't hard, I hope next one will be more challenging. I like that weekly assignment starts with easier problems and then you get more complex ones. In the next post I will cover the third week.