Unit 3 Flashcards

1
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a heuristic?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q
  1. Finding routes between two towns
  2. Finding files in a list of docs
  3. Simulated annealing to solve TSP
A

Heuristic examples

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Reasonable or non-reasonable time: O(1)

A

Reasonable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Reasonable or non-reasonable time: O(n)

A

Reasonable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

Reasonable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

Reasonable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

Reasonable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

Reasonable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

Non-reasonable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

Non-reasonable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

O(1)

A

Constant

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

O(n)

A

Linear

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

O(n^2)

A

Quadradic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

O(n^c)

A

Polynomial

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

O(log(n))

A

Logarithmic

17
Q

O(nlog(n))

A

Quasilinear

18
Q

O(c^n)

A

Exponential

19
Q

O(n!)

A

Factorial

20
Q

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

A

False

21
Q

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

A

False

22
Q

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

A

True

23
Q

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.

A

False

24
Q

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?

A

There is no algorithm that can definitely solve the problem.

25
Q

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

A

Bubble sort

26
Q

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)))

A

Merge sort

27
Q

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

A

Sequential search

28
Q

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.

A

Binary search

29
Q

What are the criteria for binary search to work

A

Sorted list of the same type

30
Q

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

A

10, 2^10 is 1024

31
Q
A