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.