Category Archives: Lesson

AOA: function of N

October 28th, 2015

Screen Shot 2014-10-12 at 11.03.54 PM

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.

AOA: Mathematical Models

October 27th, 2015

Screen Shot 2014-10-12 at 11.03.54 PM

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.

AOA: Observations

October 26th, 2015

Screen Shot 2014-10-12 at 11.03.54 PM

Classwork:
Classroom Salon: Video 2.1 Analysis of Algorithms. Observations. 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.

Forum questions and concepts:
1. What is the process used to determine the running time for ThreeSum program?
2. What is the shape of the plot of size versus running time?
3. What is the purpose of finding the log of both variables, size and running time?
4. What is the importance of the regression line?
5. What mathematical model is represented by this regression line? In other words, if you find the inverse of this transformation, what mathematical expression do you get?
5. What is T(N)?
6. What is the Doubling Hypothesis?
7. What are the key effects of the running time of a program?
8. What are the system dependent effects?
9. What do these two types of effect determine in your mathematical model?

Homework: Complete work

Data Abstractions: Rational numbers

October 8th, 2015

Screen Shot 2014-09-15 at 8.43.34 PM

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

Heaps and Heaps Sort

October 6th, 2015

Heaps and Heap Sort

Screen Shot 2015-10-08 at 1.14.31 PM

Homework:
1. Draw the max-heap that results from adding the following integers (34 45 3 87 65 32 1 12 17).
2. Starting with the resulting tree from Exercise 11.1, draw the tree that results from performing a removeMin operation.
3. Starting with an empty minheap, draw the heap after each of the following operations:
addElement(40);
addElement(25):
removeMin();
addElement(10);
removeMin();
addElement(5);
addElement(1);
removeMin();
addElement(45);
addElement(50);

Iterator and ReverseArrayIterator

September 30th, 2014

Classwork:
Visit the Classroom Salon
1. How does an iterator compare to a for each construct?
2. What must a collection implement to an iterable collection?
3. What methods must the Iterator class include? Elaborate your answer.
4. What mechanism does java use to enable/enforce the implementation of these methods?
5. Why are Iterators generic?
6. How is the ReverseArrayIterator implemented?
7. What is an iterator?
8. What is the implementation of the Iterator interface?
9. How is the ReverseArrayIterator implemented?
10. Why are the methods implemented in a nested class within client classes?
11. What two cases should throw exceptions to conform to the Iterator specification?
12. Why aren’t these two exceptions implemented?
13. Is it necessary to import Iterable? Iterator?

Homework:
Write a stack client Parentheses.java that reads in a text stream from standard input and uses a stack to determine whether its parentheses are properly balanced. For example, your program should print true for [()]{}{[()()]()} and false for [(]).

Spanning Trees

May 26th, 2015

Screen Shot 2015-05-25 at 10.13.16 PM

Screen Shot 2015-05-25 at 10.13.26 PM

Definition:

Given an undirected edge-weighted graph, a spanning tree of a graph is a connected subgraph with no cycles that includes all the vertices. A minimum spanning tree (MST) of an edge-weighted graph is a spanning tree whose weight (the sum of the weights of its edges) is no larger than the weight of any other spanning tree.

Reading assignment:
Assumptions, Underlying principles, Proposition(Cut property), Proposition (Greedy MST algorithm), and Edge-weighted graph data type.

Homework:
1. How would you find a maximum spanning tree of an edge-weighted graph?
2. Minimum bottleneck spanning tree. A minimum bottleneck spanning tree of a weighted graph G is a spanning tree of G such that minimizes the maximum weight of any edge in the spanning tree. Design an algorithm to find a minimum bottleneck spanning tree.