Lecture 3 - Algorithms

Introduction

• .Reminded that computer languages help us to complete the below process

input → □ → output

• Recalled how we recalled memory as a grid of bits last week, where each of these bits or memory locations with a number or “address”.

• In these locations we can store ints, chars, and bool values but also strings and arrays
  • string: array of characters
  • array: an continuous block of memory storing multiple values

• This week we focus less on representing each data types and more on the the central step in the above process - the algorithms.

• Computers deal with data in different ways then humans. Where we can see all values at once and jump straight to relevant data, for computers data is effectively hidden from its view and can only be viewed methodically as it doesn’t have the same bird’s eye view

• We returned to our first lecture’s topic which included ‘searching’
  • ie searching for a phone number in an address book’

• in an example searching for a value in array

  input array of ‘hidden values’ → searching algorithm → output a boolean response of true or false if found

Running Time

• When comparing algorithms, we talk about ‘correctness’ but can also talk about ‘design’
  • design: easy to understand
  • design: doesn’t use too much memory
  • overall it means, quality of performance i.e. efficiency or better known as running times, can be measured in time or steps

• Running time of code is normally done with Big O Notation.
  • the running time of an algorithm is ‘in the order of’ such and such
  • it way to approximately gauge an algorithm without getting into fine detail of executing code.

    

• So in above example, because the shapes and lines are pretty similar for red and yellow, computer scientists would consider they are effectively the same efficiency, O(n). However, the third line, the green, because it has it’s own shape and is much more distinct, is represented with a better efficiency or shorter runtime, the order of log n.

• A second way we can represent an algorithm is with Ω(n), called Omega of n. Where big O of represents the upper bound, or max steps, Omega of n discusses lower bound, or shortest possible runtime.

• Big θ, or ‘theta of’, represents an algorithm where big O and big theta are the same

Searching

• Linear searching, involves simply iterating through code, memory bit by memory bit, on an unsorted list, until either the entire array is searched or the target value is found

• This is slow but can but has an omega of 1 because by chance target value could be first in array

• Another method of searching is binary search, but this requires an array to be sorted before it can be searched.

• This method involves going to midpoint of array, and dismissing the half of the values which are above or below the target value, depending on what the midpoint turns out to be. Each subsequent step uses the same method, so effectively, after each guess, the array is half the size, meaning the answer is more and more likely to be found
  • such a method is represented by Big O of log n.

• Big O is more relevant because we like to know what the worst case scenario is for users, because the occasional lucky guess is rare. However, knowing the range can be useful.

• While binary searching appears to be the best option, however, because of the need to sort, it may not always be the best.

• Deciding factor could be how many times you will need to search array, if it’s many, then sorting is probably worth it for the shorter runtimes in subsequent searches.

• But if its just searched once, maybe a sort is not worthwhile

• Factors include resources like: time to run the code, time to write more complex or simpler code, amount of memory available for algorithm

String compare.

• a function from the string.h library of C. strcmp allows C to compare two strings.

• the syntax is:
  • int strcmp(string s1, string s2);

• if the strings match, this comparison needs to equal zero, any other, either positive or negative, will mean strings do not match

Data Structures

• A struct is a data structure which can store multiple values.

  

• To utilise this structure, we could write the following function initialising the people array with the new datatype ‘person’ as defined above

• Structs have many uses, such as in some programs, which requires values of larger amount than can be represented by 32 or 64-bit machines, can create big int structures which store an array of values to represent large, individual values.

Sorting

We learnt about three different methods for sorting numbers

1. Selection Sort
   1. Selection sort will begin by looking for the smallest number in the list and swap that number with our current position in the list.
   2. 5 2 7 4 1 6 3 0
      1. the algorithm will run through and identify the zero as the smallest, so it will get moved to the left
   3. 0 | 2 7 4 1 6 3 5
      1. because algo knows 0 is smallest, it will start from the next value and search for smallest value
      2. once it finds the one, it has to continue searching, because although its obvious this is the smallest value to a human, the machine has no way of knowing there is not another zero in array, so it has to methodically go through all values
   4. 0 1 | 7 4 2 6 3 5
      1. this same process will continue until all are sorted

2. Bubble Sort
   1. Bubble sort is another sorting algorithm that works by repeatedly swapping elements to “bubble” larger elements to the end. In other words, it works through the list and sorts the two numbers next to each other to make sure they are in the correct order, breaking the list down into bubbles of two values.
   2. 5 2 7 4 1 6 3 0

      ^ ^

      if this list was to be sorted, first the five and two would be checked, and the five would get swapped to the right side

   3. 2 5 7 4 1 6 3 0

      ^ ^

      then the five and seven, which would need no changes

   4. 2 5 7 4 1 6 3 0

      ^ ^

      then the seven and four would be checked, and the seven would get moved to the right

   5. 2 5 4 7 1 6 3 0

      ^ ^

      and so on, with this first run through ending up with the 7 all the way to the right. In the second run-through, the algorithm would go all the way up to second last value, because it already knows the 7 is in correct position

Recursion

• is a programming technique whereby a function calls itself

• In the below image we have a function which prints the mario pyramid from previous week’s exercise.

• However, instead of using nested for loops as we were taught, this example uses recursion to print the pyramid.

• To explain, the function is effectively saying to draw a pyramid of height, you need draw a pyramid of height n - 1 and then print an additional row of n width until n = 0.

• In other words, the function will keep calling itself, printing a row at a time, until n = 0

Merge Sort

• a very efficient sort algorithm.

• uses a similar concept to binary search or the phone book but with a few added steps

1. First, merge sort asks, “is this one number?” The answer is “no,” so the algorithm continues.

   7254

2. Second, merge sort will now split the numbers down the middle (or as close as it can get)

   72|54

3. Third, merge sort would look at these numbers on the left and ask, “is this one number?” Since the answer is no, it would then split the numbers on the left down the middle.

   7|2

4. Fourth, merge sort will again ask , “is this one number?” The answer is yes this time! Therefore, it will quit this task and return to the last task it was running at this point.

   72|54

5. Fifth, merge sort will sort the numbers on the left.

   27|54

6. Now, the left side has been sorted a similar process will occur with the right-hand numbers. This will result in.

   27|45

7. Both halves are now sorted. Finally, the algorithm will merge both sides. It will look at the first number on the left and the first number on the right. It will put the smaller number first, then the second smallest. The algorithm will repeat this for all numbers, resulting in:

   2457

• Merge sort is a very efficient sort algorithm with a worst case of O(n log n). The best case is still Ω(n log n)because the algorithm still must visit each place in the list. Therefore, merge sort is θ(n log n) since the best case and worst case are the same.

Summary

• Algorithms.

• Big O notation.

• Binary search and linear search.

• Various sort algorithms, including bubble sort, selection sort, and merge sort.

• Recursion.

Selection sort top, merge sort middle, bubble sort bottom