mbhushan/dpv

Algorithms - S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani

Solution Manual for Algorithms - S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani

Motivation:

• Take notes from the chapters.
• solve chapter problems.
• Solution for end of chapter exercises.
• Code problems in python-3
• Have loads of fun along the way! :)

dpv's Issues

1.7

Although I am not completely sure, but the answer should be O(mn) because the loop is called m times but multiplying by 2 shifts the digits of the other number n so it should be O(mn).

A quick check would be to see if m==1 or n==1. O(mn) fits the bill.

There is no such problem with 0.4 .

The complexity should be
sum of O(r^2) log n times (not n times of course) where r is length of number in the matrix in every step. So r varies as (r1, 2r1, 2^2r1, ...) .
We can see that O(r^2) < O(n^2)
Hence we can write the answer
so it gives us the second last option.
For the last option we must do the entire sum which
comes out to be the given ans.

0.1 d

Shouldn't it be both are true?