Cache

I was finding it very weird that only 700 MB of my 4 GB RAM memory was free when I was only running Chrome… After reading a lot of forums about memory management and chrome and all, I found out that Linux uses my unused RAM for buffers and cache. During my search, I installed a quite cute version of top, called htop. It has colors and a chart =)
But an easy way to see how much of your RAM memory is being used by buffers and cache is with the command free. In my case, the output was:

             total    used    free  shared  buffers   cached
Mem:       3909684 3201664  708020       0   180988  1648576
-/+ buffers/cache: 1372100 2537584


If I check the second line, I can see that the used memory is actually about 1.3 GB (still a lot, in my opinion), which is exactly the used memory from the line above minus the buffers and cache parts. I read somewhere that Linux has a lazy deallocation, so I don’t expect to see a free RAM memory anytime…

Programming

I am finally back to programming. Trying to use this Scala language that’s supposed to be “functional Java”. It is still not natural for me to program in these two paradigms… I have been using OO imperatively too long. My first impression is that it is a bulky language (well, of course, since it’s Java based), and sometimes this makes it hard for me to understand the code. It has even a way to pass parameters to a function implicitly. Now, who wants such a thing? I think that the trade-off of writing some extra characters on every function call and making the code readable pays off, but who am I to say? Nevertheless, the pattern matching thing really helps (of course that there is a special keyword to declare a class that is used in a matching latter) and I hope I can make those two paradigms work in a nice way together.

Anyway, it is nice to work again on a big project, where we need to care about what other developers are doing, sharing code, think about architecture and all. =)

ética x discriminacão

Hoje na reunião de projeto aconteceu uma coisa interessante… Logo no início um colega falou com meu professor que gostaria de conversar com ele depois sobre um projeto em parceria com a Franca. Meu professor disse que eles podiam adiantar e conversar naquele momento mesmo. Enquanto eles falavam sobre a proposta e o deadline (daqui a 5 dias) o meu orientador virou pro meu colega e disse “Você sabe que a Giselle tem que estar no projeto né?”. Eu, que nem estava sabendo de projeto nenhum até então virei pra ele e pro meu colega com cara de “Como assim??”. Eu nem sabia do assunto do projeto e de repente eu *tenho* que participar dele? Tá né… Aí meu professor explicou que pro projeto ser aprovado precisa ter uma porcentagem mínima de mulheres. Ou seja, se fosse um projeto só com homens ele não ia ser aprovado de jeito nenhum, e eu como a única mulher desse grupo da universidade, entrarei pra garantir que temos uma chance de ser aprovado. o.O

Qual é minha contribuicão pro projeto em si? Sabe-se lá… Ele viu que eu fiquei meio desconcertada e me garantiu que esse não foi o motivo pelo qual eu fui aceita no programa de doutorado (apesar dele ter tido sim uma quota pra mulheres, eu tenho aparentemente um bom currículo). Meu professor tentou explicar que eles fazem isso pra diminuir a discriminacão contra mulheres nas ciências. Mas sério… eles só estão gerando uma discriminacão pelo outro lado. Olha só minha situacão, eu fui chamada pra participar de um projeto simplesmente porque sou uma mulher… Pode não ter sido a intencão do meu professor, mas o fato de ninguém ter me falado disso até hoje, faltando cinco dias pra submeter a proposta, não é um indício muito forte de que eu tenho algo pra acrescentar.

Fiquei pensando nisso por um tempo. Conversei com outro colega e ele disse que se eu tiver me sentindo desconfortável a melhor coisa que eu faco é falar com meu professor, mas ele acha que na verdade esses projetos são submetidos não porque é esperado que os resultados prometidos sejam atingidos, mas sim pra gente conseguir verbas pra viajar e parcerias com outras universidades que podem gerar resultados completamente diferentes do proposto. Enfim, tudo tem dois lados. Eu posso aproveitar essa regra esquisita e usar a meu favor pra entrar nos projetos e conhecer outros pesquisadores e outras linhas de pesquisar e visitar outras universidades. Mas por outro lado, tem a minha ética e auto-estima, que me falam que ia ser melhor mesmo se eu estivesse num projeto por mérito próprio e porque as pessoas realmente acharam que eu era relevante. Infelizmente o mundo é injusto, e a segunda possibilidade parece semi-utópica… Então, melhor usar a injustica pro meu proveito enquanto eu posso (até os 35 anos. Também tem um limite de idade…).

Complexity

Joao proposed me a question once and I found it tricky. I’m going to post here the question and answer I gave him after some thinking and discussing, but feel free to disagree and discuss some more (I read the answer and I am trying to convince myself again) =)

What is the complexity of this two programs:

– Finding the mean of n random numbers.
{
int s =0;
for(int i = 0; i < N; i) {
s += rand();
}
mean = s/N;
}

– Determining of N is prime
int i = 1
{
for(; i < N; i++){
if( N % i == 0) break;
}
printf(“%d”, i);
}

There are some things you should think about when you look at those two programs. I agree with you that, if you consider just the number n, you can say that their complexity is O(n). But, that cannot be considered a valid measure of complexity. Why? Because the linearity in complexity theory is measured according to the *size* of your input. In both cases, the size is one, since it is only one number. And depending on which number you use (*type* of input), the execution time may vary. So, since this is the case for both codes below, the size of your input should be in fact measured by the number of bits of your input number. In that case, the larger the number, more bits are needed to represent it and more time is spent by your algorithm. The actual _amount_ of the number (1, 10 or 100000) does not represent anything computationally, so you can’t use it to say your program is O(n). (I hope that’s clear…).

You see that is not the case of being an algorithm to factor numbers or not, the main point here is that both programs will depend on the type of the input. So, regarding the number of bits, we could say that:

– Your program executes N steps.
– The number of bits to represent the number N is b = log N
– Therefore: N = 2^b

Which means the your program’s complexity is actually O(2^b), which is exponential.

Heurísticas

Cada vez eu gosto mais desse lugar… Hoje quem veio falar aqui pra gente foi o professor Richard M. Karp, um dos vencedores do prêmio Turing e dono de um currículo de dar inveja. Eu não vou ficar falando sobre o que ele falou na palestra, cujo título foi “Effective heuristics for NP-hard problems arising in molecular biology”. Só vou citar uma frase que eu achei interessante:

“Heuristics are often ‘unreasonably effective’ for reasons we don’t really understand.”

É ou não é?

Sobre grafos bipartidos

Uma rede de computadores pode ser facilmente representada por um grafo, no qual cada máquina representa um vértice e arestas são conexões entre essas máquinas. Nesse grafo, cada vértice possui um label que seria o endereço da máquina na rede. Mas esses labels podem ser mais que endereços, eles podem refletir diretamente a distância entre os vértices (máquinas). Em uma rede cujo endereçamento segue essa regra, o roteamento de pacotes pode ser feito de maneira ótima analisando somente informações locais (incrível, hein?? =P ). Basta fazer o seguinte: um pacote sabe sempre seu endereço de destino, quando ele alcança um vértice ele compara esse endereço com os vizinhos desse vértice e vai para o que está mais próximo do seu objetivo. Simples.

Um grafo que obviamente satisfaz essa propriedade é n-cubo. Nele, a distância entre os vértices é exatamente a distância Hamming (ou distância de edição) entre as sequências de bits atribuídas a cada vértice. Para construir uma rede dessa maneira (na qual os pacotes percorrem sempre o caminho ótimo) devemos saber que tipo de grafo pode ter seus vértices endereçados com strings de bits de modo que a distância de Hamming corresponda à distância entre os vértices no grafo.

Teorema (Djokovic – 1973):
Existe um esquema de endereçamento usando strings de binárias para os vértices de um grafo simples G tal que a distância Hamming das strings coincide com a distância dos vértices no grafo se, e somente se:
    (i) G é bipartido.
    (ii) G(a,b) é um conjunto fechado para toda aresta (a,b) em A(G).

OBS: G(a,b) = {x em V(G) | d(x,a) = d(x,b)-1}
         Um subconjunto de vértices U de V(G) é dito fechado se para todo par a,b em U: x em V(G) e d(a,x) + d(b,x) = d(a,b) então x está em U.

[1] Bipartite Graphs and their Applications (Cambridge Tracts in Mathematics) – Armen S. Asratian