logo

COMP3821 Extended Algorithms and Programming Techniques

5 Pages2703 Words54 Views
   

Added on  2021-05-28

COMP3821 Extended Algorithms and Programming Techniques

   Added on 2021-05-28

ShareRelated Documents
COMP3821 Assignment 1Jinming Dong(z5211275)March 9, 20201Algorithm:Sorting the list of integers in ascending order using merge sort takes O(n log n)running time,and assume we have more than two elements in the array.For each query,searching the index ixof x and the index iyof y using binarysearch takes O(log n) running time.|ix− iy| − 1 is the number of points lying onthe interval between x and y, n queries takes O(n log n) running time.Time Complexity:For the above algorithm, the time complexity can be calculate as the the timetaken to sort the array plus the time to search the index of x and y.That is,time complexity = O(n log n) + O(n log n) = O(n log n)2Algorithm:Sorting the list of integers in ascending order using merge sort takes O(n log n)running time,and assume we have more than two elements in the array.To find out whether there exist two elements x, y ∈ S wherexy= p , we use twoiterators i and j,placed at the index 0 and index 1 of the array respectively.We computes[j]s[i], if it is greater than p, j remains the same and increment i by1, if it is less than x, i remains the same and increment j by 1.Otherwise, wehave p,then return true.If we loop through the whole array and do not findthe appropriate i and j, then return false.Since we simply go through the arrayonce, time complexity for this operation is roughly O(n).Time Complexity:For the above algorithm, the time complexity can be calculate as the the timetaken to sort the array plus the time to compute iand j.That is,time com-plexity = O(n log n) + O(n) = O(n log n)Another algorithm:For each integer x,if there exists another integer y satisfying thatab= p, x =aorx = b, then y must be one of x × p and x \ p .For this question, we have anarray of size 2n, so there are at most 2n potential integers that meet the above1This study source was downloaded by 100000822526728 from CourseHero.com on 03-31-2021 06:50:39 GMT -05:00https://www.coursehero.com/file/70008924/a1pdf/ThisstudyresourcewassharedviaCourseHero.com
COMP3821 Extended Algorithms and Programming Techniques_1
statement.Thus we can store them in a hash map with size 2n.For each element x in the array, first check whether it is in the hash map, thatis,hash(x) == 1,if it is,then return true since it has another element y thatwe have seen before in the array satisfingxy= p oryx= p.Otherwise, computeits possible matches, namely x × p and x \ p,and store them into the hash map.We do not need to solve collisions, because duplicate values are allowed.Time Complexity:Time complexity of the above algorithm is O(n).We need a loop to go throughthe entire array,which is O(n).The check step can be done in O(1) and com-putation can be done in constant time.Time complexity = O(n) + O(1) + c,where c is a constant.Therefore, time complexity is O(n).33.1For each empty containeridentify the balls which is not in containers,if the con-tainer lights up green,then let the ballin the container and let another emptycontainer to repeat the same operation until all balls are in containers.3.2We set array B contains the balls and array C contains the containercl:the start index of Cch:the end index of Cbl:start index of Bbh:the end index of BAlgorithm:MainAlgorithm(C, B, cl, ch, bl, bh)· · ·if cl < ch:· · · · · ·p = SubAlgorithm(B, C[ch], bl, bh)· · · · · ·i=cl· · · · · ·for j=cl to ch-1:· · · · · · · · ·if C[i] identify ball B[p] lights blue or green:· · · · · · · · · · · ·swap C[i] with C[j]· · · · · · · · · · · ·i=i+1· · · · · ·swap C[i] with C[ch]· · ·MainAlgorithm(C, B, cl, i-1,bl,p-1)· · ·MainAlgorithm(C, B, i+1, ch,p+1,bh)cc:the container to partition balls bl:start index of Bbh:the end index of BSubAlgorithm(B,cc,bl, bh)· · ·for i = bl to bh:2This study source was downloaded by 100000822526728 from CourseHero.com on 03-31-2021 06:50:39 GMT -05:00https://www.coursehero.com/file/70008924/a1pdf/ThisstudyresourcewassharedviaCourseHero.com
COMP3821 Extended Algorithms and Programming Techniques_2

End of preview

Want to access all the pages? Upload your documents or become a member.

Related Documents
AVL Tree, Set Intersection Algorithms, Sloppy Inc. Communication, Array Search
|9
|2413
|78

Desklib SEO Suggestions
|9
|2414
|194

Problem 2. C-11.37 Suppose we wish to support a new met
|2
|483
|264

Pseudocode Case Complexity
|3
|496
|23

Assignment | The marked areas and submit using the Gradescope system.
|3
|925
|11

Algorithm Design with Loss Function
|6
|1366
|64