|
#2
July 22nd, 2016, 01:05 PM
| |||
| |||
| Re: IIT Bombay Algorithms
Ok, here I am providing you the Lecture Notes for Algorithm Analysis and Design of B.Tech Computer Science and Engineering of IITB. Lecture Notes for Algorithm Analysis and Design Chapter 1 Model and Analysis When we make a claim like Algorithm A has running time O(n2 log n), we have an underlying computational model where this statement is valid. It may not be true if we change the model. Before we formalize the notion of a computational model, let us consider the example of computing Fibonacci numbers. 1.1 Computing Fibonacci numbers Method 2 Observe that we only need the last two terms of the series to compute the new term. So by applying the idea of dynamic programming we gradually compute the Fn starting with F0 = 0 and F1 = 1. This takes time that is proportional to approximately n additions where each addition involves adding (increasingly large) numbers. The size of F⌈n/2⌉ is about n/2 bits so the last n/2 computations are going to take (n) steps 1 culminating in an O(n2) algorithm. Since the n-th Fibonacci number is at most n bits, it is reasonable to look for a faster algorithm. Exercise 1.2 Show that the cost of computing An is O(M(n|x|) where A is a 2 × 2 matrix and the maximum length of any entry is |x|. So the running time of computing Fn using Method 3 is dependent on the multipli- cation algorithm. Well, multiplication is multiplication - what can we do about it? Before that let us summarize what we know about it. Multiplying two n digit numbers using the add-and-shift method takes O(n2) steps where each step involves multiplying two single digits (bits in the case of binary representation), and generat- ing and managing carries. For binary representation this takes O(n) for multiplying with each bit and finally n shifted summands are added - the whole process takes O(n2) steps. Using such a method of multiplication implies that we cannot do better than (n2) steps to compute Fn. For any significant (asymptotically better) improvement, we must find a way to multiply faster.    For complete notes here is the attachment Contact- Indian Institute of Technology Bombay Powai Mumbai, Maharashtra 400076 |