{"id":69,"date":"2016-05-17T18:03:56","date_gmt":"2016-05-17T22:03:56","guid":{"rendered":"http:\/\/www.notexponential.com\/notes\/?page_id=69"},"modified":"2022-08-31T16:01:26","modified_gmt":"2022-08-31T20:01:26","slug":"project-1","status":"publish","type":"page","link":"https:\/\/www.notexponential.com\/notes\/projects\/project-1\/","title":{"rendered":"Project 1"},"content":{"rendered":"<h2><strong>Meta Option A (Baseline) Asymptotic Analysis<\/strong><\/h2>\n<p><em>If you feel that this meta option is too simple for you, feel free to select one of the meta options B or C below.\u00a0 If you are unsure, just go ahead with this meta option A.<\/em><\/p>\n<p>Within this meta option A, you have to do the sub-option based on the last digit of your GWID, and from the list options shared with you.\u00a0 Each suboption asks you to analyze a piece of code.\u00a0 You are then required to do the following.<\/p>\n<ol>\n<li>Analyze and write the time complexity of the given program.<\/li>\n<li>Explain your analysis<\/li>\n<li>Confirm the time complexity by writing a program and simulating it. Run the code for different values of n. (You will have to play with different values of n that make sense for your question.)\n<ul>\n<li>Document time taken for different values of n<\/li>\n<\/ul>\n<\/li>\n<li>Draw a graph of theoretical results (from Step 1) and experimental results (Step 2 b) to compare. You may have to change the scale (log scale, etc) to get straight lines.\u00a0 If the plots are curves, we cannot easily compare them.<\/li>\n<\/ol>\n<p>For more details, see the <a href=\"https:\/\/www.notexponential.com\/notes\/wp-content\/uploads\/2022\/08\/AsymptoticAnalysisProcessWorkbook.pdf\" target=\"_blank\" rel=\"noopener\">Asymptotic Analysis Process<\/a> file, or see this <a href=\"https:\/\/www.notexponential.com\/notes\/wp-content\/uploads\/2022\/08\/AsymptoticAnalysisProcessWorkbook.xlsx\" target=\"_blank\" rel=\"noopener\">Workbook<\/a>.<\/p>\n<p>See this <a href=\"https:\/\/www.notexponential.com\/notes\/wp-content\/uploads\/2022\/08\/SampleSubmissionStructure.pdf\">Sample Submission<\/a> for structure.<\/p>\n<h2><strong>Meta Option B (Data Structure) Analysis<\/strong><\/h2>\n<p>2a.\u00a0 Analyze Union Find data structure.\u00a0 Implement it.\u00a0 Run experiments on it, and show that the time complexity of m unions and n finds matches the theoretical prediction.<\/p>\n<p>2b. Analyze Bloom Filter data structure.\u00a0 Implement it.\u00a0 Run experiments on it, and show that the time complexity of m unions and n finds matches the theoretical prediction.<\/p>\n<h2><strong>Meta Option C (Asymptotic Design) Project<\/strong><\/h2>\n<p>Design a gradebook software, which allows the following features:<\/p>\n<ul>\n<li>Import a gradebook (CSV file), with fields: &#8220;firstname, lastname, email, phone, city, score (0-1000 integer value), department&#8221;<\/li>\n<li>Search the gradebook, with information like: &#8220;search key&#8221;<\/li>\n<li>Search should run in O(log n + k) time searching on ALL of its fields, where k is the number of results returned by the search<\/li>\n<\/ul>\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Meta Option A (Baseline) Asymptotic Analysis If you feel that this meta option is too simple for you, feel free to select one of the meta options B or C below.\u00a0 If you are unsure, just go ahead with this meta option A. Within this meta option A, you have to do the sub-option based [&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-69","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/69","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=69"}],"version-history":[{"count":15,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/69\/revisions"}],"predecessor-version":[{"id":412,"href":"https:\/\/www.notexponential.com\/notes\/wp-json\/wp\/v2\/pages\/69\/revisions\/412"}],"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=69"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}