| 
  • If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.

  • Stop wasting time looking for files and revisions. Connect your Gmail, DriveDropbox, and Slack accounts and in less than 2 minutes, Dokkio will automatically organize all your file attachments. Learn more and claim your free account.

View
 

Assignment 2 - Time Complexity

Page history last edited by Dr. Ron Eaglin 3 years ago

Assignment 2 - Time Complexity

 

Objectives

 

1. Learn the concept of complexity and Big-O Notation

2. Analyze algorithms to determine the time complexity

3. Code simple algorithms and evaluate their complexity

 

Supports: Outcome 4 -  Analyze the performance of algorithms and data structures. 

 

Summary

 

Time complexity is measured using a notation known as Big-O notation. This is covered in depth at http://en.wikipedia.org/wiki/Big_O_notation and also within the textbook. In Big O analysis you must determine the complexity of an algorithm and determine how it performs as the sample size of the data it performs an operation on increases towards infinity.

 

Lectures

 

Complexity is covered in section 2.1 of the lectures, please get familiar with the lectures at -  All Course Lectures -

 

Lecture 2.1 -Big-O Notation and Complexity (Brightcove | Youtube ). In addition you will need to get started with using lists and arrays which is covered in Lecture 2.2 (Lists and Arrays).

 

In addition there are some  very good lectures out there that go into more depth and different aspects of time complexity;

 

Additional: Time complexity of a computer program (Youtube)

 

 

Assignment

 

For assignments 1 and 2 your Big-O notation and justification will be written in the html section of JSFiddle. Lecture - Javascript Basics - Inserting into an Array covers some useful information on the basic Javascript needed for this assignment. You will be using the Javascript array

 

Programming Assignment Part 1 -

 

Using your JSFiddle account and JavaScript you will create a program that will instantiate an integer array of a specified size. Fill each array element with a random integer between 1 and 100. You will need to research the random function to do this.

 

You will write a function with 3 arguments. The name of the function will be InsertIntoArray. Argument 1 is the array, argument 2 is the index of where you are going to insert a new number, argument 3 is the number to insert. The program should insert the new number at the index given and shift all the previous entries index up by 1. Since the array is capped at 1000, the highest element of the array will be deleted. Count the number of operations performed on the array and output this to the screen. An operation is if you assign a value or compare a value - only compare or assign operations should be counted.

 

Change the array size to 100 and insert into a different index in the array. State using Big O Notation your time complexity and be prepared to justify your answer.

 

Programming parameters:

 

1. Create the array in Javascript: var array = new Array(1000);

2. Create a loop to assign each array element a random value.

3. Do not use push or splice commands - assign elements by writing the code to perform all operations

4. When inserting you will be pushing the last value off the end of the array (everything shifts right)

5. Use a global counter to count every time you make an assignment (use an = or == operator)

 

Programming Assignment Part 2 - Using your JSFiddle account and Javascript you will create a program that will instantiate an integer array of a specified size. Fill each array element with a random integer between 1 and 100. You will need to research the random function to do this. Do NOT sort the array. You can use the same code as Part 1 to create the array. In fact you can achieve both Assignment 1 and Assignment 2 with a single program.

 

You will write a function with 2 arguments. The name of the function will be SearchArray. Argument 1 is the array, argument 2 is the value you are searching for within the array. Each time the program compares 2 numbers you must count it as an operation (only count comparisons). Output the total number of operations to find the first occurrence of the number searched or value not found. State using Big O Notation your time complexity and be prepared to justify your answer. This should be output in your actual JSFiddle.

 

Hints: The best way to do this is to have an input box for number of elements in the array, value to insert or search, location to insert . Then 3 buttons; "Create Array", "Insert Into Array",  "Search Array".

 

Sample Input

 

Enter Array Size:

Enter Location: Enter Value to Insert:

Enter Value to Find:

 

 

Sample Output

 

 

Array output:

11,64,39,97,69,28,94,49,31,45,9,29,65,53,31,58,100,81,79,24,99,27,39,58,35,39,10,24,98,26,84,70,42,93,17,69,69,17,12,4,21,

75,86,25,82,32,69,21,42,24,42,100,61,25,97,60,12,100,40,40,10,75,78,86,25,3,11,65,44,17,35,4,78,77,53,5,53,18,19,26,31,51,

6,68,58,49,54,27,58,6,98,51,79,21,32,38,34,35,83,70

 

Value 99 inserted at location 20 - there were 80 operations performed in this insertion

 

The time complexity of this algorithm is  _______

 

Value 99 found at location 20 - there were 20 comparison operations performed in this search  

 

The time complexity of this algorithm is ______ 

 

 

Assignments Grading Criteria

 

For both programming assignments, Javascript code that uses the push or splice commands will not be accepted. You must hand code the both assignments using only primitive operations (+ , = ). If you have questions about what operations are legal post your questions to the bulletin board. You must complete both programming assignments and  the quiz to receive credit. The quiz is worth 2/10, each program is worth 4/10 and must be fully functional for credit.

 

More Information

 

There are some wonderful resources out there to help you get better at algorithms and complexity. I am listing some of them here, most were submitted by students on the class discussion boards.

 

 

All COP3530 Assignments

 

 

 

 

 

 

Comments (0)

You don't have permission to comment on this page.