Design and Analysis of Algorithms

Week 14 Lecture 24

Dr. Husnain Mansoor Ali

 Recap
• What is the running time of classical large
Design and Analysis of Algorithms

number multiplication?

• What is core-multiplication?

• What is the running time of Karatsuba algorithm

for large number multiplication?

2
 Exponentiation to an Integer Power
• The case of an integer exponent would seem to
Design and Analysis of Algorithms

be trivial:
– to calculate a^n, just multiply a by itself n times.
– We are interested in the number of multiplications
required, in this case it is n-1, so this is a O(n)
algorithm.

• Notice that, while 2 * 2 is easier for you to do

than 43046721 * 81, on a computer all
multiplications take the same amount of time
9
 Exponentiation to an Integer Power
Design and Analysis of Algorithms

Repeated
Squaring

10
 Exponentiation to an Integer Power
Design and Analysis of Algorithms

11
 Exponentiation to an Integer Power
Design and Analysis of Algorithms

Repeated squaring

12
 Exponentiation to an Integer Power
• Time complexity of exponentiation using
Design and Analysis of Algorithms

successive square is O (log n)

13
 Matrix multiplication
• How fast can one multiply two n×n matrices?
Design and Analysis of Algorithms

– Standard multiplication: O(n^3) operations.

– Strassen’s algorithm: O(n^2.81) operations.

– Coppersmith and Winograd’s algorithm: O(n^2.38)

operations.

14
 Strassen’s Matrix Multiplication
• The Strassen’s method of matrix multiplication is
Design and Analysis of Algorithms

a typical divide and conquer algorithm.

15
 Strassen’s Matrix Multiplication
Design and Analysis of Algorithms

16
 Strassen’s Matrix Multiplication
Design and Analysis of Algorithms

17
 Strassen’s Matrix Multiplication
Design and Analysis of Algorithms

18
 Strassen’s Matrix Multiplication
Design and Analysis of Algorithms

19
 Strassen’s Matrix Multiplication
Design and Analysis of Algorithms

20
 Strassen’s Matrix Multiplication
Design and Analysis of Algorithms

21
 Sources used: Books
• Introduction to algorithms
Design and Analysis of Algorithms

– Thomas H. Cormen, Charles E. Leiserson, Ronald L.

Rivest, Clifford Stein

• Introduction to Algorithms
– Jon Kleinberg, Eva Tardos

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

22
 Sources used: Books
• Algorithms and Data Structures
Design and Analysis of Algorithms

– Kurt Mehlhorn and Peter Sanders

• Analysis of Computer Algorithms

– Aho, Hopcroft, and Ullman

• Art of Computer Programming

– Donald E. Knuth

23
 Sources used: Online Links
• Algorithms: Design and Analysis, Part 1
Design and Analysis of Algorithms

– https://www.coursera.org/course/algo
• Algorithms: Design and Analysis, Part 2
– https://www.coursera.org/course/algo2
• Lecture Slides for Algorithm Design
– http://www.cs.princeton.edu/~wayne/kleinberg-
tardos/
• Course Notes - CS 161 - Design and Analysis of
Algorithms
– http://www.ics.uci.edu/~goodrich/teach/cs161/note
s/ 24
 Sources used: Online Links
• Linear Programming
Design and Analysis of Algorithms

– http://www.cs.yale.edu/homes/aspnes/pinewiki/Line
arProgramming.html

25
 Design and Analysis of Algorithms
Sources used:

26