The following is an algorithm for addition using the grade school method. Trace through the algorithm as we did in class and turn in the list of steps in the order they happened and what happens at each step. Use the following as the input: top_num = 56, bottom_num = 75. [6pts]
for each column x from right to left
var colans = top_num_in_col_x + bottom_num_in_col_x + carry_in_col_x
print rightmost digit of colans in the answer position of column x
carry_in_col_x+1 = all other digits of colans
Write an algorithm for "Long Multiplication," that is, the technique for multiplication you learned in grade school. This should not just be repeated applications of the addition algorithm. You can make the assumption that we already know 1x1 through 9x9.
[3 pts]
Binary search trees have a problem when inserting a list of items which are already sorted, as we discussed in lab. Look around the internet for "balanced" trees. Write a paragraph or two about how one of these trees handles insertion to solve this problem along with an example. You will probably want to draw pictures to help illustrate. Be descriptive and understand the main ideas. Also feel free to use Wikipedia as a source (but be sure to cite whatever you use!). The example should be your own, and should be interesting to the problem. [6 pts]
