1. Algorithm & Programming

1.1. Introduction to Algorithms

Algorithms are fundamental to the world of programming and computing. They represent the step-by-step instructions required to solve specific problems or perform tasks. In this section, we will delve into what an algorithm is, explore key definitions from notable computer scientists, and review real-world examples of algorithms, such as testing for prime numbers.

1.1.1. What is an Algorithm?

An algorithm is a detailed and precise set of instructions used to accomplish a task. As Gérard Berry (professor at Collège de France, 1948-) explains:

“Un algorithme, c’est tout simplement une façon de décrire dans ses moindres détails comment procéder pour faire quelque chose. Il se trouve que beaucoup d’actions mécaniques, toutes probablement, se prêtent bien à une telle décortication. Le but est d’évacuer la pensée du calcul, afin de le rendre exécutable par une machine numérique (ordinateur).”

“An algorithm is simply a way of describing in minute detail how to do something. It turns out that many mechanical actions, likely all of them, fit this definition. The goal is to remove thought from the calculation, making it executable by a computer.”

In essence, algorithms break down a problem into smaller, manageable steps that a machine (or a person) can follow without needing further decision-making. For example, in everyday life, a recipe for baking a cake can be seen as an algorithm: it provides a series of instructions to follow in a precise order to achieve a specific result—the cake!

1.1.2. Formal Definition

Donald Knuth (Professor at Stanford, 1938–), a well-known computer scientist and author of The Art of Computer Programming, provides a more formal definition:

“An algorithm is a finite and unambiguous sequence of instructions and operations that allows solving a class of problems.”

Let’s break down some key components of this definition:

1. Finite: An algorithm must have a finite number of steps. This does means that the algorithm cannot run indefinitely.

2. Unambiguous: Each step in the algorithm must be clear and leave no room for misinterpretation. The instructions should be simple enough to follow exactly, even if performed by hand.

3. Class of Problems: An algorithm is not designed to solve just one problem, but rather a whole group or class of problems that are similar in nature.

1.1.3. Essential Characteristics of an Algorithm

From Knuth’s definition, we can also infer some essential characteristics:

• Inputs: These are values provided to the algorithm, either at the start or dynamically during its execution. For example, in a prime number test, the input is the number you want to test for primality.

• Outputs: These are the results produced by the algorithm, which should have a clear relationship to the input. In the case of the prime number test, the output is either “True” (the number is prime) or “False” (the number is not prime).

• Correctness: An algorithm is said to be correct if, for every valid input, it produces the expected output. This means it must always solve the problem it’s designed to handle, and it must terminate with the right answer.

1.1.4. Example: Primality Test Algorithm

Let’s look at a simple algorithm to determine whether a given number (n) is prime. A prime number is a number greater than 1 that has no divisors other than 1 and itself.

Input: An integer (n > 1)

Output: Return True if (n) is prime, False otherwise

def is_prime(n):
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

This algorithm works by checking all integer values between \(2\) and ( \sqrt{n} ). If (n) is divisible by any of these values, then it is not prime, and the algorithm returns False. If no divisors are found, the number is prime, and the algorithm returns True.

1.1.5. Example: Fermat Primality Test

Another way to test for primality is using a probabilistic approach like the Fermat Test. While it is not always accurate, it can quickly determine if a number is likely prime.

Input: An integer (n > 1)

Output: Return True if (n) is probably prime, False if it is definitely not prime

def fermat_test(n):
    if pow(2, n-1, n) == 1:
        return True  # n is probably prime
    else:
        return False  # n is definitely not prime

This test is based on Fermat’s Little Theorem, which states that if (n) is prime, then (2^{n-1} \mod n) should equal 1. If this condition holds, (n) is “probably prime.” If not, (n) is definitely not prime. Keep in mind that this algorithm can occasionally fail for certain composite numbers, which is why it’s considered probabilistic.

1.1.6. Properties of Algorithms

Every algorithm comes with its own set of characteristics that affect its behavior, including:

• Running Time: The time it takes for the algorithm to run to completion. Different algorithms can solve the same problem, but one might do it faster than another.

• Deterministic vs. Probabilistic: Some algorithms, like the primality test, are deterministic, meaning they always give the same output for the same input. Probabilistic algorithms, such as the Fermat Test, may occasionally give the wrong answer, but they are often faster and simpler.

It’s important to note that these properties are inherent to the algorithm itself, not the programming language or the way it’s implemented.

1.2. Introduction to Python

Now that we have an understanding of algorithms, let’s explore how to implement them using Python.

Python is a popular, high-level programming language developed by Guido van Rossum in the late 1980s. It has gained widespread use due to its simplicity and versatility, making it an excellent language for beginners and professionals alike.

1.2.1. Key Features of Python

• Easy to Learn and Read: Python’s syntax is clean and simple, making it one of the most accessible programming languages for beginners. It uses indentation to define code blocks, which makes it visually organized and readable.

• Interpreted Language: Unlike languages like C or Java, Python does not need to be compiled before it is run. This allows for rapid development and testing of code.

• Dynamically Typed: Python does not require you to declare the type of a variable when you create it. The language infers the type based on the value you assign to it, making coding faster and easier.

• Multi-paradigm Support: Python supports various programming paradigms, including:

  • Procedural: Writing sequences of instructions.

  • Object-Oriented: Organizing code into objects with attributes and methods.

  • Functional: Writing functions that are treated as first-class citizens.

• Extensive Standard Libraries: Python comes with a vast collection of built-in modules and functions that allow you to perform a wide range of tasks, from web development to data analysis, without the need for external libraries.

1.2.2. From Algorithms to Python Code

Throughout this course, you will learn how to take algorithms and translate them into Python code. The process typically involves:

1. Defining the Problem: Clearly stating what you need to solve.

2. Designing the Algorithm: Writing a step-by-step plan.

3. Implementing in Python: Writing Python code based on the algorithm.

4. Testing and Debugging: Running the code with different inputs to ensure it works as expected.

By mastering the principles of algorithms and learning Python, you’ll be able to tackle a wide range of computational problems efficiently.