Write a program that takes two arrays representing integers, and returns an integer representing their product. Solution: we can use the grade-school algorithm for multiplication which consists of multiplying the first number by each digit of the second, and then adding all the resulting terms. def multiply(num1, num2): sign = -1 if (num1[0] < 0) … Continue reading Multiply Two Arbitrary-Precision Integers
Increment an Arbitrary-Precise Integer
Write a program which takes as input an array of digits encoding a non-negative decimal integer D and updates the array to represent the integer D + 1. For example, if the input is (1,2,9) then you should update the array to (1,3,0). Your algorithm should work even if it is implemented in language that … Continue reading Increment an Arbitrary-Precise Integer
The Dutch National Flag Problem
The Dutch national flag problem (DNF) is a programming problem proposed by Edsger Dijkstra. The flag of the Netherlands consists of three colors: red, white and blue. Given balls of these three colors arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of the same … Continue reading The Dutch National Flag Problem
Algorithm Design 