CSSE 221: Fundamentals of Software Development Honors

Key

Programming assignment

Written (with some code) homework due Monday.

1. No late days for questions 3-7, so I can post solutions in time to study for the exam. However, you may use a late day if you need it for Q8.
2. Make sure you are familiar with the material in the reading for the week.
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 method that returns void. 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 why they are different. (4 pts)
6. Complete the Team Preferences for Simulation Project SECTION X survey on ANGEL, where X is your section number. The survey MUST be completed by this THURSDAY so I can assign you to your project teams before next Monday. The survey is accessible following these links on the course ANGEL page: Lessons → Miscellaneous → Team Preferences for Simulation Project SECTION X. (5 pts)
7. Brainstorm 3 ideas for the Simulation project that interest you. Write them on separate paper and bring them to class. (6 pts)
8. 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.