Make some simple algorithms,

This here’s a machine-translated text that might contain some errors!

Quote

“Algorithm”, a word programmers use when they don’t wanna explain what they done.

Algoritme?

What is an algorithm?

An algorithm is a logical function that performs a given operation. So, you could technically call a function that adds two numbers together an “algorithm”, but most often an algorithm is something a little more complicated than that. Algorithms are often used to speed up operations that take a long time.

Do I have to use Python in these tasks?

Nope! You can use any programming language you prefer for these tasks.

Built-in libraries?

The idea in these tasks is to avoid using built-in libraries or special Python functions. For example, there’s a simple “one-liner” to reverse text: text[::-1], but here we want you to try to solve such tasks without using this. It may happen that we mention a built-in function if the solution is a bit difficult to figure out. This will be marked with ❗.

In practice, it should be fully possible to solve all these tasks with if, for, while and common list operations.

How to “Design” an Algorithm?

Most times, algorithms are designed iteratively. What does that mean?

1. ✅ First, break the problem down into smaller pieces.

First and foremost, think about the most important thing you need for the algorithm to work
- Does it need to return a value? A boolean? A list?
- Do I need any helper functions?

2. ❓ Any tricky situations we gotta watch out for?

What happens if ya throw in an empty list or some text that’s just… nothin’?

3. ✅ Just start by tryin’ to wrangle up a solution

4. ✅ Reckon if the algorithm works right in runtime

Give it a whirl with bigger input, does it take a spell?

5. ❓ Reckon on yer solution, ya need all them steps ya used?

Are all them if checks necessary?
If ya got more’n one for loop, is there any clear ways to make this into one for loop?
- This here’s different if ya got nested loops or loops one after t’other. One after t’other is often somethin’ ya can avoid.

6. ✅ Reckon with Extreme Scenarios with Inputs:

Example with numbers: big numbers, small numbers, negative numbers
Text example: a whole heap o’ text, a bunch o’ little words, extra spaces, big and small letters.

7. ❓ Is it a help to use pseudo-code to understand the logic better?

Task 1 - Figurin’ Out if a List Holds a Certain Number

Cook up an algorithm (function) that figures out if a list holds a certain number. It oughta return True or False dependin’ on whether that number exists in the list or not.

Here’s a list o’ test data:

Test-data for algoritme:

Test-Data	Check	Answer
`[1, 2, 3, 4, 5, 6, 7, 8, 9]`	`5`	`True`
`[1, 2, 3, 4, 5, 6, 7, 8, 9]`	`10`	`False`
`[2, 3, 5, 7, 11, 13, 17, 19, 23]`	`2`	`True`
`[2, 3, 5, 7, 11, 13, 17, 19, 23]`	`10`	`False`
`[-1, 0, 1, -34, 321, 22, 98, -214]`	`-214`	`True`
`[-1, 0, 1, -34, 321, 22, 98, -214]`	`0`	`True`
`[-1, 0, 1, -34, 321, 22, 98, -214]`	`2`	`False`

Tips til framgangsmåte

Take in a list and a list value into a function. In this task, it should be numbers, but it can be text.
Use a for-loop to go through the list
If the number is equal to the check number, return True
If the for-loop is over and you haven’t found it, return False

Svaret (i python)

def exists_in_list(the_list, check):
    for number in the_list:
        if number == check:
            return True
    return False

Task 2 - Summin’

Whip up an algorithm that adds up a list o’ numbers.

Test-data for algoritme:

[1, 2, 3, 4, 5, 6], gives the answer 21.
[5, 1, 23, 68, 22, 13, 4], gives the answer 136
[3, 3, -3, -3, 3] gives the answer 3. Alternatively, you can ignore negative numbers and give the answer 9.

Tips til framgangsmåte

Take a list into a function
Save a temporary sum as 0.
Use a for-loop to go through the list.
return the sum of the list.

Svaret (i python)

def sum_list(numbers):
    total = 0
    for num in numbers:
        total += num
    return total

Task 3a - Biggest Value in a List

Cook up an algorithm that finds the biggest number in a list.

Test-data for algoritme:

[1, 2, 3, 4, 5, 6], gives the answer 6.
[6, 17, 227, 1, 23, 42, 12], gives the answer 227
[2, -2, 2, -2, -2, 2] gives the answer 2.

Tips til framgangsmåte

Take a list into a function
Set a temporary value to the first element of the list.
Use a for-loop to go through the list and compare with the value you set in 2.
If the value is larger, set the temporary value to the new value.
return this temporary value.

Svaret (i python)

def find_max(numbers):
    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

Task 3b - If the List is Empty?

Add a check that tests if the list contains any items. If not, return None.

Svaret (i python)

def find_max(numbers):
    if len(numbers) == 0:
        return None

    largest = numbers[0]
    for num in numbers:
        if num > largest:
            largest = num

    return largest

Task 4 - Countin’ the Number o’ a Given Item in a List

Come up with a way to count how many times a certain thing shows up in a list.

Test-data for algoritme:

["apple", "banana", "orange", "apple", "apple", "banana"] with apple gives the answer 3.
[1, 4, 5, 2, 4, -3, -4, 4, 2, 4, 221, 3, 1, 1, 4, 1, 12, 33, 4, 4, 2, -4, 1, 4] with 4 gives the answer 8.
["cat", "dog", "cat", "mouse", "cat", "dog", "dog"] with dog gives the answer 3.
[7, 7, 2, 9, 7, 1, 0, 7, 3, 7, 9] with 7 gives the answer 5.
["red", "blue", "green", "red", "yellow", "red"] with red gives the answer 3.
[10, -2, -2, -2, 5, 10, 10, -2] with -2 gives the answer 4.

Tips til framgangsmåte

Take in a list and a check-value in a function
Start with a temporary count value set to 0.
Go through the list with a for-loop.
If the element is equal to the check, increase the count value by 1.
Return the count value.

Svaret (i python)

def count(the_list, check):
    count = 0
    for element in the_list:
        if element == check:
            count += 1

    return count

Task 5 - Reversin’ a `string`, text

Cook up an algorithm that flips a given string around.

Test-data for algoritme:

Hello there! becomes !ereht olleH.
heisann alle sammen becomes nemmas ella nnasieh
Python becomes nohtyP
racecar becomes racecar
12345abc becomes cba54321
god morgen becomes negrom dog

Tips til framgangsmåte

Take in a string into a function
Create a temporary value to store an empty string.
Go through the text with a for-loop with range. Here you can go through the list backwards, but it’s possible to solve this by going forward in the list.
Add each character to the temporary value in order.
Return the temporary text.

Svaret (i python)

def reverse(text):
    result = ""
    # This line is a bit complicated, but it starts
    # at the end, goes (including) to 0 (by writing
    # -1 as the end), and counts down by 1 each time
    for i in range(len(text) - 1, -1, -1):
        result += text[i]
    return result

Alternatively, you can use an algorithm that adds to the beginning instead:

def reverse(text):
   result = ""
   for i in range(0, len(text)):
       # add to the beginning instead
       result = text[i] + result
   return result

Task 6 - Palindrome Algorithm

Cook up an algorithm that checks if a given word is a palindrome. Examples of palindromes are abba, racecar, regninger.

Tips til framgangsmåte

Make a function that takes text to check.
Use a for-loop to check if the letters on each side of the text are the same.
Return False if a letter doesn’t match, if all match (for-loop finishes), return True.

Extra:
Do you see how you can make the algorithm twice as fast?

Hint

Du trenger bare å sjekke halvparten!

The answer (in python)

def palindrome(text):
    for i in range(0, len(text)):
        if text[i] != text[len(text) - i - 1]:
            return False
    return True

Faster algorithm

def palindrome(text):
for i in range(0, int(len(text) / 2)):
if text[i] != text[len(text) - i - 1]:
return False
return True

Task 7 - Checkin’ if a List is Sorted

Now, make up an algorithm to check if a list is sorted. The easiest way to do this is to start from the beginnin’ and compare if the next item is “bigger”. If an item ain’t “bigger”, then the list ain’t sorted.

Test-data for algoritme:

[1, 2, 3, 4, 5, 6], gives the answer True.
[6, 17, 227, 1, 23, 42, 12], gives the answer False
[2, -2, 2, -2, -2, 2] gives the answer False.
[2, 2, 3, 4, 4, 6], gives the answer True.
[12, 23, 34, 45, 56, 67], gives the answer True.

Tips til framgangsmåte

Make a function that takes in a list
Use a for-loop to go through the whole list (use range to the length of the list, minus 1 len(list) - 1)
Compare element \(n\) with \(n + 1\), that is, the current element with the next element.
If \(n\) is less than \(n + 1\), go to the next comparison.
If it is not less, but greater, then the list is not sorted. Return False here.
If you reach the end then the list is sorted, return True.

Svaret (i Python)

def is_sorted(the_list):
    for i in range(len(the_list) - 1):
        if the_list[i] > the_list[i + 1]:
            return False
    return True

Task 8 - Shuffle

Cook up an algorithm that mixes up a list of items. There’s a heap o’ ways to do this, but a good’un is what’s called a Fisher-Yates shuffle algorithm. You can read more ‘bout it here Wikipedia.

Test Data

["a", "b", "c", "d", "e"] → can become e.g. ["c", "e", "a", "d", "b"]
[1, 2, 3, 4, 5, 6] → can become e.g. [4, 1, 6, 3, 2, 5]
["apple", "banana", "orange"] → can become e.g. ["orange", "apple", "banana"]
["x"] → remains ["x"]
[] → remains []

How she works is this:

Algoritmen

Make a function that takes in the list of numbers
Make a new empty list to hold the mixed result.
Use a random to choose a random index in the list.
Add this element to the empty list and delete it from the old one
Return the new list from the function

Svaret (i Python)

import random

def shuffle(the_list):
    shuffled = []

    while len(the_list) > 0:
        i = random.randrange(0, len(the_list))
        shuffled.append(the_list[i])
        the_list.pop(i)

    return shuffled

Task 9 - Bogo-Sort

In this here task, you’re gonna build a downright awful, but mighty simple sortin’ algorithm. It’s real bad when it comes to big lists (it’s gonna take forever with more than 12-13 items). In Level 2, we’re gonna build a better sortin’ algorithm, bubble-sort.

Test Data

[3, 1, 2] → [1, 2, 3]
[5, 4, 3, 2, 1] → [1, 2, 3, 4, 5]
[10, 7, 8, 2] → [2, 7, 8, 10]
[1, 1, 1] → [1, 1, 1]
[9, 3, 6, 3, 9] → [3, 3, 6, 9, 9]
[0, -1, 4, -2] → [-2, -1, 0, 4]

The algorithm works like this:

Algoritmen

Make a function that takes in the list of unsorted numbers
Shuffle the list randomly (use shuffle from task 8).
Check if the list is sorted (use the check you made in task 7).
If the list isn’t sorted, repeat steps 2 and 3.
Repeat until the list is sorted, then return

Simply put: bogo-sort mixes the whole list and hopes it’s sorted.

Read about Big O notation in Level 2.

Hint: Reckon ya might wanna use shuffle from task 8 to whip up a scrambled list fer yer algorithm, partner.

Svaret (i Python)

def bogo_sort(the_list):
    while not is_sorted(the_list):
        the_list = shuffle(the_list)
    return the_list

Task 10a - Searchin’ for Text - “substring” (Tough one!)

Come up with a way to find a keyword within some text. Say ya got a sentence like hello there, ya wanna return True if the keyword is hello, and False if it’s somethin’ like hahah. This here method gotta work no matter what kinda input or output ya throw at it.

Use the text data below to check if yer method’s workin’ right.

Test-data for algoritme:

hello there everyone with there = True
hello there everyone with ever = True
hello there everyone with then = False
qwecvyufavsjekkftyergwcery with sjekk = True

Tips til framgangsmåte

Make a function that takes two strings, data and keyword.
Use a for-loop with range to go through the text.
Here it’s important to think about how far the loop should go.
Create a temporary variable that says whether the keyword has been found, set it to True by default.
Use another for-loop with range to compare where you are in the text with the keyword.
If something in the keyword doesn’t match where you’re checking now, set the temporary variable to True and break out of the inner loop.
If you get to the end of the text without finding anything, return False.

Svaret (i Python)

def search(data, word): 
    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True

    return False

Task 10b

Also add an extra check to make sure the keyword ain’t longer than the sentence.

Tips til framgangsmåte

Add this check before the for loop.

Svaret (i python)

def search(data, word): 
    if len(word) > len(data):
        return False

    for i in range(0, len(data) - len(word) + 1):
        found = True
        for j in range (0, len(word)):
            if data[i + j] != word[j]:
                found = False
                break
        if found:
            return True

    return False

Task 11 - Reversin’ Words in a Sentence (Tough One)

Now, recollect back to Task 5 ‘bout reversin’ a sentence. Go ‘head and rework (or start fresh), and build an algorithm that flips each individual word in a sentence, then puts ‘em back together again.

Test-data for algoritme:

hello there everyone becomes olleh ereht enoyreve
This is the way it goes! becomes sihT si eht yaw ti !seog
does this racecar go? of course! becomes seod siht racecar ?og fo !esruoc

Tips til framgangsmåte

Make a function that takes in a string.
❗Split the text using .split(" ").
Make a temporary variable to store the final value.
Use a for-loop to go through each word.
Use the same method for reversing as in Task 5
Use the result and add it to the variable you made in step 2.
Return the final value

Svaret (i Python)

def reverse_words(words):
    sentence = words.split(" ")
    output = ""

    for word in sentence:
        reversed_word = ""
        for i in range(0, len(word)):
            reversed_word = word[i] + reversed_word
        output += reversed_word + " "

    return output

➕Extra:

Task E1 - Deletin’ Duplicates from a List

Now, reckon ya got a list full o’ numbers, or words, but ya wanna get rid o’ them duplicates. Come up with a plan o’ action that wipes out all them copies from a list, leavin’ only the first o’ each unique item that exists in that list.

Tips til framgangsmåte

Start with a function that takes in a list
Here we’ll use while-loops instead of for. It makes it easier in Python, in other languages for with counter variables works fine.
Create a counter variable idx (for index, or i)
Use a while loop that should go to the length of the list
We will compare the element at idx with all other elements
Create a counter variable to jdx (or j) that starts at idx + 1
Compare element at idx with element at jdx, if they are the same, delete jdx by using pop(jdx).
REMEMBER! If you delete the element the list gets smaller, therefore we must go back one step at jdx -= 1.
Increase jdx by 1 and test the next element
After the inner while-loop increase idx by 1 and the outer while-loop will continue
Return finally the list with deleted duplicates

Test Data

[1, 2, 2, 3, 1, 4, 3] → becomes [1, 2, 3, 4]
["a", "b", "a", "c", "b", "d"] → becomes ["a", "b", "c", "d"]
[5, 5, 5, 5] → becomes [5]
["x", "y", "z", "x", "y", "x"] → becomes ["x", "y", "z"]
[10, -1, 10, -1, 0, 0, 10] → becomes [10, -1, 0]
["apple", "apple', "banana", "orange", "apple", "orange", "pear", "apple"]
- Should give: ["apple", "banana", "orange", "pear"]

Svaret (i Python)

def delete_duplicates(the_list):
    idx = 0

    while idx < len(the_list):
        jdx = idx + 1

        while jdx < len(the_list):
            if the_list[idx] == the_list[jdx]:
                the_list.pop(jdx)
                jdx -= 1
            jdx += 1
        idx += 1

    return the_list

Task E2 - Counting Sort

Counting sort is one of the few sortin’ algorithms that works in what we call \(O(n)\) time. Meanin’, it don’t take much longer than the number of items in the list. Read more ‘bout Big O notation in Level 2.

It kinda depends on how big the range of items is. If the smallest is 0 and the biggest is 100000 it can take a spell, so this one’s best used when the range of values is small. It also don’t work for negative numbers, but ya can modify the algorithm to handle ‘em.

The algorithm works like this:

Figure out what the biggest item is, and save that value as \(k\).
Make a list that contains \(k + 1\) items, called count.
Go through the unsorted list and use the item’s value as the index. Like, if the item has a value of 47, ya go to count[47] and increase it by 1.
Go through the count list and place the number of items that the index is. Example: If there’s a 3 at index 1, ya add three 1s.

Testdata

Unsorted Data	Sorted Data
`[7, 3, 9, 1, 4, 3, 0, 6, 8, 6, 2, 1, 9, 0, 5, 4]`	`[0, 0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 9, 9]`
`[12, 13, 15, 0, 8, 15, 8, 5, 16, 8, 0, 20, 4, 9, 17, 16, 1, 3, 6, 15, 5, 2, 3, 1, 19, 13, 17, 5, 3, 10]`	`[0, 0, 1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 6, 8, 8, 8, 9, 10, 12, 13, 13, 15, 15, 15, 16, 16, 17, 17, 19, 20]`

Tips til framgangsmåte

Start by makin’ a function that takes a list as input
Make an empty output list
Use a for-loop to go through the whole list
Keep track of the highest value in a variable before the for-loop
Update the highest value if you find somethin’ bigger
Make a list that contains this number of zeros + 1. Example: highest value is 47, then you make a list with 48 zeros. You can do this with [0] * (max + 1), or a for loop. Call it count.
Go through the list one more time with a for-loop
Use the value of the element as an index and increase by 1. count[value] += 1
Use a for-loop to go through the count list.
Use the value that is at each index to add that number of numbers
Return the sorted list

Svaret (i Python)

def counting_sort(input_list):
    output = []

    max_val = input_list[0]

    for n in input_list:
        if n > max_val:
            max_val = n

    # this here will make a whole mess o' zeros
    count = [0] * (max_val + 1)

    for n in input_list:
        count[n] += 1

    for i in range(len(count)):
        # use _ to ignore a value
        for _ in range(count[i]):
            output.append(i)

    return output

Make some simple algorithms,

How to “Design” an Algorithm?

1. ✅ First, break the problem down into smaller pieces.

2. ❓ Any tricky situations we gotta watch out for?

3. ✅ Just start by tryin’ to wrangle up a solution

4. ✅ Reckon if the algorithm works right in runtime

5. ❓ Reckon on yer solution, ya need all them steps ya used?

6. ✅ Reckon with Extreme Scenarios with Inputs:

7. ❓ Is it a help to use pseudo-code to understand the logic better?

Task 1 - Figurin’ Out if a List Holds a Certain Number

Task 2 - Summin’

Task 3a - Biggest Value in a List

Task 3b - If the List is Empty?

Task 4 - Countin’ the Number o’ a Given Item in a List

Task 5 - Reversin’ a string, text

Task 6 - Palindrome Algorithm

Task 7 - Checkin’ if a List is Sorted

Task 8 - Shuffle

Task 9 - Bogo-Sort

Task 10a - Searchin’ for Text - “substring” (Tough one!)

Task 10b

Task 11 - Reversin’ Words in a Sentence (Tough One)

➕Extra:

Task E1 - Deletin’ Duplicates from a List

Task E2 - Counting Sort

Task 5 - Reversin’ a `string`, text