Theory of Computation Flashcards
What is Backus Naur Form? (BNF)
A way of notating context-free languages. It uses statements in which the left hand side is defined by the right hand side
Why is finding out if a program will eventually stop if given a particular input significant for computation?
It demonstrates that there are some problems that cannot be solved by a computer
Time complexity of a binary search algorithm:
O(log n)
The two measures of time complexity:
Space/memory
Describe the complexity of an algorithm
What is the halting problem?
It is possible in general to write a program that can tell, given any program and its inputs and without running the program whether the given program with its given inputs will halt
Significance of the halting problem:
It shows that some problems are non-computable
Merge sort time complexity:
O(n log n)
Bubble sort time complexity:
O(n^2)
Why does bubble sort have that complexity?
In each pass through the list n items will be examined. There will be n passes through the list
What does it mean if a problem is intractable?
The problem can be solved but not in polynomial time
How to solve an intractable problem?
Use of a heuristic that provides a close-to-optimal solution
Why does linear search have time complexity O(n)?
As size of the list increases the time taken to search for an item increases
A linear search looks at each item in the list in turn
