DOC PREVIEW
UCSD CSE 101 - Homework

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CSE 101 Calibration Homework (Homework 0)Winter 2005Background, (Order and Recurrence Relations, simple algorithms)Due Thursday, January 13100 points total, DOES NOT COUNT TOWARDS GRADEAnalyzing algorithms, 10 pts. Assume proc(I) is an algorithm that takesΘ(I) time and does not change I. What are the orders of the runningtimes 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 ∗ I7. end;8. end;Order Notation, 5 pts. each Is 4dlog ne∈ O(n2)? Why or why not? (Whenunspecified, 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?1Triangles(20 points) Let G be an undirected graph with nodes v1, ..vn. Theadjacency matrix representation for G is the n × n matrix M given by:Mi,j= 1 if there is an edge from vito vj, and Mi,j= 0 otherwise. Atriangle is a set {vi, vj, vk} of 3 distinct vertices so that there is an edgefrom vito vj, another from vjto vkand a third from vkto vi. Give andanalyze 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 thenumber of nodes n of the graph, then in terms of n and the number ofedges m of the graph. Your algorithm should be faster when m << n2.Binary Conversion(10 points): Consider the following algorithm to coverta decimal number to binary. More precisely, the input is a decimal rep-resentation of a number, given as an array of digits, D[n − 1], ...D[0],representing X =PI=n−1I=0D[I]10I. The output should be an array of bitsB[n0− 1]...B[0] so that X =PI=n0−1I=0B[I]2I.The following algorithm uses a “long division by two” algorithm LDIVthat takes linear time (O(n)) to compute the decimal representation ofXdiv2, given X in decimal..The binary coversion algorithm is: Convert(D[0..n-1]: array of digits):array of bits1. 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 ofthe 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, determineswhether there is any summing triple in A. Try to be better than O(n3).Implementation (20 points) Implement the algorithm you gave for the sum-ming triples problem above. Try it on random arrays where each element2A[i] is chosen in the range 1...n, for n = 24, 26, 28, 210, 212, 214, and 216.Plot its performance on a log2n vs. log2of the time scale. Then try thesame experiment on random arrays where each element is chosen in therange 1, ..n4. Do you see a difference? If so, can you explain


View Full Document

UCSD CSE 101 - Homework

Download Homework
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?