Classroom practice, week 1: Algorithms
Zsolt Kohári · 2019.09.10.
Introduction to programming and algorithms. The description of some basic algorithms with flowcharts and pseudo-code.
This is the first classroom practice of the semester. The aim of the practice is to provide an introduction to the logic of programing. We are going to cover some very basic, widely known algorithms. The task is to describe them in a formal way, and to convert them to a sequence of instructions.
We are going to describe the algorithms in English, by pseudo-codes. In a pseudo-code the steps of the algorithm are numbered. Numbering the lines enables us to refer to them later (like "jump to step n."), making iterative algorithms possible. The programs can be descibed by flow-charts as well, in which the lines and arrows define the order of execution of the operations.
The first task is a basic, but very important one. Let us create an algorithm to print numbers below each other, from 1 to 10!. The solution should be precise, it should contain all the necessary steps.
How can we describe repetitive steps?
Supplement the pseudo-code with arrows following the sequence of execution!
Let us now transform the solution further. This time we aim to get a structured solution, that does not have line numbers, the control flow is reflected by the structure of the program itself.
Let us introduce variable names and transform the repetition used in the previous solution to a proper loop. What we get is very close to a C program.
Let us write a program that prints only the even numbers (between 1 and 10)! Do we need to test whether X is even or odd? How to solve this task with testing and how to solve it without this testing step?
Write a program to print all numbers from 1 to 100 that are divisible by 3 but are not divisible by 5.
239 +124 ──── 363
Everybody has learnt in elementary school how to add two (potentialy big) numbers together. This is probably the first algorithm that is taught to every child. By this algorithm, the complex task is reduced to a more elementary one, to the addition of numbers smaller than 10. Hence, the problem is broken down to elementary steps. We can consider the addition of single-digit numbers elementary enough, since we can perform it instantly without any aid.
Let us describe this algorithm in a formal way! Let us use arrows again to indicate the order of execution of the steps in the program!
Adding up two numbers - fix
The solution above in not perfect. What is missing, in which case does it give a wrong result?
999 + 1 ──── ?
Let us follow (by hand) the behavior of our algorithm with this input.
How can be extend the algorithm to provide the correct solution for this input as well?
