History and Philosophy of Computing On algorithms
Exercise 1 What are the essential elements for a process to qualify as an algorithm?
Exercise 2 Present a small program in any language of your liking to perform a simple arithmetical operation on numbers. Explain how that program qualifies as the implementation of an algorithm.
Exercise 3 Consider the following algorithm:
def find _max (L) :
max = 0
for x in L :
if x > max:
max = x
return max
and answer and comment to the following questions:
- What does this algorithm do on an empty list?
- What if we make L to be the set of natural numbers N?
- Does each step of the algorithm consist of primitive operations?
- Does it have defined inputs and outputs?
- Is it effective (in the sense of producing the correct result)?
- Is it guaranteed to terminate? And for L = N?
Exercise 4 Explain the association between the computability of a function and the decidability of a predicate. Provide a simple example.
Exercise 5 Can you tell what the difference is between the previous and the following algorithm:
def find_max (L) :
if len ( L ) == 1 :
return L[0]
v1 = L[0]
v2 = find _max (L[1])
if v1 > v2 :
return v1
else:
return v2
Exercise 6 What does it mean in the theory of algorithms that two problems are equivalent? Can two unsolvable problems be equivalent?
Exercise 7 Briefly overview the limitations of understanding algorithms as informal specifications and implementions in a programming language.