## Naive Fibonacci Algorithm

``` public static long fib(int N) {
if (N == 0) return 0;
if (N == 1) return 1;
return F(N-1) + F(N-2);
}```

## Dynamic Programming – Recursion + Memoization

Dynamic Programming – careful brute force, break it into sub problems, solve the sub problems and reuse the solution.  Richard Belman invented Dynamic Programming as a means to explain mathematical research he was conducting.

Naive recursive algorithm as above, exponential time, running time as recurrance:

```T(n) = T(n-1) + T(n-2) + O(1)
T(n) >= 2T(n-2)
which is of the order of 2 to the power of n/2
```

Memoized DP algorithm:  if we need to compute fib(n), if n in memo, return memo[n], else compute fib(n) and store it.  memo is initially an empty dictionary.  Then fib(k) only recurses the first time it’s called for all k.  Memoized calls cost constant time.  Number of non-memoized calls is n, non recursive work per call is constant.  Therefore running time is linear  The best algorithm for calculating Fibonacci numbers is time proportional to log(n).

```# best time achieved by resolving subproblems in advance
fib = {}
for k in range(1, n+1):
[ if k<= 2: f=1
[ else: f=fib[k-1] + fib[k-2]
fib[k]:f
return fib[n]```

```import java.util.HashMap;

public class Fibonacci {
static HashMap<Integer, Long> fibMap =
new HashMap<Integer, Long>();

// for n >= 1
public static long fib(int n) {
if (n <= 2) return 1; // quicker than lookup
// look up in map, returns null if key doesn't exist
if (fibMap.containsKey(n)) return fibMap.get(n);
long f = fib(n-1) + fib(n-2);
// store new fib in map
fibMap.put(n, f);
return f;
}

public static void main (String[] args) {
for (int i = 0; i < 92; i ++) {
System.out.println(i + " : " + fib(i));
}
}
}```

## Princeton Algorithm Courses

One of the problems I had with setting up the jar file algs4.jar was that the `CLASSPATH` variable needs to include the directory where your Java programs .class file is. You can include ‘.’ in `CLASSPATH` to indicate that the current directory should be included.  Then I followed the instructions on the book site. and modified my .bash_profile as follows.

```# Add algs.jar to classpath
set CLASSPATH=.
export CLASSPATH=\$CLASSPATH:~/algs4/algs4.jar```

## Interesting Tricks

``` // int N to binary representation
String s = "";
for (int n = N; n > 0; n /= 2)
s = (n % 2) + s;

// log base 2
public static int lg(int N) {
if (N/2 == 1) return 1;
return 1 + lg(N/2);
}```

## Recursive Algorithms

A method can call itself.  There are three important rules of thumb in developing recursive programs:

1. The recursion has a base case – always includes a conditional statements as the first statement in the program that has a return.
2. Recursive calls must address subprograms that are smaller in some sense, so that recursive calls converge to the base case.
3. Recursive calls should not address subprograms that overlap.

### Greatest Common Divisor

Euclid’s Algorithm – compute the greatest common divisor of two nonnegative integers p and q as follows: If q is 0, the answer is p.  If not, divide p by q and take the remainder r.  The answer is the greatest common divisor of q and r.

```public static int gcd(int p, int q) {
if (q-==0) return p;
int r = p % q;
return (gcd(q, r);
}```

### Binary Search

```// recursive implementation of binary search
public static int rank(int key, int[] a0) {
return rank(key, a, 0, a.length -1);
}

public static int rank(int key, int[] a, int lo, int hi) {
// index of key in a[], if present is not smaller than lo,
// and not larger than hi
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) return rank (key, a, lo, mid -1);
else if (key > a[mid]) return rank (key, a, mid + 1, hi);
else return mid;
}```

### Simple Mathematical Functions

``` // log base 2
public static int lg(int N) {
if (N/2 == 1) return 1;
return 1 + lg(N/2);
}

// natural logarithm of n factorial
// ln(xy) = ln (x) + ln (y)
public static int lnFact(int n) {
if (n == 1) return 0;
return Math.log(n) + lnFact(n-1);
}

//  n factorial
public static long nFact(int n) {
if (n == 1) return 1;
return n * nFact(n-1);
}```

## Steps in drawing out the recursive call.

How to write a method that calls itself. https://www.youtube.com/watch?v=MyzFdthuUcA – Dave Feinberg’s video series.

1. Write “if”.
There must be at least 2 cases:, a recursive case (where the method calls itself) and a base case (where the method does not).
2. Handle the simplest case(s). “Base Case”
Simplest = no recursive call needed (no further loop)
3. Write the recursive call(s).
On the next simpler input/state, it may help to store the recursive call
4. Assume the recursive call works .
Ask yourself: What does it do?
Ask yourself: How does it help?

## Factorial

### Base Case

If n! is defined as the product of all positive integers from 1 to n, then:
1! = 1*1 = 1
2! = 1*2 = 2
3! = 1*2*3 = 6
4! = 1*2*3*4 = 24

n! = 1*2*3*…*(n-2)*(n-1)*n
and so on.
Logically, n! can also be expressed n*(n-1)! .

Therefore, at n=1, using n! = n*(n-1)!
1! = 1*0!
which simplifies to 1 = 0!

### Java Recursive Factorial Method

```// precondition: n >= 0
public static in fact(int n) {
if (n=0) return 1;
else return fact(n-1) * n;
}

```

## Good Coding Practice

3 key principles of good code include being reusable, maintainable and easy to change.  There are numerous ways to uphold and ensure these principles.

## Steps to Writing Error-free Code

• Understand the difference between syntax errors and logic errors.  Syntax involves the ‘spelling and grammar’ of programming, these are generally picked up by compilers.  Check your variable names, brackets and punctuation.  Autocomplete in modern IDEs helps reduce syntax errors.
• Syntax errors that are more like semantic errors are harder to spot and will not be picked up by a compiler, for example when you type the wrong variable name by mistake, you could then end up with the wrong answer.   It is helpful to use meaningful names for your variables and functions.
• Logic errors often lead to unexpected results, and are seldom caught by a compiler.  They can come about when statements are executed in the wrong order, incorrect boolean expression and decision points, wrong data types, etc.  To eliminate logic errors, it helps to write out pseudocode before you start coding to help get the sequence right.  Check that against the specification, are you doing what you’re supposed to be doing?
• Document code clearly, it helps keep code easy to read and understand, especially when it comes to debugging.  It is easier to spot bugs in well organised code.  When you come back to your code, it will be easier to know how it works. Using a coding convention helps get the balance of white space right. This helps with code readibility.
• Initialise variables, consider the boundary cases of data types chosen.  Avoid mutable variables and consider the use of null values carefully.  A method on call on null will result in a runtime exception.  Consider array indices and use flexible data structures if required.
• Write modular code that can be tested in isolation so that the source of errors can be identified more easily.  This is improved with abstraction and encapsulation which together enables unit testing.
• Error avoidance by checking preconditions/requirements are met on the client side, only execute the code if the precondition is true,  isResourceAvailable(), if returns true then proceed.  But this isn’t always reliable, the client can’t always be trusted.

## Exceptions – defensive programming

Defensive programming assumes that the client can’t be trusted and checks argument values.  Exceptions, used correctly help software be robust and recover from errors at run-time.  Run-time errors are often related to the environment or resources, URL changed, network down, file deleted, printer switched off… These cannot be anticipated, but can be recovered from by handling the exceptions appropriately.  It should not fail silently, outputting  a message or code may not be seen or understood.  Thowing an exception means that classes can be more cohesive and leave other classes to fix problems that are in their domain, e.g. leave I/O to classes concerned with I/O.  Otherwise you bind functionality to technology, which may soon be out of date.

An Exception is a software signal which can be thrown or raised and also caught and handled, either in the same method or higher up.  There are loosely three categories, Checked Exceptions (have to be caught or specify method may throw them, Unchecked Exceptions (often a bug in the program, not obliged to catch them) and Runtime Exceptions.  Checked in this context means that the compiler checks to see that you catch or throw these exceptions, e.g. FileNotFoundException.

## Installing Kippo

Note, Kippo requires an older version of python twister.  It fails to start if twister 16.x is installed.  All worked fine with version 14.02.

```sudo apt-get install python-mysqldb mysql-server apache2
git clone https://github.com/desaster/kippo.git```

Create a database called kippo, and database user called kippo.  Then add some the necessary database tables.

```mysql -u root -p  // enter root user password
create kippo;
GRANT ALL ON kippo.* TO 'kippo'@'localhost' IDENTIFIED BY '**';
mysql -u kippo -p // enter database user password
use kippo;
source mysql.sql;
show tables;```

Copy the sample kippo.cfg file and uncomment and edit the lines relating to [database_mysql].  Then create a user to start kippo, and grant the user access to the folder.

```# edit kippo.cfg as follows
[database_mysql]
host = localhost
database = kippo

# kippo cannot be run as root user
useradd -d /home/kippo -s /bin/bash -m kippo -g sudo
# grant kippo user privileges
chown -R kippo /usr/local/src/kippo/```

Owing to some issues, install python twisted manually.

```sudo apt-get install python-dev python-pip
cd /tmp
wget https://github.com/twisted/archive/twisted-14.0.2.tar.gz
cd twisted-twisted-14.0.2/
./setup.py install
su kippo cd /usr/local/kippo/
./start.sh
# to stop kippo, try to restart it, then kill the pid```

The root password for the kippo honeypot is 123456, change this by editing the /kippo /data/userdb.txt file and restarting kippo.

Kippo defaults to listen for SSH connections on port 2222.  Using iptables, direct all connections to port 22 to kippo which is listening on port 2222, then direct set the default port for SSH to a different port.

```apt-get install iptables
iptables -t nat -A PREROUTING -p tcp --dport 22 -j REDIRECT --to-port 2222
iptables-save > /etc/iptables.rules
# set the default port for ssh to 65534
sed -i 's:Port 22:Port 65534:g' /etc/ssh/sshd_config
# restart ssh
/etc/init.d/ssh restart```

## Kippo-Graph

While I’ve followed the steps to install KippoGraph, it is currently throwing an exception originating in rb.php:761, so for now I’m just looking at the logs via script files.