Divide and Conquer Algorithms for Maximum Efficiency in Problem Solving
Explore three Divide and Conquer algorithm practices focusing on identifying maximal points in a list, finding elements in an infinite length sorted array, and optimizing pairs of integers for maximal value. Dive into these algorithmic challenges for efficient problem-solving techniques.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
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)
