Algoritmer och mjukvarudesign

Att läsa

• En hashtabell, eller hash table, är en datastruktur som används för att lagra nyckel-värde-par. Den är mycket effektiv för att snabbt hitta, lägga till och ta bort data. Här är en grundläggande förklaring av hur en hashtabell fungerar i C#: 1) Nyckel och värde: Varje element i en hashtabell består av en nyckel och ett värde. Nyckeln används för att identifiera värdet. 2) Hashfunktion: En hashfunktion tar en nyckel och omvandlar den till ett index i tex en array där värdet lagras. Detta gör att man kan hitta värdet snabbt. 3) Kollisioner: Ibland kan två olika nycklar generera samma index. Detta kallas en kollision, och det finns olika metoder för att hantera detta, såsom chaining( kedjning) eller open addressing (öppna adressering).
• Kap 8 Hashtables
• Sid 210-212 Hashtable fundmentals
• Sid 212-213 Chaining
• Sid 214 Remove items
• Sid 213-214 Openadressing
• Sid 215 Linear Probing

Att titta på

• Del 1 Intro Hashtabeller - Den första delen handlar om hashtabeller och presenteras i form av en PowerPoint där jag går igenom grundläggande koncept, vanliga begrepp och visar kodexempel på hur man kan skapa en egen implementation av en hashtabell. Jag förklarar vad en hashfunktion är, hur data organiseras i så kallade buckets, och hur man hanterar kollisioner med hjälp av chaining (kedjning). Dessutom går jag igenom vanliga algoritmer för att lägga till, ta bort och söka efter data i en hashtabell.
• Del 2 Hashtabeller Open addressing - Den andra delen om hashtabeller presenteras i en PowerPoint där jag förklarar open addressing, som är ett alternativt sätt att hantera kollisioner jämfört med chaining. Jag går igenom hur open addressing fungerar och vilka olika metoder som kan användas inom det. Dessutom pratar jag om vad som händer när hashtabellen börjar bli full. Då behöver man bland annat öka tabellens storlek dynamiskt och genomföra en rehashing, vilket innebär att alla element placeras om i en ny, större tabell.
• Fö1 Hashtabell (Pär) - I den här delen får du lära dig hur man skapar en egen klass för att implementera en hashtabell, som bland annat kan användas för att hantera bilobjekt. Som buckets används en array där varje plats innehåller en länkad lista. I dessa listor kan vi lagra key-value-par, där nyckeln (key) är bilens registreringsnummer och värdet (value) är själva bilobjektet. Vi går igenom hur add-metoden fungerar för att lägga till ett bilobjekt i hashtabellen. Den använder både en hashfunktion och en teknik för att hantera kollisioner. Om flera bilar får samma index i arrayen, används chaining, vilket innebär att flera objekt kan lagras i samma bucket med hjälp av en länkad lista. Hashfunktionen som används är baserad på DJB2-algoritmen. Den tar en sträng (t.ex. registreringsnumret) och omvandlar den till ett index i arrayen. Det är på den här platsen i tabellen som bilobjektet sedan lagras eller hämtas.
• Fö2 Hashtabell -Get Metoden(Pär) - I den här delen får du lära dig hur man skapar en get-metod som används för att hämta data från hashtabellen baserat på en nyckel – i det här fallet ett registreringsnummer. När du anropar metoden med ett regnummer som nyckel, returneras det bilobjekt som är kopplat till just den nyckeln. Om det har uppstått en kollision (det vill säga att flera olika regnummer har hamnat på samma plats i arrayen), används chaining för att hantera detta. Det innebär att flera objekt kan ligga i en länkad lista på samma index. get-metoden går då igenom listan och letar efter det regnummer som matchar det du söker. När en matchning hittas, returneras det tillhörande bilobjektet.
• Fö3 Hashtabell - Remove metoden (Pär) - I den här delen får du lära dig hur man skapar en remove-metod, som används för att ta bort ett objekt från hashtabellen baserat på en nyckel – till exempel ett registreringsnummer. Metoden letar upp rätt plats i tabellen med hjälp av hashfunktionen och söker sedan igenom den länkade listan (om chaining används) för att hitta och ta bort det objekt som matchar nyckeln.
• Fö4 Hashtabell - Openadressing (Pär) - I den här delen får du lära dig hur man hanterar kollisioner med öppen adressering. Exemplet visar hur man lägger till ett bilobjekt i hashtabellen genom att använda linjär probing – en metod där man söker efter nästa lediga plats i arrayen om den ursprungliga positionen redan är upptagen. På så sätt hittar man en tom plats där bilobjektet kan sparas, utan att använda länkade listor.
• Fö5 Hashtabell - Openadressing (Pär) - I den här delen får du lära dig hur man hanterar kollisioner med öppen adressering. Exemplet visar hur man hämtar ett bilobjekt baserat på registreringsnummer. Om det uppstår en kollision – det vill säga att flera nycklar har hamnat på samma plats – används linjär probing för att söka vidare i tabellen. Det innebär att man steg för steg kontrollerar nästa indexposition tills man hittar det bilobjekt som matchar det angivna registreringsnumret.
• Fö6 Hashtabell (Hans Edy) - Hans Edy föreläning om hash tabeller
• Fö7 Öppen adressering (Hans Edy) - Hans Edy's föreläsning om bla öppenadressering i hashtabeller

Övningar

• Gör en egna implementation av Hashtabell som har Add, Get, Remove funktionalitet. Den ska också ha egen hash- och resize. Samt hantera kollisoner med chaining och eller openadressing. Låt AI-verktyg ställa frågor till dig om Hashtabeller samt ge dig programmeringsuppgifter på Hashtabeller

Inlämningar

• Se kursrummet i Canvas vad som ska göras, hur det ska lämnas in och redovisas samt deadline.

Frågor och svar

Formulera ditt svar. Tryck sen på frågan för att se mitt svar. Jämför svaren. Vad för likheter och skillnander ser du? Vad saknas i mitt respektive ditt svar?

• What is a hash table?
  A hash table is a data structure that stores key-value pairs. It uses a hash function to compute an index into an array of buckets, from which the desired value can be found quickly.
• What is a bucket in a hash table?
  A bucket in a hash table is a container within the hash tables array where key-value pairs with the same hash value are stored.
• What is the purpose of a hash function in a hash table?
  The purpose of a hash function in a hash table is to map keys to indices of an array, enabling efficient storage and retrieval of key-value pairs.
• How is a hash function chosen for a hash table?
  The choice of a hash function depends on several factors such as distribution of keys, speed, and collision resolution strategy. A good hash function aims to distribute keys evenly across the array of buckets to minimize collisions.
• What is a hash collision?
  A hash collision occurs when two different keys produce the same hash value.
• How does a hash table handle collisions?
  Hash tables handle collisions by employing collision resolution techniques, such as chaining or open addressing.
• What is a hash collision chain?
  A hash collision chain refers to a linked list or another data structure used to store multiple key-value pairs that hash to the same index in a hash table.
• What is a hash table collision resolution algorithm?
  A collision resolution algorithm is a method used to resolve collisions that occur when multiple keys hash to the same index in a hash table.
• What is the difference between open addressing and chaining collision resolution techniques?
  In open addressing, collisions are resolved by finding an empty slot in the hash table, typically by linear probing or other methods. In chaining, collisions are resolved by storing multiple entries at the same index using linked lists or other data structures.
• How does linear probing work in open addressing?
  Linear probing is a method of resolving collisions in open addressing by searching for the next available slot in the hash table when a collision occurs. It involves linearly probing successive slots until an empty slot is found.
• What is the time complexity of searching for an element in a hash table?
  The time complexity of searching for an element in a hash table is O(1) on average, assuming a good hash function and a low load factor.
• What is the worst-case time complexity for searching for an element in a hash table?
  The worst-case time complexity for searching in a hash table is O(n), where n is the number of elements in the hash table. This occurs when there are many collisions and the hash table degenerates into a linked list at each index.
• What is the load factor of a hash table?
  The load factor of a hash table is the ratio of the number of elements stored in the hash table to the number of buckets.
• What is the ideal load factor for a hash table?
  The ideal load factor for a hash table depends on the chosen collision resolution strategy but is typically kept below 1.0 to minimize collisions and maintain performance.
• What is the purpose of a hash tables resize operation?
  The purpose of a hash tables resize operation is to maintain a low load factor and ensure efficient performance by increasing the number of buckets and redistributing the key-value pairs when necessary.
• What is the difference between a hash table and an array?
  A hash table is a data structure that stores key-value pairs and uses a hash function to compute an index for efficient retrieval. An array is a collection of elements stored in contiguous memory locations accessed using indices.
• What is the difference between a hash table and a map?
  A hash table is a specific implementation of a map data structure, which associates keys with values. While a hash table typically uses a hash function for indexing, a map may use other methods such as trees or arrays for storage and retrieval.

Att läsa

• Kom ihåg inlämning av labb 4 om Hashtabeller senast fredag kl 17:00

Att titta på

• -

Övningar

Inlämningar

• Kom ihåg inlämning av labb 4 om Hashtabeller senast fredag kl 17:00

Frågor och svar

Formulera ditt svar. Tryck sen på frågan för att se mitt svar. Jämför svaren. Vad för likheter och skillnander ser du? Vad saknas i mitt respektive ditt svar?

Att läsa

• Ett binärt sökträd (BST) är en datastruktur som används för att lagra sorterade data och möjliggör snabb sökning, insättning och borttagning av element. Här är några viktiga egenskaper hos ett binärt sökträd: 1)Noder: Varje nod i trädet innehåller en nyckel och två pekare, en till vänster barn och en till höger barn. 2) Ordning: För varje nod gäller att alla nycklar i det vänstra delträdet är mindre än nodens nyckel, och alla nycklar i det högra delträdet är större. 3) Rekursion: Trädet är rekursivt definierat, vilket innebär att varje delträd också är ett binärt sökträd.
• Kap10 Trees focus binärt sökträd

Att titta på

• Fö1 Träd (Pär) - I den här delen får du en grundläggande genomgång av datastrukturen träd. Jag förklarar vad ett träd är och går igenom vanliga begrepp som används för att beskriva dess uppbyggnad. Du får lära dig vad en nod är, vad som menas med roten (startpunkten i trädet), barn (noder som är kopplade under en annan nod), syskon (noder som har samma förälder), löv (noder utan barn), samt begreppen djup och höjd, som beskriver hur långt ner eller högt upp en nod befinner sig i trädet.
• Fö2 Binärt sökträd (Pär) - I den här delen får du lära dig vad ett binärt sökträd (BST) är och vilka grundläggande egenskaper det har. Ett binärt sökträd är en datastruktur där varje nod har högst två barn – ett vänsterbarn och ett högerbarn. Värdena i trädet är organiserade så att alla värden i vänstra delen är mindre än nodens värde, och alla värden i högra delen är större. Du får också se hur man lägger till nya värden i ett BST, både med hjälp av rekursion och med en while-loop. Båda metoderna visar hur man navigerar genom trädet för att hitta rätt plats att sätta in det nya värdet, samtidigt som trädets struktur och ordning bevaras.
• Fö3 Binärt sökträd traversering av alla noder (Pär) - I den här delen får du lära dig hur man besöker alla noder i ett binärt sökträd (BST) med hjälp av in-order-traversering. Denna metod går igenom trädet i en särskild ordning: först det vänstra barnet, sedan själva noden, och till sist det högra barnet. När man använder in-order på ett BST, kommer nodernas värden att visas i stigande ordning, till exempel från A till Ö eller från lägsta till högsta tal.
• Fö4 Binärt sökträd traversering av alla noder (Pär) - Visar hur du sökar i ett BST både rekursivt och med hjälp av while loop. Vad är tidskomplexiteten i bäst resp sämst fall?
• Fö5 Binära träd (Hans Edy) - Hans Edy's föreläsning om träd och binäraträ, där begrepp gås igenom. Hur man traverser ett träd samt implementation av träd.
• Fö6 Binärt sökträd (Hans Edy) - Hans Edy's föreläsning om binärt sökträd. Hur man lägger till, tar bort nod.

Övningar

• Låt AI-verktyg ställa frågor till dig om vanliga koncepet, kunskaper och kodings förmågor som du måste ha kring binärt sökträd samt låt AI ge dig programmeringsuppgifter om binära träd.

Inlämningar

• Se kursrummet i Canvas vad som ska göras, hur det ska lämnas in och redovisas samt deadline.

Frågor och svar

Formulera ditt svar. Tryck sen på frågan för att se mitt svar. Jämför svaren. Vad för likheter och skillnander ser du? Vad saknas i mitt respektive ditt svar?

• What is a Binary Search Tree?
  A Binary Search Tree (BST) is a binary tree in which each node has a value greater than all the values in its left subtree and less than all the values in its right subtree.
• What is the time complexity of searching for an element in a balanced BST?
  The time complexity is O(log n) in a balanced BST.
• What is the worst-case time complexity for searching an element in a BST?
  The worst-case time complexity is O(n), which occurs when the BST becomes a skewed tree (like a linked list).
• How does an in-order traversal of a BST output the elements?
  An in-order traversal of a BST outputs the elements in ascending sorted order.
• What property must the left and right subtrees of a BST node satisfy?
  All nodes in the left subtree must have values less than the node's value, and all nodes in the right subtree must have values greater than the node's value.
• What is a balanced BST, and why is it important?
  A balanced BST is a tree where the height of the left and right subtrees of any node differ by at most one. It is important because it ensures O(log n) time complexity for operations.
• Describe the process of inserting a new value into a BST.
  To insert a new value, start at the root and compare the value with the current node. If the value is less, move to the left child; if greater, move to the right child. Repeat until finding an appropriate null position to insert the new value.
• Give an example of a situation where a BST is preferable over a hash table.
  A BST is preferable when you need to maintain sorted order of elements or perform range queries, such as finding all elements between two values.
• How would you check if a binary tree is a BST?
  Perform an in-order traversal of the tree and check if the output is sorted in ascending order. If it is, the tree is a BST.

Att läsa

• Kom ihåg inlämning av labb 7 om Binära träd senast fredag kl17:00

Att titta på

• -

Övningar

Inlämningar

• Kom ihåg inlämning av labb 7 om Binärt sökträd senast fredag kl 17:00

Frågor och svar

Formulera ditt svar. Tryck sen på frågan för att se mitt svar. Jämför svaren. Vad för likheter och skillnander ser du? Vad saknas i mitt respektive ditt svar?