Oppgave 1

Anta at relasjonen R på mengden A er refleksiv og transitiv og la S være realsjonen på A gitt ved S = R ∩ R⁻¹.

• Refleksivitet: Hvis R er refleksiv. så er R⁻¹ refleksiv. Dermed er S refleksiv.
• Symmetri: La (a, b) ∈ S. Siden (a, b) ∈ R, vil (b, a) ∈ R⁻¹, og siden (a, b) ∈ R⁻¹, vil (b, a) ∈ R. Dermed vil (b, a) ∈ S.
• Transitivitet: La (a, b) ∈ R⁻¹ og (b, c) ∈ R⁻¹. Da vil (b, a) ∈ R og (c, b) ∈ R. Det gir (c, a) ∈ R siden R er transitiv. Dermed er både R og R⁻¹ transitive og det betyr at S er transitiv.

Oppgave 2

Ekvivalensklassen til "ABCD" vil inneholde 2⁴ = 16 tegnstrenger og den til "algoritme" vil inneholde 2⁹ = 512 tegnstrenger.

Oppgave 3

import java.util.*;

public class StrenglengdeKomparator implements Comparator<String>
{
  public int compare(String s1, String s2)
  {
    return s1.length() - s2.length(); // differansen i strenglengde
  }
} // class StrenglengdeKomparator

Oppgave 4

Hvis en bitsekvens i form av et int-tall starter med en 0-bit, er tallet ikke-negativt. Det å sammenligne slike bitsekvenser leksikografisk er det samme som å sammenligen dem med hensyn på vanlig tallstørrelse. En bitsekvens i form av et int-tall som starter med en 1-bit, representerer på grunn av 2-er komplement, et negativt tall. Hvis det ene tallet er ikke-negativt og det andre negativt, vil det ikke-negative tallet komme foran det negative leksikografisk. Hvis begge er negative, er en leksikografisk sammenligning det samme som å sammenligen med hensyn på tallstørrelse.

public class BitSekvens implements Comparable<BitSekvens>
{
  private int sekvens;

  public BitSekvens() { sekvens = 0; }

  public BitSekvens(int sekvens) { this.sekvens = sekvens; }

  public int compareTo(BitSekvens b)
  {
    if (sekvens >= 0 && b.sekvens >= 0) return sekvens - b.sekvens;
    if (sekvens >= 0 && b.sekvens < 0) return -1;
    if (sekvens < 0 && b.sekvens >= 0) return 1;

    return sekvens - b.sekvens;
  }

  public boolean equals(Object o)
  {
    if (o == this) return true;
    if (!(o instanceof BitSekvens)) return false;
    return compareTo((BitSekvens)o) == 0;
  }

  public String toString()
  {
    String s = Integer.toBinaryString(sekvens);
    if (sekvens < 0) return s;

    int k = 32 - s.length();
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < k; i++) sb.append('0');
    sb.append(s);
    return sb.toString();
  }

  public int hashCode()
  {
    return sekvens;
  }

}

Metoden compareTo kan også kodes direkte på bitene. F.eks. slik:

  public int compareTo(BitSekvens b)
  {
    int k = Integer.highestOneBit(sekvens ^ b.sekvens);
    if (k == 0) return 0;
    return (k & sekvens) == 0 ? - 1 : 1;
  }

Oppgave 5

  Comparator<Student> c = (s1,s2) ->
  {
    int k = s1.klasse().compareToIgnoreCase(s2.klasse());
    return k != 0 ? k : s1.compareTo(s2);
  };

eller

  Comparator<Student> c =
  Comparator.comparing((Student s) -> s.klasse().toUpperCase()).
  thenComparing(Comparator.naturalOrder());