Jag har läst lite om det. Ifall du vill ha en bok för det i C++ så har jag http://www.adlibris.com/se/product.aspx?isbn=0534491820 du kan få köpa billigt 🙂

sylar:

finns det någon här på forumet som hållit på eller håller på med det?

Jag har läst en kurs i datastrukturer, och håller just nu på med en kurs i algoritmdesign.

sylar:

Alla kodarrävar här på forumet, vad brukar ni använda för något när ni sorterar heltalslistor exempelvis?

Språkets inbyggda sortering (som ofrånkomligen är antingen mergesort eller quicksort.) Väldigt dumt att lägga ned tid på att implementera såna grundläggande byggstenar om och om igen.

Gentlemen:

Jag har läst lite om det. Ifall du vill ha en bok för det i C++ så har jag http://www.adlibris.com/se/product.aspx?isbn=0534491820 du kan få köpa billigt 🙂

Nej tack : )

Gentlernen:

Språkets inbyggda sortering (som ofrånkomligen är antingen mergesort eller quicksort.) Väldigt dumt att lägga ned tid på att implementera såna grundläggande byggstenar om och om igen.

Jo, det är sant.

För att en tråd med potential inte ska dö, så kommer här lite frågesport:

1. Du ska sortera en dubbelt länkad lista. Vilken sorteringsalgoritm använder du, och varför?

2. Du ska sortera en array med 1000 element. Vilken är den bästa möjliga komplexitet du kan få för denna funktion? Med vilken algoritm?

3. Här nedan följer en algoritm som tar en array A som är n tal lång, och skapar en n*n tvådimensionell array B som innehåller summorna mellan olika positioner i den första arrayen. (B[i, j] innehåller summan av alla tal mellan A[ i ] och A[j].) Analysera algoritmens komplexitet.

For i = 1 to n
    For j = i+1 to n
        sum = 0
        For k = i to j
            sum = sum + A[k]
        End for
        B[i, j] = sum
    End for
End for

4. Ge en algoritm med asymptotiskt bättre komplexitet än den som gavs i uppgift 3. (Dvs. om uppg. 3 var av komplexitet O(n⁵) måste din algoritm vara av ordningen O(n⁴) som värst.)

5. Du skriver ett ordlisteprogram där användaren matar in ett ord på svenska, och får tillbaka översättningen på engelska. Du har sedan tidigare statistik som visar att det finns en klar uppdelning i ord som ofta slås upp, och ord som sällan slås upp. Du har bestämt dig för att du bör använda någon sorts trädstruktur för att representera ordlistan. Vilken typ av träd använder du, och varför?

6. Implementera quicksort på ett sätt som inte drar mer än O(n) minne och som har så bra genomsnittskomplexitet som möjligt. Motivera varför din implementation har bra genomsnittskomplexitet.

En kaka till den förste som får full poäng.

Få se nu, börjar med att svara på dem som känns lite bekanta. Tar de andra sedan : )

Gentlernen:

2. Du ska sortera en array med 1000 element. Vilken är den bästa möjliga komplexitet du kan få för denna funktion? Med vilken algoritm?

Med Bucket Sort så kan man få en förväntad körtid som är linjär. Vet inte om det finns några andra som har samma komplexitet, men O(n) ska väl vara bästa möjliga.

Gentlernen:

3. Här nedan följer en algoritm som tar en array A som är n tal lång, och skapar en n*n tvådimensionell array B som innehåller summorna mellan olika positioner i den första arrayen. (B[i, j] innehåller summan av alla tal mellan A[ i ] och A[j].) Analysera algoritmens komplexitet.

For i = 1 to n                         (n)
    For j = i+1 to n                  (n-i-1)
        sum = 0                         (c1)
        For k = i to j                   (c2) loopar bara en gång så det är konstant
            sum = sum + A[k]     (c3)
        End for
        B[i, j] = sum                  (c4)
    End for
End for

Denna innersta loopen körs väl bara en gång, så den måste köras lika många gånger som den andra loopen eftersom (j-i) = (i+1 - i) = 1.

n * ((n-i-1)*(c1*c2*c3)) = n^2 - ni - n * n*c1 * n*c2 * n*c3
Ta bort lägregradstermer samt konstanter:
= O(n^2 - ni)

Blev lite knivigt med så många variabler och så, men det är min gissning.

Gentlernen:

5. Du skriver ett ordlisteprogram där användaren matar in ett ord på svenska, och får tillbaka översättningen på engelska. Du har sedan tidigare statistik som visar att det finns en klar uppdelning i ord som ofta slås upp, och ord som sällan slås upp. Du har bestämt dig för att du bör använda någon sorts trädstruktur för att representera ordlistan. Vilken typ av träd använder du, och varför?

På rak hand så skulle jag nog använda ett binärt sökträd och ordna efter minst och mest förekommande. Ord som är mindre förekommande läggs till som gren till vänster och mer förekommande till höger.
Eller kanske ännu bättre, ett AVL-tree så att trädet hålls balanserat. Då sker sökningen i O(log n) tid.

sylar:

Med Bucket Sort så kan man få en förväntad körtid som är linjär. Vet inte om det finns några andra som har samma komplexitet, men O(n) ska väl vara bästa möjliga.

Stämmer.

sylar:

Denna innersta loopen körs väl bara en gång

Stämmer inte, försök igen.

sylar:

Eller kanske ännu bättre, ett AVL-tree så att trädet hålls balanserat. Då sker sökningen i O(log n) tid.

AVL-träd är bra tänkt, men det finns ett träd som är ännu bättre för detta ändamål. Ledtråd: ord som är vanligt förekommande vill vi slå upp fort, ovanliga ord bryr vi oss inte lika mycket om.

Gentlernen:

AVL-träd är bra tänkt, men det finns ett träd som är ännu bättre för detta ändamål. Ledtråd: ord som är vanligt förekommande vill vi slå upp fort, ovanliga ord bryr vi oss inte lika mycket om.

Hmm, huffmanträd eller en max-heap kanske? I max-heapen så kan man plocka ut maximumet tills den hittar. Huffmanträden kanske är mer för att få optimal teckenkod, men det är det första jag tänker på när du nämner vanligt förekommande : )

sylar:

For i = 1 to n (n)
For j = i+1 to n (n-i-1)
sum = 0 (c1)
For k = i to j
sum = sum + A[k] (c3)
End for
B[i, j] = sum (c4)
End for
End for

I slutändan så blir väl tidskomplexiteten O(n^3), eftersom varje loop i värsta fall tar O(n).

sylar:

Hmm, huffmanträd eller en max-heap kanske? I max-heapen så kan man plocka ut maximumet tills den hittar. Huffmanträden kanske är mer för att få optimal teckenkod, men det är det första jag tänker på när du nämner vanligt förekommande : )

Huffmanträd kanske skulle fungera, men det finns en annan, mindre specialiserad, sorts träd som är väldigt bra på random lookups när det finns en tydlig skillnad mellan vanliga och ovanliga keys.

sylar:

I slutändan så blir väl tidskomplexiteten O(n^3), eftersom varje loop i värsta fall tar O(n).

Korrekt. n³/4 för att vara exakt.

Gentlernen:

Huffmanträd kanske skulle fungera, men det finns en annan, mindre specialiserad, sorts träd som är väldigt bra på random lookups när det finns en tydlig skillnad mellan vanliga och ovanliga keys.

Ingen aning då faktiskt : /

sylar:

Brukar ni lägga ner energi på att göra asymptotiska analyser av era program? : )

Givetvis.

sylar:

Ingen aning då faktiskt : /

Eftersom ingen bemödat sig om att svara på ett tag, så får jag ta och avslöja att splayträd var det tänkta svaret.

Nu står 4 och 6 kvar obesvarade, någon villig?

Har vart lite upptagen med att lära mig om minimum spanning trees, grafer och sådant. I synnerhet Prim's algoritm och Dijkstra's algoritm, rent grafiskt då.

Prim känns lite som Dijkstra's faktiskt, eftersom den tar ut kortaste vägen fram till en vertex bara. Medan Dijkstra's tar kortaste vägen till alla vertices.

Gentlernen:

Eftersom ingen bemödat sig om att svara på ett tag, så får jag ta och avslöja att splayträd var det tänkta svaret.

Aha, då lärde man sig något nytt : )

Gentlernen:

Nu står 4 och 6 kvar obesvarade, någon villig?

Kan försöka mig på fråga 6 efter jag sovit : )

Helt klart ett kul ämne som jag dock endast sniffat litegrann på hittills.

Tråden låst på grund av inaktivitet