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.
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.
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.