CSC300: Homework (MyRecursion, Union Find Problems)

(Click here for one slide per page)

• Read Recursion Call Stacks. This will give you an iea of how recursion is implemented in Java - using our friend the Stack data structure!

  The discussion in this document refers to a Java file: MyRecursionTrace.java. You can download this file and save it in a new package called ds1.student.recursion in your IntelliJ IDEA project.

  Optional: Do the exercises in this document. (You don't need to hand them in.)

• Read Algorithms Section 1.5 - Case Study: Union-Find

• Do Quiz 9 on Recursion and Union Find.

  For some of the questions on Union Find, you may want to refer to some classes provided here.

  Create a new package in IntelliJ IDEA, called ds1.student.unionfind. Download the following files and save them to this new package.

  • UnionFind.java
  • QuickFindUF.java
  • QuickUnionUF.java
  • WeightedUF.java
  • CompressionUF.java - not needed for the quiz, but provided for reference
  • TestUF.java - not needed for the quiz, but provided for reference

  These Java files refer to some other text (data) files, which you may want to look at or use. They go in a directory under the top level project in IntelliJ (in the same directory as the src subdirectory, called data/.

  • largeUF.txt - not needed for the quiz, but provided for reference
  • mediumUF.txt - not needed for the quiz, but provided for reference
  • tinyUF.txt - not needed for the quiz, but provided for reference
  • tinyUFTall2.txt - not needed for the quiz, but provided for reference

• Do the homework assigned on D2L (see Submissions).

  There are two parts to the homework: a programming assignment (hw9a) and a written assignment (hw9b). Be sure to scroll to the bottom of this page to see all of the details!

  Make sure to submit each file to the correct folder. I will not move your homework to the correct folder (mostly because I won't look closely) - downloading your submissions and autograding them is automated!

  hw9a: MyRecursion.java

  • Create a new package in IntelliJ IDEA, called: ds1.student.recursion. Download the following file and save it to this package.

    • MyRecursion.java

    Look for all the TODO comments and implement the functions and provide any short answers (in comments) as requested.

    One of the problems is to convert mickey mouse:

    

    to mickey moose:

    

    This is an example of a Fractal also known as a Recursive drawing

    Each execution of your function should draw one circle.

  hw9b: Union Find Problems

  Do the following problems from the textbook on paper. Submit a Word doc, PDF, or text document with your answers.

  • 1.5.1
  • 1.5.2
  • 1.5.3
  • 1.5.8
  • 1.5.10