Goal: To understand how to analyze code at the per operation level. To understand the terminology to discuss and communicate the runtime of algorithms. To exercise understanding of the Java language. To exercise understanding of Stacks and Queues. To be able to implement a java method given high level instructions. <\/p>\n
Give the exact number, tilde, and Big O values of assignment to the sum variable (= and +=) and and compare operations for each of the following:<\/p>\n
\r\n\/\/ a.\r\nsum = 0;\r\nfor (int i=0; i < n*n; i++){\r\n for (int j=0; j < n*n; j++){\r\n sum += 1;\r\n }\r\n}\r\n\/\/Assignment: Exact: ________, tilde: ________, Big O: ________ \r\n\/\/Compare : Exact: ________, tilde: ________, Big O: ________ \r\n\r\n\/\/b\r\nsum = 0;\r\nfor (int i=0; i < n; i++){\r\n for (int j=0; j < i; j++){\r\n sum += 1;\r\n }\r\n}\r\n\/\/Assignment: Exact: ________, tilde: ________, Big O: ________ \r\n\/\/Compare : Exact: ________, tilde: ________, Big O: ________ \r\n\r\n\/\/ c\r\nsum = 0;\r\nfor (int i=0; i < n*n; i++){\r\n for (int j=0; j < i; j++){\r\n sum += 1;\r\n }\r\n}\r\n\/\/Assignment: Exact: ________, tilde: ________, Big O: ________ \r\n\/\/Compare : Exact: ________, tilde: ________, Big O: ________ \r\n \r\n<\/pre>\n#2<\/h2>\n
a. Give the exact number of array accesses and compare operations with respect to the length of num (call this n) in the best and worst case. Describe the best and worst case and explain why they have the runtime you specify.<\/p>\n
\r\nvoid BubbleSort(int[] num) {\r\n int j;\r\n boolean flag = true; \/\/ set flag to true to begin first pass\r\n int temp; \/\/ holding variable\r\n while (flag) {\r\n flag = false; \/\/ set flag to false awaiting a possible swap\r\n for (j = 0; j < num.length - 1; j++) {\r\n if (num[j] < num[j + 1]) {\r\n temp = num[j]; \/\/ swap elements\r\n num[j] = num[j + 1];\r\n num[j + 1] = temp;\r\n flag = true; \/\/ shows a swap occurred\r\n }\r\n }\r\n }\r\n} \/\/ code credit: mathbits.com\r\n\r\n\/\/Best Case Description: __________________________________\r\n\/\/Array Access: Exact: ______________\r\n\/\/Compare : Exact: ______________\r\n\r\n\/\/Worst Case Description: __________________________________\r\n\/\/Array Access: Exact: ______________\r\n\/\/Compare : Exact: ______________\r\n<\/pre>\nb. What are the Big O and ~ runtimes of the above code?<\/p>\n
#3<\/h2>\n
a. Does $O(\\log_{10} n) = O(\\log_2 n)$? Why? (hint: recall the rules of logarithms)
\nb. Does $O(\\log_{10} n) = O(\\log n^2)$? Why?
\nc. Plot the above functions using R, Python, or Java and submit the code and a png file of the plot<\/p>\n
#4<\/h2>\n
d. Order the following functions by growth rate:
\n$n$
\n$\\sqrt{n}$
\n$n^{1.5}$
\n$n^2$
\n$n \\log n$
\n$n \\log \\log n$
\n$n \\log_2 n$
\n$n \\log(n^2)$
\n$2^n$
\n$2^{\\frac{n}{2}}$
\n$37$
\n$n^3$
\n$n^2 \\log n$<\/p>\n
b. Indicate which functions grow at the same rate.<\/p>\n
#5<\/h2>\n
Actual interview question. What is the output? Give a detailed explanation for each println statement.<\/p>\n
public class O\r\n{\r\n static int x = 1;\r\n\r\n public static void main(String args[]){\r\n O o = new O();\r\n o.call(3);\r\n }\r\n\r\n public void call(int x){\r\n O o = new O();\r\n this.x = 5;\r\n\r\n System.out.println(\"Output: \" + x);\r\n System.out.println(\"Output: \" + O.x);\r\n System.out.println(\"Output: \" + o.x);\r\n }\r\n}<\/pre>\n#6<\/h2>\n
a. What are the implementation differences between abstract classes vs interfaces?
\nb. Difference between implements and extends? Can you implement multiple interfaces or extend multiple classes?
\nc. Describe a use case for each.<\/p>\n
#7<\/h2>\npublic static void main(String args[])<\/pre>\na. Why must main be public? Why not private?
\nb. Why must main be static? Why not a normal method?
\nc. What’s the void for, and what are the args?<\/p>\n
#8<\/h2>\n
What is the result of the following sequence of method calls? Show the contents of the data structure after every operation.<\/p>\n
\r\nadd(4)\r\nadd(8)\r\nadd(1)\r\nadd(6)\r\nremove()\r\nremove()\r\n<\/pre>\nfor the following data structures:
\na. Stack
\nb. Queue
\nc. Priority queue (1 is top priority)<\/p>\n
#9<\/h2>\n
What would the output of the following code be if collection was a:
\na. Stack
\nb. Queue<\/p>\n
\r\ncollection.add(\"First\");\r\ncollection.add(\"Second\");\r\ncollection.add(\"Third\");\r\nfor (String i : collection) {\r\n System.out.println(i);\r\n}\r\n<\/pre>\n#10<\/h2>\n
Given two arrays, write a function to compute their intersection.<\/p>\n
Example:
\nGiven nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].<\/p>\n
Note:
\nEach element in the result must be unique.
\nThe result can be in any order.
\nName your source file Intersection.java<\/p>\n
\r\n\/\/ here is some code to get started with\r\nvoid main(String[] args) {\r\n {\r\n int[] x = {1, 2, 2, 1};\r\n System.out.println(\"x = \" + Arrays.toString(x));\r\n int[] y = {2, 2};\r\n System.out.println(\"y = \" + Arrays.toString(y));\r\n int[] z = intersection(x, y);\r\n System.out.println(\"intersection(x, y) = \" + Arrays.toString(z));\r\n\r\n System.out.println(Arrays.equals(z, new int[]{2}));\r\n }\r\n\r\n {\r\n int[] x = {2, 5, 3, 7};\r\n System.out.println(\"x = \" + Arrays.toString(x));\r\n int[] y = {5, 2, 9, 0, 1};\r\n System.out.println(\"y = \" + Arrays.toString(y));\r\n int[] z = intersection(x, y);\r\n System.out.println(\"intersection(x, y) = \" + Arrays.toString(z));\r\n \r\n Arrays.sort(z);\r\n int [] correct = new int[]{2,5};\r\n Arrays.sort(correct);\r\n System.out.println(Arrays.equals(z, correct));\r\n }\r\n}\r\n\r\nint[] intersection(int[] nums1, int[] nums2) {\r\n...\r\n}\r\n<\/pre>\nDue:<\/strong> 6\/9 @5pm
\nTurn in answers digitally to the hw1 folder with the filename “memo.txt”<\/p>\nGrading:<\/strong>
\n9 points: All questions correct.
\n1 point: How easy was the assignment to grade.<\/p>\n","protected":false},"excerpt":{"rendered":"Goal: To understand how to analyze code at the per operation level. To understand the terminology to discuss and communicate the runtime of algorithms. To exercise understanding of the Java language. To exercise understanding of Stacks and Queues. To be able to implement a java method given high level instructions. #1 Give the exact number,… Read more »<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"_links":{"self":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/posts\/10"}],"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=10"}],"version-history":[{"count":90,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/posts\/10\/revisions"}],"predecessor-version":[{"id":606,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/posts\/10\/revisions\/606"}],"wp:attachment":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/media?parent=10"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/categories?post=10"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/tags?post=10"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}