{"id":10,"date":"2015-03-28T17:17:07","date_gmt":"2015-03-28T17:17:07","guid":{"rendered":"http:\/\/josephpcohen.com\/teaching\/cs310-summer2015\/?p=10"},"modified":"2015-06-01T14:59:00","modified_gmt":"2015-06-01T14:59:00","slug":"hw1","status":"publish","type":"post","link":"https:\/\/josephpcohen.com\/teaching\/cs310-summer2015\/hw1\/","title":{"rendered":"HW1"},"content":{"rendered":"

CS310 Homework 1<\/p>\n

1. NULL (There is no question 1)<\/p>\n

2. Give the big O for each of the following:<\/p>\n

\r\n a.\r\n\tsum = 0;\r\n\tfor (int i=0; i < n; i++)\r\n\t{\r\n\t  for (int j=0; j < i; j++)\r\n\t  {\r\n\t    sum += 1;\r\n\t  }\r\n\t}\r\n\r\n b.\r\n\tsum = 0;\r\n\tfor (int i=0; i < n*n; i++)\r\n\t{\r\n\t  for (int j=0; j < n*n; j++)\r\n\t  {\r\n\t    sum += 1;\r\n\t  }\r\n\t}\r\n\r\n c.\r\n\tsum = 0;\r\n\tfor (int i=0; i < n*n; i++)\r\n\t{\r\n\t  for (int j=0; j < i; j++)\r\n\t  {\r\n\t    sum += 1;\r\n\t  }\r\n\t}\r\n<\/pre>\n
3
\na. Does O(log n) = O(log_2 n)?  Why? (hint: recall the rules of logarithms)
\nb. Does O(log n) = O(log n^2)?  Why?<\/p>\n
4
\na. Does O(2^n) = O(3^n)?  Why?
\nb. Does O(2^n) = O(2^(n\/2))?  Why?<\/p>\n
5
\na. Order the following functions by growth rate: <\/p>\n
N, square root of N, N^1.5 , N^2, N log N, N log log N, N log_2 N, N log(N^2), 2^N , 2^(N\/2), 37, N^3, and N^2 log N<\/pre>\n
b. Indicate which functions grow at the same rate.<\/p>\n
6
\nActual 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
7
\na. 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
8. <\/p>\n
public static void main(String args[])<\/pre>\n
a. 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
9.
\nShow the results of the following sequence: <\/p>\n
\tadd(4)\r\n\tadd(8)\r\n\tadd(1)\r\n\tadd(6)\r\n\tremove()\r\n\tremove()<\/pre>\n
  for the following data structures:
\na. Stack
\nb. Queue
\nc. Priority queue (1 is top priority)<\/p>\n
10.
\nWhat would the output of the following code be if S was a:
\na. Stack
\nb. Queue<\/p>\n
S.add(\"First\");\r\nS.add(\"Second\");\r\nS.add(\"Third\");\r\nfor (String i : S) {\r\n   System.out.println(i);\r\n}<\/pre>\n
Due:<\/strong> 6\/2 @5pm
\nTurn in answers digitally to the cs310\/hw1 folder with the filename “memo.txt”<\/p>\n","protected":false},"excerpt":{"rendered":"
CS310 Homework 1 1. NULL (There is no question 1) 2. Give the big O for each of the following: a. sum = 0; for (int i=0; i < n; i++) { for (int j=0; j < i; j++) { sum += 1; } } b. sum = 0; for (int i=0; i < n*n;…  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-summer2015\/wp-json\/wp\/v2\/posts\/10"}],"collection":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs310-summer2015\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs310-summer2015\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs310-summer2015\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs310-summer2015\/wp-json\/wp\/v2\/comments?post=10"}],"version-history":[{"count":13,"href":"https:\/\/josephpcohen.com\/teaching\/cs310-summer2015\/wp-json\/wp\/v2\/posts\/10\/revisions"}],"predecessor-version":[{"id":152,"href":"https:\/\/josephpcohen.com\/teaching\/cs310-summer2015\/wp-json\/wp\/v2\/posts\/10\/revisions\/152"}],"wp:attachment":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs310-summer2015\/wp-json\/wp\/v2\/media?parent=10"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs310-summer2015\/wp-json\/wp\/v2\/categories?post=10"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs310-summer2015\/wp-json\/wp\/v2\/tags?post=10"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}