CS 155 Exam 1 Name_______________________



CS 146 Exam 1

Solutions

1. Analysis of non-recursive algorithms. It is a wonderful theorem of number theory that every positive integer can be written as a sum of four perfect squares. For example,

5 = 02 + 02 + 22 + 12

7 = 12 + 12 + 12 + 22

23 = 12 + 22 + 32 + 32

123471 = 12 + 32 + 312 + 3502

Give an algorithm int[] fourSquares(int n) that takes input n and finds four integers whose squares add up to n, and puts them in the array ans. Then give an asymptotic estimate for its running time T(n) on strings of length at most n. Make the estimate as tight as you can. Be sure your algorithm works on input 23.

(a) your Java code:

public static int[] fourSquares(int n){

int[] ans = new int[4];

int i,j,k,u, isq, jsq,ksq;

for(i=1,isq = 1;isq ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download