Last modified on 30 November 2013, at 18:55

User:Mark Otaris/Lua programming/Algorithms

Computer science, programming and software engineering are all very related fields. Computer science is the science of computers, programming is the process of creating computer programs and software engineering is the process of using computer software to solve problems. This chapter will cover concepts that are important to understand in all these three fields.

KnowledgeEdit

There are two types of knowledge: descriptive knowledge and procedural knowledge. Descriptive knowledge, which is also called declarative knowledge and propositional knowledge, is knowledge that is comprised of facts. It is expressed in declarative sentences. For example, the following statement is descriptive knowledge: "the square root of nine is three". That is a fact, but it doesn't tell us how we can find the square root of nine. Procedural knowledge, which is also called imperative knowledge, is knowledge that tells us how to do something. It can be thought of as "how-to" knowledge, or as recipes to do something. A list of steps that one can follow to find the square root of nine, for example, would be procedural knowledge.

AlgorithmsEdit

An algorithm can be thought of as a sequence of steps to execute combined with a flow of control that tells when each step needs to be executed. This is true in all fields, including mathematics, science, cooking and computer science. Often, the flow of control will be included in the steps. This is the case, for example, in the following algorithm, which can be used to multiply two numbers, assuming that x and y are the two numbers that need to be multiplied and that y isn't a decimal or negative number:

  1. Start with a number n, which is equal to x, and with a number i, which is equal to 1
  2. If i is equal to y, stop. n is the product of x and y
  3. Add x to n
  4. Increase i by 1
  5. Go back to the second step

Try to follow the steps here with different numbers. You will notice that you will always obtain the product of x and y as long as y isn't negative or decimal. For example, let's use this algorithm to multiply 3 with 2. We start with n being equal to 3 (since x is equal to 3), and i being equal to 1. Since 1 is not equal to 2, we do not stop yet. We add x to n, which now equals 6. We then increase i by one, so it now equals 2. Then, we go back to the second step and since i is now equal to y, we stop and we take the value of n as our answer. n, by this point, equals 6, which indeed is the product of 3 and 2.

This algorithm, in Lua, would look like this:

-- We assume that x and y have already been defined to the numbers that need to be multiplied.
n, i = x, 1 -- We set n to equal x and i to equal 1.
while true do
	if i == y then
		-- If i is equal to y, stop and take n as the answer.
		print("The product of " .. x .. " and " .. y .. " is " .. n .. ".")
		break
	end
	n = n + x -- We add x to n.
	i = i + 1 -- We increase i by 1.
	-- We go back to the second step.
end

It could also be simplified to the following:

-- We assume that x and y have already been defined to the numbers that need to be multiplied.
n = 0
for _ = 1, y do
	n = n + x
end
 
print("The product of " .. x .. " and " .. y .. " is " .. n .. ".")

Which could, finally, be simplified to just the following:

-- We assume that x and y have already been defined to the numbers that need to be multiplied.
 
print("The product of " .. x .. " and " .. y .. " is " .. x*y .. ".")