CSSE 221: Fundamentals of Software Development Honors

Key

Programming assignment

Written (with some code) homework due Monday.

1. No late days for questions 3-6, so I can post solutions in time to study for the exam. However, you may use a late day if you need it for Q5-6
2. Complete all the reading.
3. Write a method that takes a linked list as an argument and removes every other element from it. It should mutate the list, so will be a void function. You can verify your answer by writing the code (10 pts)
4. Say we want to sort a list of n items. Which of the data structures that we studied could you insert all n items into and then remove them in order and have the data come out sorted, and it take O(n log n) total time? Explain your answer. (5 pts)
5. Insert, in this order, the Strings "exam", "two", "tuesday" into a HashSet first, then a TreeSet, and then print each set (each class has a toString() method). Show the outputs and explain they are different (4 pts)
6. Brainstorm 3 ideas for the Simulation project that interest you. Write them on separate paper and bring them to class (6 pts)
7. Finish the recursion exercises you started in class:
   1. (10 pts) How often are the Hofstadter Female and Male Sequences in the slides different in the first 50 positions? first 500? first 5,000? first 5,000,000?
      1. Write your four answers as comments at the top of the file containing the code you used to solve this.
      2. Commit your work!
   2. (25 pts) Complete the recursive drawSierpinski() method in the SierpinskiRenderer class in the sierpinski package. This method should render the Sierpiński Triangle as shown in the figure below. The triangle is rendered by following these steps:
      1. Draw a solid equilateral triangle.
      2. In a contrasting color, draw another solid equilateral triangle whose corner points are the midpoints of the original’s sides.
      3. Repeat this process recursively for each of the three corner triangles. That is, you will need three recursive calls in your method.
      4. Technically speaking, this process is repeated an infinite number of times to create the true Sierpiński triangle, but we don’t have that much time. So, stop your recursion when the length of a side of the triangle becomes shorter than some fixed constant, say 5.