Objective

Students will be able to determine the relation between the growth rate of functions, use asymptotic notations, determine the time complexity of programs, and create array-based implementations of an abstract data type.

Assignment Questions

1. (This exercise is a variation of Exercise 2.1 in Chapter 2 of the textbook) Consider the following functions of n, where n is a natural number, n 1.

2,,log2 ,2,,37,2 log,3,log

Order the functions by growth rate. 2. Using the definition of the Big-Oh asymptotic notation, show that

10 = (2)

3. (This exercise is a variation of Exercise 2.7 in Chapter 2 of the textbook) For each of the following program fragments, determine the time complexity (Big-Oh).

(1) sum =0; for(i = 0; i < n; i++) sum++;

(2) sum =0; for(i = 0; i < n; i++)

for(j = 0; j < n; j++) sum++;

(3) sum =0; for(i = 0; i < n; i++)

for(j = 0; j < n*n; j++) sum++;

(4) sum =0; for(i = 0; i < n; i++)

for(j = 0; j < i; j++) sum++;

4. Consider the Bag interface given below. Write and test an ArrayBag class the implements the interface.

public interface Bag {

public boolean isEmpty(); public void print(); public void add(String s); public void remove(String s); public int count(String s); //counts occurrences of s in the bag

}

Guidelines

The assignment is to be completed individually. Questions are based on Week 1 and 2 content.

You are allowed to use all of the code given in the lectures (for example, the implementation of the methods of the ArrayList class). In those cases, make sure you properly credit its source.

Deliverables: A compressed folder, Assignment 1, containing

- three Java files: Bag.java, ArrayBag.java, and Main.java (Main is the class that tests the ArrayBag class)

- 2-3 screenshots of the running program

- A document with the answers to questions 1 through 3. Name your file asymptotic

notations, for example 1234567 asymptotic notations.docx.