{"id":71,"date":"2016-05-17T18:04:12","date_gmt":"2016-05-17T22:04:12","guid":{"rendered":"http:\/\/www.notexponential.com\/notes\/?page_id=71"},"modified":"2019-02-18T18:23:12","modified_gmt":"2019-02-18T22:23:12","slug":"project-2","status":"publish","type":"page","link":"https:\/\/www.notexponential.com\/notes\/projects\/project-2\/","title":{"rendered":"Project 2 &#8211; Divide &#038; Conquer, Greedy"},"content":{"rendered":"<p><span style=\"color: #808080;\"><strong>Basic Options (For self practice and code review)<\/strong><\/span><\/p>\n<ul>\n<li><span style=\"color: #808080;\"><strong>Quick select, probabilistic<\/strong><\/span><br \/>\n<span style=\"color: #808080;\">See book, Section 4.6.\u00a0 Try with different settings of probability &#8211; 0.5, 0.2, 0.8 etc.<\/span><\/li>\n<\/ul>\n<p><strong>Project 2 Options (Choose the option that matches the last digit of GWID)\u00a0<\/strong><\/p>\n<p><strong>Option 0: Quick select, deterministic (median of medians method)<br \/>\n<\/strong>See textbook, Section 4.6<\/p>\n<p><strong>Option 1: Closest pair of points<\/strong><br \/>\nSee textbook, Section 4.7<\/p>\n<p><strong>Option 2,3: Staircase \/ Pareto-optimal Points<br \/>\n<\/strong>See textbook, Section 4.11, Exercise #12<\/p>\n<p><strong>Option 4,5: Convex hull<\/strong><br \/>\nWe are given a set P of n points in a two-dimensional plan, and we want to compute the convex hull of P. The convex hull is defined as the smallest convex polygon containing the points. (A way to visualize a convex hull is to imagine nails on all the points of the plane and put an elastic band around the points \u2013 the shape of the elastic band is the convex hull.) Describe an O(n log n) time divide and conquer algorithm to find the convex hull of the set P of n points.<\/p>\n<p><strong>Option 6: Finding Max Number in Circular Shifted Array<\/strong><br \/>\nWe are given an array A[1..n] of sorted integers that has been circularly shifted<br \/>\nsome positions to the right. For example, [35, 42, 5, 15, 27, 29] is a sorted array that has been<br \/>\ncircularly shifted 2 positions, while [27, 29, 35, 42, 5, 15] has been shifted 4 positions.<br \/>\nWe can obviously find the largest element in A in O(n) time. Describe an O(log n) algorithm.<\/p>\n<p><strong>Option 7: Kruskal&#8217;s Algorithm for Minimum Spanning Tree<br \/>\n<\/strong>See textbook, Section 5.5<\/p>\n<p><strong>Option 8: Merging Sorted Lists<br \/>\n<\/strong>See textbook, Section 5.3<br \/>\nYou are given an array a[] of numbers, where a[i] is the size of the i-th list to merge.\u00a0 You have to produce the sequence in which to merge the lists, and the total cost of merging all the lists.\u00a0 <em>Implementation Notes: Use a heap data structure.\u00a0 (You don&#8217;t have to implement your own heal structure, you can simply use the inbuilt one in Java\/C#.)<\/em><\/p>\n<p><strong>Option 9: Hoffman Coding<\/strong><br \/>\nGiven a set of symbols and their frequency of usage, find a binary code for each symbol, such that:<br \/>\na. Binary code for any symbol is not the prefix of the binary code of another symbol.<br \/>\nb. The weighted length of codes for all the symbols (weighted by the usage frequency) is minimized.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Basic Options (For self practice and code review) Quick select, probabilistic See book, Section 4.6.\u00a0 Try with different settings of probability &#8211; 0.5, 0.2, 0.8 etc. Project 2 Options (Choose the option that matches the last digit of GWID)\u00a0 Option 0: Quick select, deterministic (median of medians method) See textbook, Section 4.6 Option 1: Closest [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":66,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-71","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/71","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/comments?post=71"}],"version-history":[{"count":15,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/71\/revisions"}],"predecessor-version":[{"id":274,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/71\/revisions\/274"}],"up":[{"embeddable":true,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/66"}],"wp:attachment":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/media?parent=71"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}