Computer Science 501
Data Stuctures and Algorithm Analysis
Fall 2013, The College of Saint Rose
Lecture 8: Interfaces; Iterators; Linked Structures
Date: Wednesday, October 23, 2013
Agenda
- Announcements
- Lab 5: Sorting With Comparators [HTML] [PDF] due - discussion next week
- Programming Project 2: Analyzing Sorting Algorithms [HTML] [PDF] due date is now 11:59 PM, Monday, November 4
- Midterms returned; discussion
- Lecture 7 assignment recap
- Final words (for now) on searching and sorting
- Interfaces
- Iterators
- Lab 6: The Two Towers Problem [HTML] [PDF] out
- Linked structures
Lecture 8 Assignment
Due at the start of class, Wednesday, October 30.
Please submit answers to these questions
in Submission
Box under "LA8" by the start of our next
class. We will discuss these questions at the start of class, so no
late submissions are accepted. Please be sure that your name is
clearly indicated in all submissions.
- Bailey Problem 9.10, p. 213. (3 points)
- Bailey Problem 9.12, p. 213. (5 points)
- Suppose you wish to determine the highest floor in an n-story
building from which an object can fall without breaking. You have 2
such objects to experiment with, but once one breaks, it can no
longer be used for subsequent tests. Design the most efficient
algorithm you can to solve this problem and state its efficiency
class. (5 points)
- In the Lab 6: The Two Towers Problem [HTML] [PDF] lab,
you are asked to iterate through all subsets of a set (its power
set). This is an important operation for many brute-force
algorithms like the one you are tackling in that lab.
A related problem is to generate all permutations of a set,
also often an important mechanism for solving a problem by brute
force. How many permutations are there of a list of n items?
Describe an algorithm (either a pencil and paper approach or a
psuedocode algorithm) that would generate all permutations. (7
points)
As an example, the permutations of the set 123 would be: 123, 132,
213, 231, 312, 321. (Hint: I find this ordering - the
lexicographic ordering to be the most natural way to think
about generating these. Think first about how you would generate the
permutations of 1-element, 2-element, 3-element, and 4-element sets,
then see if you can generalize.)
Examples
- Iterators
- Iterables
- IntegerGenerator
- SimpleLinkedList