Computing Concepts

This is where additional content for our theory-related sessions will be located.

Algorithms

Linear and Binary Search

Linear Search

def search(xs, target):
	for i in range(len(xs)):
		if xs[i] == target:
			return i
	return -1

xs= [1,2,3,4,5,6,7]
location = search(xs, 5)
if location != -1:
	print("The location of the item is: {}".format(location))
else:
	print("The item was not found")

Q What are the steps (in English) this code is performing?

Q What is the ‘best’ case (ie the one which requires the fewest steps)?

Q What is the ‘worst’ case (ie, the one which requires the most steps)?

(Extention) This code is not very ‘pythonic’ - how could the code be rewritten to be more pythonic?

Binary Search

def search(xs, target):
	# TODO

xs= [1,2,3,4,5,6,7]
location = search(xs, 5)
if location != -1:
	print("The location of the item is: {}".format(location))
else:
	print("The item was not found")

Q What are the steps (in English) this code is performing?

Q What is the ‘best’ case (ie the one which requires the fewest steps)?

Q What is the ‘worst’ case (ie, the one which requires the most steps)?

Q What situations would the ‘Linear’ version work and the ‘Binary’ version not work (what assumption is being made)?

Data Types

This week we’re looking at representations of data using computing.

Representing Numbers

Algorithmic Strategies

Complexity

Note: the last two are broken - the values get too big and crash the graphing tool.

Numerical Values