JAVA Assignment I need on time
CS 220 – Data Structures Assignment 2 Instructions for solving a problem: • It's important to solve the problem, however, it's more important to understand the problem and solution. • We came here for learning, so we can be better prepared for our next career. • Solving the problem - steps: o Understand the problem o Think about different ways to solve it o Use different test cases and manually try to solve the problem without starting coding. ▪ If you can solve the problem that's excellent ▪ If you can’t solve the problem, then: • Think differently • Revisit the slides and books • Search on google to see how other people have solved this problem o If you are seeing other's code, try to understand the code instead of just memorizing it. o Remember memorizing code never helps and we have plagiarism detector. o Start coding o After finishing the coding, test your code with your test cases manually. o Finally, run your program. Instructions for performing the assignment: • Answer (analyze, discuss) the questions in a clear, coherent, and professional way. o Specifically write these: ▪ How you are solving the problem. • This is to show your thinking level to solve the problem. • You may mention the techniques you are following, the data structure you are using, whether you are using loop or not etc. ▪ Verifying that your program is correct? • This is to show your thinking level to analyze the problem. • You may mention that you will use (have used) these (use your own input to verify the program) test cases to verify your program. • Implement your solution to the problem (question) in Java/Python/C++. • You are encouraged to read book/online resources. If you take any help from these clearly cite the source on your writing. o Possible help includes, but not limited to: ▪ Seeing YouTube video ▪ Seeing solution of the problem online ▪ Seeing discussion about the problem online ▪ Discussing with someone except your classmates on this course. • Submit the assignment on Blackboard. Feel free to contact me (
[email protected]) anytime, for any confusion or difficulty in understanding. Grade points and other information: • This assignment has total 10 grade points. a. Question 1 to 5 are worth 0.4 points each totaling 2 points. b. Question 6 to 10 are worth 1.5 points each. Each question: i. Discussion is 1 point. ii. Implementation is 0.5 points. c. Overall clear, coherent, organized writing and submitting the report as instructed is 0.5 point. Deliverable: • Submit 1 zip file in blackboard. o That zip file will include a single PDF file and the source codes for each problem. ▪ PDF file: Analysis, discussion about the problem. ▪ Source codes: Your source code can be in Java, Python or C++. mailto:
[email protected] Questions: 1. What is binary tree and binary search tree? Discuss their similarities and differences. 2. How can we traverse the nodes of a tree? In which scenario we should use which traversal mechanism? 3. What are the advantages of binary search over a linear search? 4. What is a priority-queue? Discuss some use cases of priority-queue 5. What is a heap? What is the advantage of the heap over a stack? What is the time complexity to get the minimum item from min-heap? Question 6 (Programming problem): Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4 Example 2: Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1 Constraints: • 1 <= nums.length=""><= 104="" •="" -104="">< nums[i],="" target="">< 104="" •="" all="" the="" integers="" in="" nums="" are="" unique.="" •="" nums="" is="" sorted="" in="" ascending="" order.="" question="" 7="" (programming="" problem):="" given="" an="" array="" of="" meeting="" time="" intervals="" intervals="" where="" intervals[i]="[starti," endi],="" return="" the="" minimum="" number="" of="" conference="" rooms="" required.="" example="" 1:="" input:="" intervals="[[0,30],[5,10],[15,20]]" output:="" 2="" example="" 2:="" input:="" intervals="[[7,10],[2,4]]" output:="" 1="" constraints:="" •="" 1=""><= intervals.length=""><= 104="" •="" 0=""><= starti="">< endi=""><= 106="" question="" 8="" (programming="" problem):="" given="" an="" integer="" array="" nums="" and="" an="" integer="" k,="" return="" the="" kth="" largest="" element="" in="" the="" array.="" note="" that="" it="" is="" the="" kth="" largest="" element="" in="" the="" sorted="" order,="" not="" the="" kth="" distinct="" element.="" example="" 1:="" input:="" nums="[3,2,1,5,6,4]," k="2" output:="" 5="" example="" 2:="" input:="" nums="[3,2,3,1,2,4,5,5,6]," k="4" output:="" 4="" constraints:="" •="" 1=""><= k=""><= nums.length=""><= 104="" •="" -104=""><= nums[i]=""><= 104="" question="" 9="" (programming="" problem):="" given="" the="" root="" node="" of="" a="" binary="" search="" tree="" and="" two="" integers="" low="" and="" high,="" return="" the="" sum="" of="" values="" of="" all="" nodes="" with="" a="" value="" in="" the="" inclusive="" range="" [low,="" high].="" example="" 1:="" input:="" root="[10,5,15,3,7,null,18]," low="7," high="15" output:="" 32="" explanation:="" nodes="" 7,="" 10,="" and="" 15="" are="" in="" the="" range="" [7,="" 15].="" 7="" +="" 10="" +="" 15="32." example="" 2:="" input:="" root="[10,5,15,3,7,13,18,1,null,6]," low="6," high="10" output:="" 23="" explanation:="" nodes="" 6,="" 7,="" and="" 10="" are="" in="" the="" range="" [6,="" 10].="" 6="" +="" 7="" +="" 10="23." constraints:="" •="" the="" number="" of="" nodes="" in="" the="" tree="" is="" in="" the="" range="" [1,="" 2="" *="" 104].="" •="" 1=""><= node.val=""><= 105="" •="" 1=""><= low=""><= high=""><= 105="" •="" all="" node.val="" are="" unique.="" question="" 10="" (programming="" problem):="" given="" an="" array="" of="" integers="" nums="" and="" an="" integer="" target,="" return="" indices="" of="" the="" two="" numbers="" such="" that="" they="" add="" up="" to="" target.="" you="" may="" assume="" that="" each="" input="" would="" have="" exactly="" one="" solution,="" and="" you="" may="" not="" use="" the="" same="" element="" twice.="" you="" can="" return="" the="" answer="" in="" any="" order.="" example="" 1:="" input:="" nums="[2,7,11,15]," target="9" output:="" [0,1]="" explanation:="" because="" nums[0]="" +="" nums[1]="=" 9,="" we="" return="" [0,="" 1].="" example="" 2:="" input:="" nums="[3,2,4]," target="6" output:="" [1,2]="" example="" 3:="" input:="" nums="[3,3]," target="6" output:="" [0,1]="" constraints:="" •="" 2=""><= nums.length=""><= 104="" •="" -109=""><= nums[i]=""><= 109="" •="" -109=""><= target=""><= 109 • only one valid answer exists. follow-up: can you come up with an algorithm that is less than o(n2) time complexity? 109="" •="" only="" one="" valid="" answer="" exists.="" follow-up:="" can="" you="" come="" up="" with="" an="" algorithm="" that="" is="" less="" than="" o(n2)="" time="">