"1.     Fylla í Helmingunarleit"

        // Notkun:  k = leita (f, i, j, x);
        // Fyrir:       f[i .. j−1] er í minnkandi röð
        // Eftir:       f[i .. j−1] er óbreytt , i <= k <= j , og  f[i .. k−1] >= x > f[k .. j−1]
        int leita(double[]f, int i, int j, double x)
        {
            if (i == j) return i;
            int m = i + ( j−i )/2 ;
            if (f[m] ?1? x) return leita(f, i, ?2?, x);
            else return leita(f, ?3?, j, x);
        }




        int leita(double[]f, int i, int j, double x)
        {
            int p=i , q=j;
            while(?4?)
            {
                // | >=x | óþekkt | <x |
                //  i     p        q    j
                int m = p + (?5?)/2;
                if (f[m] ?6? x)  p = ?7?;
                else q = ?8?;
            }
            return p;
        }



        Til að finna út hvort það sé goggur/jafntog eða bara goggur. Í Notkun/Fyrir/Eftir:

        Ef X = a[k] þá er goggurjafntog í línunni þar sem J breytist (j=m) og bara goggur í línunni þar sem i breytist (i = m+1)
        Ef X = a[k-1] þá er bara goggur í línunni þar sem J breytist (J = m) og goggurjafntog í línunni þar sem i breytist (i=m+1)









        Svar/Answer:
        ?1? <
        ?2? m
        ?3? m+1
        ?4? p!=q eða p<q
        ?5? q-p
        ?6? >=
        ?7? m+1
        ?8? m


"2.     Fylla í Selection Sort"

        // Notkun:  swap (f, i, j);
        // Fyrir:       f[i] og f[j] eru sæti í f
        // Eftir:       Búið er að víxla gildunum í f[i] og f[j]
        void swap(double [] f, int i, int j);

        // Notkun:  sort (f, i, j);
        // Fyrir:       f[i .. j−1] er ekki −tómt svæði í f
        // Eftir:       Búið er að raða f[i . . j −1] í minnkandi röð
        void sort (double [] f, int i, int j)
        {
            int p = ?1?;
            while (?2?)
            {
                // | stærstu gildi í minnkandi röð | óþekkt |
                //  i                               p        j
                int q = ?3?;
                while(?4?)
                {
                    // a) | stærstu gildi í minnkandi röð | óþekkt |
                    //     i                               p   q    j
                    // b)   p < q <= j
                    // c) f[p] er stærst af f[p . . q−1]
                    if(f[q] ?5? f[p])
                    swap(f, p, q);
                    q++;
                }
                p++;
            }
        }





        ATH: Í hverri umferð ytri lykkju finnur Selection Sort minnsta stakið  í óraða svæðinu og raðar því rétt o.s.fv.








        Svar/Answer:
        ?1? i
        ?2? p!=j
        ?3? p+1
        ?4? q!=j eða q<j
        ?5? >

"3.     Fastayrðing seinni lykkju Heap Sort"

        Svar: d)

        | hrúga með stærsta efst | stærst í vaxandi röð |
         0                        i                      n


"4.     a) Fastayrðing fyrri lykkju    Heap Sort"


        | hrúga | óþekkt |
        EÐA
        | óþekkt | uppfyllir hrúguskilyrði |



    "b) Tímaflækja Heap Sort"


        Svar/Answer:

        Tímaflækjan er O(n log n) vegna þess að heapsort vinnur í tveimur
        lykkjum, fyrri og seinni, og hver umferð í hvorri lykkju hefur tímaflækju O(log n).
        Í báðum tilfellum felst hver umferð lykkjunnar í að rúlla gildi niður hrúgu á réttan
        stað. Þar eð hrúgan inniheldur í mesta lagi n gildi er tímaflækja umferðarinnar
        O(log n).

"5.     Gera Quicksort ef þú færð Partition gefið "


        Svar/Answer:

        // Notkun: sort(a,start,end);
        // Fyrir: a[start..end-1] er svæði í fylkinu a.
        // Eftir: Búið er að raða a[start..end-1] í vaxandi röð.
        void sort( double a[], int start, int end )
        {
            if(end-start < 2) return;
            int k,n;
            skipta(a,start,end,k,n);
            sort(a,start,k);
            sort(a,k+1,n);
            sort(a,n+1,end);
        }


"6.     Merge Sort "

        Svar:

        // Notkun: sort(a,b,i,j);
        // Fyrir: a[i..j-1] og b[i..j-1] eru svæði í fylkjunum a
        // og b.
        // Eftir: Búið er að raða a[i..j-1] í vaxandi röð,
        // b[i..j-1] inniheldur nú eitthvert drasl.
        void sort( double a[], double b[], int i, int j )
        {
            if( j-i<2 ) return;
            int r = i+(j-i)/2;
            int q = i+(r-i)/2;
            int s = r+(j-r)/2;
            // | A | B | C | D |
            //  i   q   r   s   j
            sort(a,b,i,q);
            sort(a,b,q,r);
            sort(a,b,r,s);
            sort(a,b,s,j);
            merge(a,b,i,q,r);
            merge(a,b,r,s,j);
            merge(b,a,i,r,j);
        }


"7.     Tímaflækjur"

        Aðferð                Versti tími    Meðaltími
        Insertion-sort          O(n^2)      same
        Selection-sort          O(n^2)      same
        Quicksort               O(n^2)      O(n log n)
        Merge-sort              O(n log n)      same
        Radix-sort              O(n)            same
        Radix-sort= (gerið ráð fyrir að raðað sé heiltölum af takmarkaðri stærð, assume integers of limited size are being sorted)
        Heapsort                O(n log n)      same

        Fyrir quicksort þarf að tiltaka bæði versta tíma og meðaltíma. Í hinum aðferðunum dugar
        að segja hver versti tíminn er þar eð meðaltíminn er sá sami. Við nefnum ekki besta tíma
        því við höfum takmarkaðan áhuga á honum.



"8.     Meginreglan um upplýsingahuld"


        Svar/Answer:

        Meginreglan um upplýsingahuld segir að fela skuli sérhverja veigamikla
        útfærsluákvörðun (stundum kallað hönnunarákvörðun eða smíðaákvörðun) í einingu.
        Tilgangurinn er að gera kleift að endurskoða ákvörðunina seinna, þ.e. skipta um skoðun.
        Þetta gerir viðhald hugbúnaðarkerfisins auðveldara því seinni tíma breytingar eru ekki
        eins líklegar til að valda keðjuverkun í virkni kerfisins.



"9.     Pow Pow"


        Svar:

        public static double pow(double x, int n)
        {
            if( n==0 ) return 1.0;
            if( n%2==0 ) return pow(x*x, n/2);
            else return x*pow( x*x, n/2);
        }



"10.    Binary Tree's"


        i. Tvíleitartré – Binary search tree

                Tréð er í vaxandi "In-Order" röð


        ii. AVL-tré – AVL tree

                Tréð er í vaxandi "In-Order" röð
                Munurinn á lengd vinstri og hægri hlið getur verið mesta lagi 1 (í lengd)


        iii. Hrúga með hæsta gildi efst – Heap with greatest value on top

                Hrúga með hæsta gildi efst


        iv. Hrúga með minnsta gildi efst – Heap with least value on top


                Hrúga með minnsta gildi efst




        "Pre-Order"

                Root -> Left -> Right

        "In-Order"

                Left -> Root -> Right

        "Post-Order"

                Left -> Right -> Root