Given two numbers represented as strings, return multiplication of the numbers as a string.<\/p>\n
Note:
\n* The numbers can be arbitrarily large and are non-negative.
\n* Converting the input string to integer is NOT allowed.
\n* You should NOT use internal library such as BigInteger.<\/p>\n
$ java MultiplyStrings 1 0\r\n0\r\n$ java MultiplyStrings 1 1\r\n1\r\n$ java MultiplyStrings 100 10\r\n1000\r\n$ java MultiplyStrings 99 88\r\n8712\r\n$ java MultiplyStrings 1234567890 1234567890\r\n1524157875019052100\r\n$ java MultiplyStrings 12345678909999 11111111111111\r\n137174210111098628257898889\r\n$ java MultiplyStrings 298374091823740981273409817324 182374981237409817234099182374\r\n54415969398083955415924144796721184778955953290573100647176\r\n<\/pre>\n#2<\/h2>\n
Describe a family of graphs with V vertices and E edges for which the worst-case running time of Dijkstra\u2019s algorithm is achieved. Describe a small graph and walk through each part of Dijkstra\u2019s algorithm and explain why this input is so bad. Don’t simply execute the algorithm on your graph. Explain line by line how each part of the algorithm is impacted by this worst case graph.<\/p>\n
#3<\/h2>\n
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.<\/p>\n
For example,
\nGiven [3,2,1,5,6,4] and k = 2, return 5.<\/p>\nNote:
\n* Your runtime must be $O(n \\log k)$ and explain why in your memo.txt
\n* You may assume k is always valid, 1 \u2264 k \u2264 array’s length.<\/p>\n$ java KthLargestElement k [array]\r\n\r\n\/\/Given k = 2 and array [3,2,1,5,6,4]\r\n$ java KthLargestElement 2 3 2 1 5 6 4\r\n5\r\n\/\/Given k = 5 and array [8,7,6,5,4,3,2,1]\r\n$ java KthLargestElement 5 8 7 6 5 4 3 2 1\r\n4\r\n\/\/Given k = 1 and array [8,7,6,5,4,3,2,1]\r\n$ java KthLargestElement 1 8 7 6 5 4 3 2 1\r\n8\r\n\/\/Given k = 2 and array [3,2,3]\r\n$ java KthLargestElement 2 3 2 3\r\n3\r\n<\/pre>\n#4<\/h2>\n
FindSingle<\/strong> You are given a sorted array of numbers where every value except one appears exactly twice; the remaining value appears only once. Design a sublinear algorithm for finding which value appears only once. Argue that your solution is not O(n). The method is called int findsingle(int[] a)<\/strong>. Solve this problem using divide and conquer and explain in a memo.txt why your solution is divide and conquer. Hint: write out some examples and look for patterns.<\/p>\n
Here are sample inputs:<\/p>\n
$java FindSingle 1 1 2 2 3 4 4 5 5 6 6 7 7 8 8\r\n3\r\n$java FindSingle 10 10 17 17 18 18 19 19 21 21 23\r\n23\r\n$java FindSingle 1 3 3 5 5 7 7 8 8 9 9 10 10\r\n1<\/pre>\nHere is some starting code:<\/p>\n
\r\npublic static void main(String[] args) throws Exception {\r\n\r\nif (args.length > 0){\r\n\t\/\/using java8 magic\r\n\tint[] in = Arrays.stream(args).map(String::trim).mapToInt(Integer::parseInt).toArray();\r\n\tSystem.out.println(Arrays.toString(in) + \" \" + findsingle(in));\r\n}else{\r\n\t\t\r\n\t{\r\n\tint [] in = new int[]{1,1,2,2,3};\r\n\tSystem.out.println(Arrays.toString(in) + \" \" + findsingle(in));\r\n\t}\r\n\t\r\n\t{\r\n\tint [] in = new int[]{1,1,2,3,3};\r\n\tSystem.out.println(Arrays.toString(in) + \" \" + findsingle(in));\r\n\t}\r\n\t\r\n\t{\r\n\tint [] in = new int[]{1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8 };\r\n\tSystem.out.println(Arrays.toString(in) + \" \" + findsingle(in));\r\n\t}\r\n\t\r\n\t{\r\n\tint [] in = new int[]{10, 10, 17, 17, 18, 18, 19, 19, 21, 21, 23};\r\n\tSystem.out.println(Arrays.toString(in) + \" \" + findsingle(in));\r\n\t}\r\n\t\r\n\t{\r\n\tint [] in = new int[]{1, 3, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 10};\r\n\tSystem.out.println(Arrays.toString(in) + \" \" + findsingle(in));\r\n\t}\r\n}\r\n\r\n}\r\n\r\n\/**\r\n * Find and return single element in a sorted array of numbers \r\n * where every value except one appears exactly twice; the \r\n * remaining value appears only once.\r\n * \r\n * @param a Sorted array\r\n * @return element without a pair\r\n *\/\r\nstatic int findsingle(int[] a) throws Exception{\r\n\r\n\t\/\/ Some sample lines. Feel free to remove them.\r\n\tif (a.length == 1) return a[0];\r\n\tif (a.length == 2) throw new Exception(\"No single\");\r\n\t\r\n\treturn 0;\r\n}\r\n<\/pre>\nDue:<\/strong> 7\/7 @5pm. Submit the code to users in a hw3 folder. Each question is 2 points and then 2 points for how easy it is to grade.<\/p>\n","protected":false},"excerpt":{"rendered":"
#1 Given two numbers represented as strings, return multiplication of the numbers as a string. Note: * The numbers can be arbitrarily large and are non-negative. * Converting the input string to integer is NOT allowed. * You should NOT use internal library such as BigInteger. $ java MultiplyStrings 1 0 0 $ java MultiplyStrings… Read more »<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,1],"tags":[],"_links":{"self":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/posts\/246"}],"collection":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/comments?post=246"}],"version-history":[{"count":24,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/posts\/246\/revisions"}],"predecessor-version":[{"id":670,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/posts\/246\/revisions\/670"}],"wp:attachment":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/media?parent=246"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/categories?post=246"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/tags?post=246"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}