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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- financial management exam 1 answers
- psychology exam 1 quizlet
- developmental psychology exam 1 quizlet
- philosophy exam 1 quizlet
- sociology 101 exam 1 quizlet
- sociology 101 exam 1 answers
- organic chemistry exam 1 practice
- introduction to sociology exam 1 quizlet
- psychology exam 1 practice test
- lifespan development exam 1 quizlet
- psychology exam 1 review
- group 1 name periodic table