Divide and Conquer Algorithm Challenges in Computer Science
Design efficient divide and conquer algorithms for finding maximal points in a list, detecting elements in an increasing sorted array, and determining the largest value across pairs of integers. Improve upon runtimes of existing algorithms for enhanced computational efficiency.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CS 330 Discussion 2 Fall 2016
Divide and Conquer Practice 1 Design an algorithm called ????????????? whose input is a list of points ? = {?1,?2 ??} where each point ??is a coordinate pair ??,??, which returns all maximal points in ? and report its runtime (which should be better than ? ?2). A maximal point is a point ??such that there is no ??for which ??> ??and ??> ??(that is, all points ??for which there is no point both above and to the right of ??). For example, in the graph below all red points are maximal points. (To simplify things, you may assume ? is sorted by ?-coordinate beforehand).
Divide and Conquer Practice 2 You re given a increasingly sorted array of infinite length ?. However, all elements at after some index ? have value , and all elements up until are integers. For example, ? could be 1,2,3,4,6,9, , , with ? = 6. However, your algorithm does not know what ? is beforehand. Design an algorithm which finds the index of an element ? which is known to be in ? in ? log? time.
Divide and Conquer Practice 3 Design an algorithm called ????????? which takes an array of integers ? = {?1,?2,?3 ??} and returns the largest value of ?? ??across all pairs of (?,?) satisfying ? ?. Report its runtime, which should be faster than ?(?2). For example, if ? was {6, 2,0,5, 3,2} you would return 7 (corresponding to ? = 2,? = 4). (Note that in this example the largest difference between two elements here is 9, but it s in the wrong direction. Also note that the greedy algorithm which finds the smallest element and then the largest element to its right or vice-versa fails for this example)
