October 28th, 2015

Classroom Salon: Video 2.3: Order of Growth

Visit edmodo.com:
1.
Quiz
How many accesses does the following code fragment make as a function of N?
(Assume the compiler does not optimize away any array accesses int eh innermost loop)

int sum = 0;
for (int i = 0; i < N ; i++ )
---> for (int j = i + 1; j < N ; j++ ) 
--------> for (int k = 1; k < N ; k = k*2 )
------------> if ( a[i] + a[j] >= a[k]) sum++;

~3N^2
~(3/2)N^2 lgN
~(3/2)N^3
~3N^3

2.
Proposition: Binary search uses at most 1 + lgN compares to search in a sorted array of size N.
Def. T(N) = # compares to binary search in a sorted subarray of size <= N. Binary search recurrence. T(N) <= T(N/2) + 1 for N>1, with T(1) = 1
Give an example to show
T(N) <= T(N/2) + 1 for N>1, with T(1) = 1
Show how 1 + 1 + … + 1 become 1 + lg N

3.
Write a program, YI_Better3Sum.java, so its order of growth is N^2 log N

4.
Create a table to compare the execution run time from the original 3-Sum and the Better3Sum.

October 27th, 2015

Classwork:
Classroom Salon: Video 2.2 Analysis of Algorithms. Mathematical Models. Answer questions, reply to postings, add to posting and vote on answers.
Make sure you have a full set of answers in edmodo.com based on what you learned through the classroom salon discussions on this video.

1. What is defined as Cost of basic operations?
2. What operations would have a constant cost?
3. What operations would have proportional cost?
4. What operations would have N and N^2 cost?
5. what is the frequency of the instructions in the 1-Sum program?
6. How is the frequency of instructions in the 2-Sum different from the 1-Sum?
7. What is the tilde notation?
8. What are the tilde functions for the 2-Sum and the 3-sum?
9. Approximately how many array accesses as a function of input size N for the 3-Sum program?
10. Explain with simplify notation the three examples given for estimating discrete sum.

Homework:
1. Complete work
2. Show mathematically how T(N) is equal to 20.5 seconds when N = 64,000.

October 8th, 2015

An immutable data type has the property that the value of an object never changes once constructed.

An assertion is a boolean expression that you are affirming is true at that point in the program.

Use Creative Problem Rational numbers as a template to implement Complex.java as an immutable data type that supports addition, subtraction, and multiplication.

Challenge: implement the division operation.

Homework:
Read more on Asserstions and Inmutability.

Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, Addison-Wesley Professional, 2011, ISBN 0-321-57351-X