Algoritmer och mjukvarudesign

Välkommen till Pär Erikssons delar av kursen. Min enkla pedagogiska ide' och erfarenhet är att man lär sig mycket genom att lägga ner tid ca 2-4 timmar varje dag på att läsa i kursboken, titta på inspelningar samt skriva av befintlig kodexempel ur boken, inspelningar etc. Gör små förändringar i och av den för att sen testköra och se vad som händer. Ta paus varje timme. Ha en tänkt app för företag, klubb eller förening som du använder dina nya kunskaper på. Där du tänker, hur kan jag tillämpa det nya jag lärt mig på deras app? Jag kör ofta en tänkt liten bilfirma som jag applicerar nya koncept/kunskaper på och skriver koden för.

Veckoplanering - Vad titta på? Vad läsa? Vad göra?

Att läsa

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å

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

Inlämningar

Se vecka 18

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

Kap 8 Hashtables

Att titta på

N/A - Lorem lipsum

Övningar

Exercise 3
Exercise 4

Inlämningar

Inlämning av labb 4 om Hashtables, fredag 17:00
Handin 4

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?

N/A
N/A

Att läsa

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

Exercise 5
Exercise 6

Inlämningar

Se vecka 22

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

Kap 10 Trees focus binärt sökträd

Att titta på

N/A - Lorem lipsum

Övningar

Inlämningar

Inlämning av labb 7 om Binärt sökträd, fredag 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?

Question 5
Answer 5
Question 6
Answer 6

HashTable

Se spellista

Tree

Se spellista

Kursnamn: Algoritmer och mjukvarudesign

Program: IT-säkerhet och mjukvarutestning – kandidatprogram

Beskrivning: Olika typer av datastruktur introduceras, som länkadelistor, köer, hashtabeller och träd. För- och nackdelar diskuteras med avseende till snabbhet, minnesresurser och komplexitet som grund för kvalificerade val av datastruktur för att lösa ett specifikt problem.

Se kursplan

Algoritmer och mjukvarudesign

Veckoplanering - Vad titta på? Vad läsa? Vad göra?

Vecka 17

Att läsa

Att titta på

Övningar

Inlämningar

Frågor och svar

Vecka 18

Att läsa

Att titta på

Övningar

Inlämningar

Frågor och svar

Vecka 21

Att läsa

Att titta på

Övningar

Inlämningar

Frågor och svar

Vecka 22

Att läsa

Att titta på

Övningar

Inlämningar

Frågor och svar

Hans Jernberg

Pär Eriksson

Elin Ekman

HashTable

Tree