Create simple algorithms

This is a machine-translated text that may contain errors!

Quote

“Algorithm”, a word used by programmers when they don’t want to explain what they did.

Algorithm?

What is an algorithm?

An algorithm is a logical function that performs a given operation. So, you can 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 assignments?

No! You can use any programming language you prefer in these assignments.

Built-in libraries?

The idea in these tasks is to avoid using built-in libraries or special Python functions. For example, there is 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 little 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 often, algorithms are designed iteratively. What does this mean?

1. ✅ Break the problem down into smaller parts first.

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

2. ❓ Are there any “edge-cases”?

What happens if you throw in an empty list or text?

3. ✅ Start by just trying to create a solution

4. ✅ Check if the algorithm seems to work in runtime

Try larger input, does it take a long time?

5. ❓ Consider your solution, do you need all the steps you have used?

Are all if checks necessary?
If you have more than one for loop, are there clear ways to make this one for loop?
- This is different if you have nested loops or loops one after another. One after another is often possible to avoid.

6. ✅ Consider extreme scenarios with inputs:

Example with numbers: large numbers, small numbers, negative numbers
Text example: a lot of text, many small words, extra spaces, uppercase and lowercase letters.

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

Task 1 - Finding out if a list contains a given number

Create an algorithm (function) that determines whether a list contains a given number. It should return True or False based on whether the number exists in the list or not.

Here is a list with test data:

Test-data for algoritme:

Test-Data	Sjekk	Svar
`[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 - Summation

Create an algorithm that sums a list of 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 - Maximum Value in a List

Create an algorithm that finds the largest value 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 in 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 elements. 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 - Count the Number of a Given Element in a List

Create an algorithm that counts the number of a given element 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 - Reverse a `string`, text

Create an algorithm that reverses a given string.

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 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 is 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

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

Tips til framgangsmåte

Create 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 does not match, if all match (for-loop completes), return True.

Ekstra:
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 - Checking if a list is sorted

Create an algorithm that checks if a list is sorted. The easiest way to check this is to start from the beginning and compare if the next element is “larger”. If an element is not “larger”, then the list is not 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

Create a function that takes a list as input
Use a for-loop to iterate through the entire list (use range to the length of the list, minus 1 len(list) - 1)
Compare element \(n\) with \(n + 1\), i.e. the current element with the next element.
If \(n\) is less than \(n + 1\), proceed 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

Create an algorithm that shuffles a list of items. There are many ways to do this, but a good way is what is called a Fisher-Yates shuffle algorithm. You can read more about this 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 []

It works like this:

Algoritmen

Create a function that takes the list of numbers as input.
Create a new empty list to hold the mixed result.
Use a random function to select 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 task, you will create a (practically) terrible, but extremely simple sorting algorithm. It is extremely bad when it comes to large lists (it will take forever with more than 12-13 items). In Level 2, we will create a better sorting 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 as follows:

Algoritmen

Create a function that takes the list of unsorted numbers as input.
Shuffle the list randomly (use shuffle from task 8).
Check if the list is sorted (use the check you created in task 7).
If the list is not sorted, repeat steps 2 and 3.
Repeat until the list is sorted, then return.

Simply explained: bogo-sort shuffles the entire list and hopes it is sorted.

Read about Big O notation in Level 2.

Hint: Feel free to use shuffle from task 8 to create an unsorted list for your algorithm.

Svaret (i Python)

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

Task 10a - Search for text - “substring” (Difficult!)

Create an algorithm that can find a keyword in text. That is, if you have a sentence like hello there you will return True with the keyword hello, False with a keyword like hahah. This algorithm should work regardless of input and output.

Use the text data below to check if your algorithm works.

Test-data for algorithm:

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

Create a function that takes two strings, data and keyword.
Use a for-loop with range to iterate through the text.
Here it is 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 does not match where you are checking now, set the temporary variable to True and break out of the inner loop.
If you reach 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 ensure that the keyword is not 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 - Reversing Words in a Sentence (Difficult)

Recall Task 5 about reversing a sentence. Modify (or start over) to create an algorithm that reverses each individual word in a sentence, then puts them back together.

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

Create a function that takes a string as input.
❗Split the text using .split(" ").
Create a temporary variable to store the final value.
Use a for-loop to iterate through each word.
Use the same method for reversing as in Task 5
Use the result and add it to the variable you created 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 - Deleting Duplicates from a List

Suppose you have a list containing numbers or text, but you want to delete the duplicates. Create an algorithm that deletes all duplicates from a list and contains only the first of each unique element that exists in the list.

Tips til framgangsmåte

Start with a function that takes a list as input
Here we will use while loops instead of for. This 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 the element at idx with the element at jdx, if they are the same, delete jdx using pop(jdx).
REMEMBER! If you delete the element, the list becomes smaller, therefore we must go back one step with 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
Finally, return 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 yield: ["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 sorting algorithms that works in what we call \(O(n)\) time. That is, it doesn’t take much longer than the number of elements in the list. Read more about Big O notation in Level 2.

It depends a bit on how large the range of elements is. If the smallest is 0 and the largest is 100000 it can take a little time, so this can be used if the range of values is small. It also doesn’t work for negative numbers, but it is possible to modify the algorithm to work with negative numbers.

The algorithm works like this:

Find out how large the largest element is, store the value of this element as \(k\).
Create a list that contains \(k + 1\) elements, count.
Go through the unsorted list and use the value of the number as the index. That is, if the element has the value 47, then you go to count[47] and increase it by 1.
Go through the count list and place the number of numbers as the index is. Example: There is 3 at index 1, so you add three 1 numbers.

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 creating a function with a list as input
Create an empty output list
Use a for-loop to go through the entire list
Keep track of the maximum value in a variable before the for-loop
Update the maximum value if you find something larger
Create a list that contains this number of zeros + 1. Example: the largest value is 47, then you create a list with 48 zeros. You can do this with [0] * (maks + 1), or a for loop. Call it count.
Go through the list once more with a for-loop
Use the value of the element as the index and increment by 1. count[value] += 1
Use a for-loop to go through the count list.
Use the value at each index to add that many 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 will create a pile of 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

Create simple algorithms

How to “design” an algorithm?

1. ✅ Break the problem down into smaller parts first.

2. ❓ Are there any “edge-cases”?

3. ✅ Start by just trying to create a solution

4. ✅ Check if the algorithm seems to work in runtime

5. ❓ Consider your solution, do you need all the steps you have used?

6. ✅ Consider extreme scenarios with inputs:

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

Task 1 - Finding out if a list contains a given number

Task 2 - Summation

Task 3a - Maximum Value in a List

Task 3b - If the list is empty?

Task 4 - Count the Number of a Given Element in a List

Task 5 - Reverse a string, text

Task 6 - Palindrome Algorithm

Task 7 - Checking if a list is sorted

Task 8 - Shuffle

Task 9 - Bogo-sort

Task 10a - Search for text - “substring” (Difficult!)

Task 10b

Task 11 - Reversing Words in a Sentence (Difficult)

➕ Extra:

Task E1 - Deleting Duplicates from a List

Task E2 - Counting Sort

Task 5 - Reverse a `string`, text