Stanford Algorithm Specialization Solutions

Here is a record of my solutions to the Stanford Algorithm Specialization on Coursera. All codes are written in Python. The contents are the same as those on my GitHub:

Course 1: Divide and Conquer, Sorting and Searching, and Randomized Algorithms

Week 1: Quiz

Question 1
Question 2
Question 3
Question 4
Question 5

Week 1: Programming Assignment

In this programming assignment you will implement one or more of the integer multiplication algorithms described in lecture.

To get the most out of this assignment, your program should restrict itself to multiplying only pairs of single-digit numbers. You can implement the grade-school algorithm if you want, but to get the most out of the assignment you’ll want to implement recursive integer multiplication and/or Karatsuba’s algorithm.

So: what’s the product of the following two 64-digit numbers?

3141592653589793238462643383279502884197169399375105820974944592

2718281828459045235360287471352662497757247093699959574966967627

[TIP: before submitting, first test the correctness of your program on some small test cases of your own devising. Then post your best test cases to the discussion forums to help your fellow students!]

[Food for thought: the number of digits in each input number is a power of 2. Does this make your life easier? Does it depend on which algorithm you’re implementing?]

The numeric answer should be typed in the space below. So if your answer is 1198233847, then just type 1198233847 in the space provided without any space / commas / any other punctuation marks.

(We do not require you to submit your code, so feel free to use any programming language you want — just type the final numeric answer in the following space.)

Solution:

def karatsuba(x, y):
    n = len(str(x))
    mid = n // 2
    
    if n == 1:
        return x * y
    else:
        a, b = int((str(x))[:mid + 1]), int((str(x))[mid + 1:])
        c, d = int((str(y))[:mid + 1]), int((str(y))[mid + 1:])
        p, q = a + b, c + d
        ac, bd, pq = a * c, b * d, p * q
        adbc = pq - ac- bd
        return (10 ** n) * ac + (10 ** mid) * adbc + bd
        
        
x = 3141592653589793238462643383279502884197169399375105820974944592
y = 2718281828459045235360287471352662497757247093699959574966967627
print(karatsuba(x, y))

Week 2: Quiz

Week 2: Programming Assignment

Course 2: Graph Search, Shortest Paths, and Data Structures

Week 1: Quiz

Week 1: Programming Assignment

Course 4: Shortest Paths Revisited, NP-Complete Problems and What To Do About Them

Week 1: Quiz

Week 1: Programming Assignment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s