Kursplan för Algoritmer och datastrukturer I

Algorithms and Data Structures I

Det finns en senare version av kursplanen.

Kursplan

  • 5 högskolepoäng
  • Kurskod: 1DL210
  • Utbildningsnivå: Grundnivå
  • Huvudområde(n) och successiv fördjupning: Datavetenskap G1F, Teknik G1F

    Förklaring av koder

    Koden visar kursens utbildningsnivå och fördjupning i förhållande till andra kurser inom huvudområdet och examensfordringarna för generella examina:

    Grundnivå
    G1N: har endast gymnasiala förkunskapskrav
    G1F: har mindre än 60 hp kurs/er på grundnivå som förkunskapskrav
    G1E: innehåller särskilt utformat examensarbete för högskoleexamen
    G2F: har minst 60 hp kurs/er på grundnivå som förkunskapskrav
    G2E: har minst 60 hp kurs/er på grundnivå som förkunskapskrav, innehåller examensarbete för kandidatexamen
    GXX: kursens fördjupning kan inte klassificeras.

    Avancerad nivå
    A1N: har endast kurs/er på grundnivå som förkunskapskrav
    A1F: har kurs/er på avancerad nivå som förkunskapskrav
    A1E: innehåller examensarbete för magisterexamen
    A2E: innehåller examensarbete för masterexamen
    AXX: kursens fördjupning kan inte klassificeras.

  • Betygsskala: Underkänd (U), godkänd (3), icke utan beröm godkänd (4), med beröm godkänd (5)
  • Inrättad: 2007-03-19
  • Inrättad av: Teknisk-naturvetenskapliga fakultetsnämnden
  • Reviderad: 2010-04-27
  • Reviderad av: Teknisk-naturvetenskapliga fakultetsnämnden
  • Gäller från: vecka 27, 2010
  • Behörighet: 10 hp programmering (Programkonstruktion, Programmeringsteknik II eller motsvarande) och 10 hp matematik, inklusive grundläggande algebra.
  • Ansvarig institution: Institutionen för informationsteknologi

Mål

För godkänt betyg ska studenten kunna


  • analysera körtiden för en (enkel) algoritm/program i relation till indatats storlek, i bästa, sämsta, och genomsnittliga fall,

  • välja lämpliga algoritmer och datastrukturer för lagring av data, sökning och sortering, samt implementera dessa.

  • använda och implementera grundläggande grafalgoritmer.

Innehåll

Matematiska grunder: asymptotisk notation, summationer, rekursionsformler.
Datastrukturer: träd, prioritetsköer, "heaps".
Sökmetoder: binära sökträd, balanserade sökträd, hashtabeller.
Sorteringsmetoder.
Enkla grafalgoritmer: djup-först och bredd-först sökning.
Implementering av algoritmer och datastrukturer.

Undervisning

Föreläsningar, lektioner, laborationer och
obligatoriska inlämningsuppgifter.

Examination

Skriftligt prov (4 hp) samt inlämningsuppgifter (1 hp).

Övriga föreskrifter

Kursen kan inte räknas in i examen med Programkonstruktion II (1IT022) eller
Datastrukturer (1DL009, 1TD191, 1MB026).

Litteratur

Litteraturlista

Gäller från: vecka 27, 2009

I bibliotekets söktjänst kan du se om en titel finns elektroniskt.

Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Introduction to Algorithms. 3rd ed. MIT Press, 2009.