Algorithm Design
Computers have become an essential tool for solving many problems arising in industries and research. The engineering approach for solving problems in computer science is usually the following one:
Understand the terms of problem
Model the problem in a formal language often involving mathematics
Design an algorithm to solve the formal problem
Program and test the solution
Deploy/use the program
This course spans from step 2 to 4 and is mainly focused on the 3rd step Design an algorithm. Depending of the problem, the difficulty of the algorithm design can range from trivial to extremely difficult.
For example a very simple problem can be: During the development of a shopping website I have to compute the total price of the items in a shopping cart. In this case, the solution is trivial and you should be able to solve it without really thinking about it.
A more complicated example can be: I work in a graphics card factory, a robot must drill each card in a certain number of places for the fixing screws. In what order should the robot make the holes to minimize the total travel length and therefore the machining time of a board? Now the problem starts to be more complicated, we see that the problem is stated as an optimization problem: you might be able to design a brute force algorithm (test every possible solution and keep the best one) that works for small instance sizes but going further will definitely requires some thinking.
Algorithmics
The study of algorithm corresponds to a field of research mixing mathematics and computer science and predates the existence of computers. The main questions which are addressed in algorithmics are:
Existence or computability. Does there exist an algorithm to solve a given problem? This question is out of the scope of this course.
Complexity. How does the number of basic operations performed by the algorithm growths when the size of the input increases? How does the amount of memory required by the algorithm growths when the size of input increases?
Correction. How can I prove that a given algorithm produces a correct output for all valid inputs?
Aim of this course
As you have probably understood now, this is not a programming course! Indeed, we assume that you know the principles of imperative programming: how to write functions, conditions, loops, use arrays…
In this course, you will see:
how to perform the complexity analysis of an algorithm;
3 main classes of algorithms: greedy, divide and conquer, and dynamic with plenty of examples for all of them;
how to identify a suitable class of algorithms for a new problem
how to design an algorithm for a new problem
You will not see some related or more advanced topics such as:
parallel and distributed algorithms
approximation algorithms
…