CSE 101 Calibration Homework Homework 0 Fall 2006 Background Order and Recurrence Relations simple algorithms Due Friday September 29 100 points total DOES NOT COUNT TOWARDS GRADE Analyzing algorithms 10 pts Assume proc I is an algorithm that takes I time and does not change I What are the orders of the running times of the following two algorithms Alg1 n 1 begin 2 I 1 3 While I n do 4 begin 5 proc I 6 I 7 end 8 end Alg2 n 1 begin 2 I 1 3 While I n do 4 begin 5 proc I 6 I 2 I 7 end 8 end Order Notation 5 pts each Is 4dlog ne O n2 Why or why not When unspecified logs are base 2 Is log n n log n Why or why not Is 4n O 2n Why or why not Is n n 1 n 2 1 O n Why or why not 1 Triangles 20 points Let G be an undirected graph with nodes v1 vn The adjacency matrix representation for G is the n n matrix M given by Mi j 1 if there is an edge from vi to vj and Mi j 0 otherwise A triangle is a set vi vj vk of 3 distinct vertices so that there is an edge from vi to vj another from vj to vk and a third from vk to vi Give and analyze an algorithm for deciding whether a graph has a traingle in it where the input graph is given by its adjacency matrix representation Analyze your algorithm s worst case performance first in terms of just the number of nodes n of the graph then in terms of n and the number of edges m of the graph Your algorithm should be faster when m n2 Binary Conversion 10 points Consider the following algorithm to covert a decimal number to binary More precisely the input is a decimal representation of a number given as an array of digits D n 1 D 0 PI n 1 representing X I 0 D I 10I The output should be an array of bits PI n0 1 B n0 1 B 0 so that X I 0 B I 2I The following algorithm uses a long division by two algorithm LDIV that takes linear time O n to compute the decimal representation of Xdiv2 given X in decimal The binary coversion algorithm is Convert D 0 n 1 array of digits array of bits 1 Initialize B 0 4n array of bits 2 I 0 a pointer to which bit we are computing 3 While I 4n do 4 begin 5 B I D 0 mod2 6 D LDiv2 D 7 I 8 end 9 Return B possibly removing initial 0 s if you want Prove that this algorithm is correct and give a time analysis in terms of the number n of digits Summing triples 20 points Let A 1 n be an array of positive integers A summing triple in A is 3 distinct indices 1 i j k n so that A i A j A k Give and analyze an algorithm that given A determines whether there is any summing triple in A Try to be better than O n3 Implementation 20 points Implement the algorithm you gave for the summing triples problem above Try it on random arrays where each element 2 A i is chosen in the range 1 n for n 24 26 28 210 212 214 and 216 Plot its performance on a log2 n vs log2 of the time scale Then try the same experiment on random arrays where each element is chosen in the range 1 n4 Do you see a difference If so can you explain it 3
View Full Document
Unlocking...