Problem Set 1—Algorithms

Purpose

This problem set reinforces your ability to describe algorithms in precise but non-executable pseudocode.

Background

This problem set is based on our September 3 class and material in sections 1.1 and 2.1 of our textbook.

Activity

Devise algorithms to solve each of the following problems. Write each algorithm in pseudocode.

Problem 1

Given a positive integer, n, find the smallest power of 10 that is greater than or equal to n. For example, if n were 8 your algorithm would return 10, if n were 17 your algorithm would return 100, if n were 100 your algorithm would also return 100, etc.

Problem 2

Given two matrices, A and B, compute their sum. (If you haven’t seen matrices yet, think of a matrix as a two-dimensional table of numbers. Elements in a matrix are usually identified by their row and column positions in this table, i.e., A_ij is the number in row i and column j of matrix A. The sum of matrices A and B is a third matrix, C, of the same shape as A and B, and defined by the rule C_ij = A_ij + B_ij.)

Problem 3

Given a real number, x, find an approximation to the cube root of x, without using any exponentiation operator. As for how accurate your approximation should be, I am interested in the structure of the algorithm you devise, not in an arbitrary level of accuracy. It should be clear that your algorithm can be tuned to whatever level of accuracy its user wants, by, for example, adjusting some parameter or constant in it, but I won’t care exactly what value you give for the relevant parameter(s) or constant(s).

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. If you worked in a group on this exercise, the whole group should schedule a single meeting with me. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.