2. Algorithms.

 

2.1 Definition of an Algorithm

So, what is an algorithm? Well, simply put, an algorithm is a step-by-step procedure for solving a problem. Think of it like a recipe. You follow the instructions in order, and you get the desired result. Algorithms are fundamental to computer science and programming. They are the backbone of every program and application we use.

Algorithms are not just confined to the world of computers. We use algorithms in our everyday lives all the time! For example, think about following a set of directions to get to a new place, or even the steps you take to make a cup of tea. Those are algorithms too! Algorithms can be simple or complex.

2.2 Characteristics of Algorithms.

Algorithms aren’t just any set of instructions; they have specific characteristics that make them useful for solving problems:

i.       Finiteness: An algorithm must always terminate after a finite number of steps. It can’t go on forever in an infinite loop!

ii.    Definiteness: Each step in an algorithm must be clearly and unambiguously defined. There should be no room for interpretation or guesswork.

iii. Effectiveness: Each step must be feasible and executable. It should be something that can actually be done with the available resources.

iv.  Input: An algorithm must have clearly specified inputs. It needs to know what data it’s going to work with.

v.     Output: An algorithm must produce a clearly specified output. It needs to deliver the desired result.

So, remember these characteristics when you’re designing your own algorithms. They’re essential for creating solutions that are reliable and efficient.

 2.3. Examples of Algorithms.

Let’s look at some examples of algorithms to make this more concrete:

Simple Algorithms:

 Okay class, let’s clarify the simple algorithms with a bit more detail, so everyone understands.

 Simple Algorithms:

1.     Calculating the sum of numbers: Imagine you have a list of numbers: 5, 2, 8, 1. The algorithm works like this:

                               i.            Start with a sum of 0.

                            ii.            Add the first number to the sum: 0 + 5 = 5.

                         iii.            Add the next number to the sum: 5 + 2 = 7.

                          iv.            Add the next number to the sum: 7 + 8 = 15.

                             v.            Add the last number to the sum: 15 + 1 = 16.

                          vi.            The final sum is 16.

            In Python, you can do this easily using the sum() function.

2.   Finding the largest number in a list: Let’s say our list is: 3, 9, 1, 6.

                               i.            Assume the first number is the largest.

                            ii.            Compare the next number with the current largest. Since 9 is larger, update the largest to 9.

                         iii.            Compare the next number with the current largest. Since 1 is smaller, the largest remains 9.

                          iv.            Compare the next number with the current largest. Since 6 is smaller, the largest remains 9.

                             v.            The largest number in the list is 9.

3.   Searching for an element in a list: Suppose we want to find the number 4 in the list: 1, 5, 4, 2.

                               i.            Look at the first element. Is it 4? No.

                            ii.            Look at the next element. Is it 4? No.

                         iii.            Look at the next element. Is it 4? Yes! We found it!

                          iv.            If we went through the whole list and didn’t find the number, then it’s not in the list.

These are basic examples, but they illustrate the fundamental idea of an algorithm: a clear, step-by-step process to solve a specific problem.

More Complex Algorithms:

Sorting Algorithms:

As we discussed, these algorithms arrange elements in a specific order, like ascending or descending. Let’s dive deeper into some common examples:

Bubble Sort:

·       How it Works: Bubble sort is one of the simplest sorting algorithms. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest element "bubbles" to the end of the list with each pass.

·       Example: Imagine you have the list . In the first pass, you’d compare 5 and 1, swap them to get . Then compare 5 and 4, swap them to get “, and so on.

·       When to Use: Due to its simplicity, bubble sort is often used to introduce the concept of a sorting algorithm. Bubble sort may be a better option since it can be implemented quickly, but for larger datasets, the speedup from quicksort might be worth the trouble implementing the algorithm.

·       Limitations: Bubble sort is not efficient for large datasets. It has a time complexity of O(n^2), which means the time it takes to sort increases quadratically with the number of elements.

 

Insertion Sort:

·       How it Works: Insertion sort builds the final sorted array (or list) one item at a time. It iterates through the input data, growing the sorted array one element at a time. Much like its name implies, the algorithm iterates through the list, taking one element at a time and "inserting" it into the correct position relative to all the other elements already sorted.

·       Example: Imagine you are holding a hand of cards, and you pick up a new card. You would then shift the other cards in your hand to the right spot to insert the new card in the correct location.

·       When to Use: Insertion sort is efficient for sorting small number of elements and nearly sorted lists.

·       Limitations: Insertion sort is also not efficient for large datasets. It also has a time complexity of O(n^2).

Merge Sort:

·       How it Works: Merge sort is a divide and conquer algorithm. It divides the unsorted list into n sublists, each containing one element (a list of one element is considered sorted). It then repeatedly merges sublists to produce new sorted sublists until there is only one sublist remaining, which will be the sorted list.

·       When to Use: Merge sort is more efficient than bubble sort and insertion sort for larger lists.

·       Limitations: Merge sort requires additional memory space to store the sublists.

Search Algorithms:

 These algorithms are designed to efficiently find specific elements in large datasets.

Binary Search:

·       How it Works: Binary search is a highly efficient search algorithm that works on sorted lists. It repeatedly divides the search interval in half. If the middle element is the target value, the search is complete. If the target value is less than the middle element, the search continues in the left half of the interval. If the target value is greater than the middle element, the search continues in the right half of the interval.

·       When to Use: Binary search is very efficient for searching in large, sorted datasets.

·       Limitations: Binary search requires the list to be sorted first. If the list is not sorted, you need to sort it first, which adds to the overall time complexity.

2.4. Advantages and Limitations of Algorithms

Algorithms have their pros and cons:

Advantages:

4.   Provide a clear and logical approach to problem-solving.

5.    Can be easily translated into code.

6.   Algorithms can be reproduced by others making them a valuable tool for research and development.

Limitations:

7.    May not be suitable for all types of problems.

8.   Can be difficult to design for complex problems.

9.   Some algorithms might perform very well for some problems while performing poorly for others.

So, it’s important to choose the right algorithm for the task at hand and to be aware of its limitations.