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.
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.
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)
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.
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.