IntroProg 2017

Aufgabe1
- Zahlen in Binärbaum einfügen
- als Array darstellen
- Zugriffs Laufzeit O notation

Aufgabe2
- Zahlen in Min Heap einfügen
- als Array darstellen
- Laufzeit finden Min

Aufgabe3
- Zahlen in AVL baum einfügen
- Angeben ob Rotation wenn ja um welchen Knoten

Aufgabe4
- Speisekarten als struct mit nr, gericht, preis
  nr im Array aufsteigend sortiert, implementiere binaere suche
  bei Treffer print<nr><gericht><preis> und return <preis>, bei
  nicht Treffer return -1.

Aufgabe4.1
- Was ist die Laufzeit begründe?

Aufgabe4.2
- Wenn Array nicht sortiert, terminiert der Algorithmus?, liefert er korrektes Ergebnis?

Aufgabe5
- mehrere Beispiele von zu sortierenden Zahlen, gib an welchen sortier Algorithmus,
  begründe, teilweise mehrere Antworten möglich
  z.B.: - 1 Milliarde Daten großer Werte bereich
  			(MergeSort)
  		- 1 Million Daten Werte zwischen -70 und 90
  			(CountSort)
  		- 8 Planeten, nach entfernung sortieren
  			(BubbleSort)
  		- sortierte Liste alle paar Minuten kleine Änderung dann neu sortieren
  			(InsertionSort)
  		- Zählen der Linksabbieger an Kreuzung, bis zu 1000 täglich, an welchen Tagen am Meisten
  			(SelectionSort)

Aufgabe6
- gegeben folgender Algorithmus:
	Summe(x,y)
		resultat = 0
		for i=1 to x do
			resusltat = resultat + 1
		for j=1 to y do
			resultat = resultat + 1
		return resultat

  und Tabelle mit links Quantifizierungen und rechts andere Teil
  z.B.:	-A(keine Quantifizierung)		-1 Summe(x,y)=12
  		-B für alle k aus {1...j}		-2 Summe(x,y)= x+2
  							...
- gib Korrektheitsaussage an mit Begründung
	(Summe = x + y)

andere Tabelle:
- gib 1. Schleifeninvariante an mit Begründung
	(resulat = i - 1)

- gib 2. Schleifeninvariante an mit Begündung, von der sich die Korrektheitsaussage ableien lässt 
	(resultat = x + j -1)


(in keiner der Tabellen passte eine Variable der linken Seite zu den auf der rechten Seite -> niemals Quantifizierung)