CS 5800, Spring 2018 (Clinger’s section)
Homework 5 (70 points)
Assigned: Thursday, 8 February 2018
Due: Wednesday, 14 February 2018, 6pm
This homework is to be submitted electronically following instructions that will
soon appear on the course assignments page.
The Java code you write for this homework assignment is not allowed to
contain any import or package declarations.
0. [5 points] Create a directory named src5, which will contain all of the files
you submit for this assignment, including at least:
README
Q1.pdf
Q2.java
Set.java
Sets.java
Create a README file in the format described below. Your README file must
be a plain text file in UTF-8 that contains no lines longer than 80 characters.
The name of that file must be README, with no suffix; submitting a file named
README.txt, or any name other than README, will interfere with our automated
grading and lower your grade on the assignment. Your README file must be
structured as follows:
1. Its first line must consist of your name.
2. Its second line must consist of your CCIS ID.
3. Its third line must consist of the email address you would like us to use
when communicating with you, as when we report your grade for this
homework assignment.
4. You may write any comments you like in the fourth and following lines,
but those comments are optional.
1. [5 points] Consider the following problem:
Given a Java arraycontaining n int values, return the smallest value
in the array.
Prove that every algorithm for this problem has a worst-case running time in
Ω(n).
Typeset your proof using LATEX or some similar system suitable for typeset-
ting mathematics, and convert your typeset proof into a PDF file named Q1.pdf.
Place that Q1.pdffile inside the src2 directory you created for question 0 above.
1
2. [15 points] Inside your src5 directory from question 0, create a file named
Q2.java that defines a Java class named Q2 that defines a public static method
named smallest that satisfies the specification given in the following skeleton
code:
class Q2 {
// Given a array of n integers
// and a non-negative integer k 0, then that left curly brace is followed by the char-
acters in the string ((Integer) s1.min()).toString()
– if s1.size() > 1, then for each of the larger int values in the set a
comma is followed by the characters that express that value
– a right curly brace }
in that order.
4
Examples for questions 3 and 4:
Set s0 = Sets.empty();
Set s00 = Sets.empty();
Set s2 = s00.adjoin(2);
Set s28 = s2.adjoin(8);
Set s285 = s28.adjoin(5);
Set s2853 = s285.adjoin(3);
Set s5 = s0.adjoin(5);
Set s58 = s5.adjoin(8);
Set s582 = s58.adjoin(2);
Set s583 = s58.adjoin(3);
Set s5832 = s583.adjoin(2);
Set s585 = s58.adjoin(5);
assert s0.size() == 0;
assert s00.size() == 0;
assert s58.size() == 2;
assert s585.size() == 2;
assert s0.contains(0) == false;
assert s00.contains(5) == false;
assert s58.contains(2) == false;
assert s583.contains(2) == false;
assert s585.contains(5) == true;
assert s585.contains(8) == true;
assert s5.min() == 5;
assert s5832.min() == 2;
assert s2853.min() == 2;
assert s5.max() == 5;
assert s5832.max() == 8;
assert s2853.max() == 8;
assert ! s0.equals(null);
assert ! s582.equals(null);
assert ! s582.equals("some random object");
assert s0.equals(s00);
assert ! s0.equals(s5);
assert s2853.equals(s5832);
assert ! s2853.equals(s285);
assert s0.hashCode() == s00.hashCode();
assert s2853.hashCode() == s5832.hashCode();
assert s5832.toString().equals ("{2,3,5,8}");