CSC 343
Homework 2

• Exercises 3.1, 3.2, 3.3 on function growth rates.
• Exercise 3.12, analyzing programs
• Exercises 3.15 and 3.16, on the meaning of upper and lower bounds
• Exercises 3.19 and 3.20, on variants of the binary-search algorithm

• Exercise 2.3-6 on modifying the insertion-sort algorithm
• Exercise 2.3-7, an algorithm to find numbers in a list that add up to a given number
• Problem 4-1, examples of solving recurrences
• Problem 4-5, on chip testing

You are given a list of points in a plane, each specified by an (x,y) coordinate pair, and you want to know whether there is a single circle that they're all on. (Don't worry about "close enough"; you may assume for this problem that your floating-point numbers are infinitely accurate.) Describe an algorithm in pseudocode to solve this problem. Analyze it: tell how long it takes, as a function of the number of points.

• Project 3.2 from the Shaffer book, measuring the time actually taken by sequential and binary search algorithms. For this assignment, store everything in fixed-size arrays.

• Let's write some standard algorithm -- say, an insertion sort -- for several different implementations of the List ADT. (Which is not necessarily what's in Shaffer, p. 96: I would separate the notion of a "current position" from the list, and I would probably move the "insert", "remove", and "clear" methods into a MutableList sub-interface....) In all five cases, define a class to represent a list of Strings, with suitable constructors, toString() methods, implementations of some basic operations, and an insertion sort to demonstrate that it all works.

  The five implementations:

  • an array, as built into the Java language
  • an ArrayList, as built into the java.util library
  • a LinkedList, as built into the java.util library
  • a linked list, built from Links as described in Shaffer section 4.1.2
  • a linked list, built using class polymorphism ("a StringList is either an EmptyStringList or a NonEmptyStringList")

  Get all of these to work. Discuss the pros and cons of the various implementations. What kinds of problems would be easier to do in one implementation than another?