ࡱ> EGD5@ 0bjbj22 (,XX; 86,b$$n($$$$$$$$%RQ(6$GGG6$K$G$G$ `"# p e,##a$0$F#b((4#(#LZ@T46$6$ $ CSE 5311 Design and Analysis of Algorithms FALL 2004 Department of Computer Science The University of Texas at Arlington Home Assignment I Quiz 1 (09/23/04) will be based on these questions Answer questions 1a to 1c pertaining to the STOOGE_SORT Algorithm given below. STOOGE_SORT(A,i,j) if A[i] > A[j] then exchange A[i] ( A[j] if i+1 ( j then return k ( ((j-i+1)/3( STOOGE_SORT(A,i,j-k) STOOGE_SORT(A,i+k,j) STOOGE_SORT(A,i,j-k) Argue that STOOGE_SORT (A,1,length[A]) correctly sorts the input array A[1 .. n], where n = length[A]. Give a recurrence for the worst-case running time of STOOGE_SORT and a tight asymptotic bound on the worst-case running time. Compare the worst-case running time of STOOGE_SORT with that of insertion sort, merge sort, heapsort, and quicksort. Given an array of integers A[1..n], such that, for all i, 1 ( i < n, we have (A[i]-A[i+1]( ( 1. Let A[1] = x and A[n] = y, such that x < y. Design an efficient search algorithm to find j such that A[j] = z for a given value z, x ( z ( y. What is the maximal number of comparisons to z that your algorithm makes? What is Counting Sort? Give the Algorithm and provide analysis. What are Fibonacci Heaps? Give an example of a Fibonacci Heap. Write basic algorithms for insertion and deletion in Fibonacci Heaps. You are given a collection of n bolts of different widths and n corresponding nuts. You are allowed to try a nut and bolt together, from which you can determine whether the nut is larger than the bolt, smaller than the bolt, or matches the bolt exactly. However there is no way to compare two nuts together or two bolts together. The problem is to match each bolt to its nut. Design an algorithm for this problem with average case efficiency of ((n log n). Explain how we can check a graphs acyclicity by using Bredth-first search. Does either of the two traversals DFS or BFS always find a cycle faster than the other? If your answer is yes, indicate which of them is better and explain why it is the case; if you answer no, give two examples supporting your answer. A graph is said to be bipartite if all its vertices can be partitioned into two disjoint subsets X and Y such that every edge connects a vertex in X with a vertex in Y. a. Design an DFS-based algorithm for checking whether a graph is bipartite. b. Design a BFS-based algorithm for checking whether a graph is bipartite. Prove that the number of different paths of length k>0 from the ith vertex to the jth vertex of a graph(undirected or directed) equals the (i,j)th element of Ak, where A is the adjacency matrix of the graph. [ to be discussed in class]. You are given a list of numbers for which you need to construct a min-heap. (A Min-heap is a complete binary tree in which every key is less than or equal to the keys in its children.) Write a min-heap algorithm and analyze its complexity. Suppose we are to find the k smallest elements in a list of n elements, and we are not interested in their relative order. Can a linear-time algorithm algorithm be found when k is a constant? If so give the algorithm. In either case, justify your answer. Modify Dijkstras single source shortest path algorithm so that it checks if a directed graph has a cycle. Analyze your algorithm. Design a divide-and conquer algorithm for polynomial evaluation. How many additions and multiplications does your algorithm require? Compare your algorithm with that based on Horners rule in terms of efficiency. GUIDELINEs for 1-pg Reference Sheet Printed on only one side of the Sheet One inch (or 2.5 cms) Margin on all four sides Single Column format Font Type: Times Roman or Times New Roman or Aerial Minimum Font Size : 11 Your full name should be written on the sheet CSE 5311 Fall 2004 Page  PAGE 1 of  NUMPAGES 2 +26z{ ! " # & ) * + , 0 1 2 3 5 C L M N O Q R S T U V X Z [ \ ξ|xsxsxnsxsxsxsxnxsxsxgxsxsxnxs jhe0 he05 he06he0he0CJOJQJhe0he05CJOJQJhe0h^ 5CJOJQJaJh^ 5CJOJQJaJhe05CJOJQJaJhe0he05CJOJQJaJhe0CJOJQJaJhx5CJOJQJaJhe0he0CJOJQJaJhe0he0CJaJ(+-7V{  % & 5 X c x  & F 88^8gde0h`hgde0 & Fgde0$a$gde0$a$gdx5gde0gde0\ _ ` a b c p q w z { | }     ! " , - @ A E F \ ] a b c d g h t u v w x z { | } ̴̧ jhe0CJOJQJ jhe0CJOJQJhe06CJOJQJhe0CJOJQJ jhe0 jhe0 jhe0 he05 he06 jhe0he0=  0 $ % t _ ` & ' ./,$a$gdd $ & Fa$gd' $ & Fa$gd_$a$gdr $ & Fa$gdGh^hgd_ & Fgde0gde0 hh^h`hgde0 & Fgde0         B C _ ` % & ' E F #ǽdzǩ jQh'CJOJQJh'CJOJQJh h_6CJOJQJ]h_CJOJQJhgCJOJQJhx5CJOJQJhrCJOJQJhe06CJOJQJ jhe0CJOJQJhe0CJOJQJ jhe0CJOJQJ2./,x !cdefVWXY殤ҤyҤhe0CJOJQJ!hCH:hCH:6CJH*OJQJ]hCH:hCH:6CJOJQJ]hCH:CJOJQJh CJOJQJh h'6CJOJQJ]hdCJOJQJhrCJOJQJhGCJOJQJh'CJOJQJh'h'6CJOJQJ]-,wxefWXYYZ2G $ & F a$gdt+$a$gdt+$a$gdd $ & Fa$gdCH:$a$gdr $ & Fa$gd'$a$gd $h`ha$gd żżht+mHnHujht+U*jht+Uht+h ht+CJOJQJht+ht+>*CJOJQJht+CJOJQJG{ $ & F a$gdt+&1h:pt+/ =!"#$%@@@ e0NormalPJ_HmH nHsH tHDA@D Default Paragraph FontRi@R  Table Normal4 l4a (k@(No ListBJ@B e0Subtitle$a$5CJ(OJQJ4@4 dHeader  !4 @4 dFooter  ! ,+-7V{%&5Xcx0$%t_`&'./, w x e f W X Y Y Z 2G{00000000 0000 0 0 0 0 0 0 0 00 00 0 00 000 00 00 00 00 000 00 000 0 0 0 00 0 00p0p0 0 0p 0 0 0 0@00 @@+-7V{%&5Xcx0$%t`', w 0000000 0000 0 0 0 0 0 0 0 00 00 0 00 00 0 0 0 0 00w:::=\   ,G #%*57=!~[th[l[l[6[4l[jZZhqqdmmzz8*urn:schemas-microsoft-com:office:smarttagsdate8*urn:schemas-microsoft-com:office:smarttagsCityV*urn:schemas-microsoft-com:office:smarttagsplacehttp://www.5iantlavalamp.com/=*urn:schemas-microsoft-com:office:smarttags PlaceType=*urn:schemas-microsoft-com:office:smarttags PlaceName 2004239DayMonthYear#+,NO !\]cdwx)/      a k z|Q] H L 333333333-7{5X`wH e  V 2G{ Mohan Kumar 9' \8p;3 Q@?0?E k6dT|fֱ$kl =6s&G\~zMx IxY ^`OJPJQJ^Jo(^`OJQJ^Jo(hHopp^p`OJQJo(hH@ @ ^@ `OJQJo(hH^`OJQJ^Jo(hHo^`OJQJo(hH^`OJQJo(hH^`OJQJ^Jo(hHoPP^P`OJQJo(hH hh^h`o(hH) ^`hH) 88^8`hH) ^`hH() ^`hH() pp^p`hH()   ^ `hH. @ @ ^@ `hH.   ^ `hH.^`o( ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH.hh^h`o(.^`o(.0^`0o(hh^h`.hh^h`o(. ^`hH. pLp^p`LhH. @ @ ^@ `hH. ^`hH. L^`LhH. ^`hH. ^`hH. PLP^P`LhH. hh^h`o(hH) ^`hH) 88^8`hH) ^`hH() ^`hH() pp^p`hH()   ^ `hH. @ @ ^@ `hH.   ^ `hH.^`o() ;3|fk6dT$klIx0?EQ@=6s~zMx9' T        hD          Gg_dt+e0CH: ^ 9'x5r-@@UnknownG: Times New Roman5Symbol3& : Arial;|i0Batang?5 z Courier New;Wingdings"qhJ83 3 243QH)?e0*CSE 5311 Design and Analysis of Algorithms Mohan Kumar Mohan Kumar4         Oh+'0 (4 P \ ht|+CSE 5311 Design and Analysis of AlgorithmsoSE  Mohan KumarohaohaNormalu Mohan Kumar8haMicrosoft Word 10.0@&>|@x@؟3 ՜.+,0 hp  CSE@UTAA +CSE 5311 Design and Analysis of Algorithms Title  !"#$%&'()*+,-./012356789:;=>?@ABCFRoot Entry F@-HData 1Table/)WordDocument(,SummaryInformation(4DocumentSummaryInformation8<CompObjj  FMicrosoft Word Document MSWordDocWord.Document.89q