DATS 2300202002

Prev Up Next

Forelesninger uke 2

I denne uken går vi igjennom kapittel 1.2 og deler av kapittel 1.3. 

 

Permutasjoner og leksikografisk sortering

I denne videoen går vi gjennom hvordan vi ordner forskjellige permutasjoner - leksikografisk sortering. Jeg går også gjennom litt hvordan man lager neste permutasjon algoritmisk. Les også mer i kompendiet om hvordan dette gjøres. Easter bunny: Hva spør siri om i videoen? Hvor mange ganger knoter jeg med å si "leksikografisk".

Nyttige linker:

• https://www.cs.hioa.no/~ulfu/appolonius/kap1/3/kap13.html#1.3.2

 

Intervaller

Hva er forskjellen på følgende metoder?

• int maks(int left, int right);
• int maks(int begin, int end);

I denne videoen går vi igjennom intervaller: både lukkede intervaller [left, right], og halvåpne intervaller [begin, end). Les også i kompendiet. 

Turneringstrær

I denne videoen går vi gjennom vår første datastruktur utenom et flatt array - nemlig binære trær, eller nærmere bestemt turneringstrær.  Vi bruker turneringstrær til å finne største tall i et array. I kompendiet er det beskrevet mer bla. her.

 

Nest største verdi i en tabell

I disse to videoene går vi gjennom hvordan vi finner nest største verdi i en tabell. I første video lager vi en algoritme som likner på maks-funksjonen vi tidligere har brukt. I den andre videoen bruker vi turneringstrær til å finne nest største verdi.

Binærtrær

Siden vi har snakket om turneringstrær så kan det være veldig nyttig å se på binærtrær generelt. I denne videoen går vi gjennom hvordan vi kan snakke om binærtrær og noder i treet. 

Stor O notasjon, bobling, sortering, og binærtrær

I disse to forelesningsvideoene så går vi gjennom stor O-notasjon, og hvordan og hvorfor vi snakker om "O(n)", "O(log(n))", og "O(n^2)" funksjoner. Vi går også gjennom bobling og nevner såvidt konseptet om inversjoner (usorterte tall). Til slutt går vi noe gjennom binærtrær - denne gangen ved å se på hvordan vi kan lage en klasse for å representere treet istedenfor et array som vi har sett på tidligere. Vi diskuterer så noen fordeler og ulemper med de to måtene å lagre et binærtre på. Andre video kutter litt før jeg avslutter (litt usikker på hvorfor dette skjedde), men det er ingenting essensielt som mangler i videoen. 

Relevante linker:

• https://www.bigocheatsheet.com/
• Tom Scott sin video om Big O notation - veldig mange av de temaene som gås gjennom i forelesning: Why My Teenage Code Was Terrible: Sorting Algorithms and Big O Notation