Week 1

Question 1

What makes a problem Decidable ?

Answer 1

An algorithm exists which solves every instance of that problem

Question 2

What is an Effective procedure

Answer 2

Is an algorithm which solves. Decision problem in a finite number of steps, correctly giving the answer yes or no for every input over which the problem is defined

Question 3

Describe the speed ai u which an effective procedure is completed

Answer 3

Makes no claim as to how quickly it will finish the procedure might take billions of years but as long as it is guards tered to return the correct answer after a finite number of steps it is classed as effective

Question 4

Describe the halting problem

Answer 4

Given a computer program and an input to that program does the program halt (that is not enter an infinite loop) for that input

Question 5

Define a Decision problem

Answer 5

A decision problem is a problem for which the answer is either yes or no

Question 6

we say that teh halting problem is (2 words)

Answer 6

undecidable or uncomputable

Question 7

what makes a problem computable?

Answer 7

am algorithm existing for its solution, even if the complexity might make it impossible to actually carry out the algorithim in practice.

Question 8

names of the four NY algorithms

Answer 8

twilight, the knife, the carnival amd teh boston shuffler

Question 9

describe the way a list is indexed

Answer 9

the first item in a list in index 0 the second is index 1