Description
CSC 4520 HW0: Getting to Know You and Java Practice
This is the very first homework in CSC 4520. The goal is to learn more about you as an individual and explore your knowledge in programming and Java.
Submitting This Assignment On iCollege Grading and Corrections We’ve provided some example inputs and outputs to help you test your code and check your work. Producing the correct output for these examples is necessary but not sufficient for receiving full credit. There may be other test cases that we use in grading–you should consider writing your own examples. Showing Your Work There are three ways of showing your work. Any of these ways will help you earn “effort” credit. Following these practices will also help us verify that your work is your own. This helps you avoid being falsely accused of academic dishonesty. 1. You should add comments that explain the key ideas behind your approach. We’ve added placeholders in HW0.java where you can do this. 2. You may also add additional test cases in order to ensure that your code is 100% correct. Remember that you can consult outside resources and work with other students as long as you write up your own solutions and cite any links or people you received help from within citations.txt. See syllabus/collaboration for details. Q1: maxOfArray (3 points) Write maxOfArray, which takes in an array of integers and returns the largest integer within the array. If the array is empty, throw an IllegalArgumentException. Some examples: int testResult1 = maxOfArray(new int[] {1, 3, 4, 5, 2}); int testResult2 = maxOfArray(new int[] {-1, -3, -4, -5, -2}); System.out.println(testResult1); // should output 5 System.out.println(testResult2); // should output -1 maxOfArray(new int[] {}); // Should throw IllegalArgumentException Q2: twoSum (3 points) Write twoSum, which takes in an array of integers and a target sum, and returns a 2-element array that represents two distinct indices of elements that sum up to the target value. Some examples: int[] testResult3 = twoSum(new int[] {0, 2, 3, 4, 5}, 6); int[] testResult4 = twoSum(new int[] {1, 2, 3, 4, 5}, 10); System.out.println(Arrays.toString(testResult3)); // should output [1, 3] System.out.println(Arrays.toString(testResult4)); // should output [-1, -1] ● In the first example, arr[1] + arr[3] = 2 + 4 = 6. ● In the second example, we returned [-1, -1] because there are not two distinct elements within the array that sum to 10 (you can’t use 5 twice). Q3 (4 points) Write add, which given two numbers represented as Lists of single-digit integers, returns their sum as a list of integers. Some examples: List testResult5 = add(Arrays.asList(1, 2, 3), Arrays.asList(2, 4, 2)); List testResult6 = add(Arrays.asList(9, 9, 9), Arrays.asList(1)); // 123 + 242 = 365 // [1, 2, 3], [2, 4, 2] => [3, 6, 5] System.out.println(testResult5); // should output [3, 6, 5] // 999 + 1 = 1000 // [9, 9, 9], [1] => [1, 0, 0, 0] System.out.println(testResult6); // should output [1, 0, 0, 0]
CSC4520 HW1: Pseudocode and Recursion
The goal of this homework is to practice what we covered in Lecture 2 and 3. Please review both lectures in order to have the context to solve these problems. Submitting This Assignment iCollege In order to complete the coding portions of this assignment, you must make commits of your code. We will take the latest commit as your “final submission”. Grading and Corrections We’ve provided some example inputs and outputs to help you test your code and check your work. Producing the correct output for these examples is necessary but not sufficient for receiving full credit. There may be other test cases that we use in grading–you should consider writing your own examples. Java Language API You may use more basic data types like int[ ], float [ ], matrix like [ ][ ]. For Java Abstract ones like ArrayList<>, List<>, it’s better for your mastering of Java knowledge. Otherwise, you can just ignore them ( or simple convert [ ] to ArrayList at the end). Focus on Algorithms’ details, not Java Language. Runnable, correctness, efficiency. (well organized, easy to read, not in a mass) Showing Your Work 1. You should add comments that explain the key ideas behind your approach. 2. You may also add additional test cases in order to ensure that your code is 100% correct. Q1: Find Missing Number (2 points) Convert the following pseudocode algorithm into Java. You’ll find example tests within the main method to ensure you’re headed in the right direction. Make sure you understand each example. algorithm findMissing Input: integer array A of length N where each element is distinct and in the range [0, N] Output: integer x where x is in the range [0, N], but not in A s = the sum of all numbers in A return (N(N+1))/2 – s Q2: TwoSum (Fast) (3 points) Convert the following code into Pseudocode and put it in twosum.txt. Hint: for some loops, you should describe what it does in English. There are no tests for this problem, so be sure to double check and test your translation manually, similar to how we did in lecture. public static int[] twoSumFast(int[] arr, int target) { HashSet seen = new HashSet<>(); for (int j = 0; j < arr.length; j++) { int otherAddend = target – arr[j]; if (seen.contains(otherAddend)) { for (int i = 0; i < arr.length; i++) { if (arr[i] == otherAddend) { return new int[] {i, j}; } } } else { seen.add(arr[j]); } } return new int[] {-1, -1}; } Q3: countFives (2 points) Write countFives, which takes in an integer and returns the number of times 5 appears as a digit within the number. Examples: countFives(123467890) // should output 0 countFives(555555) // should output 6 countFives(15354) // should output 2 In order to receive full credit for this problem, you must use recursion. I.e. using =, for, while, etc. is prohibited. Hint: recall the % and / operators: 123 % 10 // evaluates to 3 123 / 10 // evaluates to 12 Q4: pickTrees (3 points) You build homes out of wood and you need material from a nearby forest. However, you want to avoid deforestation, so you decide for each tree you cut down, you’ll leave its neighbors alone, giving the forest time to recover. However, you still need as much wood as possible, so you have to be careful about which trees you pick to cut down. Write pickTrees, which takes in an array of N trees arr where arr[i] represents how much wood you can harvest by cutting down tree i. It should return the max amount of wood you can harvest while following the rule of skipping neighbors: // Pick tree 0, tree 2, and tree 4 => 1 + 3 + 5 = 9 wood total int testResult5 = pickTrees(new int[] {1, 2, 3, 4, 5}); System.out.println(testResult5); // should output 9 // Pick tree 1 and tree 3 => 3 + 3 = 6 wood total int testResult6 = pickTrees(new int[] {1, 3, 4, 3}); System.out.println(testResult6); // should output 6 // Pick tree 0 and tree 3 => 5 + 9 = 14 wood total int testResult7 = pickTrees(new int[] {5, 1, 4, 9}); System.out.println(testResult7); // should output 14 In order to receive full credit for this problem, you must use recursion. I.e. using =, for, while, etc. is prohibited.
CSC4520 HW2: Runtime and QuickSort
The goal of this homework is to practice what we covered in Lecture This assignment is due on SEP 29, 2022 at 11:59PM Eastern Time. Most of this homework does not require coding, but instead, expects you to analyze existing code. Please read each question carefully. We’ve provided an example question and ideal answer in example.txt to help you get started on the runtime analysis questions. Submitting This Assignment iCollege Grading and Corrections Since this is a written assignment, There are no tests or examples. This assignment will be graded out of 10 points. The point values of each problem are listed in the title. We will use manual inspection and written rubrics to assign points in a fair, standardized way. Academic Integrity Remember that you can consult outside resources and work with other students as long as you write up your own solutions and cite any links or people you received help from within citations.txt. Q1 Mysterious Function (30 point) What’s the worst case runtime of the following function? Please remember to define n, provide a tight upper bound. public static void mystery1(int z) { System.out.println(z); if (z >= 10) { mystery1(z/10); System.out.println(z); } } Q2 Exponentiation (Fast?) (40 points) ● What’s the best case, worst case, and average-case runtime of pow? Assume n = power. Please remember to define n, provide a tight upper bound. algorithm pow Input: positive integer b, non-negative integer p Output: computing b^p (i.e. b raised to power of p) if p = 0 return 1 else if p = 1 return b else if p is even temp = pow(b, p / 2) return temp * temp else return b * b * pow(b, p-2) Q3 QuickSort (30 point) Given the QuickSort implementation from class, provide an 18-element list that will take the least number of recursive calls of QuickSort to complete. As a counter-example, here is a list that will cause QuickSort to make the MOST number of recursive calls: public static List input() { return Arrays.asList(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0); } And here’s the QuickSort algorithm, for convenience: algorithm QuickSort Input: lists of integers lst of size N Output: new list with the elements of lst in sorted order if N < 2 return lst pivot = lst[N-1] left = new empty list right = new empty list for index i = 0, 1, 2, … N-2 if lst[i] <= pivot left.add(lst[i]) else right.add(lst[i]) return QuickSort(left) + [pivot] + QuickSort(right)
CSC4520 HW3
Given this Tree T, answer the following questions: 1 Assuming T is defined in Java, what code do I write to get “sun” back? 2 What will System.out.println(T.getChildren().get(2).getChildren()) output? Be as specific as possible. 3 Given the following code, what will we output for mystery(T)? public static void mystery(TreeNode node) { List<TreeNode> children = node.getChildren(); for (int i = 1; i < children.size(); i++) { TreeNode child = children.get(i); System.out.println(child.getValue()); mystery(child); } }
CSC4520 HW4: Graphs, Traversals
Reference
Example Undirected Graph
Visual Adjacency List Adjacency Matrix
[[], [2], [1]] [
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
]
Questions start on next page ⤵
Q1. Given an undirected graph with 10 vertices but 45 edges, which of the following will be
true? Select all that apply.
A) Every node will have at least one neighbor
B) The graph will have duplicate labels
C) An Adjacency List would be more space-efficient to represent this graph vs. a Matrix
D) The graph is GUARANTEED to have a cycle in it
E) None of the above
Q2. There are N cities, with M roads, where each road connects a pair of cities. You are given
city x. We want to see if every city has a direct road leading to x. Return true if this condition is
met, and false otherwise.
A) If we represent this as a graph problem, what are the nodes and edges?
B) Is this a directed or undirected graph? – Please consider the situation between two cities
in the real world. The question is not about two places in a city.
C) Given an adjacency matrix for this graph, describe using words how you would find the
answer to this problem. You do not have to write code.
D) Given an adjacency list for this graph, describe using words how you would find the
answer to this problem. You do not have to write code.
Q3. Given the graph below, answer the following questions.
A) Represent this graph as an adjacency list.
B) Represent this graph as an adjacency matrix.
C) What is the ordering of nodes If we run Graph DFS starting on node 1? Assume we visit the
smallest neighbour first.
D) Write your Java code(submit a .java file) to implement the DFS for graph traversal using the
adjacency matrix (either recursive or iterative).
For the test case, you can directly use the above example. And you should call the DFS
function several times with different starting points to show the different traversal orders.
DFS(graph, 0); // one possible output likes 0
DFS(graph, 1); // one possible output likes 1 0 2 4 3
DFS(graph, 2); // …
DFS(graph, 3); // …
DFS(graph, 4); // …
CSC4520 HW5: Minimum Spanning Tree
Reference
Example Undirected Graph
Visual Adjacency List Adjacency Matrix
[[], [2], [1]] [
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
]
Questions start on next page ⤵
0
2
1
Q1. Say we had |V|-1 edges picked from a connected, weighted, and undirected graph. Are we
guaranteed that these edges form a MST? Why or why not?
Q2. Programming problem(submit a .java file) On a 2D-plane shown as below,
some points with coordinates [xi, yi] are located. The cost of connecting two points [xi,
yi] and [xj, yj] is the manhattan distance between them: |xi – xj| + |yi – yj|,
where |val| denotes the absolute value of val.
Return the minimum cost and connected edges to make all points connected. You can use either Prim
or Kruskal algorithm. Suppose the number of points is no more than 100. You don’t need to further
improve the algorithm.
The coordinates can be Integer or Float (It doesn’t matter. Your code and test case can use Integer).
Example: Input Explanation: