{"id":31,"date":"2016-04-18T01:28:05","date_gmt":"2016-04-18T05:28:05","guid":{"rendered":"http:\/\/www.notexponential.com\/notes\/?page_id=31"},"modified":"2024-09-15T07:25:02","modified_gmt":"2024-09-15T11:25:02","slug":"lectures-3-4-divide-and-conquer","status":"publish","type":"page","link":"https:\/\/www.notexponential.com\/notes\/lectures\/lectures-3-4-divide-and-conquer\/","title":{"rendered":"Lectures 3 &#038; 4 &#8211; Divide and Conquer"},"content":{"rendered":"\n<p>The main slides for the introduction to Divide and Conquer design template.<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/www.notexponential.com\/notes\/wp-content\/uploads\/2024\/09\/DivideAndConquer_Part1.pdf\" type=\"application\/pdf\" style=\"width:100%;height:600px\" aria-label=\"Embed of DivideAndConquer_Part1.\"><\/object><a id=\"wp-block-file--media-9e4c2bf5-7525-45a3-996d-5fb7a3437211\" href=\"https:\/\/www.notexponential.com\/notes\/wp-content\/uploads\/2024\/09\/DivideAndConquer_Part1.pdf\">DivideAndConquer_Part1<\/a><a href=\"https:\/\/www.notexponential.com\/notes\/wp-content\/uploads\/2024\/09\/DivideAndConquer_Part1.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-9e4c2bf5-7525-45a3-996d-5fb7a3437211\">Download<\/a><\/div>\n\n\n\n<p><\/p>\n\n\n\n<p><\/p>\n\n\n\n<p>A helpful video on D&amp;C design technique.<\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Divide and Conquer Algorithms - A Quick Introduction\" width=\"625\" height=\"469\" src=\"https:\/\/www.youtube.com\/embed\/XWIZBGCJzI8?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p><\/p>\n\n\n\n<p>There are 3 techniques for sovling recurrence relations:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Unfolding<\/li>\n\n\n\n<li>Substitution (Guess and Prove)<\/li>\n\n\n\n<li>Master Theorem Cookbook Method<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Master Theorem for Solving Recurrence Relations\" width=\"625\" height=\"469\" src=\"https:\/\/www.youtube.com\/embed\/PIsNrfaqYN4?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p><\/p>\n\n\n\n<p>Some applications of D&amp;C Technique.<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/www.notexponential.com\/notes\/wp-content\/uploads\/2024\/09\/DivideAndConquer_Part2.pdf\" type=\"application\/pdf\" style=\"width:100%;height:600px\" aria-label=\"Embed of DivideAndConquer_Part2.\"><\/object><a id=\"wp-block-file--media-dcfccc72-26c4-435e-8dd1-1b8490a8296a\" href=\"https:\/\/www.notexponential.com\/notes\/wp-content\/uploads\/2024\/09\/DivideAndConquer_Part2.pdf\">DivideAndConquer_Part2<\/a><a href=\"https:\/\/www.notexponential.com\/notes\/wp-content\/uploads\/2024\/09\/DivideAndConquer_Part2.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-dcfccc72-26c4-435e-8dd1-1b8490a8296a\">Download<\/a><\/div>\n\n\n\n<p>A helpful video on algorithms for finding median in linear time.<\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Median Finding Algorithm in Linear Time\" width=\"625\" height=\"469\" src=\"https:\/\/www.youtube.com\/embed\/NAg20sPY_mk?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p><\/p>\n\n\n\n<p>Closest pair of points is a fun problem that uses divide and conquer approach.<\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Closest Pair of Points - Divide and Conquer Algorithm\" width=\"625\" height=\"352\" src=\"https:\/\/www.youtube.com\/embed\/IragEuvjBt4?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>The main slides for the introduction to Divide and Conquer design template. A helpful video on D&amp;C design technique. There are 3 techniques for sovling recurrence relations: Some applications of D&amp;C Technique. A helpful video on algorithms for finding median in linear time. Closest pair of points is a fun problem that uses divide and [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":27,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-31","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/31","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=31"}],"version-history":[{"count":6,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/31\/revisions"}],"predecessor-version":[{"id":520,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/31\/revisions\/520"}],"up":[{"embeddable":true,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/27"}],"wp:attachment":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/media?parent=31"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}