Unit 3

Question 1

What two factors do computer scientists have to consider when creating an algorithm?

Answer 1

Time (number of steps) and space (memory needed)

Question 2

What is a heuristic?

Answer 2

A reasonable time algorithm that provides an approximate solution to a problem. It’s “good enough”

Question 3

1. Finding routes between two towns
2. Finding files in a list of docs
3. Simulated annealing to solve TSP

Answer 3

Heuristic examples

Question 4

Reasonable or non-reasonable time: O(1)

Answer 4

Reasonable

Question 5

Reasonable or non-reasonable time: O(n)

Answer 5

Reasonable

Question 6

Reasonable or non-reasonable time: O(n^2)

Answer 6

Reasonable

Question 7

Reasonable or non-reasonable time: O(n^c)

Answer 7

Reasonable

Question 8

Reasonable or non-reasonable time: O(log(n))

Answer 8

Reasonable

Question 9

Reasonable or non-reasonable time: O(nlog(n))

Answer 9

Reasonable

Question 10

Reasonable or non-reasonable time: O(c^n)

Answer 10

Non-reasonable

Question 11

Reasonable or non-reasonable time: O(n!)

Answer 11

Non-reasonable

Question 12

O(1)

Answer 12

Constant

Question 13

O(n)

Answer 13

Linear

Question 14

O(n^2)

Answer 14

Quadradic

Question 15

O(n^c)

Answer 15

Polynomial

Question 16

O(log(n))

Answer 16

Logarithmic

Question 17

O(nlog(n))

Answer 17

Quasilinear

Question 18

O(c^n)

Answer 18

Exponential

Question 19

O(n!)

Answer 19

Factorial

Question 20

True or false: Every problem with an initial condition can be solved in a reasonable amount of time using a modern computer.

Answer 20

False

Question 21

True or false: Every problem can be solved using a computer and an algorithmic method, but some solutions require much more time than others

Answer 21

False

Question 22

True or false: To show that a problem is undecidable, you need to show that there exists an instance of the problem that cannot be solved via an algorithm

Answer 22

True

Question 23

True or false: One can use the Python programming language to create a program that determines whether any program/function and any input will descend into an infinite loop.

Answer 23

False

Question 24

Suppose you are working on a project that leads to a problem that you and your group determines to be undecidable. What consequences are most likely to be true based on that fact?

Answer 24

There is no algorithm that can definitely solve the problem.

Question 25

Compares and orders elements pairwise until the list is ordered. The method is better for a list of 10 numbers. (O(n^2))

Answer 25

Bubble sort

Question 26

Splits the list into multiple sublists then sorts them as it puts the lists back together. The method is better for a list of 150 numbers. (O(nlog(n)))

Answer 26

Merge sort

Question 27

Looks through a list one element at a time until it finds the target value. Also known as linear sort.

Answer 27

Sequential search

Question 28

Takes a sorted list and splits it in half, eliminating half of the list based on whether the target is above or below. This is more efficient than sequential search.

Answer 28

Binary search

Question 29

What are the criteria for binary search to work

Answer 29

Sorted list of the same type

Question 30

How many guesses would it take to guess a number between 1 and 600?

Answer 30

10, 2^10 is 1024