Hej allihopa!

På måndagsövningen gick vi igenom lite saker och jag tänkte dela med mig av de relevanta anteckningar som gjordes under övningen så att ni kan ta del av materialet också:

Kod för algoritmerna (NOTERA! SKRIVET AV CHATGPT!):

# Code written by ChatGPT!

# This is not my own code!

def binary_search(arr, target):

print("Binary search\n")

low = 0

high = len(arr) - 1

while low <= high:

mid = (low + high) // 2

print(f"Comparing target {target} with middle element {arr[mid]} at index {mid}")

if arr[mid] == target:

return mid

elif arr[mid] < target:

low = mid + 1

else:

high = mid - 1

return -1

# Example

arr = [2, 3, 4, 10, 40]

target = 10

result = binary_search(arr, target)

def bubble_sort(arr):

print("Bubble sort\n")

n = len(arr)

for i in range(n):

for j in range(0, n - i - 1):

print(f"Comparing {arr[j]} and {arr[j+1]}")

if arr[j] > arr[j + 1]:

arr[j], arr[j + 1] = arr[j + 1], arr[j]

print(f"Swapping {arr[j]} and {arr[j+1]}")

# Example

arr = [64, 34, 25, 12, 22, 11, 90]

bubble_sort(arr)

def hash_search(hash_table, key):

print("hash_search\n")

if key in hash_table:

print(f"Key {key} found with value {hash_table[key]}")

return hash_table[key]

else:

print(f"Key {key} not found")

return None

# Example

hash_table = {1: 'apple', 2: 'banana', 3: 'cherry'}

key = 2

result = hash_search(hash_table, key)

def heapify(arr, n, i):

largest = i

left = 2 * i + 1

right = 2 * i + 2

if left < n and arr[largest] < arr[left]:

print(f"Comparing {arr[largest]} and {arr[left]}")

largest = left

if right < n and arr[largest] < arr[right]:

print(f"Comparing {arr[largest]} and {arr[right]}")

largest = right

if largest != i:

print(f"Swapping {arr[i]} and {arr[largest]}")

arr[i], arr[largest] = arr[largest], arr[i]

heapify(arr, n, largest)

def heap_sort(arr):

print("Heap sort\n")

n = len(arr)

for i in range(n // 2 - 1, -1, -1):

heapify(arr, n, i)

for i in range(n - 1, 0, -1):

print(f"Swapping {arr[0]} and {arr[i]}")

arr[0], arr[i] = arr[i], arr[0]

heapify(arr, i, 0)

# Example

arr = [12, 11, 13, 5, 6, 7]

heap_sort(arr)

def insertion_sort(arr):

print("Insertion sort\n")

for i in range(1, len(arr)):

key = arr[i]

j = i - 1

while j >= 0 and key < arr[j]:

print(f"Comparing {key} and {arr[j]}")

arr[j + 1] = arr[j]

j -= 1

arr[j + 1] = key

print(f"Placed {key} at position {j+1}")

# Example

arr = [12, 11, 13, 5, 6]

insertion_sort(arr)

def linear_search(arr, target):

print("Linear search\n")

for i in range(len(arr)):

print(f"Checking element {arr[i]} at index {i}")

if arr[i] == target:

return i

return -1

# Example

arr = [2, 3, 4, 10, 40]

target = 20 # Returns -1

result = linear_search(arr, target)

def merge_sort(arr):

print("Merge sort\n")

if len(arr) > 1:

mid = len(arr) // 2

L = arr[:mid]

R = arr[mid:]

merge_sort(L)

merge_sort(R)

i = j = k = 0

while i < len(L) and j < len(R):

print(f"Comparing {L[i]} and {R[j]}")

if L[i] < R[j]:

arr[k] = L[i]

i += 1

else:

arr[k] = R[j]

j += 1

k += 1

while i < len(L):

arr[k] = L[i]

i += 1

k += 1

while j < len(R):

arr[k] = R[j]

j += 1

k += 1

# Example

arr = [12, 11, 13, 5, 6, 7]

merge_sort(arr)

def partition(arr, low, high):

pivot = arr[high]

i = low - 1

for j in range(low, high):

print(f"Comparing {arr[j]} and pivot {pivot}")

if arr[j] < pivot:

i += 1

arr[i], arr[j] = arr[j], arr[i]

print(f"Swapping {arr[i]} and {arr[j]}")

arr[i + 1], arr[high] = arr[high], arr[i + 1]

return i + 1

def quicksort(arr, low, high):

print("Quick sort")

if low < high:

pi = partition(arr, low, high)

quicksort(arr, low, pi - 1)

quicksort(arr, pi + 1, high)

# Example

arr = [10, 7, 8, 9, 1, 5]

quicksort(arr, 0, len(arr) - 1)

def counting_sort(arr):

print("Counting sort\n")

max_val = max(arr)

count = [0] * (max_val + 1)

for num in arr:

count[num] += 1

print(f"Counting element {num}: {count}")

idx = 0

for i in range(len(count)):

while count[i] > 0:

arr[idx] = i

count[i] -= 1

print(f"Placing element {i} at index {idx}")

idx += 1

# Example

arr = [4, 2, 2, 8, 3, 3, 1]

counting_sort(arr)

def selection_sort(arr):

print("Selection\n")

for i in range(len(arr)):

min_idx = i

for j in range(i + 1, len(arr)):

print(f"Comparing {arr[min_idx]} and {arr[j]}")

if arr[j] < arr[min_idx]:

min_idx = j

print(f"Swapping {arr[i]} and {arr[min_idx]}")

arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Example

arr = [64, 25, 12, 22, 11]

selection_sort(arr)

Sist var det också fokus på Reguljära uttryck (mer relevant till framtida laborationer).

Lite bra regler:
. betyder vilket tecken som helst, (ex: a, l, 0, § är godkända av detta reguljära uttrycket)
g* betyder ett valfritt antal g-tecken. (ex: , g & ggggggg är alla godkända av detta reguljära uttrykcet)
v+ betyder att det är åtminstone 1 v-tecken (men flera också tillåtna). (ex: v, vv & vvvvvvvv är godkända, men är inte godkänt!)

Det inom klamrar [] betyder vilket av de tecken inombords, exempelvis [aeiouyåäö] godkänner a, e och ä. Om du vill ha ett intervall av vissa tecken kan du använda dig av - inom det för att signalera intervallet (ex [a-z])

Paranteser betyder hela det uttrycket i sig (ab) betyder ab

| betyder eller i detta fall så a|b betyder a eller b, men inte båda samtidigt.

Du kan kombinera fler av dessa för att få till vissa speciella uttryck (exempelvis [acgt]* blir DNA-strängar av valfri längd, tomma strängen räknas som DNA här också).

Dock kan reguljära uttryck bli jobbiga också, som uppgift sök upp det reguljära uttrycket för giltiga mail-addresser. Då kanske det finns fall där andra typer av automater för syntax blir mer hjälpsamt.

Sist, en uppgift kan vara att försöka skapa ett reguljärt uttryck som godkänner alla förnamn och där var en bra lösning följande:
[A-Z][a-z]*

Dock täcker det nästan alla namn... Hur skulle du göra för att täcka detta förnamn? (Det uttalas som Albin):

Brfxxccxxmnpcccclllmmnprxvclmnckssqlbb11116

Sist med bra länkar att se över:

https://www.csc.kth.se/utbildning/kth/kurser/DD1320/tilda08/utdelat/forel/f07.html

https://www.geeksforgeeks.org/heap-sort/

https://sv.wikipedia.org/wiki/Regulj%C3%A4ra_uttryck

Jag hoppas att allt hjälper er inför kommande uppgifter
Mvh Patrik Johansson