MATHEMATICS DEPARTMENT
2024-2025 ACADEMIC YEAR
MATHEMATICS LECTURE NOTES
Theme 5_Algorithms and Informatics
9th Grade
Student’s
Name: ……………………………
Surname: ………………………..
Number: ...……………………….
Class: …………………………….
0
Algorithm and Informatics
Algorithms work by following a set of instructions or rules to complete a task or solve a problem. They can be
expressed as natural languages, programming languages, pseudocode, flowcharts.
Today, an algorithm refers to the step-by-step application of clearly defined rules and processes to solve a problem
or complete a specific task. The algorithmic approach defines a comprehensive problem-solving method used for the
development, evaluation, and application of algorithms. While it is commonly used in fields such as computer
science, mathematics, engineering, and economics, its fundamental principles can be applied in all branches of
science. The process steps for the problem-solving method with the algorithmic approach can be followed as shown
in below.
Steps of the problem-solving method with an algorithmic approach
1. Defining the Problem: Clearly expressing what the problem is.
2. Determining Inputs and Outputs: Determining the input which makes the algorithm ways of and the expected
outputs.
3. Deciding the Operation of the Algorithm: Representing the algorithm by natural language, flowcharts or
pseudocode.
4. Testing and Optimization: To enhance the algorithm testing the algorithm and make some optimizations.
functioning of the algorithm
Algorithmic Natural Language: The functioning of the algorithm is explained using everyday language.
Flowchart: The functioning of the algorithm is explained with a visual representation.
Pseudocode: The functioning of the algorithm is explained with sentences that do not belong to programming
language but reflect coding logic.
1
Example: Express the operation of the algorithm that finds the area of a rectangle in natural language.
Algorithmic Natural Language Functioning of the Algorithm
Step 1: Start
Step 2: Obtaining Inputs
Step 3: Area calculation
Step 4: Obtaining output
Step 5: End
Notes:
2
Constructing Flowchart
In flowcharts following symbols are used. In the table the symbols and their meanings are given.
Symbol Meaning
Indicates the beginning or end of a flowchart.
Represents data input or output
Used to perform operations and assign values
to variables.
Indicates a decision point where a condition is
checked and the flow splits into two or more
paths. Can be used in loop structures.
Represents flow directions.
Represents that a section or report has been
created and that this document has been
printed.
Represents connection points.
3
Example: In the figure triangle ABC is a right triangle. Express the algorithm for A
finding the area of triangle ABC by algorithmic natural language and flowchart.
x
B C
y
Algorithmic Natural Language Functioning of the Algorithm
Step 1: Start
Step 2: Obtaining Inputs
Step 3: Area calculation
Step 4: Obtaining output
Step 5: End
Flowchart:
4
Example: In the example below, the algorithm that finds the remainder of division of 13 by 3 by repetitive
subtraction method is expressed by algorithmic natural language.
1. Step: Start
2. Step: Obtaining Inputs
Put dividend (13) and divisor (3)
3. Step: Calculating the Remainder
At first step subtract 3 from 13 and the take remainder as 10.
Then, subtract 3 from 10 and take remainder as 7.
Then, subtract 3 from 7 and take remainder as 4.
Then, subtract 3 from 4 and take remainder as 1.
4. Step: Checking the Condition
If the remainder is less than the divisor (1<3) finish; if it is not go step 3.
5. Step: Finding the Result
The final remainder and the last value that satisfies the condition (1) is the remainder of the division.
6. Step: End
Make a flowchart by using the algorithm above.
5
Pseudocode: Pseudocode is a series of instructions written in a simple and explanatory language that describes how
a computer program will work, which can be read and understood by humans. Pseudocode does not use the
technical details and complex syntax of a real programming language.
For example, if we express the algorithm which calculates the area of a rectangle by pseudocode it, it will be like
below.
Input: Length of long side, Length of short side
Output: Area
Start
Area= length of long side * length of short side
Print ‘Area of rectangle’, Area
End
Remark: While writing pseudocode, we are using some operators. Arithmetic operators are symbols that perform
mathematical operations on variables or constants in programming and mathematics. Comparison operators are
symbols that tells the mathematical comparison of two quantities.
Arithmetic Operators Meaning of the Operators
Addition (+) Calculates the sum of two numbers.
Subtraction (-) Calculates the difference between two
numbers.
Multiplication (*) Calculates the product of two numbers.
Division (/) Allows one number to be divided by another.
Exponent (^) Calculates the power of one number with
respect to another.
Mod (%) Gives the remainder of one number divided by
another.
Comparison Operators Meaning of the Operators
< Less than
> Greater than
<= Less than or equal to
>= Greater than or equal to
= Equal to
6
Example: Make the flowchart of the algorithm given by natural language.
Step 1:Start
Step 2: Enter Age
Step 3: Condition: Age <13
: if true print ‘Kid’
: if wrong: Condition: 13<= Age <20
:If true print ‘Teen’
: if wrong: print ‘Adult’
Step 4: End
Example: In Işık University, students are entering one midterm exam and one final exam in a term. The pseudocode
of the algorithm that decides a student’s Pass or Fail situation is given below. Make a flowchart according to this
pseudocode.
Input: Midterm Grade (A) and Final Grade (B)
Output: Write ‘Pass’ of ‘Fail’
Start:
The average grade is calculated.
Average Grade = ( A*40 + B*60) / 100
If Average Grade >= 70, then write ‘Pass’
If Average Grade < 70, then write ‘Fail’
End
7
Activity 1
The price of a pack of wet wipes in a market is 100 TL. Discounts will be applied based on the number of packs
purchased in bulk. The operation of the algorithm that calculates the total amount the customer will pay based on
the number of packs purchased is given in the flowchart below.
Start
Enter the
number of
product (x)
No No x >= 100
1 < x <= 49 50 < x <= 99
Yes Yes
Yes
x*95 x*90 x*85
Total amount is Total amount is
Total amount is ……. TL ……. TL
……. TL
End End End
8
Answer the following questions.
a) Define the problem.
b) Define the input and output that works algorithm.
c) Write the algorithm by pseudocode.
d) Write the algorithm by algorithmic natural language.
e) Test the algorithm by calculating the total amount the customer will pay if he/she buys 60 or 200.
9
Example:
Input: A positive integer x On the left, an algorithm is presented in pseudocode
that determines whether a positive integer is
Output: A result indicating whether x is divisible by 5 or not, divisible by 5.
as “true” or “false”
a) Describe the algorithm’s process using
Start: natural algorithmic language.
b=x % 10 è Find the ones digit of the number
If b is 0 or 5,
Print “TRUE(x is divisible by 5)”
If b is not 0 or 5,
Print “FALSE(x is not divisible by 5)”
End
b) Represent the algorithm with a flowchart and test whether 47 is divisible by 5 using the flowchart.
Cryptology is the science of protecting and concealing information. The factorization of numbers plays an important
role in cryptology. The RSA algorithm, named after its inventors Ron Rivest, Adi Shamir and Leonard Adleman, is
based on the multiplication of large prime numbers. In this algorithm, while the product of two large prime numbers
can be easily calculated, factoring a number into its prime factors is extremely difficult. This computational difficulty
forms the foundation of RSA security because decrypting a message requires finding the prime factors of these large
numbers. Without an efficient prime factorization algorithm, breaking such encryption is difficult.
The main algorithms developed for factoring prime numbers include trial division algorithms, Pollard’s rho algorithm,
and Shor’s algorithm, which is used by quantum computers.
10
Activity 2
Trial division is an algorithm for finding the prime factors of a number. In this algorithm, the divisibility of the given
number by the smallest prime number,2, is checked first. If the number is divisible by 2, the result is divided by 2,
and the process continues until the remainder is no longer zero. Then, the division process continues with other
prime numbers such as 3,5 and 7. The division process is carried out for prime numbers smaller than the square root
of the number whose prime factors are to be found.
Algorithmic Natural Language
Start
Input: A positive integer x
Output: A list of prime factors of x
Step 1: Take x as input.
Step 2: Create an empty list named “prime factors” to store the obtained prime factors.
Step 3: Perform division by 2
If x is even
While x is divisible by 2
Divide x by 2 and update the result as x
Add 2 to the prime factors list.
Step 4: Perform division with other prime numbers
Initialize variable y as 3.
While y is less than or equal to the square root of x
If x is divisible by y
Divide x by y and update the result as x
Add y to the prime factors list
Increment y by 2
Step 5: Check the last factor
If x is greater than 1
x is a prime number and should be added to the prime factors list
Result: Provide the prime factors list as output.
11
a) Obtain the list of prime factors of the number 75.
b) Discuss why the division process in algorithmic language is performed for prime numbers smaller than the
square root of the number whose prime factors are to be found.
c) Evaluate the effect of increasing number (731 021) on the performance of the algorithm.
Example: An encryption algorithm is designed by writing digits into 4 seperate cells to form a four digit natural
number. This algorithm first subtracts each digit from 9, then determines the remainder when the result is divided
by 5. Finally, it encrypts the number of placing the determined digit in the corresponding cell with the same number
as the original input cell. The encryption process for a given number is shown below.
When Pınar enters digits into the algorithm, the resulting encrypted digits are provided below.
It is known that the four digit number abcd entered by Pınar is divisible by 4 and the remainder when divided by 9 is
3.
Find the natural number abcd entered by Pınar entered into the algorithm.
12
Programming Language: A programming language is formal language used to create a sequence of instructions that
computers can understand and execute.
Each programming language has its own unique syntax. Programmers use syntax to convert algorithms into code.
This allows computers to perform the desired tasks. Syntax includes the rules and structures of the programming
language, and if not used correctly, the program may run incorrectly or not run at all.
Example: A doctor at the hospital where they
work will be on duty every three days
according to the scheduled shift plan. The
doctor will have their first shift on Tuesday.
An algorithm written in a programming
language is used to determine on which day
the doctor’s 9th shift will fall.
In the given code, the English word “print”
corresponds to Turkish word “yazdır”.
Express the given algorithm’s process in
natural algorithmic language, and determine
on which day the 9th shift will fall.
13
Activity 3
1) Among n coins of the same size, one has a different mass. What is the minimum number of weighings required
to identify it? Explain your reasoning if applicable.
2) Complete the table below by making assumptions for different integer values that n can take. Then, create
generalizations about the number of weighings.
3) Compare your assumptions with your generalizations and express them as a proposition. If you have reached
more than one proposition, express each one seperate sentences.
4) Select one of your propositions and express the process an algorithm that determines the minimum number of
weighings needed to identify the coin with a different mass among n coins of the same size in natural algorithmic
language.
Algorithmic natural language
14
5) Apply your algorithm for different values of n. Calculate the minimum number of weighings for each case and
compare the results.
6) An automobile parts manufacturer is planning to establish a new testing system to perform quality control on
screw packages coming from the production line. Each screw package contains 1024 screws, an each screw must
have a mass within the specified tolerance range. Using your algorithm, determine the minimum number of
weighings required to detect one defective screw among the 1024 screws.
7) A pharmaceutical production family aims to establish a test protocol to ensure quality control during the
production process of a newly developed cardiovascular drug. Each batch contains 2187 capsules, and each
capsule must contain the specified amount of the active ingredient. Using your algorithm, determine the
minimum number of weighings required to detect one defective capsule if there is any.
Activity 4
In a group of n people, if each person shakes hands with every other person exactly once, the total number of
handshakes needs to be determined. The table below shows the total number of handshakes based on the number
of people in the group.
1) Using the pattern in the table, derive the algebraic expression for the total number of handshakes when the
number of people is n.
2) Define the input values and expected outputs for an algorithm that calculates the total number of handshake.
15
3) Represent the algorithm’s process using natural algorithmic language, a flowchart and pseudocode.
4) Using your algorithm, calculate the total number of handshakes for groups of 5,6 and 7 people. Compare the
results.
5) How does the performance of your algorithm change as the number of people increases?
16
Examining Relational Models with Graph Theory in Algorithmic Structures
Graph theory studies the relationships between objects using nodes (vertices) and edges that connect these nodes.
The situation where everyone in a group shakes hands with each other can be explained by graph theory.
In the figure, the handshake between two people is represented as a graph
with the help of nodes and edges. In this graph, nodes A and B represent the
individuals, and the edge between them shows the relationship between the
nodes (handshake).
Graph theory provides a model for many real life problems, from social networks to general network connections,
from pathfinding systems to electrical circuits.
Algorithms operate on these models to solve specific problems.
17
Activity 5
Solving the Circulation Problem in the City of Königsberg Using Graph Theory
1) In the visual representations given in the table below, graphs are provided to represent different paths between
specific points in a city. Based on this, if person starting from point A can return the starting point while using
each path only once, mark it with tick, if not, mark it with cross in the table as shown in the example.
Graph Verbal Condition of Returning the
Representation All Nodes starting Node
Having an Condition
Even Number
of Edges
A person starting Nodes A and B
from node A can each have two
reach node B using edges. All
edge a, then nodes have an
return to starting even number
node using edge b. of edges.
18
2) The graph on the side can be drawn on paper starting from node A or B,
without lifting the pen, by following arrows in the image and crossing each
edge exactly once, returning the starting point.
Try drawing the other graph examples in the table on paper selecting a
starting point, without lifting your pen, and crossing each edge only once.
3) Explain the relationship between the number of edges each node has (whether odd er even) and the feasibility
of drawing the graph on paper.
19
4) Examine the island in the given model, which
represents the bridges of Königsberg and point A.
Express whether it is possible to return to the
starting point while crossing each bridge exactly
once.
5) Examine whether the number of edges connected to each node in the graph,being odd or even, affects route
planning.
6) Define the input data and expected outputs for an algorithm that determines wheter it is possible to return to
the starting point while crossing each bridge exactly once.
7) Explain the algorithm’s process using algorithmic natural language and a flowchart.
20
8) Test your algorithm for different scenarios(e.g. the closure of one of the bridges or the addition of new edges to
a node.)
Example: In a data center, there are 3 different servers (A, B, C) and three
different data repositories (Ç, D, E), with a graph showing the relationship
between A and Ç provided as an example. Each server can exchange data with
the data repositories at high speed and reliably. According to the design rules
of the data center, create a graph that provides the best data transfer between
servers without cross (intersection) connections.
21
Activity 6: In cybersecurity systems, passwords are one of the fundamental tools for protecting data in terms of
digital privacy and data security. For example, the password you set to log into your social media account is made up
of letters, numbers, and symbols selected from the ASCII character set derived from the phrase 'American Standard
Code for Information Interchange'. The ASCII character set is based on a coding system. In the table provided below,
each character is represented by a specific numerical value.
Computers fundamentally use their own unique system. All data (such as letters, numbers, images) is stored and
processed in computers as 0s and 1s
For example the correspondence of letter a in ASCII is 65. The computer saves 65 as 1000001. In below the
operation of converting 65 to 10000001 is given.
This is the operation of writing a
number in base 10 in base 1.
If we say mathematically:
(65)10 = (1000001)2
22
1) Define a encyrpted text of at least 8 characters. Your text must contain one uppercase letter, one lowercase
letter and one special character. ( ], @, /, … etc). Do not use non-ASCII characters.
2) Find the representation of your encryption text in computer system. Compare the values you obtained with
those found by your friends. Determine whether the encrypred texts contain similar or different characters.
3) Explain your process of an algorithm that converts a number in the decimal system to a number in the computer
system using algorithmic natural language.
23
Logical Connectives and Quantifiers in Algorithmic Structures
Activity 7
A high school has initiated a special program to grant scholarships to students who have excelled in academic and
social activities. This program determines the students who will receive scholarships by considering their grade point
averages, participation in activities, and involvement in scientific projects. The table below contains information
about students applying for scholarships, their grade point averages, the duration of their participation in voluntary
activities, and whether they have participated in a scientific project.
24
a) In the table below, express verbal statements containing conditions using logical connectors and quantifiers.
Identify the students who meet the conditions and fill the table as shown in the example.
b) Is having 20,000 students applying for scholarships sufficient for identifying students who meet the
conditions? What alternative could be used?
25
c) The scholarship committee, which collects students' information, evaluates the following criteria for each
application:
* The grade point average must be greater than 85.
* Must have participated in voluntary activities for at least 2 years.
* Must have been involved in a scientific project.
Express the functioning of the algorithm that finds students meeting all these conditions above by
algorithmic natural language.
d) Using the algorithmic natural language you wrote, complete the column in the table that determines
whether students qualify for a scholarship, and test your algorithm.
e) Test the algorithm you obtained for the two conditions given below and complete the table.
26
Example: A musical instrument manufacturer produces triangular instruments by using metal parts. An algorithm is
used in the production process to determine which parts can be combined and what type of triangular instrument will
be produced. The flowchart of this algorithm is given below. Accordingly, identify the roles of the logical connectors
used in the algorithm that checks the suitability of metal parts for the production of musical instruments in the
flowchart.
27
Usage of Logical Connectives and Quantifiers in Algorithms
Activity 8
1) Complete the given algebraic proof for the statment “the square of every odd integer is also odd.”
2) Express the process of an algorithm that determines whether the square of every odd integer is also odd using
algorithmic natural language and a flowchart.
3) Test your algorithm for integers from -10 to 10.
4) Explain the similarities and differences between the steps of your algorithm’s process and the steps of the
algebraic proof.
28
Example: For the given proposition “Given a three digit natural number abc and , if
.” Answer the following questions.
a) Prove the proposition.
b) Using the proof steps obtained, express the algorithmic process in natural algorithmic language for
determining whether a three digit natural number is divisible by 7.
c) Examine the pseudocode and explain the function of logical connectives.
29
Example: Given proposition “If a natural number leaves a remainder 13 when divided by 45, then the remainder of
the same number when divided by 5 and 9 are 3 and 4, respectively.”
Answer the following questions.
a) Express the given proposition using symbolic notation.
b) Prove the proposition using symbolic notation.
30
c) Describe the algorithm that determines the remainders of a number when divided by 5 and 9, given that it
leaves a remainder of 13, when divided by 45, using natural algorithmic language, pseudocode and a
flowchart.
31