Question
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
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,
- 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
notations, for example 1234567 asymptotic notations.docx.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started