Besvarelse fra gruppe nummer: [UDFYLD] NOTE: medmindre andet er angivet, forventes svaret at være kort (ofte een linie). ************************* OPGAVE 1 ************************* SPØRGSMÅL: Beskriv metoden I brugte detaljeret nok til at andre kan udføre den (5-10 liniers svar). SVAR: ************************* OPGAVE 2 ************************* SPØRGSMÅL: Angiv gennemsnittet. SVAR: ************************* OPGAVE 3 ************************* SPØRGSMÅL: Angiv gennemsnittet. SVAR: ************************* OPGAVE 4 ************************* SPØRGSMÅL: Angiv gennemsnittet. Beskriv metoden i bruger til at finde den "rette plads i S" detaljeret nok til at andre kan udføre den (5-10 liniers svar). SVAR: ************************* OPGAVE 5 ************************* SPØRGSMÅL: Angiv gennemsnittet. SVAR: ************************* OPGAVE 6 ************************* SPØRGSMÅL: Mindste sorteringsnetværk for at sortere 4, 8, og 10 elementer? SVAR: ************************* OPGAVE 7 ************************* SPØRGSMÅL: Angiv gennemsnittet. SVAR: ************************* OPGAVE 8 ************************* SPØRGSMÅL: Udfyld nedenstående to tabeller: ---------- Tabel 1 ---------- ALGORITME BEDSTE TID VÆRSTE TID SelectionSort InsertionSort MergeSort RadixSort ---------- Tabel 2 ---------- ALGORITME BEDSTE RÆKKEFØLGE VÆRSTE RÆKKEFØLGE SelectionSort InsertionSort RadixSort MergeSort ************************* OPGAVE 9 ************************* SPØRGSMÅL: Hvad er det optimale antal sammenligninger for at sortere 3 og 4 elementer ? SVAR: ************************* OPGAVE 10 ************************* SPØRGSMÅL: Hvorledes kan fire personer samarbejde således at algoritmen bliver udført på ca. en fjerdedel af tiden for een person (10-25 liniers svar i alt): SVAR: Mergesort: SelectionSort: ************************* OPGAVE 11 ************************* SPØRGSMÅL: Angiv for de tre input mængder en hash-funktion der spreder bedst muligt ud, dvs. en hash-funktion hvor tabel indgangen med de fleste elementer har færrest mulige elementer. SVAR: Input Fleste elementer i Hash-Funktion en tabel indgang 1 2 3 ************************* OPGAVE 12 ************************* SPØRGSMÅL: Hvor lang er den længste voksende følge man kan opnå ? SVAR: ************************* OPGAVE 13 ************************* SPØRGSMÅL: Angiv en længst mulig delsekvens som forekommer i begge strenge i ovenstående eksempel. SVAR: ************************* OPGAVE 14 ************************* SPØRGSMÅL: Hvad er det mindste antal delsummer I behøver at gemme for et array af længde 16, således at alle delsum(i,j) spørgsmål kan besvares med henholdvis 1 og 2 additioner? SVAR: 1 addition: 2 additioner: ************************* OPGAVE 15 ************************* SPØRGSMÅL: Angiv en sti fra S til T i ovenstående graf som besøger flest mulige knuder, men hvor hver knude besøges højest een gang på stien. SVAR: ************************* OPGAVE 16 ************************* SPØRGSMÅL: Angiv længden af den kortest vej fra S til T i ovenstående graf. SVAR: ************************* OPGAVE 17 ************************* SPØRGSMÅL: Angiv tiden for det tre løsninger. 2 brikker: 4 brikker: 8 brikker: ************************* OPGAVE 18 ************************* SPØRGSMÅL: Angiv tiden for det tre sorteringer: 8 kort: 16 kort: 32 kort: ************************* OPGAVE 19 ************************* SPØRGSMÅL: Fra og med hvilket N er 0.01*N^2 større 100*N ? Fra og med hvilket N er 0.0001*2^N større 10000*N ? ************************* OPGAVE 20 ************************* SPØRGSMÅL: Udfyld følgende tabel: ---------- Tabel ---------- KØRETID X I ET SEKUND X I ET ÅR Y I ET SEKUND Y I ET ÅR N N*log(N) N^2 100*N^2 N^3 2^N ======================================================================