Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Algorithm Design and Analysis > Test 1 > Flashcards

Test 1 Flashcards

1
Q

What is an algorithm?

A

An unambiguous sequence of simple, mechanically executable instructions that solve a problem. A logical sequence of steps that will solve the correct problem.

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

What are functional requirements?

A

What the function has to do; functionality.

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

What are nonfunctional requirements?

A

Constraints, ex: max runtime

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

What does data turn into after being processed?

A

Information

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

What is a problem?

A

A question to which an answer is sought

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

What are parameters?

A

Input to the problem

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

What is restart penalty?

A

Time/effort cost accrued when a programmer looks at code that they either have never seen or haven’t seen in a while.

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

What is information?

A

Data that has meaning

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

How is an algorithm presented?

A

As an ordered sequence of instructions of finite size

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

What is a computing agent?

A

An actor that can react to the instructions and carry out the computations

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

What do all programs require?

A

An entry point and an end point

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

Why do many algorithms look like a coding language?

A

Because the writer works with that language frequently in day-to-day

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

Is there a fixed finite bound on the size of inputs?

A

No

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

Is there a fixed finite bound on the size of the ordered set of instructions?

A

No

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

Is there a fixed finite bound on the amount of memory space available?

A

No

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

Is there a fixed finite bound on the capacity or ability of the computing agent?

A

Yes (before parallelism)

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

What are problems?

A

Specific tasks solved by an algorithm.

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

What are parameters to the problem?

A

Variables that are not assigned specific values in the statement of the problem

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

What is an instance of the problem?

A

A specific assignment of values to the parameters.

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

What is a key?

A

An item that identifies a record

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

How do we know if a solution is efficient?

A

If it solves the problem within the require resource constraints

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

Why is Big O notation / complexity analysis useful?

A

It measures algorithm efficiency agnostic of program environment

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

What is the time complexity analysis of an algorithm?

A

The determination of how many times a basic operation is performed for each value of the input size.

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

What does T(n) represent?

A

The number of times the algorithm does the basic operation for an instance of size n. It is the every-case time complexity of the algorithm.

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

What does W(n) represent?

A

Worst case complexity analysis

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

What does A(n) represent?

A

Average case complexity analysis

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

What does B(n) represent?

A

Best case complexity analysis

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

What is memory complexity?

A

An analysis of how efficient the algorithm is in terms of memory.

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

What are the factors that should be taken into account when performing algorithm analysis?

A

1 Time it takes to execute the basic operation
2 Overhead instructions
3 Control instructions

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

How often does the worst case happen?

A

Not very often

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

What are overhead instructions?

A

Instructions that don’t increase with input size. Examples are initializations, setup, cleanup.

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

What are control instructions?

A

Calls that increase with input size. Ex: Range checking, operating system calls.

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

What are the properties of an algorithm and the implementation of the algorithm?

A

1 Basic Operations
2 Overhead Instructions
3 Control Instructions

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

What is analysis of correctness?

A

Analyzing an algorithm with the goal of proving that the algorithm actually does what it is supposed to do

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

What is the difference between pure quadratic functions and complete quadratic functions?

A

Complete quadratic functions contain a linear term, pure quadratic functions do not.

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

What is the term for an algorithm in Theta(n^2) time complexity?

A

Quadratic time algorithm

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

What is the growth rate?

A

The impact over time as n increases

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

What are some order complexity categories?

A

Big O of:

log n, n, n log n, n^2, 2^n, n!

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

What is Big O?

A

Asymptotic upper bound for ONE choice of constant

40
Q

What is small o(f(n))?

A

Asymptotic upper bound for EVERY choice of constant

41
Q

What is Big Theta?

A

The asymptotic tight bound (inside Big O and Big Theta)

42
Q

What is Big Omega?

A

The asymptotic lower bound

43
Q

What is a greedy algorithm?

A

An algorithm that builds up a solution incrementally, blindly optimizing for some local criterion

44
Q

What is a step?

A

It depends. May be lines of algorithmic code, number of arithmetic operations, or some other criterion.

45
Q

Which steps (operations) do we count?

A

The ones that cost the most

46
Q

What is the most costly type of operation?

A

Comparisons

47
Q

What is a divide and conquer algorithm?

A

An algorithm that breaks the problem down into multiple sub problems, solves each sub problem independently, and then combines the solutions to form a solution to the original problem. Top down approach (typically).

48
Q

Why is average case hard to compute?

A

Because data isn’t always known and the average may change over time

49
Q

What is a top down algorithm?

A

One that starts with the base case and breaks it down

50
Q

Is Dynamic Programming top down or bottom up?

A

Bottom up

51
Q

What is a dynamic programming algorithm?

A

An algorithm in which the problem is broken down into a series of overlapping subproblems. Solutions to the subproblems are built up to larger and larger subproblems, saving computation time.

52
Q

What are the four steps in developing a dynamic programming algorithm?

A

1 Establish the base case
2 Determine recursive property that gives the solution to an instance of the problem
3 Solve an instance of the problem in bottom-up fashion by solving smaller instances first
4 Construct an optimal solution in a bottom-up fashion

53
Q

What are the characteristics of an optimization problem?

A

1 There are multiple candidate solutions
2 Each candidate solution has a value associated with it
3 A solution to the instance is a candidate solution with an optimal value
4 The optimal value is likely to be a minimum or a maximum

54
Q

What is a path?

A

A sequence of adjacent vertices in a graph

55
Q

What is a simple path?

A

A path with distinct vertices (you don’t pass through same vertex twice)

56
Q

What is a cycle?

A

A simple path with three or more vertices such that the last is adjacent to the first

57
Q

What is the principle of optimality?

A

An optimal solution to an instance of a problem always contains optimal solution to all subinstances

58
Q

When does the principle of optimality not apply?

A

When the subproblems are not identical to the larger problem

59
Q

What does NP stand for and mean?

A

Non-deterministic Polynomial. It means we are unable to immediately come up with a solution, and must use a form of guessing. We can’t immediately solve the problem, but we can quickly test potential solutions.

60
Q

What is a heuristic in terms of algorithms?

A

A “good enough” and “fast enough” solution that is not guaranteed to be the best or most optimal solution.

61
Q

What are methods of solving NP complete problems?

A

1 Use a heuristic
2 Solve the problem approximately instead of exactly
3 Use an exponential time solution anyways
4 Choose a better abstraction (abstract less, maybe)

62
Q

What is the dynamic programming paradigm relating to graphs?

A

1 The graph is implicit
2 Nodes are the subproblems
3 Edges are the dependencies between subproblems

63
Q

In which cases would you use a dynamic programming algorithm over a divide and conquer algorithm?

A

When the subproblem size is not substantially smaller than the original problem or subproblem size.

64
Q

What is memoization?

A

Within dynamic programming, storing a processed value in a hash table, indexed by its parameter values

65
Q

If asked to provide/explain an algorithm, what concept paradigm works best?

A

A high level, logical view. Algorithms should be describable to customer for validation & should leave freedom to developers for implementation.

66
Q

Within an algorithm design and analysis context, what does promising mean?

A

The algorithm looks good and you are on the right track.

67
Q

What is a naive approach?

A

The simple, most obvious solution that will solve the problem but may not be optimal.

68
Q

What are the attributes of a greedy algorithm?

A

1 Solve optimization problems
2 Not divided into subproblems
3 Obtain a solution by making a sequence of choices, each choice appears to be best choice at that step
4 Locally optimal
5 Once a choice is made, it cannot be reconsidered
6 Choice is made without regard to past or future choices

69
Q

What is the greedy approach?

A

1 Initially the solution is an empty set
2 At each iteration, items are added to the solution set until the set represents a solution to that instance of the problem

70
Q

What are the primary steps in a greedy algorithm?

A

1 Selection - Choose next item to add according to greedy criterion satisfying local optimization
2 Feasibility check - Determine if new set is feasible by determining if it is possible to complete this set to provide a solution
3 Solution check - Determine whether the new set produced is a solution to the problem instance

71
Q

What is a spanning tree?

A

A connected subgraph that contains all the vertices in G and is a tree.

72
Q

Is it possible to have multiple MSTs per graph?

A

Yes

73
Q

What does it mean if there are no cycles in a graph?

A

It is an MST

74
Q

What is the difference between Kruskal and Prim’s algorithms?

A

Kruskal uses disjoint sets at beginning containing each vertex, Prim doesn’t. Kruskal better for sparse graphs, Prim better for dense graphs.

75
Q

What was Huffman’s first name?

A

David, he went to MIT.

76
Q

Why are there holes in a Huffman code tree?

A

To prevent duplicate prefixes

77
Q

In Huffman encoding, what is a unique binary string representing a character called?

A

A code word

78
Q

What is entropy?

A

A measure of the number of bits actually required to store data. Sometimes called a measure of surprise.

79
Q

When is Huffman encoding practical?

A

1 The encoded string is large relative to the code table

2 We agree on the code table beforehand

80
Q

How does predictability work?

A

More compressible means less random means more predictable

81
Q

What is a prime caveat of using a greedy algorithm?

A

You may be able to find one or more solutions considering different variables to be optimized, but there will usually be a counterexample where that solution will be suboptimal.

82
Q

What are 3 heap management algos?

A

1 Best fit - tightest fit for data
2 Worst fit - loosest fit for data
3 First fit - first available that fits

83
Q

What are some greedy analysis strategies?

A

1 Show that after each step of algo, its solution is at least as good as any other algo’s
2 Exchange argument - Gradually transform any solution to the one found by the greedy algorithm without hurting its quality

84
Q

What is the difference between brute force and backtracking?

A

Backtracking only considers possible candidate solutions.

85
Q

Where is backtracking usually efficient?

A

For many large instances of a problem

86
Q

What is slack time?

A

The amount of time a job’s start or end can be shifted while still meeting the deadline.

87
Q

Why would you want to invert jobs?

A

A priority change occurred

88
Q

What is the idea behind clustering?

A

Differentiating between distinct sets.

89
Q

What is backtracking?

A

A systematic way to go through all possible configurations of a space, and ignoring results that are not solutions by ruling them out as early as possible.

90
Q

When is backtracking used?

A

When a feasible solution is needed rather than an optimal one

91
Q

How is backtracking implemented?

A

A modified depth-first search of the solution space tree

92
Q

What is a state space tree?

A

Each branch represents an “action” taken towards the solution. “Is any child of this going to be a solution?”

93
Q

What is pruning?

A

It is a DFS of state space tree.

94
Q

What is a pruned state space tree?

A

A subtree consisting of visited nodes.

95
Q

What is a bounding function?

A

A procedure that “kills” live nodes in the state space tree, preventing them from being considered.

96
Q

What is a goal node?

A

A node sought in a tree search that satisfies certain conditions, depending on the problem.

Algorithm Design and Analysis (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions