Description

A program has to perform correctly Algorithms effectiveness.
what it is supposed to do. That is the
However, if doing what is supposed to
do also requires the usage of limited resources, as time, memory, or even power consumption, this is a matter of efficiency, instead of effectiveness.
Effectiveness versus Efficiency We will study the efficiency of algorithms, thus try to compute how much it takes to execute an algorithm.
● What is an algorithm
● Algorithm examples
● Summations and Logarithms
CSC 6013 – Week 2
Algorithms – History
What is an algorithm?
● Informally, a strategy for solving a problem.
This definition of algorithm is
correct, but too
generic, thus, we need a more specific one.
● Historically, a Latinized version of the name of Persian mathematician Abū Ja’far Muhammad ibn Mūsā al-Khwārizmī (800-867) who wrote the oldest known math book about using symbols to solve equations titled al-Kitīb al-mukhtasar fī hisāb al-jabr wa’l muqābala (The compendious book on calculation by completion and balancing).
● His work also named the latinized word Algebra from the arabic word al-jabr which means completion and is used as “add the same quantity to both sides of the equation”.
Wikipedia: Al-Khwarizmi.

A program has to perform correctly Algorithms effectiveness.
what it is supposed to do. That is the
However, if doing what is supposed to
do also requires the usage of limited resources, as time, memory, or even power consumption, this is a matter of efficiency, instead of effectiveness.
Effectiveness versus Efficiency We will study the efficiency of algorithms, thus try to compute how much it takes to execute an algorithm.
● What is an algorithm
● Algorithm examples
● Summations and Logarithms
CSC 6013 – Week 2

A program has to perform correctly Algorithms effectiveness.
what it is supposed to do. That is the
However, if doing what is supposed to
do also requires the usage of limited resources, as time, memory, or even power consumption, this is a matter of efficiency, instead of effectiveness.
Effectiveness versus Efficiency We will study the efficiency of algorithms, thus try to compute how much it takes to execute an algorithm.
● What is an algorithm
● Algorithm examples
● Summations and Logarithms
CSC 6013 – Week 2
Algorithms – Logarithms
If a number b power a number x is equal to n, then the logarithm of n base b is x.
● log10 (1000) = 3 (decimal or common log)
● log2 (1024) = 10 (binary log)
● log5 (15625) = 6 (logarithm base 5)
One can use this logarithm property to find logarithms of any base:
Numerically the Euler number e is comfortable to handle mathematical operations, thus the logarithm of base e is called the natural logarithm. However, in Computer Science the binary logarithm is far more useful.
Wikipedia: Logarithm.

Asymptotic Analysis
The effort for an algorithm applied to a problem of a given size.
An algorithm efficiency is measured in how much resources it needs when applied to a problem of a given size.
The resources can be the memory that will be necessary, or how much energy will be consumed, or even how much bandwidth it will require.
However, the more usual resource is time. We want to answer:
“how long will it take?”
● Counting tasks
● Examples
● The notations Big Oh, Big Omega, and Big Theta
CSC 6013 – Week 2

Asymptotic Analysis – The name
What Asymptotic means?
● According to the Cambridge dictionary:
○ An asymptotic line is a line that gets closer and closer to a curve as the distance gets closer to infinity.
● Practically speaking, we try to estimate how much it cost to run an algorithm;
○ We will focus now on the amount of time, thus the amount of effort to execute a series of operations, but similar analysis can be done for other measures.
● Our analysis will be asymptotic because we will try to approach the value of the effort curve as the problem grows, a.k.a., limiting behavior.
Wikipedia: Asymptotic analysis.
Asymptotic Analysis – The effort
The idea: count what matters when the problem is large
● Given an algorithm that receives an input of size n, we are looking for a function of n, T(n), that describes the amount of work done by the algorithm.
● Usually, we count the number of fundamental steps to be executed in the worst case scenario (maximum over the valid inputs of size n).
○ Thus, we are looking for an asymptotic upper bound, rather than an exact count of operations for cases when n is large enough.
● We want to estimate the effort needed as the algorithm is applied to an input as its size grows.
Text: Asymptotic Analysis.

Asymptotic Analysis
The effort for an algorithm applied to a problem of a given size.
An algorithm efficiency is measured in how much resources it needs when applied to a problem of a given size.
The resources can be the memory that will be necessary, or how much energy will be consumed, or even how much bandwidth it will require.
However, the more usual resource is time. We want to answer:
“how long will it take?”
● Counting tasks
● Examples
● The notations Big Oh, Big Omega, and Big Theta
CSC 6013 – Week 2

Asymptotic Analysis
Example 1 – Counting positive elements in an array
● The problem size (n) is the size of the array A;
● The worst case scenario is counting elements and they are all positive;
● Each line from 5 to 9 will have a cost (let’s call them c1 to c5) and it will be execute a certain number of times; ● The total effort would be:
○ T(n) = c1 + n c2+ n c3+ n c4+ c5
○ T(n) = c1 + c5 + n ( c2+ c3+ c4 )
○ T(n) = c6 + n c7
The cost T(n) is upper bounded by a function f(n).
○ T(n) <= n c6 + n c7 ○ T(n) <= n ( c6 + c7 )
○ T(n) <= n c8
As the problem size grows from n to 2n effort – T(2n) = 2 T(n).
Asymptotic Analysis
Example 2 – Elements Uniqueness
● The problem size (n) is the size of the array A;
● The worst case scenario is without two equal values
(both loops go through and line 8 is never executed);
● Each line from 5 to 9 will have a cost (c1 to c5) and it will be execute a certain number of times; ● The total effort would be:
○ T(n) = (n-1) c1 + ((n-1)n)/2 c2+ ((n-1)n)/2 c3+ 0 c4+ c5
○ T(n) <= n c1 + n2 ( c2+ c3 ) + c5
The cost T(n) is upper bounded by a function f(n2).
○ T(n) <= n c1 + n2 c6 + c5
○ T(n) <= n2 c1 + n2 c6 + n2 c5
○ T(n) <= n2 ( c1 + c6 + c5 )
○ T(n) <= n2 c7
As the problem size grows from n to 2n effort – T(2n) = 22 T(n).
Asymptotic Analysis
Example 3 – Number of digits in a binary number
● The problem size (n) is the entered number n;
● The worst case scenario is irrelevant as we always go until number n end up becoming 0 (no if command);
● Each line from 4 to 8 will have a cost (c1 to c5) and will be execute a certain number of times; ● The total effort would be:
○ T(n) = c1 + log2(n) c2+ log2(n) c3+ log2(n) c4+ c5
○ T(n) = c1 + c5 + log2(n) ( c2+ c3 + c4 )
The cost T(n) is upper bounded by a function f(log2 n).
○ T(n) = c6 + log2(n) c7
○ T(n) <= log2 (n) c6 + log2 (n) c7
○ T(n) <= log2 (n) ( c6 + c7 )
○ T(n) <= log2 (n) c8
As the problem size grows from n to 2n effort – T(2n) = log(2) + T(n).

Asymptotic Analysis
The effort for an algorithm applied to a problem of a given size.
An algorithm efficiency is measured in how much resources it needs when applied to a problem of a given size.
The resources can be the memory that will be necessary, or how much energy will be consumed, or even how much bandwidth it will require.
However, the more usual resource is time. We want to answer:
“how long will it take?”
● Counting tasks
● Examples
● The notations Big Oh, Big Omega, and Big Theta
CSC 6013 – Week 2

Asymptotic Analysis – Notations
Complexity of Time
The more commonly found form of asymptotic analysis is the complexity of time, which is basically the upper bound to the worst case scenario as we consider before. This is denoted usually by the Big Oh notation:
● The Big-Oh is a function that is an upper bound of the worst-case of the algorithm:
○ It safely states the longest the algorithm will take;
Practically speaking, an algorithm is in O(log n) means that this algorithm will require at most T(n) operations and T(n) <= c log n for all values of n above a certain (small) value.
Wikipedia: Big O notation.
Asymptotic Analysis – Big Oh
Practically speaking, an algorithm is in O(log n) means that this algorithm will require at most T(n) operations and T(n) <= c log n for all values of n above a certain (small) value.
For the examples seen:
● Example 1 – Counting positive numbers in an array
○ Has a time complexity O(n);
● Example 2 – Elements Uniqueness
○ Has a time complexity O(n2);
● Example 3 – Number of digits in a binary number
○ Has a time complexity O(log n);
It means that Example 3 will scale better than Example 1, and Example 2 will scale worst than Example 1.
Video: Big-O Notation.

Asymptotic Analysis – Big Oh
● The Big-Oh is a function that is an upper bound of the worst-case of the algorithm;
The slowest it can be ○ It safely states the longest the algorithm will take.
– upper bound ● Formally, if a function T(n) denotes the number of operations taken by a given algorithm, this function is said to be in O(g(n)) if T(n) is bounded above by some constant multiple of g(n) for all large value of n. In such way, we don’t really care about the actual values of the constants ci.
○ For example, an algorithm is in O(log n) means that this algorithm will require at most T(n) operations and T(n) <= c log n for all values of n above a certain (small) value.
Most of asymptotic analysis made is Big-Oh for time complexity.
Asymptotic Analysis – Big Omega
● The Big-Omega is a function that is a lower bound of the worst-case of the algorithm; The fastest it can be – ○ It safely states the shortest the algorithm will lower bound take.
● Formally, if a function T(n) denotes the number of operations taken by a given algorithm, this function is said to be in (g(n)) if T(n) is bounded below by some constant multiple of g(n) for all large n.
○ For example, an algorithm is in (log n) means that this algorithm will require at least T(n) operations and T(n) >= c log n for all values of n above a certain (small) value.
When we are not using
Big-Oh, Big Omega is employed.
Asymptotic Analysis – Big Theta
● The Big-Theta is a function that express both a lower and upper bound of the algorithm; What to expect – ○ Big-Theta summarizes Big-Oh and Big-Omega. upper and lower ● Formally, if a function T(n) denotes the number of bound enveloppe operations taken by a given algorithm, this function is
said to be in (g(n)) if T(n) is bounded above by some constant multiple of g(n) and bounded below by some constant multiple of g(n) for all large n.
○ For example, an algorithm is in (log n) means that this algorithm will require at least T(n) operations and T(n) >= c1 log n and at most T(n) operations and T(n) <= c2 log n for all values of n above a certain (small) value.
Sometimes there is no Big Theta.

Second Coding Project – P#2
1. Create a program that finds the number of entries in an array of Integers that are divisible by a given Integer. Your function should have two input parameters – an array of Integers and a positive Integer – and it should return an Integer indicating the count using a return statement.
2. Create a program that, given an array of Reals, without sorting the array, finds the smallest gap between all pairs of elements (for an array A, the absolute value of the difference between each pair of elements). Your function should have one input parameter – an array of Reals – and should return a number indicating the smallest gap using a return statement.
3. Create a program that, given an Integer n>1 and two nxn matrices A and B of Reals, find the product of the matrices. Your function should have three input parameters – an Integer n and two nxn matrices of numbers – and should return the nxn product matrix using a return statement.
More details in Canvas P#2 prompt.
Second Coding Project – P#2
For Program 1) you should execute the following test cases:
A. [20, 21, 25, 28, 33, 34, 35, 36, 41, 42] number of entries that are divisible by 7 B. [18, 54, 76, 81, 36, 48, 99] number of entries that are divisible by 9
For Program 2) you should execute the following test cases: A. [50, 120, 250, 100, 20, 300, 200]
B. [12.4, 45.9, 8.1, 79.8, -13.64, 5.09]
For Program 3) you should execute the following test cases: A.
B.
To all programs you have to submit the code (.py file) and a .pdf with the test cases output.
Second Coding Project – P#2
If you are not familiar with matrix multiplication, you might the following internet resources helpful.
The definition of matrix multiplication from Wikipedia:
https://en.wikipedia.org/wiki/Matrix_multiplication A simpler definition of matrix multiplication:
https://www.mathsisfun.com/algebra/matrix-multiplying.html Two videos of matrix multiplication:
Video #1: https://youtu.be/sYlOjyPyX3g Video #2: https://youtu.be/n8ICyS8CKIQ
Your task:
Second Quiz – Q#2
● The second quiz in this course covers the topics of Week 2;
● The quiz will be available this Friday, and it is composed by 10 questions;
● The quiz should be taken on Canvas (Module 2), and it is not a timed quiz:
○ You can take as long as you want to answer it (a quiz taken in less than one hour is usually a too short time);
● The quiz is open book, open notes, and you can even use any language Interpreter to answer it;
● Yet, the quiz is evaluated and you are allowed to submit it only once.
Your task: