announcements

2016-01-25 CRITICAL SURVEY

posted Jan 25, 2016, 3:39 AM by Samuel Konstantinovich   [ updated Jan 25, 2016, 3:41 AM ]

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

posted Jan 20, 2016, 6:19 AM by Samuel Konstantinovich   [ updated Jan 20, 2016, 6:19 AM ]

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

posted Jan 19, 2016, 6:25 AM by Samuel Konstantinovich   [ updated Jan 19, 2016, 6:25 AM ]

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

posted Jan 15, 2016, 8:59 AM by Samuel Konstantinovich   [ updated Jan 15, 2016, 8:59 AM ]

Submit group names/repos here:

USE THE SSH LINK!!!! Do not paste https links.
http://goo.gl/forms/uSDBkNCol9

2016-01-14 Exam Review

posted Jan 14, 2016, 9:15 AM by Samuel Konstantinovich   [ updated Jan 14, 2016, 9:15 AM ]

2009 AP Computer Science Part II questions:

http://apcentral.collegeboard.com/apc/public/repository/ap09_frq_computer_science_a.pdf

-You should do 1,3,4. This is good practice in reading the questions. 
-Try to read/code each question in 20 minutes. 

I want feedback next week. Tell me if you think they are difficult/easy/impossible/etc.




2016-01-12

posted Jan 12, 2016, 9:28 AM by Samuel Konstantinovich   [ updated Jan 12, 2016, 9:29 AM ]


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.sh

READ 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

posted Jan 7, 2016, 6:28 AM by Samuel Konstantinovich   [ updated Jan 7, 2016, 8:52 AM ]

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

posted Jan 6, 2016, 9:31 AM by Samuel Konstantinovich   [ updated Jan 6, 2016, 9:35 AM ]

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

posted Jan 5, 2016, 6:55 AM by Samuel Konstantinovich   [ updated Jan 5, 2016, 6:55 AM ]

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 3
Done.


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 sorted
Done.

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

posted Jan 4, 2016, 7:20 AM by Samuel Konstantinovich   [ updated Jan 4, 2016, 7:56 AM ]

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