### announcements

#### 2016-01-25 CRITICAL SURVEY

This is your final project exit quiz, it is a required part of your project. Complete this by the end of class unless you are absent, then complete it by the end of the day. You must be logged in to a gmail account to access the form: https://docs.google.com/forms/d/1jCGS73W-Q3ZGJK6xwmF8f8cz1TTS41BEZy_AiVgemaY/viewform?usp=send_form |

#### 2016-01-20

You should be well on your way to an amazing final project! Please let me know of any issues. Video Game + Charity Related (feel free to skip) Some of you may care: (since after finals you have some time to kill) Last year I found a game for free for my students, sadly XCOM is no longer free. However! at $1 you can get it and more at https://www.humblebundle.com/ |

#### 2016-01-19

Update your README.md file as you work. 1-Project Description 2-Directions to compile/run 3-Directions to use it. 4-Day by Day Changelog (Starting AFTER your demo-version) including : -each new feature -each new bugfix -each new bug introduced -goals for your next few updates. |

#### 2016-01-15

Submit group names/repos here: USE THE SSH LINK!!!! Do not paste https links. http://goo.gl/forms/uSDBkNCol9 |

#### 2016-01-14 Exam Review

2009 AP Computer Science Part II questions: -You should do 1,3,4. This is good practice in reading the questions. -Try to read/code each question in 20 minutes. -Here are solutions http://apcentral.collegeboard.com/apc/public/repository/ap09-comp-sci-a-canonicals.pdf I want feedback next week. Tell me if you think they are difficult/easy/impossible/etc. |

#### 2016-01-12

To Run processing: /tmp/processing-3.0.1/processing When you reboot, processing gets deleted, The script to install processing: /home/support/konstans/public_html/processing/extract.shREAD THE TEXT... DO NOT SKIM. If you copy the extract.sh file to your home directory, you can just run it like: ~/extract.sh |

#### 2016-01-07

Bubble sort issues: -reverse order has the most swaps and does the most work. -random order is slower however! (in practice there are hardware optimizations that make the if statements the bottleneck) Calendar: Final Project Start: 2016-01-07 Final Project Demo Commit: 2016-01-18 Final Project Final Commit: 2016-01-25 Final Exam: 2016-01-28 |

#### 2016-01-06 Testing Methods

public class Driver2{ public static void main(String[]args){ int size = 10000; String choice = "insertion"; String order = "random"; // reversed sorted if(args.length >= 1){ choice = args[0]; } if(args.length >= 2){ //pick number of elements size = Integer.parseInt(args[1]); } if(args.length > 2){ order = args[2]; } int[]ary = new int[size]; //default is random order Sorts.fillRandom(ary); if(order.equals("random")){ } if(order.equals("sorted")){ Arrays.sort(ary); } if(order.equals("reversed")){ Arrays.sort(ary); for(int i = 0; i < ary.length / 2; i++){ Sorts.swap(ary,i,ary.length-i-1); } } long start = System.currentTimeMillis(); if(choice.equals("bubble")){ Sorts.bubbleSort(ary); } if(choice.equals("insertion")){ Sorts.insertionSort(ary); } if(choice.equals("selection")){ Sorts.selectionSort(ary); } long end = System.currentTimeMillis(); System.out.println("Time:"+ (end-start)/1000.0 + " seconds. Size = "+ary.length); } } echo ---------------- echo -Insertion echo ---insertion random java Driver2 insertion 20000 random java Driver2 insertion 40000 random java Driver2 insertion 80000 random echo ---insertion sorted java Driver2 insertion 20000 sorted java Driver2 insertion 40000 sorted java Driver2 insertion 80000 sorted echo ---insertion reversed java Driver2 insertion 20000 reversed java Driver2 insertion 40000 reversed java Driver2 insertion 80000 reversed echo ---------------- echo -Selection echo ---selection random java Driver2 selection 20000 random java Driver2 selection 40000 random java Driver2 selection 80000 random echo ---selection sorted java Driver2 selection 20000 sorted java Driver2 selection 40000 sorted java Driver2 selection 80000 sorted echo ---selection reversed java Driver2 selection 20000 reversed java Driver2 selection 40000 reversed java Driver2 selection 80000 reversed |

#### 2016-01-05 Sorts.java

Lets say we have the array: [1 , 2, 9, 5, 0, 3] Selection sort: Each pass finds the correct element for the next slot. Each line represents a completed outer loop: [1 , 2, 9, 5, 0, 3] starting array [ 0 , 2, 9, 5, 1, 3] swapped 0 and 1[ 0 , 1, 9, 5, 2, 3] swapped 1 and 2[ 0 , 1, 2, 5, 9, 3] swapped 2 and 9[ 0 , 1, 2, 3, 9, 5] swapped 5 and 3[ 0 , 1, 2, 3, 5, 9] swapped 5 and 3Done. Insertion sort: Each pass places the next element in the correct spot Each line represents a completed outer loop: [ 1 , 2, 9, 5, 0, 3] starting array assume 1 is sorted[ 1 , 2, 9, 5, 0, 3] 2 is in the correct place compared to 1. Now 1,2 are sorted[ 1 , 2, 9, 5, 0, 3] 9 is in the correct place compared to 1 and 2, now 1,2,9 are sorted.[ 1 , 2, 5, 9, 0, 3] Shift 5 into the correct place, now 1 2 5 9 are sorted.[ 0, 1 , 2, 5, 9, 3] Shift 0 into the correct place, now 0 1 2 5 9 are sorted[ 0, 1 , 2, 3, 5, 9] Shift 3 into the correct place, now 0 1 2 5 9 are sortedDone. Bubble Sort: loop from start to end, pushing up the values that need to "bubble" to the top. Since bubble sort needs to be explained a bit more here is step by step: Each "pass" is the outer loop. This is indicated in blue to be clear. Each line of each pass is the inner loop. Start with: [1 , 2, 9, 5, 0, 3] Outer loop 1st pass: 1 and 2 are fine 2 and 9 are fine 9 and 5 need to be swapped [1 , 2, 5, 9, 0, 3] now 9 and 0 need to be swapped [1 , 2, 5, 0, 9, 3] now 9 and 3 need to be swapped [1 , 2, 5, 0, 3, 9] Now the last element is in the correct place! Don't loop that far anymore [1 , 2, 5, 0, 3, 9]2nd pass 1 and 2 are fine 2 and 5 are fine 5 and 0 need to be swapped [1 , 2, 0, 5, 3, 9] 5 and 3 need to be swapped [1 , 2, 0, 3, 5, 9] Now the last two elements are in the correct place! Don't loop that far anymore [1 , 2, 0, 3, 5, 9]3rd pass 1 and 2 are fine 2 and 0 swap [1 , 0, 2, 3, 5, 9] 2 and 3 are fine Now the last three elements are in the correct place! Don't loop that far anymore [1 , 0, 2, 3, 5, 9]4th pass: 1 and 0 need to swap [0 , 1, 2, 3, 5, 9] 1 and 2 are fine Now the last four elements are in the correct place! Don't loop that far anymore [0 , 1, 2, 3, 5, 9]5th pass 0 and 1 are fine Now the last five elements are in the correct place! Don't loop that far anymore [0 , 1, 2, 3, 5, 9]We are done! |

#### 2016-01-04

Baron's Review Here: http://marge.stuy.edu/~konstans/(slightly dated, but most of the stuff is super effective) Big O notation is used to measure the runtime of functions as the input grows. When a function is O(n) that means that when you increase the input size, the runtime increases in a linear fashion. Double input size means double* the runtime . When a function is O(n^2) that means that when you increase the input size, the runtime increases in a quadratic fashion. Double input size means FOUR times* the runtime. O(c^n) is exponential. Increase the input size by one, and the runtime increases by a factor of c times*. * All of these can be off by a constant factor that we don't care about, as long as the pattern holds. So if you double the input and it triples the runtime, that is still linear. Also note that two data points are not sufficient to determine the runtime growth. We really need 3 or more data points to see. Formal Definition: Lets think of x as the input size of a function. You can say f(x) is O(g(x)) as x approaches infinity IF AND ONLY IF: There exists some positive real constant M such that: f(x) <= M * g(x) Think of and f() and g() as the amount of work the function does, not the result of the actual function. (we simplify g(x) in terms of a function of n as follows) 3x^2 is O(n^2) 230x is O(n) 5*2^x is O(2^n) Remember we do NOT care about constants! 4x is still O(n) Big O examples and more text: https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/ |

1-10 of 61