The sorting spreadsheet

has been uploaded to BlackBoard, so check it out.

lecture notes

Bubble Sort, Selection Sort
O(n^2)
as n got really big, problem couldn't be solved in our lifetimes

analyze algorithms

Insertion Sort, also, modification of radix sort

http://en.wikipedia.org/wiki/Insertion_sort
also O(n^2)

modification of radix sort
call range of the numbers m
O(n + m)

if n is a billion
and m is a billion

analyze algorithms to choose appropriate method

http://www.claymath.org/millennium/


traveling salesman problem

generate all possible permutations of cities
then add up cost of all roads
find the minimum
for four cities, 4!
4 x 3 x 2 x 1


what if i have 100 cities?

how many perms? 100!

2^100 < 100!

http://en.wikipedia.org/wiki/Traveling_salesman_problem

von Neumann architecture
not able to solve it


multiprocessor machines
distributed computing

http://en.wikipedia.org/wiki/DNA_computing
http://en.wikipedia.org/wiki/Quantum_computing

HTML
http://www.w3schools.com/html/html_formatting.asp

gradual move from marking up formatting explicitly to marking up meaning
we'll see more in CSS (cascading style sheets)

font tag
deprecated
instead, we use CSS
style

notes from lecture

Two point curve for the latest lab section
No curve for other section

fear not! there will be other quizzes

computer concepts
___________________
algorithm - like a recipe

task: take a bunch of nums, in any random order, and make them appear in ascending order
Bubblesort
Selection sort
Insertion sort

As the cardinality of numbers get really big, time to carry it out can get out of control
Analysis of Algorithms


Bubblesort: "Are they in the right order?"
if yes, leave alone. if no, swap
http://en.wikipedia.org/wiki/Bubblesort

How long will Bubblesort take? in worst scenario, best, average?
thinking about worst
we have N numbers we want to sort
how many operations will it take?

O(n^2)
10 x 10 == 100

hertz
kilahertz
megahertz
gigahertz

2.8 gigahertz
that's a lot

1 million numbers

Moore's Law

selection sort: "scan for the smallest number and put it into the correct position"
we do less swaps, but still is O(n^2)
http://en.wikipedia.org/wiki/Selection_sort

understand the animations at Wikipedia

x is pos in array (in the collection)
y is size of the number

check BlackBoard soon for the Excel spreadsheet from class

notes

We will make our very *first* program!
adding program

what did I do?
Drew the GUI. Changed the fornt size and other properties of the controls. Changed the name property of a bunch of controls.

at run time, to get access to the properties of a control, we use the . operator

Private Sub cmdCalculate_Click()
    Dim x As Integer
    Dim y As Integer
    Dim z As Integer
    x = txtFirstNumber.Text
    y = txtSecondNumber.Text
    z = x + y
    lblOutput.Caption = z
End Sub

HW: Take as input the Title, FirstName and LastName. Calculate FullName and Display it.

VB or VBA programming


Excel
Relative references, Absolute references, Mixed References
A1 style vs R1C1 style

Relative references change when you copy them

Absolute references stay put
Mixed References: row absolute, column relative
OR
column absolute, row relative


R1C1 stands for row 1 column 1

notes from lecture

CS12

making a web page using WinSCP

first, using notepad
c:\josh\webpage1.html

how do we specify path?
1) full path
c:\josh\subfolder\cow3.jpg
2) relative path
./subfolder/cow3.jpg
../parallelfolder/cow3.jpg
3) we can store it in the same folder
cow3.jpg
4) you can specify a URL
http://co2calculator.files.wordpress.com/2008/09/grazing-cow-1b.jpg

this is called hotlinking. NOT a nice thing to do. and dangerous.

you can host it yourself. or you can get web site hosting from elsewhere

we have:
cs12.cs.qc.cuny.edu/~yourloginname

file transfer protocol, ftp
WinSCP
for Macs (Fugu)

WinSCP lets you edit in place

create a new HTML file using WinSCP
first, create a folder called public_html

venus.cs.qc.cuny.edu/~joshwaxman/cowpic.html

chmod

VB
Dim varName as Integer

Assignment statement
varName = 7
varName = 9
that is why it is called a variable
its value varies over time

MsgBox is an output statement

Private Sub CommandButton1_Click()
    Dim TaxRate As Double
    TaxRate = 0.078
    MsgBox TaxRate
    TaxRate = TaxRate + 0.05
    MsgBox TaxRate
End Sub

notes

Microsoft DOS
it was a "Disk Operating System"
it used a command prompt instead of GUI
cmd

command prompt

A, B were floppy disks
C was typically hard drive

backslash is the root folder

commands:
tree
c:
dir
dir *.xlsx
cd
cd josh
cd .
cd ..
md
mkdir

BATCH file

three letter palindrome
<([A-Za-z])[A-Za-z]\1>

101
1010
10100

bitshift

VB programming
variable
has name, address, value, data type
declare a variable
Dim TaxRate As Double
double is the data type
7.45 is a double

7 is an integer
"hello there" is a string

Private Sub CommandButton1_Click()
    Dim TaxRate As Double
End Sub

notes

Download and Install WinSCP

webserver
cs12.cs.qc.cuny.edu/~login

username: first two letters of last, first two letters of first name, last 4 digits of SSN
password: all digits of ssn

username: wajo6789
password: 123456789

for Mac, download Fugu instead

HTML
HyperText Markup Language

w3schools.com

markup tags
a is for anchor

read up until HTML attributes

save as DOTM
right click on your own file, rather than Normal, and add the UserForm

write the codebehind
event handler
write VBA syntax
write VBA code to handle these event


input statements
output statements
processing statements

MsgBox is an output statement

Excel
formula auditing
name box to name specific cells

try to login