Algorithms

My own solutions to the problems in the Algorithms Toolbox course.

Week 2

1. Find the nth Fibonacci Number Fn
2. Find the last digit of a large Fibonacci number
3. Euclidian algorithm for GCD
4. LCM of two positive integers
5. Compute Fn modulo m where n may be very large
6. Find the last digit of the sum of the first n Fibonacci numbers
7. Find the last digit of the sum of Fibonacci numbers m through n
8. Find the last digit of the sum of the squares of the first n Fibonacci numbers

Week 3

1. Greedy algorithm for changing money
2. Fractional knapsack via greedy algorithm
3. Complete trip with fewest stops to refuel
4. Maximize advertising revenue
5. Fewest points to sample all line segments
6. For distinct integers ai, maximize k in a1+a2+...+ak = n
7. Arrange multidigit numbers to maximize total number

Week 4

1. Binary search a sorted list
2. Binary search a sorted list, duplicates allowed
3. Check list for presense of majority element
4. 3-way partition quick sort
5. Count number of inversions in a sequence
6. Given points and segments, compute for each point number of segments it intersects
7. Given points on 2D plane, find the closest pair Z. Implement your own recursive python deep copy

Week 5

1. Money changer vis dynamic programming
2. Minimum number of x2,x3,+1 operations to get n from 1
3. Edit distance between two strings
4. Longest common subsequence between two strings
5. Longest common subsequence between three strings

Week 6

1. Given n gold bars of various weights, find maximum that can fit in a knapsack of some max weight
2. Partition n items of various value equally among 3 friends
3. Add parentheses to arithmetic expression to maximize its value