CMSC 341 — Data Structures — Fall 2013

Homework 1

Due Dates:

• Sections 1 & 3: Thursday, September 19, in class.
• Sections 2 & 4: Monday, September 23, in class.

Referenced exercises are from Data Structures and Algorithm Analysis in Java by Mark A. Weiss. Page numbers are for the third edition (3/e) and the second edition (2/e) of the textbook. (For this problem set, the page numbers for the two editions happen to be the same.)

1. Exercise 2.1 (3/e: p. 50, 2/e: p. 50).
2. Exercise 2.2 (3/e: p. 50, 2/e: p. 50), parts a-d. Briefly justify your answers.
3. Exercise 2.5, (3/e: p. 50, 2/e: p. 50). Briefly justify your answers.
4. Exercise 2.28 (3/e: p. 54, 2/e: p. 54), parts a & b.
   Additional Instructions: Try to make your algorithm as fast as possible. First explain your strategy in a few English sentences. Then, provide pseudo-code for your algorithm. (Do not include an entire Java program.) Briefly justify the correctness and running time of your program.
5. Consider the following Java program. The program compiles without any errors, but throws an exception at run time. Explain why the error occurs at run time and not at compile time.
   public class Node<T> { private T data; public Node(T data) { this.data = data; } public void setData(T data) { System.out.println("Node.setData: this.data = " + this.data); this.data = data; } } public class MyNode extends Node<Integer> { public MyNode(Integer data) { super(data); } public void setData(Integer data) { System.out.println("MyNode.setData: data = " + data); super.setData(data); } public static void main (String [] args ) { MyNode mn = new MyNode(5); Node n = mn; n.setData("Hello"); } }