Tuesday, May 4, 2021

VPN Router: Clearing up the confusion about flashing DD-WRT into a Netgear R7000P router in 2021

 

 This last weekend I went over flashing DD-WRT, an open source firmware for routers, into a brand-new NETGEAR R7000P router. My particular goal was to run a VPN client in the router itself, a feature supported by DD-WRT.

When you search about the process online it's a bit scary, because there is a lot of stern warnings about possibly bricking the router (that is, rendering it completely non-operational) if you do anything wrong.

And yet I found that the greatest risk of bricking the router comes from the sorry state of information online itself. It often is confusing, inconsistent, broken, or plain wrong. Once you finally find out what it is that you need to do, the process is very simple.

So here is what I did, and some notes on incorrect or confusing information online.

What I did:

  • Installed router per NETGEAR instructions, no problem.
  • Downloaded the DD-WRT firmware files from http://ftp.dd-wrt.com/dd-wrtv2/downloads/betas.  One thing that I found confusing is that everybody was pointing out to the beta portion of the FTP site. As far as I can tell, that is the right thing to use. Another apparently very important point (and the reason bricking often happens) is that you should really get the files for your exact model, including things like "v2" (version) in the model's description.
  • Typically there is a chk file for flashing over the original router firmware, and then a router model-specific bin file for a second flashing.
  • You apply the chk file by going to your router's administration page (usually accessible via 192.168.1.1, or routerlogin.net/routerlogin.com). Once the chk file has been flashed, you already have DD-WRT in your router. You then go to DD-WTR's administration page (again, 192.168.1.1) and apply the bin file. I basically followed the instructions in this still very accurate page: https://www.myopenrouter.com/article/how-flash-your-netgear-router-dd-wrt-5-easy-steps.
  • Online explanations say that after flashing DD-WRT you will be able to connect to the wireless network without a password (meaning, to actually connect to the wireless network, as opposed to accessing the web interface for the router, which does use the default username and password root and admin), but in my case this was not true; DD-WRT kept the network password from before the flashing.

If you do just the above you should be fine. However, for completeness and clarification, here are some of the things I found that were wrong or confusing:

  • Some pages (for example this one) mention that the more recent NETGEAR firmware prevents flashing the router with DD-WRT. I have not found that not to be true at all, at least for my R7000P.
  • www.MyOpenRouter.com is an important site in this community, and includes the helpful instruction page I mentioned above, but it also has some very confusing pages providing links to specific firmware updates that are out-of-date (for example, this one, which lists an out-of-date file dd-wrt.K3_R7000P.chk). These same posts also point to the FTP mentioned above, but make no attempt to explain which one is the right resource to use.
  • Several people mention that the DD-WRT Wiki, as well as its router database, are great resources. However, some people correctly point out that the router database is often out of the date. The site itself refer to you the database, and once you follow the link it warns you it is out of the date. It also seems incomplete; for example, the entry for the R7000P lists only the bin firmware file, not the chk one. The Wiki would not even load most of the time, but when I managed to open it I found it completely useless, with very cryptic instructions that seemed more like someone's note to themselves.

Wednesday, May 13, 2015

União e Intersecção de Intervalos

Conjuntos são como clubes, associações, países, etc

Um conjunto é como se fosse um clube, uma associação de pessoas. Para fazer parte, o elemento precisa satisfazer certos critérios, certas condições.
Por exemplo, para ser membro (elemento) do Clube de Xadrez, a pessoa tem que jogar xadrez e pagar uma anuidade. Pra ser elemento de [3,4], um número x tem que satisfazer o critério 3  4.

Intervalos são um tipo de conjunto

Escrever 3 x é apenas uma abreviação para 3 x e x 4. Ou seja, x é maior ou igual a 3, e menor ou igual a 4. Isso significa que todo número real indo de 3 a 4 pertence a esse intervalo: por exemplo, 3,1, 3,2, ... 3,9, 3,9999, etc.
Até π=3,14159... pertence a esse intervalo, pois ele é maior ou igual a 3 (pois é maior que 3), e menor ou igual a 4 (pois é menor do que 4). Note que inclusive o 3 e o 4, pois eles passam no teste: 3 é maior ou igual a 3 (pois é igual), e menor ou igual a 4 (pois é menor). E 4 é maior ou igual a 3 (pois é maior), e menor ou igual a 4 (pois é igual).
O intervalo ]3;4[ é parecido, mas a condição agora é sem o "ou igual": 3 < x < 4. O número tem que ser maior do que 3, e menor do que 4. Isso significa que o 3 e o 4 não estão nesse intervalo. 3 não está porque não é maior do que 3 (um número nunca é maior do que si mesmo) e 4 não está nesse intervalo porque não é menor do que si mesmo, 4!
A notação usando colchetes é sugestiva: quando escrevemos "[3", estamos incluindo o 3. Pode-se pensar que o colchete está "abraçando" o 3, incluindo-o. Já "]3" está dando as costas para o 3, excluindo-o. O mesmo vale para "4]" (incluindo) e "4[" (excluindo).
Uma forma de ler em voz alta o intervalo [3;4] é "intervalo de 3 inclusive a 4 inclusive". Lemos "]3;4[" como "o intervalo de 3 exclusive a 4 exclusive". Podemos inclusive misturar os dois casos: ]3,4] exclui o 3 mas inclui o 4. [3,4[ inclui o 3, mas exclui o 4.

Voltando a conjuntos sendo como clubes

Mas voltando à idéia de que conjuntos são clubes com critérios de admissão: quando ninguém satisfaz o critério, o clube fica vazio. Por exemplo, o clube (conjunto) dos números primos pares e maiores do que 5 é o conjunto vazio, pois o único número primo par é 2 e ele não é maior do que 5. Ele era o único que talvez satisfizesse a condição, mas nem ele satisfaz.
Outro clube vazio é o clube dos números pares ímpares (lógico).
Esses "clubes vazios" são simplemente o conjunto vazio, denotado por { } ou ∅.
Às vezes um clube tem um único membro: o clube dos números primos pares só tem o elemento 2 lá, nenhum outro número satisfaz. A gente denota esse conjunto como { 2 }.

União, e União de Intervalos

Certos clubes são especiais pois o critério para pertencer a eles é pertencer a outros clubes. Por exemplo, o conjunto união de [3, 5] e [5, 6] exige que para fazer parte, o elemento tem que fazer parte ou de [3;5], ou de [5;6]. Isso resulta em todos os numeros em [3,6], portanto [3;6] é a união de [3;5] e [5;6].
A regra geral para união é a seguinte: um elemento pertence à união dos conjuntos A1,...,An se, e somente se, ele pertence a pelo menos um dos conjuntos A1,...,An (note que isso inclui o caso em que ele pertence a mais de um desses conjuntos, ou mesmo de todos).
A União Européia é um clube parecido. Pra ser cidadão da União Européia, a pessoa tem que ser cidadã ou de Portugal, ou da França, ou da Alemanha, etc... O resultado é o conjunto de todas as pessoas dos países da União Européia.
Veja bem, união não precisa ser só de intervalos, mas serve para qualquer conjunto. Intervalo é só um tipo de conjunto. Um exemplo de conjunto que não é intervalo é, por exemplo, {1, 4, 5, 6}, que é um conjunto com 4 números. Ele conjunto tem "buracos" entre os elementos -- o 2, por exemplo, não pertence a ele -- e não é um intervalo.
Mesmo com conjuntos que não são intervalos, podemos falar da união. Por exemplo, a união dos conjuntos [0, 1, 2} e { 1, 2, 4, 5, 6} é o conjunto {0, 1, 2, 4, 5, 6}, ou seja, todos os elementos que fazem parte de pelo menos um dos conjuntos originais.
Note que acima o 1 e 2 pertencem a ambos os conjuntos. Isso não impede que eles pertençam à união, pois pra pertencer a União basta pertencer a pelo menos um conjunto. Quem pertence aos dois conjuntos pertence a pelo menos um deles!

Intersecção, e Intersecção de Intervalos

A intersecção também é um tipo de clube que tem como condição o fato de pertencer a outros clubes. A diferença é que pra pertencer à intersecção, um elemento deve pertencer a todos os conjuntos sendo interseccionados. A intersecção de {1,2,3}, {2, 3, 4} e {0,2,3,5} é {2,3} pois apenas esses dois elementos pertencem todos os três conjuntos. A intersecção de {2, 3, 4} e {0, 1, 7} é o conjunto vazio, pois nenhum número pertence a ambos esses conjuntos.
Se a intersecção for de vários conjuntos, um elemento deve pertencer a todos eles pra poder pertencer à intersecção. Por exemplo, a intersecção de {0,1,2], {-1,0,2} e {2,4,5} é o conjunto unitário {2}, pois só o 2 pertence a todos os conjuntos. Note que o 0 pertence a dois deles, mas como não está no terceiro, é rejeitado na hora de entrar na intersecção.
A intersecção dos países da União Européia é o conjunto vazio, pois pra pertecer à intersecção de todos aqueles países, a pessoa teria que ser cidadão de todos os países: ser cidadão de Portugal E cidadão da França E cidadão da Alemanha. Acho que não existe ninguém que seja cidadão de todos esses países ao mesmo tempo, então a intersecção é o conjunto vazio.
Lembre-se: um intervalo é nada mais, nada menos do que um "clube", com uma condição para pertencer que toma a forma de a ≤ x ≤ b, (ou < ao invés de ≤ para intervalos abertos). Os números 3, 3,5 e 4 pertencem a [3,4], enquanto 3 e 3,5 pertencem a [3;4[ mas o 4 não pertence.
Intervalos d tipo ]-infinito; 3] significam "maior do que -infinito e menor ou igual a 3". Como todo número é "maior do que -infinito", isso é a mesma coisa que simplesmente dizer: "menor ou igual a 3".
O mesmo raciocínio se aplica para [4;+infinito[. Todo número maior ou igual a 4 pertence a esse intervalo, pois todos não "menores que infinito".

Exercícios

Dadas todas essas explicações, pratique resolvendo esses exercícios:
1. Quantos pontos estão contidos nos seguintes intervalos: a. [2;2] b. [2;2[ c. ]2;2[
2. Quais as seguintes intersecções:
a. [1;3] ∩ [0; 2] b. [-1;3] [0; 2] c. [3;4] [4,8] d. [3,4[ ]4, 8] e. [0;1] [3;4] f. [0;1] [1;2]
3. Quais as seguintes uniões (Note que as uniões não são necessariamente intervalos):
a. [3;4] [4;8] b. ]-infinito,;7] [7;+infinito[ c. [2;4] [6,8]

Respostas


1. Quantos pontos estão contidos nos seguintes intervalos:
a. [2;2] = {2}, pois apenas x = 2 satisfaz 2 ≤ x ≤ 2. b. [2;2[ = ∅, pois nenhum x satisfaz 2 ≤ x < 2, nem mesmo o 2, pois não é verdade que 2 < 2. c. ]2;2[ = ∅, pois nenhum x satisfaz 2 < x < 2, nem mesmo o 2, pois não é verdade que 2 < 2.
2. Quais as seguintes intersecções:
a. [1;3] ∩ [0; 2] = [1;2] b. [-1;3] [0; 2] = [0;2] c. [3;4] [4,8] = {4}, pois apenas 4 pertence a ambos os intervalos d. [3,4[ ]4, 8] = ∅, pois nem o 4 pertence a ambos os intervalos e. [0;1] [3;4] = ∅ pois nenhum número pode ser ≤ 1 e maior ou igual a 3 ao mesmo tempo. f. [0;1] [1;2] = {1}, pois apenas o 1 está nos dois intervalos.
3. Quais as seguintes uniões (Note que as uniões não são necessariamente intervalos):
a. [3;4] [4;8] = [3;8], pois todos os números em [3;8] estão ou em [3;4] ou em [4;8] b. ]-infinito,;7] [7;+infinito[ = ]-infinito;+infinito[, ou seja, todos os números reais. c. [2;4] [6,8] = { x : 2 ≤ x ≤ 4 ou 6 ≤ x ≤ 8 }, que se lê assim: "o conjunto dos números x tais que 2 ≤ x ≤ 4 ou 6 ≤ x ≤ 8". Infelizmente não há um modo de descrever esse conjunto como um intervalo (por exemplo [2;8]), pois essa união não é um intervalo por ter um "buraco" no meio: os números entre 4 e 6 exclusive não pertencem à essa união pois não pertencem a nenhum dos dois intervalos originais. Se tivéssemos escrito [2;8], estaríamos incluindo esses números indevidamente.

Friday, March 27, 2015

ArrayHashSet, a Set in Java with random access and list iterators

Java offers a very useful Set implementation called LinkedHashSet, which keeps a parallel list to a HashSet that keeps the original insertion order available for iteration. This leads to more predictable outcomes with minimum overhead.

I've already wondered why they have not provided an analogous ArrayHashSet implementation in which an ArrayList fills the role of the parallel list, which would make middle-insertion slower, but on the other hand would offer random access.

Also, I don't know why they don't let LinkedHashSet provide a list iterator for more flexible iteration.

Anyway, given all that, I have implemented ArrayHashSet, which provides random access and list iterator. Here's the code:

/*
 * Copyright (c) 2013, SRI International
 * All rights reserved.
 * Licensed under the The BSD 3-Clause License;
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 * 
 * http://opensource.org/licenses/BSD-3-Clause
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright
 * notice, this arrayList of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright
 * notice, this arrayList of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 * 
 * Neither the name of the aic-expresso nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package com.sri.ai.util.collect;

import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.ListIterator;

/**
 * Analogous to {@link LinkedHashSet}, but with an {@link ArrayList} instead of a {@link LinkedList},
 * offering the same advantages (random access) and disadvantages (slower addition and removal of elements),
 * but with the extra advantage of offering an iterator that is actually a {@link ListIterator}.
 * @author braz
 *
 * @param
 */
public class ArrayHashSet extends AbstractSet {

private HashSet   set;
private ArrayList arrayList;

public ArrayHashSet() {
this.set  = new HashSet();
this.arrayList = new ArrayList();
}

// additional random access methods

public ArrayHashSetIterator listIterator() {
return new ArrayHashSetIterator(arrayList.listIterator());
}

public ArrayHashSetIterator listIterator(int index) {
return new ArrayHashSetIterator(arrayList.listIterator(index));
}

public E get(int index) {
return listIterator(index).next();
}

public void set(int index, E element) {
ArrayHashSet.ArrayHashSetIterator listIterator = listIterator(index);
listIterator.next();
listIterator.set(element);
}

// end of additional random access methods

// required implementations

public ArrayHashSet(Collection collection) {
this();
addAll(collection);
}

@Override
public boolean add(E element) {
boolean modified = set.add(element);
if (modified) {
arrayList.add(element);
}
return modified;
}

@Override
public ArrayHashSetIterator iterator() {
return new ArrayHashSetIterator(arrayList.listIterator());
}

@Override
public int size() {
return set.size();
}

// end of required implementations

// methods not required to be implemented, but more efficient

@Override
public boolean contains(Object o) {
return set.contains(o);
}

@Override
public Object[] toArray() {
return arrayList.toArray();
}

@Override
public T[] toArray(T[] a) {
return arrayList.toArray(a);
}

@Override
public boolean remove(Object o) {
boolean removed = set.remove(o);
if (removed) {
arrayList.remove(o);
}
return removed;
}

@Override
public void clear() {
set.clear();
arrayList.clear();
}

// end of methods not required to be implemented, but more efficient

private class ArrayHashSetIterator implements ListIterator {

private ListIterator arrayListIterator;
private E lastElementProvided;

public ArrayHashSetIterator(ListIterator arrayListIterator) {
this.arrayListIterator = arrayListIterator;
}

@Override
public boolean hasNext() {
return arrayListIterator.hasNext();
}

@Override
public E next() {
return lastElementProvided = arrayListIterator.next();
}

@Override
public void add(E element) {
if (set.add(element)) {
arrayListIterator.add(element);
}
}

@Override
public boolean hasPrevious() {
return arrayListIterator.hasPrevious();
}

@Override
public int nextIndex() {
return arrayListIterator.nextIndex();
}

@Override
public E previous() {
return lastElementProvided = arrayListIterator.previous();
}

@Override
public int previousIndex() {
return arrayListIterator.previousIndex();
}

@Override
public void remove() {
arrayListIterator.remove();
set.remove(lastElementProvided);
}

@Override
public void set(E element) {
if (element.equals(lastElementProvided)) {
// no need to do anything
}
else {
if (set.contains(element)) {
// cannot add because element would appear more than once
throw new IllegalArgumentException("Cannot set already-present element in a different position in ArrayHashSet.");
}
else {
arrayListIterator.set(element);
set.remove(lastElementProvided);
set.add(element);
}
}
}
}
}


and here is a unit testing class:

/*
 * Copyright (c) 2013, SRI International
 * All rights reserved.
 * Licensed under the The BSD 3-Clause License;
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at:
 * 
 * http://opensource.org/licenses/BSD-3-Clause
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 * 
 * Neither the name of the aic-util nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package com.sri.ai.test.util.collect;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import java.util.NoSuchElementException;

import org.junit.Before;
import org.junit.Test;

import com.sri.ai.util.Util;
import com.sri.ai.util.collect.ArrayHashSet;

public class ArrayHashSetTest {

@Before
public void setUp() throws Exception {
}

@Test
public void test() {

ArrayHashSet set;

set = new ArrayHashSet();
assertTrue(set.isEmpty());
assertEquals(set.size(), 0);

assertEquals(Util.list(), Util.listFrom(set.iterator())); // tests iteration order

set.add("tree");
assertFalse(set.isEmpty());
assertEquals(set.size(), 1);
assertEquals("tree", set.get(0));

set.add("almond");
assertFalse(set.isEmpty());
assertEquals(set.size(), 2);
assertEquals("tree", set.get(0));
assertEquals("almond", set.get(1));

assertEquals(Util.list("tree", "almond"), Util.listFrom(set.iterator())); // tests iteration order

set.clear();
assertTrue(set.isEmpty());
assertEquals(set.size(), 0);

set.add("almond");
assertFalse(set.isEmpty());
assertEquals(set.size(), 1);
assertEquals("almond", set.get(0));

set.add("tree");
assertFalse(set.isEmpty());
assertEquals(set.size(), 2);
assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));

set.add("leaf");
assertFalse(set.isEmpty());
assertEquals(set.size(), 3);
assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("leaf", set.get(2));

assertEquals(Util.list("almond", "tree", "leaf"), Util.listFrom(set.iterator())); // tests iteration order

set.remove("tree");
assertFalse(set.isEmpty());
assertEquals(set.size(), 2);
assertEquals("almond", set.get(0));
assertEquals("leaf", set.get(1));

assertEquals(Util.list("almond", "leaf"), Util.listFrom(set.iterator())); // tests iteration order

set.remove("leaf");
assertFalse(set.isEmpty());
assertEquals(set.size(), 1);
assertEquals("almond", set.get(0));

assertEquals(Util.list("almond"), Util.listFrom(set.iterator())); // tests iteration order

set.remove("almond");
assertTrue(set.isEmpty());
assertEquals(set.size(), 0);

assertEquals(Util.list(), Util.listFrom(set.iterator())); // tests iteration order

set.add("almond");
set.add("tree");
set.add("tree");
set.add("almond");
set.add("leaf");
set.add("tree");

assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("leaf", set.get(2));
assertEquals(Util.list("almond", "tree", "leaf"), Util.listFrom(set.iterator())); // tests iteration order

set.set(2, "trunk");
assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("trunk", set.get(2));
assertEquals(Util.list("almond", "tree", "trunk"), Util.listFrom(set.iterator())); // tests iteration order

set.set(2, "leaf");

assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("leaf", set.get(2));
assertEquals(Util.list("almond", "tree", "leaf"), Util.listFrom(set.iterator())); // tests iteration order

set.set(2, "leaf");

assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("leaf", set.get(2));
assertEquals(Util.list("almond", "tree", "leaf"), Util.listFrom(set.iterator())); // tests iteration order

try {
set.set(2, "almond"); // cannot add an already-present element in a different position
fail("Should have thrown an exception");
}
catch (IllegalArgumentException e) {
// good, did what it had to do
}
catch (Exception e) {
fail("Should have thrown an IllegalArgumentException but threw " + e);
}

try {
set.set(3, "almond"); // cannot set a non-existing position
fail("Should have thrown an exception");
}
catch (NoSuchElementException e) {
// good, did what it had to do
}
catch (Exception e) {
fail("Should have thrown an NoSuchElementException but threw " + e);
}

// should remain the same after failed operations
assertEquals("almond", set.get(0));
assertEquals("tree", set.get(1));
assertEquals("leaf", set.get(2));
assertEquals(Util.list("almond", "tree", "leaf"), Util.listFrom(set.iterator())); // tests iteration order
}
}


Monday, June 16, 2014

Resolução de equações de segundo grau através de fatoração

Escrevi uma explicação sobre a resolução de equações de segundo grau para o meu sobrinho que pode ser útil para outras pessoas:

Primeiro precisamos relembrar fatoração. Temos DOIS casos de fatoração relevante aqui:

Método de fatoração No1 - trinômio:

É quando temos uma expressão:

x^2 +Sx + P, onde S é a soma de dois números a e b, e P seu produto.

Por exemplo

x^2 + x - 6           (x^2 quer dizer "x ao quadrado")

Nesse caso S = 1 (invisível, multiplicando o x, e P é -6). Pensando nas possibilidades, dois números com soma 1 e produto -6 são 3 e -2. Então x^2 + x - 6 = (x + 3)(x - 2)

Podemos dizer isso porque, aplicando a distributiva,

(x + 3)(x - 2) = x^2 + 3x -2x -6 = x^2 + (3 - 2)x - 6

Ou seja, os números a e b iguais a 3 e -2, quando aplicamos a distributiva, multiplicam o x e são somados, gerando S igual a 1, e sozinhos, sem multiplicar o x, são multiplicados, gerando P igual a -6.

Método de fatoração No 2 - trinômio quadrado perfeito:

É um caso particular do primeiro método, onde a e b são o mesmo número (vamos chamar esse valor comum de d).

Se temos x^2 + 2dx + d^2, isso é o mesmo que (x + d)^2

Por que esse é um caso particular do primeiro método? Por que acima temos que S = 2d, e P é igual a d^2. Os números a e b que geram essa soma e produto são d e d (somados dão 2d e multiplicados dão d^2).

Na verdade, como esse método é um caso particular do primeiro, se você lembrar só do primeiro método usando S e P, já dá pra resolver os dois casos. Por exemplo, se você ver:

x^2 + 6x + 9

e usar S e P, vai achar 3 e 3. Isso é o mesmo que você acharia usando o trinômio quadrado perfeito, pois 6 = 2.d = 2.3 e 9 = d^2 = 3^2.

Portanto

x^2 + 6x + 9 = (x + 3)(x + 3)

Note que os casos acima SÓ funcionam quando o x^2 é multiplicado por 1. Se tivermos um caso, por exemplo com 3 multiplicando o x^2:

3x^2 + 3x - 6

temos que primeiro fatorar o número que multiplica o x^2 (fazer a distributiva ao contrário):

3x^2 + 3x - 6 = 3 ( x^2 + x - 2)

Agora o que está dentro do parênteses pode ser fatorado de acordo com S e P. Achamos os números 3 e -2. Assim, reescrevemos o acima como:

3 ( x^2 + x - 2) = 3 ( (x + 3)(x - 2) ) = que é o mesmo que 3 vezes (x + 3) vezes (x - 2) 3(x + 3)(x - 2)

Note que o fato pra passar de 3 ( (x + 3)(x - 2) ) para 3(x + 3)(x - 2) pode ter te dado a impressão de deveria ter usado a distributiva porque o (x + 3)(x - 2) estava entre parênteses, mas isso não é correto porque a distributiva SÓ se aplica quando o que está entre parêntes é uma SOMA ou SUBTRAÇÃO.

Bom, ok, o que está acima é o que precisamos relembrar sobre fatoração. Agora vamos ver como podemos usar isso para resolver equações de segundo grau.

O que é uma equação de segundo grau? É quando temos uma igualdade (=) envolvendo uma variável, e essa variável aparece elevada ao quadrado. Alguns exemplos são:

3x^2 + 2x + 1 = x^2 + x
3x^2 + 2x + 1 = 0
3x^2 + 1 = x^2 + x
x^2 = 0 x^2 - 5 = 0

Todas essas são equações do segundo grau porque o x aparece elevado ao quadrado, mesmo que o x sem ser ao quadrado também apareça.

Pra resolver uma equação de segundo grau, primeiro passamos tudo para um lado e deixamos o 0 sozinho do outro lado:

3x^2 + 2x + 1 = x^2 + x - 3
3x^2 + 2x + 1 - x^2 - x + 3 = 0

depois reduzimos os termos semelhantes, isso é, somamos tudo que multiplica o x^2 , o que multiplica o x, e os números sem x:

3x^2 + 2x + 1 - x^2 - x + 3 = 0
(3 - 1)x^2 + (2 - 1)x + 1 + 3 = 0
2x^2 + 1x + 4 = 0
2x^2 + x + 4 = 0

Depois que isolamos o zero e reduzimos os termos semelhantes, SEMPRE teremos alguém multiplicando o x^2, alguém multiplicando o x, e um número sozinho. Chamamos o multiplicador de x^2 de a, o multiplicado de x de b, e o número sozinho de c.

2x^2 + x + 4 = 0
tem a = 2, b = 1 e c = 4

Quando um ou mais termos não aparece, é porque ele é 0. Por exemplo, 3x^2 + 2x = 0

tem a = 3 e b = 2, mas qual o c? É 0, porque o acima é o mesmo que

3x^2 + 2x + 0 = 0

ou seja, o numero sozinho é 0.

Outro exemplo:

2x^2 + 3 = 0

Desta vez esta faltando o termo com x, mas o acima é igual a

2x^2 + 0.x + 3 = 0

ou, seja, é facil ver que o b nesse caso é 0.

As vezes tanto o b quanto o c são zero:

x^2 = 0

tem b e c iguais a zero, pois o acima é igual a

x^2 + 0.x + 0 = 0

Lembre-se de prestar atenção nos numeros negativos:

-2x^2 + 3x -1 = 0
tem a = -2, b igual a 3 e c igual a -1

Ou seja, é preciso prestar atenção nos sinais.

Note que o a nunca será 0, pois se estiver faltando um termo com x^2, então nem temos uma equação de 2o grau, que sempre exige um termo com x^2 !

Muito bem, agora sabemos "extrair" os coeficientes a, b, e c de uma equação de segundo grau. Pra resumir, jogamos tudo pro lado esquerdo da equação, reduzimos (somamos os multiplicadores de termos semelhantes) e identificamos o a, b e c como multiplicadores de x^2, x e números sozinhos.

Agora podemos estudar varios casos pra solucionar equações de segundo grau:

Caso 1:

b e c são zero:

Nesse caso temos apenas:

a.x^2 = 0

então

x^2 = 0/a
x^2 = 0
x = raiz(0)        (raiz(alguma coisa) é a notação que uso para a raiz do que vem dentro dos ()s)
x = 0

Esse caso cobre os seguintes exemplos, entre outros:

5x^2 = 0
-3x^2 = 0
-x^2 = 0

O x é 0 em todos os casos que caem no Caso 1, portanto o conjunto solução é S = { 0 }.

Caso 2: 

 O c é zero, mas o b não é:

ax^2 + bx = 0

note que quando é assim podemos fatorar o x:

x( a.x + b) = 0

Ou seja, x vezes (ax + b) é igual a zero. O único jeito de multiplicar duas coisas e dar 0 é se pelo menos uma dessas coisas é igual a zero. Isso quer dizer que ou o x é 0, ou (ax + b) é zero.

Se o x é 0, então pronto, achamos uma solução. Mas se ele não for, outra solução é dada a partir de

ax + b = 0

que é uma equação de PRIMEIRO grau que já sabemos resolver. Fazemos assim:

ax = - b x = -b/a

Ou seja, -b/a é outra soluçãp. Voce nao precisa decorar essa formula se não quiser, basta lembrar de fatorar o x quando o c for zero, ver que x = 0 é uma solução e que a solução da equação do primeiro grau deve ser outra:

Exemplo no caso 2:

x^2 - 4x = 0
x( x - 4) = 0

Então x = 0 é solução e x - 4 = 0, ou seja x = 4 também é solução. Portanto, o conjunto solução é S = {0, 4} (dois valores para x que tornam a equacao verdadeira).

Outro exemplo:

2x^2 + 3x = 0
x ( 2x + 3) = 0
então

x = 0 ou

2x + 3 = 0

qie significa que

x = -3/2

Portanto, S = {0, -3/2}.

Caso 3:

b é zero e c não é zero.

Entao temos

ax^2 + c = 0
ax^2 = - c
x^2 = -c/a
x = + ou - raiz(-c/a)

O "+ ou -" significa que o -c/a funciona como solução tanto do jeito que está quando com o sinal invertido. Isso vai ficar mais claro nos exemplos abaixo.

Nesse caso tambem não precisa decorar a fórmula, basta repetir esse raciocínio quando ver que b é 0. Por exemplo:

2^x^2 - 8 = 0
2^x^2 = 8
x^2 = 8/2
x^2 = 4
x = + ou - raiz(4)
x = 2 ou x = -2

Aqui entendemos porque o "+ ou -". Isso acontece porque tanto a raiz(4), que é 2, serve de solução, quanto o negativo dela, -2. Podemos ver isso simplesmente substituindo o valor do x com esses dois valores:

x^2 = 4
(2)^2 = 4
4 = 4, portanto 2 é solução.

Agora vamos testar o -2:
x^2 = 4
(-2)^2 = 4
4 = 4, também funciona, pois o quadrado de -2 também é 4.

Os dois valores, 2 e -2, tornam a equação verdadeira, portanto S = {-2, 2}

Caso 4:

a = 1, mas nem o b nem o c são zero.

Nesse caso é um pouco mais difícil, pois precisamos fatorar o termo da esquerda:

x^2 + x - 6 = 0

De acordo com o caso S e P, podemos escrever o lado da esquerda como:

(x + 3)(x - 2) = 0

Lembra o que falamos sobre o único jeito de dois números se multiplicarem dar zero é se pelo menos um for zero? Então isso quer dizer que

x + 3 = 0 ou x - 2 = 0

Temos agora duas equações de primeiro grau, cada uma dando uma solução. A primeira dá x = -3 e a segunda dá x = 2, portanto S = {-3, 2}. Ou seja, tanto x = -3 quanto x = 2 tornam a equação verdadeira.

Mais um exemplo, dessa vez com a regra do trinômio quadrado perfeito:

x^2 - 6x + 9

Como S = -6 é o mesmo que (-3) + (-3),  e P = 9 é o mesmo que (-3).(-3), temos

(x - 3)^2 = 0
que é o mesmo que
(x - 3)(x - 3) = 0

Caímos de novo na situação em que duas coisas multiplicadas são 0 e portanto uma delas deve ser zero. Mas na verdade essas "duas coisas" são a "mesma coisa", (x-3), só que duplicada. Isso quer dizer que x - 3 deve ser zero para que essa equação funcione e seja verdadeira. x - 3 = 0 portanto x = 3.

Essa é a única solução, portanto S = {3}.

Caso 5:

Nem b nem c são zero, e a não é 1.

O Caso 4 só funciona quando a = 1, porque a fatoração só funciona quando o x^2 não é multiplicado por ninguém. Porem podemos lidar com esse caso desse jeito aqui:

ax^2 + bx + c = 0
e o a não é 1.

Se multiplicarmos a equacao dos dois lados por 1/a, cancelaremos aquele a!

1/a ( ax^2 + bx + c ) = 1/a . 0
1/a ( ax^2 + bx + c ) = 0       (pois 1/a . 0 dá 0)
1/a . ax^2 + 1/a . bx + 1/a . c = 0      (distributiva)
ax^2 / a + (b/a)x + c/a = 0      (produto de frações)
x^2 + (b/a)x + c/a = 0           (cancelamos o a "de baixo"  com o a multiplicando o x^2)

Agora temos uma nova equacão do segundo grau. Quem são o a, b, e c dessa nova equacao? Vamos chama-los de a', b' e c' pra não confundir com o a, b, e c originais.

O a' é quem multiplica o x^2, ou seja , a' = 1.
b' é quem multiplica o x, portanto b' = b/a
c'
é quem está sozinho, sem x nenhum, ou seja, c' = c/a.

Como o a' dessa equação é 1 podemos usar o Caso 4 nela. Ou seja, o Caso 5 nos ajuda a transformar o problema em um novo problema que podemos resolver com o Caso 4.

Vamos ver alguns exemplos:

2x^2 + 10x + 8 = 0

Como a não é 1, usamos o Caso 5:

1/2 (2x^2 + 10x + 8) = 1/2 . 0

Usando as mesmas regras que usamos antes:

1/2 (2x^2 + 10x + 8) = 1/2 . 0
1/2 . 2x^2 + 1/2 . 10x + 1/2 . 8 = 0
x^2 + 5x + 4 = 0

(note que multiplicar por 1/2 é a mesma coisa que dividir por 2, e de fato foi esse o efeito, cada coeficiente passou a ter a metade do valor).

Agora temos uma equação na qual podemos usar o Caso 4! S = 5 e P = 4 são soma e produto de 4 e 1, portanto

(x + 4)(x + 1) = 0
o que leva a dizer que
x + 4 = 0
ou
x + 1 = 0
e portanto
x = -4
ou
x = -1

Assim, S = {-4, -1}.

Wednesday, February 9, 2011

How to pin a document to the taskbar in Windows 7, instead of to the jump list of the corresponding application

When you drag a document to the taskbar in Windows 7, it will add that document to the jump list associated to the corresponding application (if the application is not there already, it places it there). The problem with it is that, to access the document, you need to right-click the application icon to show the jump list, and then click on the document. It takes too long. Sometimes you want to have super quick access to that one document (while we are at it, it may be worth mentioning that Win+1, Win+2 etc give access to items in the taskbar -- another very quick way of accessing them).

A basic solution is to create a shortcut for the application and add the corresponding document as an argument to the shortcut. See the steps below for details. This was elaborated from this page (here's a version with lots of screen shots).

- Go to document of interest, right-click on it, go to Properties, copy and paste its location, that is, its path;
- Drag the application icon (from, say, the Start Menu) to the Desktop to make a shortcut;
- Right-click on application shortcut, go to Properties, and paste, between quotes, the path to the file (see example below);
- Add, the the file path, the name of the file (because the location in its Properties window contains only the path, not the name, of the file).

Example:

When you open the shortcut properties, you may seem something like:

"C:/Program Files/Application.exe"

Make that
"C:/Program Files/Application.exe" "C:/Users/John/Documents/FileOfInterest.xxx"

PS: This assumes that the application takes a document full path and name as a first argument, and opens it. This is the case for most applications, but not necessarily all. In the case this is not true, you would have to find out how to open a file with that application from the command prompt (because using a shortcut is like running a command from the command prompt).