Lessons 12–13 · 2 lessons · M. R. Fayziyeva, D. M. Sayfurov, N. S. Xaytullayeva. Informatics and Information Technologies, Grade 9. “Nashriyot uyi Tasvir”, Tashkent, 2020
13
Linear algorithms
Textbook: pp. 35–37
GoalNames the three basic types of algorithm (linear, branching, repeating), designs a linear algorithm in words and as a flowchart, and swaps the values of two variables.
New words
linear algorithm: all instructions are carried out one after another with no conditions · chiziqli algoritmalgorithmic construct: one of the three basic structures – sequence, branching, repetition · algoritmik konstruksiyaassignment: putting a value into a variable, written x = value · qiymat berishtemporary variable: an extra variable that keeps a value safe while others change · oraliq o‘zgaruvchi
Explanation
In the 1970s the Dutch scientist Edsger Dijkstra showed that any algorithm can be written with three constructs – sequence, branching and repetition. So algorithms are divided into linear, branching and repeating types. In a linear algorithm all instructions are carried out one after another, in the written order, with no conditions. Its flowchart consists of an oval (start), parallelograms for input/output, rectangles for calculation and an oval (end), all along one line. Typical linear algorithms: calculating by a formula and swapping the values of two variables. A swap needs a third, temporary variable: t = x, x = y, y = t; otherwise, once x = y is done, the old value of x is lost.
💡 Where will I use this?
In real life
A class organiser wrote a worksheet for making one invitation per pupil: “Multiply the number of pupils by the paper needed for one invitation.” This is a linear algorithm and is carried out in the same order every time.
Who uses it
Accountants, office workers and programmers write simple calculation steps carried out in the same order.
Try it today
Write a linear algorithm in words for working out how many minutes one regular daily activity takes in a week, if it takes the same time every day. Test it with your own numbers.
Worked examples
Madina bought n notebooks at p so‘m each and a pen for 3000 so‘m. The total is S = n · p + 3000. Algorithm: start; input n, p; compute S = n · p + 3000; output S; end. For n = 4, p = 5000: S = 20 000 + 3000 = 23 000 so‘m.
Step
x
y
t
start
5
9
–
t = x
5
9
5
x = y
9
9
5
y = t
9
5
5
Swap: x = 5, y = 9. 1) t = x → t = 5; 2) x = y → x = 9; 3) y = t → y = 5. Result: x = 9, y = 5. Without t: x = y → x = 9 (the old 5 is lost); y = x → y = 9 – both end up 9.
Class activity
“Card swap”: two cards with numbers lie on the desk with one empty spot. Students swap the cards using the empty spot and say the three steps.
Practice
1
What is a linear algorithm?
An algorithm whose instructions are all carried out one after another in the written order, with no conditions.
2
Compute the circumference C = 2 · 3.14 · R for R = 5.
31.4
3
Let x = 3, y = 8. What are x and y after t = x; x = y; y = t?
x = 8, y = 3
4
Why is a third variable needed to swap two values?
When x = y is done, the old value of x is erased; t keeps it safe beforehand.