Tölvunarfræði 2 - Vor 2012

• Dagskrá
• Verkefni
• Dæmatímar
• Námsmat
• Kennslubók
• Lokapróf
• Spjallborð

---

Lausnum skal skilað til viðkomandi dæmakennara (sjá lista yfir dæmatíma).

Reynið að skrifa stutt, skýr og hnitmiðuð forrit. Notið réttan inndrátt og gætið þess að forritin ykkar séu læsileg.

Skiladagur: þriðjudaginn 27. mars fyrir kl 16:00

---

Dæmi 1 (2 stig) - Innsetning í 2-3 tré

Leysið dæmi 3.3.1 í bókinni.

Draw the 2-3 tree that results when you insert the keys E A S Y Q U T I O N in that order into an initially empty tree.

Lausn

---

Dæmi 2 (1 stig) - Rauð-svört tré

Leysið dæmi 3.3.9 í bókinni.

Which of the following are red-black BSTs?

Lausn: (iii) og (iv) eru rauð-svört tré, en (i) og (ii) eru það ekki. (i) er ekki í jafnvægi og (ii) er ekki tvíleitartré.

---

Dæmi 3 (2 stig) - Innsetning í rautt-svart tré

Leysið dæmi 3.3.10 í bókinni.

Draw the red-black BST that results when you insert items with the keys E A S Y Q U T I O N in that order into an initially empty tree

Lausn - Lokastaðan

Lausn - Uppbygging trésins

---

Dæmi 4 (2 stig) - Word frequency counter

Skrifið forrit sem les orð af aðalinntaki og prentar út á aðalúttak hversu oft hvert orð kemur fyrir í inntakinu.

Notið rautt-svart tré (RedBlackBST) til að halda utan um talninguna.

Lausn - wc.java

import java.util.Scanner;

public class wc
{
	public static void main(String[] args)
	{
		RedBlackLiteBST<String, Integer> count = new RedBlackLiteBST<String, Integer>();

		Scanner scan = new Scanner(System.in);

		while (scan.hasNext())
		{
			String word = scan.next();

			if (count.contains(word))
				count.put(word, count.get(word) + 1);
			else
				count.put(word, 1);
		}

		for (String s : count.keys())
		{
			System.out.printf("%s: %d\n", s, count.get(s));
		}
	}
}

---

Dæmi 5 (3 stig) - File index

Skrifið forrit í C eða Java sem tekur inn lista af skrám sem viðföng í skipanalínu og býr til flýtivísi þ.a. það sé hægt að fletta hratt upp öllum skránum sem innihalda gefið orð.

Forritið á að lesa orð af aðalinntaki og prenta út lista yfir allar skrár (af þeim sem voru gefnar upp á skipanalínu sem viðföng) sem innihalda viðkomandi orð.

Notið rautt-svart tré til að geyma flýtivísinn. Lyklarnir í trénu eiga að vera orð og gildin eiga að vera listi af skrám sem innihalda viðkomandi orð.

Þið megið nota java.util.TreeSet tilvik sem gildi í trénu.

Lausn - FileIndex.java

import java.io.File;
import java.util.Scanner;
import java.util.TreeSet;

public class FileIndex
{
	public static void main(String[] args) throws Exception
	{
		RedBlackLiteBST<String, TreeSet<File>> st = new RedBlackLiteBST<String, TreeSet<File>>();

		System.out.println("Indexing files");

		for (String filename : args)
		{
			System.out.println("  " + filename);

			File file = new File(filename);
			Scanner scan = new Scanner(file);

			while (scan.hasNext())
			{
				String word = scan.next();

				if (!st.contains(word))
					st.put(word, new TreeSet());

				TreeSet set = st.get(word);
				set.add(file);
			}
		}

		Scanner stdin = new Scanner(System.in);

		while (stdin.hasNext())
		{
			String query = stdin.next();

			if (!st.contains(query))
				continue;

			TreeSet<File> set = st.get(query);

			for (File file : set)
				System.out.println("  " + file.getName());
		}
	}
}