You are not logged in.

Currywurst mit Pommes

Erfahrener Schreiberling

  • "Currywurst mit Pommes" started this thread

Posts: 438

Date of registration: Oct 14th 2002

1

Tuesday, February 13th 2007, 9:37am

Datenstrukturen u. Algorithmen - Klausur (Erfahrungen?)

Im März steht die Klausur für D u. A. (Wolter / Peinecke) an.

Leider scheint es ja keinen Probekausuren/Altklausuren zu geben. Deswegen würde mich interessieren, was mich erwarten wird. Vielleicht kann sich ja noch jemand an ein paar Aufgabe erinnern.

Teilweise gab es auf den Übungszetteln ja ziemliche Knobelaufgaben - kommt soetwas auch vor ? 8o ... oder Beweise ?

Update: Habe gerade entdeckt, dass gestern eine Übungsklausur hochgeladen wurde (Elearning).

This post has been edited 1 times, last edit by "Currywurst mit Pommes" (Feb 13th 2007, 9:43am)


BLUESCREEN

Junior Schreiberling

  • "BLUESCREEN" is male

Posts: 244

Date of registration: Oct 11th 2005

2

Tuesday, February 13th 2007, 3:05pm

Danke für den Hinweis - wollte auch schon danach fragen.

Posts: 101

Date of registration: Nov 8th 2005

Location: Hannover

3

Wednesday, February 21st 2007, 8:54pm

Meine Frage hat zwar mit Erfahrung nicht zu tun aber mit d. Klausur :D

Welche Hilfsmitteln sind bei d. Klausur zugelassen? Im Stud.IP stehts nichts und auf der Homepage stehts auch nicht. ?(

Danke im vorraus :)

Torrero

Senior Schreiberling

  • "Torrero" is male

Posts: 854

Date of registration: Oct 16th 2003

Location: Laatzen

Occupation: Angewandte Informatik

4

Wednesday, February 21st 2007, 9:41pm

Vor 2 Jahren waren bei Herrn Wolter keine zugelassen, soweit ich mich noch erinnern kann.

julianr

Erfahrener Schreiberling

Posts: 298

Date of registration: Oct 13th 2005

Location: I live in a giant bucket.

5

Thursday, February 22nd 2007, 1:41pm

Jop, hat Niklas Peinecke in der letzten Übung auch so angekündigt (und begründet, aber das kann man sich bei DSA ja denken).

Posts: 101

Date of registration: Nov 8th 2005

Location: Hannover

6

Thursday, February 22nd 2007, 2:21pm

oh je 8o

migu

free rider

  • "migu" is male

Posts: 2,643

Date of registration: Dec 11th 2001

Occupation: Developer

7

Thursday, February 22nd 2007, 5:59pm

Quoted

Original von flower-power
oh je 8o
Keine Panik! Die Klausur ist auch ohne Hilfsmittel sehr gut zu schaffen. So war es jedenfalls vor vier Jahren und ich denke nicht, dass sich daran etwas geändert hat. :)
tar: Anlegen eines leeren Archivs wird feige verweigert.

This post has been edited 1 times, last edit by "migu" (Feb 22nd 2007, 5:59pm)


BLUESCREEN

Junior Schreiberling

  • "BLUESCREEN" is male

Posts: 244

Date of registration: Oct 11th 2005

8

Thursday, February 22nd 2007, 10:22pm

Wurden die Klausurthemen eigentlich irgendwie eingegrenzt?

Es gab ja einige Themen, die in der Vorlesung zwar vorkamen, aber in den Übungen nichtmal angesprochen wurden, wie z. B. ADT Set, ADT Tabelle, Rot-Schwarz-Bäume und einige der Sortierverfahren.

np

Junior Schreiberling

Posts: 155

Date of registration: Oct 23rd 2002

9

Monday, February 26th 2007, 9:31am

Quoted

Original von BLUESCREEN
Wurden die Klausurthemen eigentlich irgendwie eingegrenzt?

Es gab ja einige Themen, die in der Vorlesung zwar vorkamen, aber in den Übungen nichtmal angesprochen wurden, wie z. B. ADT Set, ADT Tabelle, Rot-Schwarz-Bäume und einige der Sortierverfahren.
Nein, es kann grundsätzlich alles vorkommen, was in der Vorlesung oder Übung erwähnt wurde. Würden in der Klausur nur Themen der Übung behandelt, dann könnte man die Vorlesung ja gleich weglassen. ;)

Currywurst mit Pommes

Erfahrener Schreiberling

  • "Currywurst mit Pommes" started this thread

Posts: 438

Date of registration: Oct 14th 2002

10

Monday, February 26th 2007, 9:56am

Hat jemand zufällig die Lösung für die Aufgabe aus der Übungsklausur. Ich dachte erst: ganz einfach. Aber die innere Schleife entspricht meinen Überlegungen nach ja log4(n+1). Wie bilde ich dann da noch die Summen von (zu den for -Schleifen) ?

Ach ja: Kennt jemand gute Websites zu Summen ? Ich hab da wohl doch ein paar "kleine" Lücken...

Source code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void f(int n)
{
   int i,j,k;
   for(i=1; i<=n; i++)
   {
       for(j=1; j<=n/2; j++)
      {
         k=n;
         while(k>0)
        {
             k=k/4;
        }
     }
  }
}

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

11

Monday, February 26th 2007, 1:23pm

Quoted

Original von Currywurst mit Pommes
Hat jemand zufällig die Lösung für die Aufgabe aus der Übungsklausur. Ich dachte erst: ganz einfach. Aber die innere Schleife entspricht meinen Überlegungen nach ja log4(n+1). Wie bilde ich dann da noch die Summen von (zu den for -Schleifen) ?
Ich vermute mal, die Aufgabe besteht darin, die Laufzeit der Prozedur in Abhängigkeit des Arguments anzugeben. Dann verstehe ich Dein Problem allerdings nicht. Die Zählvariablen der Schleifen sind doch gar nicht miteinander verknüpft. Es läuft also auf die simple Multiplikation der Anzahlen der Schleifendurchläufe hinaus.

Was genau meinst Du zudem mit "Summen"?
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Currywurst mit Pommes

Erfahrener Schreiberling

  • "Currywurst mit Pommes" started this thread

Posts: 438

Date of registration: Oct 14th 2002

12

Monday, February 26th 2007, 1:30pm

d'oh...ich glaube ich habe es mir komplizierter gemacht als es ist. du hast recht.

Also wäre die Laufzeitklasse O(n²*log(n)) ?

This post has been edited 2 times, last edit by "Currywurst mit Pommes" (Feb 26th 2007, 1:32pm)


neon

Praktikant

  • "neon" is male

Posts: 11

Date of registration: Mar 15th 2007

13

Wednesday, March 21st 2007, 5:09pm

Meine Lösung zu Aufgabe 5 b) und c) der Probeklausur:

0
1
2 herz
3 pik
4 karo
5 kreuz
6 koenig
7 bube
8 as
9 dame
10

mittlere Anzahl von Zugriffen für erfolgreiche Suche 15/8 = 1,875

Ist das richtig?

Wie geht d) ? ?(

Bitte um Antworten :(

This post has been edited 2 times, last edit by "neon" (Mar 21st 2007, 5:17pm)


sommla

Junior Schreiberling

  • "sommla" is male

Posts: 169

Date of registration: Oct 27th 2005

14

Wednesday, March 21st 2007, 5:56pm

Quoted

Original von neon

0
1
2 herz
3 pik
4 karo
5 kreuz
6 koenig
7 bube
8 as
9 dame
10



Ich würd sagen, dass das falsch ist.
koenig kommt auf 0
1. für h1= 5
2. 5 schon belegt, also h2
3. h2 = 2, also immer zwei schritte weiter (0 ist wieder erster freier platz)

Damit kommt "as" auch dann auf 6



Die mittlere Anzahl der Zugriffe ist genau 2.
1/8 * ( 1+2+1+1+2+2+4+3) = 2
Lieber ein Haus im Grünen als 'nen Grünen im Haus.

neon

Praktikant

  • "neon" is male

Posts: 11

Date of registration: Mar 15th 2007

15

Wednesday, March 21st 2007, 6:44pm

koenig sind aber 6 Buchstaben also ist h1=6.

as sind 2 Buchstaben also ist h1=2. Das ist belegt also h2=2. Somit landet as auf 8.

sommla

Junior Schreiberling

  • "sommla" is male

Posts: 169

Date of registration: Oct 27th 2005

16

Wednesday, March 21st 2007, 6:47pm

oh mist, stimmt hast recht - bin noch beim ö gedanklich gewesen ;)
Lieber ein Haus im Grünen als 'nen Grünen im Haus.

neon

Praktikant

  • "neon" is male

Posts: 11

Date of registration: Mar 15th 2007

17

Wednesday, March 21st 2007, 6:49pm

halb so schlimm, wär ja mit könig richtig gewesen. ;)

Scooby22

Trainee

  • "Scooby22" is male

Posts: 77

Date of registration: Sep 12th 2004

Location: Laatzen

Occupation: Angew. Informatik

18

Wednesday, March 21st 2007, 7:38pm

sehe ich das richtig

hi(x)=( h1(x) + i * h2(x)) mod M für i=1.....

weil in meinem Buch steht

hi(x)=( h1(x) + i² * h2(x)) mod M

diese Formel wende ich doch nur an , wenn es zu einer Doppelkollision kommt oder?
Bin gerade verwirrt.

This post has been edited 2 times, last edit by "Scooby22" (Mar 21st 2007, 7:55pm)


Adler07

Trainee

  • "Adler07" is male

Posts: 54

Date of registration: Feb 25th 2007

Occupation: Informatik

19

Wednesday, March 21st 2007, 7:39pm

Ergebnis ist richtig?

hallo,ich denke ,es gibt einige Fehler in der Lösung von oben und zwar:

für die Aufgabe 5 b)

element Zugriffe
0
1
2 herz 2
3 pik 1
4 karo 1
5 kreuz 1
6 koenig 1
7 bube 2
8 as 4
9 dame 2
10


die mittlere Zugriffszahl: (2+1+1+1+1+2+4+2)/8 = 14/8

This post has been edited 1 times, last edit by "Adler07" (Mar 21st 2007, 7:39pm)


Neutrino

masselos

  • "Neutrino" is male

Posts: 661

Date of registration: Oct 6th 2005

Location: Hannover

Occupation: SRA Mitarbeiter

20

Monday, March 26th 2007, 9:06pm

prüfungsergebnis?

weiß jmd wann es die Ergebnisse gibt?