Local (in time) versus long term optimal decision making

Locally optimal decision making: measured with tests where questions take only a few minutes to solve

Longer term optimal decision making: difficult to measure with a test at all

Having a child is pressing the reset button

When your life is like a painting that has so much in it that it can't really be changed rationally anymore... not that it's right or wrong... it's just sort of a certain way, probably lots of mistakes, the child is a fresh canvas where a new painting can arise, with much more foresight, assuming the kid actually listens to parents.

Keep a count of nodes in left subtree with binary search tree

This comes up in Gayle Laakmann McDowell's book.

You need to have the number of nodes to the left of each node, and you want that updated with each insert.

This post is about doing this by walking down the tree as you do for BST insert.

One way is to just update each node to say the number of nodes in its subtree (including itself). When you add one node to the tree, this goes up by one at the current node, no matter if you walk left or right. The you check the left child to see how many a node has on the left.

The code in the book does it differently. It inserts a node into a binary tree but only increases the current nodes count if the node put in the left child.With all nodes inserted, the tree nodes then have a count of how many nodes are on the left of each node. It's sort of like letting marbles roll into position. At each node you watch how many end up rolling left, and then will end up being the number of left nodes.

Longest increasing subsequence, considering contigous or not, starting with brute force and then optimizing

Introduction

 A way to solve problems like this is to keep a candidate list of subsolutions. You walk along the input and either add to an existing subsolution or start a new one. A brute force approach would be to keep track of all possible candidates and then verify to find which ones are best after the list of all of them is generated. However, a more efficient approach is to only add a candidate if you know that it may contribute, and prune away candidates if you know they will not contribute.

 

Longest Contiguous Increasing Subsequence

Say you want to find the longest contiguous increasing subsequence of an array.

(Using python syntax for description.)

For example:

X = [0, 8, 4, 9, 2, 3]


Brute force:
Walk across the list from left to right, and keep a list of possible solutions S you have found so far. This means that when you are at position i you do this:

Keep all lists already in S
Consider each list in S and add a new one that has X[i] appended to the end.

(This will also generate a new list that starts on X[i] because the empty list is in S.)

def longestContiguousSubsequence(X):



 # Staring with just one empty solution []. 

 S = [[]]

 for i in range(len(X)):
     for j in range(len(S)):
         newLists = []
         for s in S:
             copyOfList = list(s) 
             copyOfList.append(X[i])
             newLists.append(copyOfList)
         S += newLists


 max = 0
 maxList = []


 for s in S:
  if increasing(s):   # assume increasing returns true if the sequence is increasing
      if len(s) > max:
          max = len(s)
          maxList = s 

 return maxList

# test
print longestContiguousSubsequence(X)

This works but it does a lot of extra work.

For example, [0, 8] and [0, 4] are both put into S. However, you really don't need to keep both of them. The last element of [0, 4] is less than the last element of [0, 8], and there's no way that [0, 4] could do any better than [0, 8]. You can always add more increasing items to the end of [0, 4]. So, here's a rule: if you are about to add a new list it has to be "better" (it has to have more potential) than existing lists.

In here's what makes a list better:
(1) It's better if it has a lower number on the end.
(2) It's better if it's longer.

When you add a list, you are appending on new number. You're making a new list that's one longer, so it might better than the one that it comes from. But you want to compare it to other existing lists of equal length to see if it has a lower ending number, if it doesn't have a lower ending number, it's not useful. (Also if there are longer lists with lower numbers at the end, this one will not be useful, later on we can use this fact also.)

This means that really there can never be more than one useful list in S of a given length. The only list you would keep in S of a given length is one with the minimum ending value.

This means that we can have an array "Best" exactly the length of the list X that just stores a best list for each possible length. It will store a reference to a list at each element of the array. The first element is the best list of length 1, the second element is the best list of length 2, etc.

Since Python has zero based arrays, we'll actually use an array Best that has length of S + 1. The index of the array is equal to the lengh of the candidate sequence stored at that position.

Now, when you are adding a candidate list, and it turns out to be length n, you always look to the Best array to see if there's a list of length n that has a lower ending value, if so, you don't need to add it.

One more simplification: you don't need to store the whole lists in Best. You really only need to know where the list ends and the length of the list. That's enough to fully describe any subsequence. The index to Best is the length of the list, so if you just store where the list ends (one number) in each element of Best, that is enough.

Now, when you are about to add a new candidate list of length n by appending x, just look at Best[n] and it will give the the index i to the end of the best list of that length. If X[i] is smaller than x, you don't need to add your new list. If X[i] is bigger than x, you do need to add your new list, which just means replacing Best[n] with a new ending index.

 for i in range(len(X)):
   for lengthOfList in range(len(Best)):
     newLengthOfList = legthOfList + 1
     newEndOfList = X[i]
     if newEndOfList < Best[newLengthOfList]:
       Best[newLengthOfList] = X[i]


There's another optimization. If you can put x at the end of some subsequence s as above, then you don't need to put s at the end of any shorter subsequence. The shorter one would just end up having the exact same ending value and a shorter length, which can't possible be useful. So you really you only need to append to one of the candidate subsequences at most.

Walk along Best from highest index to lowest to find where to add to create a new list with one added. Then skip the others because they won't contribute to the final solution.

However, you don't really have to walk down the list one by one. The list represents the set of best solutions. Any solution A in the list that is shorter than solution B in the list will always have a lower number on the end (otherwise it would have been eliminated). So in a list of best solutions, the longer ones have higher values at the end. Because our Best array is indexed by length, it's also in order lowest last value to highest last value.

Longest Increasing Subsequence (Does not need to be contiguous)

This section is examining a different problem, where the goal is to find the longest increasing subsequence, and it does not need to be contiguous. Now I'm assuming that each candidates are being stored as a lists. (Other sources like Wikipedia have more efficient ways, but this is for explanation purposes.)

The approach to this is similar as described in the last section. You keep a list of best lists, indexed by length. You encounter a new number and you can create a new list with it appended to an existing candidate if it will create a new list that is "better" than those existing so far. (This includes the possibility of it creating a list longer than all of those existing so far and the possibility of creating a list that's just the same length as an existing but has a lower end value.)

Candidate solutions end up looking like this for example:
Best[1]:  0
Best[2]:  0, 4
Best[3]:  0, 4, 12
Best[4]:  0, 4, 12, 16

Notice that the ending number is always increasing. It must be, because if it was less than the previous, then the previous would not be useful. (Previous checks ensure that each list is useful, it has to be either longer or have a lower value at the end to get added.)

You could walk down Best from longest to shortest, one by one, checking the end value at each and append when you find the sufficiently small end value.

For example, if you found an 8, you could create a new list where it's appended to 0, 4 giving:
Best[1]:  0
Best[2]:  0, 4
Best[3]:  0, 4, 8
Best[4]:  0, 4, 12, 16

Or, if you found a 14, you'd want to make a new list with it appended to 0,4,12
Best[1]:  0
Best[2]:  0, 4
Best[3]:  0, 4, 12
Best[4]:  0, 4, 12, 14

In the examples, you can see that you really want to try adding it to the longest list with an ending value that's lower. (The only one that will work is the longest with an ending value lower. The ending values has to be lower for you to add it at all. And, if you tried one that wasn't longest, you'd always be trying to make a new list that's no better than one you already have based on ending value... because the one after it would have a lower ending value.) For example, if ending values are 0, 4, 12, 14, then 8 can only be extending 0, 4, there is not other option.


Considering ending values:
0 4 12 14
       ^
You can find where you'd want to put 8 with a binary search of the list's end values.
Binary search for 8, which will put you between value 4 and 12 (index 2 and index 3), so you'd want a new sublist extending the list shown at Best[2] and replacing Best[3].

In summary the algorithm is effectively maintaining a list of candidates like this for example:

Best[1]:  0
Best[2]:  0, 4
Best[3]:  0, 4, 12
Best[4]:  0, 4, 12, 14

At each iteration, walking down the input:
  It can put in a new best (Best[5] in this example) by appending

An optimization: Making new lists by copying is expensive. Here's more efficient way to get the job done. Represent the list as linked lists. For example:
0 4 12
(0) <- 3="" array="" p="" position="">
Now when you want to add 14. Create node with 14 and just set its point to (12) of this list (0) <- p="">



Above essentially creates an array of nodes where each of the nodes's points certain other previously created node.


Instead of using nodes, standard algorithms accomplish the same with a "parent" array.


You were creating one node at each iteration i (which each check of an input value). You can just put an index in an array p instead. Create an array of parents, each points to a child index (Very much like a node. Each element of the array is an index which is associated with another index. Just like each node is a reference to a number that's associated with a reference to another node.) For examples: At the addition of 4, the pointer p[1] would be set to point to the position of 0, which is i=0. At the addition of 12 (at i=2) the pointer (just a number) p[2] would point to position of the array that holds 4 (which is i=1).

N is length of array (assume its indices start at 1)
Note that each index that p stores can point you to a number in the input (if that's what you want) or to a previous node in p (if that's what you want). (Just like each node will give you either the data of the node or the next node.)
So p[N] points to the position in the array of the last value. (It also points to a position in the parent array.)
p[p[N]] points to the position in the array of the second to last value. (It also points to a position in the parent array.)

Talking to women

Probably the deeper you go into reality, into what you are really thinking and into what she is really thinking, and what her motivations are, all the way down to the evolutionary level, the farther away you are from connecting. Better off at a much different level. A level of interest in the items of life, the events of the day, with attendtion to believing her internal model of the world and working with that. Haven't varified that. However I've seen many times how women have a very odd disbelieving reaction to characterizing human behvior (and their own) in terms of evolutionary biology.

Dating

Woman said she only spends time alone with a guy if she is dating him. (Formally I though dating was spending time alone, but it's not in this case.) I believe that in her culture, dating means an interaction in public that establishes that they are a romantic couple, possibly in a bar-type scene or just in a restaurant. Dating is not just going out or going in for one meeting, it's a state of the relationship, like going steady. Once the relationship is in that dating phase, she's OK with spending time alone. It's like a social verification stage before intimate involvement.

Nature, evolution, religion, cognitive dissonance

Vast majority of people believe in a god of some sort. The beliefs are not true, but they are effective. The numbers indicate that believes (in terms of reproduction) are highly successful and represent the majority of humanity. It's amazing that nature managed to generate people capable of both logical and belief in religion. Innovations of evolution like cognitive dissonance made this possible.