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 - Första delen om Hashtabeller , en powerpoint där jag går igenom vanliga koncept, begrepp samt kode exempel för att skapa en egen implementation hashtabell. Koncepet som Hashfunktion, buckets, hantera kollisioner med chaining gås igenom. Samt vanliga algoritmer för att lägg till, ta bort och söka i hashtabell.
• Del 2 Hashtabeller Open addressing - Andra delen om Hashtabeller , en powerpoint där jag går igenom open addressering som är ett annt sätt att hantera kollisoner än chaining. Vidare pratar jag om hur man hantera när tabellen börjar bli full då görs bla en dynamsik ökninga av dess storlek samt rehashing.
• Fö1 Hashtabell (Pär) - Här lär du dig skapa en egen klass för hashtabell implementation för att hantera bla bilobjekt. Som bucket används en array av länkad lista i vilken vi kan lägga Key_Value par där Key är regnummer och value är bil objektet. Add metoden gås igenom för att kunna lägg till ett bil objekt där key är regnummer och value är bil objektet. I Add används: Hash funktionalitet samt kollisionteknik. Kollisioner hanteras med chaining tekniken där jag använder en länkad lista för att lägg till flera bilar på samma index position. I HashFunctions metod skapas med en DBJ2 algoritmen. Baserat på en sträng får jag via HashFunction en index position där bil objekt ska läggas till eller hämtas ifrån.
• Fö2 Hashtabell -Get Metoden(Pär) - Här lär du dig att skapa Get metoden där man hämtar ut data baserat på en nyckel, regnummer, och får tillbaka ett value, ett bilobjekt. I Get hanteras den chaining som ev uppstod vid kollision där olika nyckelvärden,regnummer, fick samma index position. Då loopas den länkade listan igenom för att finna matching nyckelvärden,regnummer och då returneras det objekt dvs det matchande bilobjektet
• Fö3 Hashtabell - Remove metoden (Pär) - Här lär du dig att skapa remove metoden.
• Fö4 Hashtabell - Openadressing (Pär) - Här lär du dig hur du hantera kollsion med öppenaddresseringsteknik. Exemplet visar att lägga till data där man gör en linjär sökning efter nästa lediga index postion att lägg bil objektet i.
• Fö5 Hashtabell - Openadressing (Pär) - Här lär du dig hur du hantera kollsion med öppenaddresserings teknik. Exemplet visar att hämta till bildata på regnummer där man gör en linjär sökning för att kolla om bilen finns på nästa lediga indexpositon.
• 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) - Generell genomgång om vad data strukturen träd är. Går igenom vanlig begrepp som nod, rot, barn, syskon, löv, djup och höjd.
• Fö2 Binärt sökträd (Pär) - Vad är binärt sökträd. Dess grundegenskaper. Visar hur man lägget till i ett BST. Både hur m gör det rekursivt och med och hur du gör det med hjälp av while loop
• Fö3 Binärt sökträd traversering av alla noder (Pär) - Hur du besöker alla noder i BST:n med hjälp av in-order algoritmen vilket gör att nodernas värden presenteras i stigande ordning från A-Ö
• 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ä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ö6 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ö7 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 samt 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?