Ruby in 100 Minutes

####string gotcha

Ruby can’t do string + num

Use .to_s to get around it

Or maybe use this:

number = 4
puts "print a number: #{number}"

####Symbols

• Starts with a colon then one or more letters
• Less methods than Strings

####Iterating

Use times method to repeat an instruction

5.times do
  ...
end

####Arrays

• Return nil when index out of range
• << operator for appending a signle element
• Elements don’t need to be of same type

####Hashes

• { key => value ... }
• methods: keys, values

• simplified syntax when all keys are symbols:

  { symbol: value ... }

  (for Ruby 1.9 and higher)

####Conditionals

method name ending in a ?: return true or false

####chomp

• get rid of the Enter
• gets.chomp

####exponentiation

**

5**2

####random

• rand(1) always produce 0
• rand(101): 0-100
• srand
• srand 0 seed with current time in ms

####block as a parameter

• precede the parameter with an ampersand(&)

####global variable

• preced the variable with $

DoCP: Lesson 2

####Happy Valley

• Happy: millions
• Maybe: billions
• Sad: trillions

####Python “is” operator

is: same object ==: structurally identical

####Aspects

• Correctness
• Efficiency
• Debugging

####List comprehensions ####List comprehensions

####Aspect-oriented programming

seperate out different aspects as much as possible

####Generator expressions

####Generator Functions

####Law of Diminishing Returns

Max Flow and Parallel Algorithms

###Problem 1

• Enforcing $\leq max$ constraint:

              o --------- o
       max   /             \
    s ----- o ----- o ----- t
  

###Problem 2

Edmonds-Karp algorithm - Compute maximum flow efficiently

###Problem 3

• Enforcing $\geq min$ constraint:

              o ----- o
       >=min /         \
            s           t
     sum-min \         / 
              o ----- o
  

###Problem 4

non-zero-sum game is weird

###Problem 5

• In the end, you’ll inevitably hit the bottleneck, one or another.
• In this problem, the bottleneck is memory bandwidth

Linear Programming

###Problem 1

• Dual gives an lower bound on how you can minimize it, proving the primal

###Problem 2

• $y=\lvert x\rvert$ is not a convex region, but $y\geq\lvert x\rvert$ is!
• Introducing extra variables for constraints is a very useful technique

###Problem 3

Integral constraints naturally guarantee that the variables are integers

###Problem 4

Another method for convex optimization: Recursive Golden Selection

###Relation with optimization

• Linear programming relaxation gives a lower bound of OPT
• Optimization gives an upper bound of OPT
• They are approaching OPT from different direction
• relaxation -> OPT <- optimization

NP Hardness

• Only a small tweak to the problem will make a huge difference(1->2)
• Decision problem is easier to phrase and solve than search problem, but in NP sense, they are tantamount

###Problem 1

• The divide between NP and P is hard to find
• Greedy algorithm sometimes is pretty good, it can be simple, efficient and correct(or approximately correct)

###Problem 2

• The idea of using greedy algorithm to get approximate solution of NP hard problem
• Find some subset violating the rules, forbid all of them instead of carefully determine(time-consuming) which is the OPT
• Find special structure of the problem and do something about it

###Problem 3

• Make sure the dictionary length is different, or it won’t work
• When trying to reduce from a NP problem to your problem, usually you only get to reduce to a specific instance of your problem. But you don’t know if your problem is overall equally hard
• The guarantee that all instances of the problem is equally hard is what cryptography is looking for

###Problem 4

Duplicate the constraint