On completion of this module the learner will/should be able to

1. Apply structured methodologies to problem solving in computing.
2. Design algorithms to solve computational problems.
3. Critically evaluate and assess the performance of algorithms.
4. Translate real-world problems into computational problems

• Introduction to Computational Thinking and Algorithms
• Analysis of Algorithms
• Designing and Testing Algorithms
• Sorting Algorithms
• Searching Algorithms
• Graph Algorithms
• Critique and Evaluation of Real World Implementations

• Dictionary of Algorithms and Data Structures: https://xlinux.nist.gov/dads/

• What on Earth is Recursion? Computerphile, 2014. https://www.youtube.com/watch?v=Mv9NEXX1VHc
• Programming Loops vs Recursion. Computerphile, 2017. https://www.youtube.com/watch?v=HXNhEYqFo0o
• XoaX.net Video tutorials on Algorithms, covering Complexity, Sorting and Searching. http://xoax.net/comp_sci/crs/algorithms/index.php
• Visualization of 24 sorting algorithms in 2 minutes. Viktor Bohush, 2016. https://www.youtube.com/watch?v=BeoCbJPuvSE

• Harel D. and Feldman Y. (2012). Algorithmics - The Spirit of Computing (3rd Edition). Springer.
• Pollice G., Selkow S. and Heineman G. (2016). Algorithms in a Nutshell, 2nd Edition. O' Reilly.
• Goodrich M.T. and Tamassia R. (2014). Data Structures and Algorithms in Java (6th edition). John Wiley & Sons Inc.
• Cormen T.H. (2013). Algorithms Unlocked. MIT Press.
• Cormen T.H., Leiserson C.E., Rivest R.L. and Stein C. (2009). Introduction to Algorithms (3rd Edition). MIT Press.
• MacCormick J. (2013). Nine Algorithms That Changed the Future: The Ingenious Ideas That Drive Today's Computers. Princeton University Press.

• The Secret Rules of Modern Living: Algorithms. BBC Four, first broadcast on September 24 2015.
• The Wall Street Code. vpro backlight, 2013. https://www.youtube.com/watch?v=kFQJNeQDDHA

• Furia C. A., Meyer B. and Velder S. (2014). Loop invariants: analysis, classification, and examples. ACM Computing Surveys. vol. 46, no. 3. http://se.ethz.ch/~meyer/publications/methodology/invariants.pdf

01 Intrduction

:02 Review of Programming and Mathematical Concepts

• Brackets
• exponents (power)
• Multiplication (multiplication and division and remainder)
• Division
• Addition
• Subtraction

indicate that a quantity is to be multiplies by itself some number of times

A variable is simply a storage location and associated name which can use to store some information for later use

Type of variables

• Integer
• floating
• string

• Numeric data
  • integers (whole numbers) e.g 1, 3, -123
  • floating point, i.e real numbers e.g 2.12, 32.23
• Character data
  • !, 4, K, abababa
  • string data type
  • enclosed in quotes, e.g “the quick brown fox”
• Boolena: true or false

• Programming languages are often classified as being either strongly typed or weakly typed
• strongly types languages will generate an error or refuse to compile if the argument passed to a function does not closely match the expected type
• weak typed languages may produce unpredicted results or may perform implicit type conversion if the argument passed to a function does not match the expected type.

• A function is a block of code designed to perform a particular task
• A function is executed when “something” invokes it (calls it)

• sequential
• selection
• Iteration

• Unordered List Itemstatements are executed line by line in the order the appear

• allows different blocks of code to be executed based on some condition
• Examples: if, if/else if/else, switch

• repeatedly execute a series of statements as long as the condition stated in parenthesis is true
• for loops, while loops, do/while loops

array
list
cars = [“Ford”, “Volvo”, “BMW”]

03 Analysing Algorithms Part 1

• Features of an algorithm
• Algorithmic efficiency
• Performance & complexity
• Orders of magnitude & complexity
• Best, average & worst cases

• An algorithm is a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer (Oxford English Dictionary)
• Algorithms can be thought of like a “recipe” or set of instructions to be followed to achieve the desired outcome
• Many different algorithms could be designed to achieve a similar task
  • What criteria should we take into account?
  • How should we compare different algorithms, and decide which is most appropriate for our use case?

• Input: An algorithm has zero or more well-defined inputs, i.e data which are given to it initially before the algorithm begins
• Output: An algorithm has one or more well-defined outputs i.e data which is produced after the algorithm has completed its task
• Finiteness: An algorithm must always terminate after a finite number of steps
• Unambiguous: Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case
• Correctness: The algorithm should consistently provide a correct solution (or a solution which is within an acceptable margin of error)
• Feasibility: It should be feasible to execute the algorithm using the available computational resources
• Efficiency: The algorithm should complete its task in an acceptable amount of time

• Different algorithms have varying space and time efficiency
  • E.g. there are several commonly used sorting algorithms, each with varying levels of efficiency
  • All algorithms are not created equal!
• Time efficiency considers the time or number of operations required for the computer takes to run a program (or algorithm in our case)
• Space efficiency considers the amount of memory or storage the computer needs to run a program/algorithm
• In this module we will focus on time efficiency

• There are two options for analysing algorithmic efficiency:
  • A priori analysis – Evaluating efficiency from a theoretical perspective. This type of analysis removes the effect of implementation details (e.g. processor/system architecture). The relative efficiency of algorithms is analysed by comparing their order of growth. Measure of complexity.
  • A posteriori analysis – Evaluating efficiency empirically. Algorithms which are to be compared are implemented and run on a target platform. The relative efficiency of algorithms is analysed by comparing actual measurements collected during experimentation. Measure of performance.

• In general, complexity measures an algorithm’s efficiency with respect to internal factors, such as the time needed to run an algorithm
• External Factors (not related to complexity):
  • Size of the input of the algorithm
  • Speed of the computer
  • Quality of the compiler

It is important to differentiate between:

• Performance: how much time/memory/disk/… is actually used when a program is run. This depends on the computer, compiler, etc. as well as the code
• Complexity: how do the resource requirements of a program or algorithm scale, i.e., what happens as the size of the problem being solved or input dataset gets larger?

Note that complexity affects performance but not the other way around

• Note that algorithms are platform independent
• i.e. any algorithm can be implemented in an arbitrary programming language on an arbitrary computer running an arbitrary operating system
• Therefore, empirical comparisons of algorithm complexity are of limited use if we wish to draw general conclusions about the relative performance of different algorithms, as the results obtained are highly dependent on the specific platform which is used
• We need a way to compare the complexity of algorithms that is also platform independent
• Can analyse complexity mathematically

• We can compare algorithms by evaluating their running time complexity on input data of size n
• Standard methodology developed over the past half-century for comparing algorithms
• Can determine which algorithms scale well to solve problems of a nontrivial size, by evaluating the complexity the algorithm in relation to the size n of the provided input
• Typically, algorithmic complexity falls into one of a number families (i.e. the growth in its execution time with respect to increasing input size n is of a certain order)
• Memory or storage requirements of an algorithm could also be evaluated in this manner

• We will use the following classifications for order of growth (listed by decreasing efficiency, with the most efficient at the top):
  • Constant
  • Logarithmic ( log(𝑛) )
  • Sublinear • Linear (𝑛)
  • 𝑛 log(𝑛)
  • Polynomial (e.g. 𝑛2, 𝑛3, 𝑛4, etc.)
  • Exponential

• When evaluating the complexity of an algorithm, keep in mind that you must identify the most expensive computation within an algorithm to determine its classification
• For example, consider an algorithm that is subdivided into two tasks, a task classified as linear followed by a task classified as quadratic. The overall performance of the algorithm must therefore be classified as quadratic

• As well as the size n of the input, the characteristics of the data in the input set may also have an effect on the time which an algorithm takes to run
• There could be many, many instances of size n which would be valid as input; it may be possible to group these instances into classes with broadly similar features
• Some algorithm “A” may be most efficient overall when solving a given problem. However, it is possible that another algorithm “B” may in fact outperform “A” when solving particular instances of the same problem
• The conclusion to draw is that for many problems, no single algorithm exists which is optimal for every possible input
• Therefore, choosing an algorithm depends on understanding the problem being solved and the underlying probability distribution of the instances likely to be treated, as well as the behaviour of the algorithms being considered.

• Worst case: Defines a class of input instances for which an algorithm exhibits its worst runtime behaviour. Instead of trying to identify the specific input, algorithm designers typically describe properties of the input that prevent an algorithm from running efficiently.
• Average case: Defines the expected behaviour when executing the algorithm on random input instances. While some input problems will require greater time to complete because of some special cases, the vast majority of input problems will not. This measure describes the expectation an average user of the algorithm should have.
• Best case: Defines a class of input instances for which an algorithm exhibits its best runtime behaviour. For these input instances, the algorithm does the least work. In reality, the best case rarely occurs.

Analysing Algorithms Part 2

• Review of key concepts
  • Complexity
  • Orders of growth
  • Best, average & worst cases
• Asymptotic notation
  • O (Big O)
  • Ω (omega)
  • Θ (theta)
• Evaluating complexity
• Examples

• Complexity measures the efficiency of an algorithm’s design, eliminating the effects of platform-specific implementation details (e.g. CPU or complier design)
• We can compare the relative efficiency of algorithms by evaluating their running time complexity on input data of size n (memory or storage requirements of an algorithm could also be evaluated in this manner)
• E.g. how much longer will an algorithm take to execute if we input a list of 1000 elements instead of 10 elements?
• Standard methodology developed over the past half-century for comparing algorithms
• Can determine which algorithms scale well to solve problems of a nontrivial size, by evaluating the complexity the algorithm in relation to the size n of the provided input
• Typically, algorithmic complexity falls into one of a number families (i.e. the growth in its execution time with respect to increasing input size n is of a certain order). The effect of higher order growth functions becomes more significant as the size n of the input set is increased

• As well as the size n of the input, the actual data that is input may also have an effect on the time which an algorithm takes to run
• There could be many, many instances of size n which would be valid as input; it may be possible to group these instances into classes with broadly similar features
• For many problems, no single algorithm exists which is optimal for every possible input instance
• Therefore, choosing an algorithm depends on understanding the problem being solved and the underlying probability distribution of the instances likely to be encountered, as well as the behaviour of the algorithms being considered
• By knowing the performance of an algorithm under each of these cases, you can judge whether an algorithm is appropriate to use in your specific situation

• Worst case: Defines a class of input instances for which an algorithm exhibits its worst runtime behaviour. Instead of trying to identify the specific input, algorithm designers typically describe properties of the input that prevent an algorithm from running efficiently.
• Average case: Defines the expected behaviour when executing the algorithm on random input instances. While some input problems will require greater time to complete because of some special cases, the vast majority of input problems will not. This measure describes the expectation an average user of the algorithm should have.
• Best case: Defines a class of input instances for which an algorithm exhibits its best runtime behaviour. For these input instances, the algorithm does the least work. In reality, the best case rarely occurs.

• For any particular value of n, the number of operations or work done by an algorithm may vary dramatically over all the instances of size n
• For a given algorithm and a given value n, the worst-case execution time is the maximum execution time, where the maximum is taken over all instances of size n
• We are interested in the worst-case behaviour of an algorithm because it often is the easiest case to analyse
• It also explains how slow the program could be in any situation, and provides a lower bound on possible performance
• Good idea to consider worst case if guarantees are required for the maximum possible running time for a given n
• Not possible to find every worst-case input instance, but sample (near) worst-case instances can be crafted given the algorithm’s description

• Big O notation (with a capital latin letter O, not a zero) is a symbolism used in complexity theory, mathematics and computer science to describe the asymptotic behaviours of functions
• In short, Big O notation measures how quickly a function grows or declines
• Also called Landau’s symbol, after the German number theoretician Edmund Landau who invented the notation
• The growth rate of a function is also called its order
• The capitalised greek letter “omicron” was originally used; this has fallen out of favour and the capitalised latin letter “O” is now commonly used
• Example use: Algoroithm X runs in 𝑂(𝑛2) time
• Big O notation is used in computer science to describe the complexity of an algorithm in the worst-case scenario
• Can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm
• Big O notation can be thought of as a measure of the expected “efficiency” of an algorithm (note that for small sizes of n, all algorithms are efficient, i.e. fast enough to be used for real time applications)
• When evaluating the complexity of algorithms, we can say that if their Big O notations are similar, their complexity in terms of time/space requirements is similar (in the worst case)
• And if algorithm A has a less complex Big O notation than algorithm B, we can infer that it is much more efficient in terms of space/time requirements (at least in the worst case)

Suppose 𝑓(𝑥) and 𝑔(𝑥) are two functions defined on some subset of the set of real numbers

<m 18>f(x)=O(g(x)) for x right infinity</m>

if and only if there exist constants 𝑁 and 𝐶 such that

<m 18>delim{|}{f(x)}{|}⇐C delim{|}{g(x)}{|} for x all x > N</m>

Intuitively, this means that 𝑓 does not grow more quickly than 𝑔

(Note that N is size of the input set which is large enough for the higher order term to begin to dominate)

• Note that when using Big O notation, we aim to identify the tightest upper bound possible
• An algorithm that is 𝑂(𝑛2) is also 𝑂(𝑛3) , but the former information is more useful
• Specifying an upper bound which is higher than necessary is like saying: “This task will take at most one week to complete”, when the true maximum time to complete the task is in fact five minutes!

• We can use Ω (omega) notation to describe the complexity of an algorithm in the best case
• Best case may not occur often, but still useful to analyse
• Represents the lower bound on the number of possible operations
• E.g. an algorithm which is Ω 𝑛 exhibits a linear growth in execution time in the best case, as n is increased

• Finally, Θ (theta) notation is used to specify that the running time of an algorithm is no greater or less than a certain order
• E.g. we say that an algorithm is Θ(𝑛) if it is both O(𝑛) and Ω 𝑛 , i.e. the growth of its execution time is no better or worse than the order specified (linear in this case)
• The actual functions which describe the upper and lower limits do not need to be the exact same in this case, just of the same order

• Two concepts:
  • The input data size 𝑛, or the number of individual data items in a single data instance to be processed
  • The number of elementary operations 𝑓(𝑛) taken by an algorithm, or its running time
• For simplicity, we assume that all elementary operations take the same amount of “time” to execute (not true in practice due to architecture, cache vs. RAM vs. swap/disk access times etc.)
• E.g. an addition, multiplication, division, accessing an array element are all assumed to take the same amount of time
• Basis of the RAM (Random Access Machine) model of computation
• The running time T n of an implementation is: <m>T(n)=c*f(n)</m>
  • 𝑓(𝑛) refers to the fact that the running time is a function of the size n of the input dataset
  • 𝑐 is some constant
  • The constant factor 𝑐 can rarely be determined and depends on the specific computer, operating system, language, compiler, etc. that is used for the program implementation

• When evaluating the complexity of an algorithm, keep in mind that you must identify the most expensive computation within an algorithm to determine its classification
• For example, consider an algorithm that is subdivided into two tasks, a task classified as linear followed by a task classified as quadratic.
  • Say the number of operations/execution time is:
  • <m>T(n)=50+125n+5n^2</m>
  • The overall complexity of the algorithm must therefore be classified as quadratic, we can disregard all lower order terms as the <m>n^2</m> term will become dominant for input sizes of 𝑛=6 or above
• An algorithm with better asymptotic growth will eventually execute faster than one with worse asymptotic growth, regardless of the actual constants
• The actual breakpoint will differ based on the constants and size of the input, but it exists and can be empirically evaluated
• During asymptotic analysis we only need to be concerned with the fastest-growing term of the T(n) function. For this reason, if the number of operations for an algorithm can be computed as <m 13>T(n)=c*n^3+d*n log(n)</m>, we would classify this algorithm as <m 13>O(n^3)</m> because that is the dominant term which grows far more rapidly than <m 13>n log(n)</m>

• If we want to pass multiple values to a method, the easiest way to do this is to pass in an array
  • E.g. an array of numbers to be sorted

// passing an array of integers into a method in Java 
void myMethod(int[] elements) {
    // do something with the data here 
}

def my_function(elements):
    # do something with the data here
 
test 1 = [5, 1, 12, -5, 16]
my_function(test1)

Array with 5 elements: <m 30>tabular{11}{111111}{5 1 12 {-5} 16}</m>

• O(1) describes an algorithm that will always execute in the same time (or space) regardless of the size of the input data set
• Consider the Java code sample to the right
• No matter how many elements are in the array, this method will execute in constant time
• This method executes in constant time in the best, worst and average cases

boolean isFirstElementTwo(int[] elements) 
{
    if(elements[0] == 2) { 
        return true; 
    } 
    else { 
        return false; 
    } 
}

# O(1) Example
def is_first_el_two(elements):
    if elemenents[0] == 2:
        return True
    return False
 
test1 = [2, 1, 0, 3]
test2 = [0, 2, 3, 4]
 
print(is_first_el_two(test1))  # prints True
print(is_first_el_two(test1))  # prints False

• Consider the code samples
• The worst possible time complexity depends linearly on the number of elements in the array
• Execution time for this method is constant in the best case

boolean containsOne(int[] elements) { 
    for (int i=0; i<elements.size(); i++){ 
        if(elements[i] == 1) { 
            return true; 
        } 
    } 
    return false; 
}

# O(n) Example
def contains_one(elements)
    for i in range(0, len(elements)):
        if elements[i] == 1:
            return True
    return False
 
test1 = [0, 2, 1, 2]
test2 = [0, 2, 3, 4]
 
print(contains_one(test1))  # prints True
print(contains_one(test1))  # prints False

• <m>O(n^2)</m> represents an algorithm whose worst case performance is directly proportional to the square of the size of the input data set
• This class of complexity is common with algorithms that involve nested iterations over the input data set (e.g. nested for loops)
• Deeper nested iterations will result in higher orders e.g. <m>O(n^3), O(n^4)</m>, etc.

• Consider the code samples below
• The worst execution time depends on the square of the number of elements in the array
• Execution time for this method is constant in the best case

boolean containsDuplicates(int[] elements) 
{ 
  for (int i=0; i<elements.length; i++){ 
    for (int j=0; j<elements.length; j++){ 
      if(i == j){ // avoid self comparison continue; 
      } 
      if(elements[i] == elements[j]) { 
        return true; // duplicate found 
      } 
    } 
  } 
  return false; 
}

# O(n^2) Example
def contains_duplicates(elements):
  for i in range (0, len(elements)):
    for j in range(0, len(elements)):
      if i == j: ##avoid self comparison
        continue
      if elements[i] == elements[j]:
        return True # duplicate found
  return False
 
test1 = [0, 2, 1, 2]
test2 = [1, 2, 3, 4]
 
print(contains_duplicates(test1))  # prints True
print(contains_duplicates(test2))  # prints False

05_recursive_algorithms_part_1.pdf

The video and the code is a very condensed summary of the following section and not part of the syllabus, you can skip to Iteration and recursion

Socratica - Recursion, the Fibonacci Sequence and Memoization

memoization.py

from functools import lru_cache
 
#@lru_cache(maxsize=1000)
def fibonacci(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    elif n > 2:
        return fibonacci(n-1) + fibonacci(n-2)
 
for n in range(1, 1001):
    print(n, ":", fibonacci(n))

• Iteration and recursion
• Recursion traces
• Stacks and recursion
• Types of recursion
• Rules for designing recursive algorithms

• For tasks that must be repeated, up until now we have considered iterative approaches only
• Recap: iteration allows some sequence of steps (or block of code) to be executed repeatedly, e.g using a loop or a while loop
• Recursion is another technique which may be applied to complete tasks which are repetitive in nature

• “Normally”, procedures (or methods) call other procedures
  • e.g the main() procedure calls the alpha() procedure
• A recursive procedure is one which calls itself
  • e.g the beta() procedure contains a call to beta()

• you can see that the count method calls itself
• this program would output the values 0 1 2 to the console if run

void main(){
	count(0);
}
 
void count(int index){
	print(index);
	if(index <2){
		count(index+1);
	}
}

def count(index):
  print(index)
  if index < 2:
    count(index + 1)
 
count(0)    # outputs 0 1 2 

• A program stack basically operates like a continuer of trays in a cafeteria. It has only two operations:
  • Push: push something onto the stack
  • Pop: pop something off the top of the stack
• When the method returns or exits, the method’s activation frame is popped off the stack
• Each time a method is invoked, the method’s activation frame (record) is placed on top of the program stack.

• with the technique of recursion, a problem may be solved bye solving smaller instances of the same problem
• Some problems are more easily solved by using a recursive approach
• E.g
  • Traversing through directories of a file system
  • Traversing through a tree of search results
  • some sorting algorithms are recursive in nature
• Recursion often leads to cleaner and more concise code which is easier to understand

• Note: any set of tasks which may be accomplished using a recursive procedure may also be accomplished by using an iterative procedure
• Recursion is “expensive”. The expense of recursion lies in the fact that we have multiple activation frames and the fact that there is overhead involved with calling a method.
• If both of the above statements are true, why would we ever use recursion?
• In many cases, the extra “expense” of recursion is far outweighed by a simpler, clearer algorithm which leads to an implementation that is easier to code.
• Ultimately, the recursion is eliminated when the complier creates assembly language (it does this by implementing the stack)
• If the recursion tree has a simple form, the iterative version may be better
• If the recursion tree appears quite “bushy”, with very few duplicate tasks, then recursion is likely the natural solution

• Linear recursion: the method makes a single call to itself
• Tail recursion: the method makes a single call to itself, as the last operations
• Binary recursion: the method makes 2 calls to itself
• Exponential recursion: the method makes more than two calls to itself

• Tail recustioon is when the last operation in a method is a single recursive call.
• Each time a method is invoked, the method’s activation frame(record) is placed on top of the program stack.
• In this case, there are multiple active stack frames which are unnecessary because they have finished their work.
• Can be expensive and inefficient, so use carefully!

• infinite recursion occurs when a recursion method does not have a base case
• consider the method to the right:
  • If we call infinite(1), the next call will be infinite(0), then the infinite(-1), then infinite(-2) etc..
  • This method will keep making recursive calls to itself until a StackOverflowError occurs (recursive calls have taken up all available memory)

void infinite(int x){
	infinite(x-1);
}

def infinite(x):
  infinite(x-1)
 
infinite(1)
# RecusrionError:
# maximimum recursion depth exceeded

• Circular recursion occurs when recursive calls stop making progress towards the base case
• Conside this method
  • if we call circular(1), the next call will be circular(2), then the circular(1), then circular(2) etc..
  • As with the infinite recursion example, this method will keep making recursive calls to itself until a stack overflow error occurs (recursive calls have taken up all available memory)

void circular(int x){
	if(x==1){
	  circular(x+1);
	}
	circular(x-1);
}

def circular(x):
  if x ==1:
    circilar(x + 1)
  circular(x - 1)
 
circilar(1)    # RecursioError:
# maximum recusrion depth exceeded
# in comparison

1. Base case: a recursive algorithm must always have a base case which can be solved without recursion. Methods without a base case will results in infinite recursion when run.
2. Making progress: for cases that are to be solved recursively, the next recursive call must be a case that makes progress towards the base case. Methods that do not make progress towards the base case will results in circular recursion when run.
3. Design rule: Assume that all the recursive calls work.
4. Compound interest rule: Never duplicate work by solving the same instance of a problem in separate calls.

• Think about the task which you wish to accomplish, and try to identify any recurring patterns, e.g. similar operations that must be conducted, like traversing through nested directories on a file system
• Divide the problem up using these recurring operations
• Then
  • Identify cases you know can be solved without recursion (base cases). Avoid ending with a multitude of special cases; rather, try to identity a simple base case
  • invoke a new copy of the method within each recursion step
  • each recursion step resembles the original, larger problem
  • Make progress towards the base case(s) with each successive recursive step/call

• A recursive method is one which calls itself within its method body
• Recursion allows us to solve a problem, by breaking it up into smaller instances of the same problem
• Recursive methods must always have a base case which may be solved without recursion
• In the next lecture we will consider some example problems which may be solved using recursion

• Review of recursion
• Sample recursive algorithms
  • Factorials
  • Greatest common divisor
  • Fibonacci series

• “Normally”, procedures (or methods) call other procedures
  • e.g the main() procedure calls the alpha() procedure
• A recursive procedure is one which calls itself
  • e.g the beta() procedure contains a call to beta()

1. Base case: a recursive algorithm must always have a base case which can be solved without recursion. Methods without a base case will result in infinite recursion when run.
2. Making progress: for cases that are to be solved recursively, the next recursive call must be a case that makes progress towards the base case. Methods that do not make progress towards the base case will result in circular recursion when run.
3. Design rule: assume that all the recursive call work
4. Compound interest rule: Never duplicate work by solving the same instance of a problem in separate recursive calls.

• The factorial of a non-negative integer n may be computed as the product of all positive integers which are less than or equal to n
• This is denoted by n!
• in general : n! = n * (n-1)* (n-2)*(n-3)*….*1
• The above is essentially an algorithm which may be implemented and used to calculate the factorial of any n >0
• Note: the value of 0! is defined as 1 ( i.e 0! = 1 following the empty product convention), The input n=0 will serve as the base case in our recursive implementation
• Factorial operations are commonly used in many areas of mathematics, e.g combinatorics, algebra, computation of functions such as sin and cos, and the binomial theorem.
• One of its most basic occurrences is the fact that there are n! ways to arrange distinct objects into a sequence
• In general: n! = n *(n - 1)*(n-2)*(n-3)*..*1
• Example factorial calculation: 5! = 5*4*3*2*1 = 120

def factorial(n):
	answer = 1
	while n > 1:
		answer *= n
		n -=1
	return answer
 
print(factorial(5))
#prints 120

def factorial_rec(n):
	if n <1:
		return 1
	else: 
		return n*factorial_rec(n-1)
 
print(factorial_rec(5))
#print 120

• The greatest common divisor (gcd) of two integer is the largest positive integer which divides into both numbers without leaving a remainder
• e.g the gcd of 30 and 35 is 5
• Euclid’s algorithm (c. 300 BC) may be used to determine the gcd of two integers
• Example application: finding the largest square tile which can be used to cover the floor of a room without using partial/cut tile

def euclid(a, b):
	while b != 0:
		temp = b
		b = a% b
		a = temp
	return a
 
print(euclid(35, 49))
# print 7

def euclid (a, b):
	if b == 0:
		return a
	else:
		return euclid(b, a%b)
print(euclid(35, 49))
# prints 7

• 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610
• the Fibonacci series crops up very often in nature and can be used to model the growth rate of organisms
• e.g leaf arrangements in plants, numbers of petals on a flower, the bracts of a pinecone, the scales of pineapple, shells, proportions of the human body
• The fibonacci series is named after the Italian mathematician Leonardo of Pisa, who was also known as Fibonacci
• His book Liber Abaci (published 1202) introduced the sequence to western world (Indian mathematicians knew about this sequence previously).
• We will use the convention that zero is included in the series and assigned to index 1
• if fib(n) is a method that returns the nth number in the series, then: fib(1)=0, fib(2)=1, fib(3)=1, fib(4)=2, fib(5)=3, fib(6)=5, fib(7)=8, etc…
• In general, fib(n) = fib(n-1) +fib(n-2)
• The results for fib(1) and fib(2) do not conform to this rule; therefore they will serve as base cases in our recursive implementation

def fib(n):
	i, n1, n2 =1, 0, 1
	while i <n:
		temp =n1
		n1 = n2
		n2 =n1 +temp
		i = 1+ i
	return n1
 
print(fib(5))
#prints 3

def fib(n):
	if n==1:
		return 0
	elif n ==2:
		return 1
	return fib(n-1) +fib(n-2)
 
print(fib(5))
#prints 3

07_algorithms_cryptography_ssl_2019_part1.pdf

• Crytography (terms and definitions)
• Types of cry–systems (symmetric and asymmetric)
• Examples of systems in practice

• Cryptography is the science of secrecy and is concerned with the need to communicate in secure, private and reliable ways
• From a computational thinking/algorithmics perspective, a novel feature is the fact (as we will see ) that modern methods used to solve cryptographic problems exploit the difficulty of solving other problems.

This is somewhat surprising…..

problems for which no good algorithms are known are crucial here.

• The basic problem to be solved is that of encrypting and decrypting data.
  • How should we encode an important message in such a way that the receiver should be able to decipher it, but not an eavesdropper?
  • Moreover, can then message be signed by the sender so that:
    1. The receiver can be sure that only the sender could have sent it.
    2. The sender cannot later deny having sent it
    3. The receiver, having received the signed message, cannot sign a message in the sender name, not even additional versions of the very message that has just been received.

• Data that can be read and understood without any special measure is called plaintext(or clear text). Plaintext, P, is the input to an encryption process(algorithm).
• Encryption is the process of disguising plaintext in such a way as to hide its substance.
• The result (output..) of the encryption process is ciphertext, C

A general encryption procedure(left ) and decryption procedure (right) is as follows:

<m 20>C = Encr(P)</m> and <m 20>P = Decr(C)</m>

• In conventional cryptography, also called secret-key or symmetric-key encryption, one key is used both for encryption and decryption
  • EG. The data Encryption Standard (DES) cryptosystem

Substitution Cipher

• The Caesar cipher shifted the alphabet by 3 characters

• Caesar cipher is a one to one mapping. A mono alphabetic substitution!
• Cryptanalysis exploits statistical properties of the English language.
• “E” is the most frequently occurring letter

So from example above, this kind of cypher is easily broken…

Polyalphabetic substitution:

• The key is a simple phrase of fixed length(which can repeat).
• Add the value of the letter in the key to the value of the letter inthe plaintext to ciphertext, and “wrap around” if necessary (modulo 36)

• This is essentially multiple Caesar-type ciphers
• Main advantage is that same plaintext get mapped onto different cipher-text.

Polyalphabetic substitution continued

• This is essentially multiple Caesar-type ciphers
• Main advantage is that same plaintext get mapped onto different ciphertext

• The strength of a cryptosystem is a function of:
  • The strength of the algorithm
  • The length (or size) of the key

• The assumption is that the general method of encryption (i.e the algorithm is known), and the security of the system lies in the secrecy of the key.
  • eg: General idea of a combination pad lock is known, strength is in secret combination.
• The larger the key, the higher the work factor for the cryptanalyst.
• A brute-force attack means trying all possible key values.

• In our earlier example, we had a phrase as our key to unlocking the secret message:

…and each letter of the phrase could take on 1 of 26 possible numeric values.

Ours are (t =20, h= 8 etc…)

As we had 10 characters in our phrase, and each character could be any 1 of 26 possible values, our potential key space is <m>26^10</m> i.e there are 141,167,095,653,376 possible keys or “phrases”.

• Let's think of key as multiples of bits or bytes in a computer system
• If a key is 8 bits long, then there are 2^8 = 256 possible keys
• A key that is 56-bits long has 2^56 possible key values. A very large number!
  • *72,057,594,927,936 possible values in fact! * If a computer could try one million keys per second, it would take over 2000 years to try all key values.*
• 72, 057, 594, 927, 936 possible values @1,0000,000
• 72,057,594,037,927,936/1,000,000 = 72057594037 seconds required to test all values
• 72057594037/60 = 1,200,959,900 minutes required to test all values
• 1,200,959,900/60 = 20,015,998.33 hours required to test all values
• 20,015,998.33/24 = 833,999.93 days required to test all values/365 = 2,284 YEARS
• If a 64-bit key were used, it would take 600,000 years to try all possible key values (at a test rate 1 million keys per second)
• For a 128-bit key, it would take 10^25 years. The universe is only 10^10 years old.
• When trying a brute force attack need to consider:
  • Number of keys to be tested
  • The speed of each test

• Consider our problem statement from earlier (which outlined what our desired solution should solve)

• Does not address the signature issue…
  • Receiver could make up fake messages?
  • Sender could deny having sent authentic messages
• Another major drawback (particularly in a distributed environment like the internet) is the issue of key distribution and management
• Symmetric systems require parties to cooperate in the generation an distribution of key pairs. Not scalable (even where it might be “culturally” feasible)

• Ciphers have improved significantly in terms of complexity since the days of Caesar. However….
• As noted, a big issue with symmetric cryptographic systems is that of Key management; specifically with respect to transferring keys.
• How do the sender and receiver agree on the same key?
• split the key into several parts?
• Other…?

• The problems of key distribution are solved by public key cryptography
• Public key cryptography is an asymmetric scheme that uses a pair of keys for encryption: a public key, which encrypts data, and a corresponding private, or secret key for decryption.
• You publish you public key to the world while keeping your private key secret. Anyone with a copy of your public key can then encrypt information that only you can read.
• Crucially, it is computationally infeasible to deduce the private key from the public key

• The primary benefit of public key crptograohy is that it allows people who have no pre-existing security arrangement to exchange messages securely.

• The need for sender and receiver to share secret keys via some secure channel is eliminated; all communications involve only public keys, and no private key is ever transmitted or shared.

Prime number: A number is prime if it is greater than 1 and if its only factors are itself and 1.

• 1 is not prime (1 is not greater than 1)
• 2 is prime (the only even prime)
• 3 is prime
• 4 is not prime (no other even number - except 2 - is prime)…4 *1, 2*2
• 5 is prime (but being odd does not necessarily make you prime)
• 6 is not prime 6*1, 3*2
• 8 is not prime…8*1, 2*4
• 9 is not prime (but it is odd)…9*1, 3*3

• First published in 1978 (and still secure) (researchers: Ron Rivet, Adi Shamir, Len Adleman)
• A block ciphering scheme, where the plaintext and cipher-text are integers between 0 and -1, for some value n.

Format

A block of plaintext(message), M, gets transformed into a cipher block C

• Both sender and receiver know the value of n (public)
• sender/everyone knows the value of e (public)
• Receiver only knows the value of d (Private)

Requirements:

• Suppose I wish to send my access number securely across an “open” network.

e.g. PIN = 2345

• I don't want my account to be hacked; neither does my employer!
• My employer implements a security system (based on the RSA algorithm, for instance) and tells me (and everyone else)….

• An “attacker” listening in on the connection might capture your encrypted PIN (i.e they could discover 29,9,16,14)
• Furthermore they would know that this is the output of the known RSA algorithm (C = P^e mod n)
• …They would know that e=7 and that n = 33 as these are publicly available)
• But… they won't be able to figure out P (the plaintext) in a reasonable amount of time

• Can only be done (in a reasonable amount of time) if you know the private/secret, d
• d is not publicly available and is jealously guarded by the owner.
• Decryption is straightforward if you know the value of d.

• Raising the ciphertext to the power of d, modulo n, will give you back the plaintext.

• Note that a knowledges of the encryption algorithm, a knowledge of the encryption key and a copy of the ciphertext is not sufficient to get back the plaintext (in a reasonable amount of time)
• You must also know the value of d, the private key.
• The beauty of RSA is that the encryption key and process can be made public without compromising the security of the system. This solves the “Key distribution” problem outlined earlier.

• Future session to look at RSA in more detail including some of the underpinnings of the algorithm.
• Authentication and signatures using RSA
• Secure Sockets Layer(SSL) Algorithm
• RSA performance
• Attacking RSA

• Contribute to the discussion forum on Moodle/LearnOnline
• Further reading in this area