5/16

Sing, Prayer

ANNOUNCEMENTS
================
* DML UG Research Assistant position available
* How is Boggle coming?

5.1 What is Algorithm Analysis?
5.2 Examples of Algorithm Running Times
5.4 General Big-Oh Rules
5.7 Checking an Algorithm Analysis
5.8 Limitations of Big-Oh Analysis


DISCUSSION & REVIEW
===================

5.3 The Maximum Contiguous Subsequence Sum Problem

Maximum Contiguous Subsequence Sum Problem
	Given a sequence of integers, find a subsequence that gives 
	the maximum sum

* show some code that solves it in cubic, quadradic, and linear time.

* Quadratic algorithms are impractical for input sizes exceeding a few thousand
* Cubic algorithms are impractical for input sizes as small as a few hundred

5.4 General Big-Oh Rules

The growth rate of a function is most important when N is sufficiently large
Big-Oh notation is used to capture the most dominant term in a function
		
Notes

		
[1]    for ( int i = 0; i < n; i++ )            O(N)
         sum++;

[2]    for ( int i = 0; i < n; i += 2 )         O(1/2 N) => O(N)    
         sum++;

[3]    for ( int i = 0; i < n; i++ )            O(N^2)
         for ( int j = 0; j < n; j++ )
            sum++;

[4]    for ( int i = 0; i < n; i++ )            O(2N) => O(N)
         sum++;
       for ( int j = 0; j < n; j++ )
         sum++;

[5]    for ( int i = 0; i < n; i++ )            O(N*N^2) => O(N^3)
         for ( int j = 0; j < n*n; j++ )
            sum++;

[6]    for ( int i = 0; i < n; i++ )            O(N * ((N-1)/2)) => O(N^2) 
         for ( int j = 0; j < i; j++ )
            sum++;

[7]    for ( int i = 0; i < n; i++ )            O(N * N^2 * ((N^2 - 1)/2)) => O(N^5)
       	 for ( int j = 0; j < n*n; j++ )
        	for ( int k = 0; k < j; k++ )
            	sum++;

Extra Information
http://www.leepoint.net/notes-java/algorithms/big-oh/bigoh.html