Test 1 Flashcards
What is an algorithm?
An unambiguous sequence of simple, mechanically executable instructions that solve a problem. A logical sequence of steps that will solve the correct problem.
What are functional requirements?
What the function has to do; functionality.
What are nonfunctional requirements?
Constraints, ex: max runtime
What does data turn into after being processed?
Information
What is a problem?
A question to which an answer is sought
What are parameters?
Input to the problem
What is restart penalty?
Time/effort cost accrued when a programmer looks at code that they either have never seen or haven’t seen in a while.
What is information?
Data that has meaning
How is an algorithm presented?
As an ordered sequence of instructions of finite size
What is a computing agent?
An actor that can react to the instructions and carry out the computations
What do all programs require?
An entry point and an end point
Why do many algorithms look like a coding language?
Because the writer works with that language frequently in day-to-day
Is there a fixed finite bound on the size of inputs?
No
Is there a fixed finite bound on the size of the ordered set of instructions?
No
Is there a fixed finite bound on the amount of memory space available?
No
Is there a fixed finite bound on the capacity or ability of the computing agent?
Yes (before parallelism)
What are problems?
Specific tasks solved by an algorithm.
What are parameters to the problem?
Variables that are not assigned specific values in the statement of the problem
What is an instance of the problem?
A specific assignment of values to the parameters.
What is a key?
An item that identifies a record
How do we know if a solution is efficient?
If it solves the problem within the require resource constraints
Why is Big O notation / complexity analysis useful?
It measures algorithm efficiency agnostic of program environment
What is the time complexity analysis of an algorithm?
The determination of how many times a basic operation is performed for each value of the input size.
What does T(n) represent?
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.
What does W(n) represent?
Worst case complexity analysis
What does A(n) represent?
Average case complexity analysis
What does B(n) represent?
Best case complexity analysis
What is memory complexity?
An analysis of how efficient the algorithm is in terms of memory.
What are the factors that should be taken into account when performing algorithm analysis?
1 Time it takes to execute the basic operation
2 Overhead instructions
3 Control instructions
How often does the worst case happen?
Not very often
What are overhead instructions?
Instructions that don’t increase with input size. Examples are initializations, setup, cleanup.
What are control instructions?
Calls that increase with input size. Ex: Range checking, operating system calls.
What are the properties of an algorithm and the implementation of the algorithm?
1 Basic Operations
2 Overhead Instructions
3 Control Instructions
What is analysis of correctness?
Analyzing an algorithm with the goal of proving that the algorithm actually does what it is supposed to do
What is the difference between pure quadratic functions and complete quadratic functions?
Complete quadratic functions contain a linear term, pure quadratic functions do not.
What is the term for an algorithm in Theta(n^2) time complexity?
Quadratic time algorithm
What is the growth rate?
The impact over time as n increases
What are some order complexity categories?
Big O of:
log n, n, n log n, n^2, 2^n, n!
What is Big O?
Asymptotic upper bound for ONE choice of constant
What is small o(f(n))?
Asymptotic upper bound for EVERY choice of constant
What is Big Theta?
The asymptotic tight bound (inside Big O and Big Theta)
What is Big Omega?
The asymptotic lower bound
What is a greedy algorithm?
An algorithm that builds up a solution incrementally, blindly optimizing for some local criterion
What is a step?
It depends. May be lines of algorithmic code, number of arithmetic operations, or some other criterion.
Which steps (operations) do we count?
The ones that cost the most
What is the most costly type of operation?
Comparisons
What is a divide and conquer algorithm?
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).
Why is average case hard to compute?
Because data isn’t always known and the average may change over time
What is a top down algorithm?
One that starts with the base case and breaks it down
Is Dynamic Programming top down or bottom up?
Bottom up
What is a dynamic programming algorithm?
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.
What are the four steps in developing a dynamic programming algorithm?
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
What are the characteristics of an optimization problem?
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
What is a path?
A sequence of adjacent vertices in a graph
What is a simple path?
A path with distinct vertices (you don’t pass through same vertex twice)
What is a cycle?
A simple path with three or more vertices such that the last is adjacent to the first
What is the principle of optimality?
An optimal solution to an instance of a problem always contains optimal solution to all subinstances
When does the principle of optimality not apply?
When the subproblems are not identical to the larger problem
What does NP stand for and mean?
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.
What is a heuristic in terms of algorithms?
A “good enough” and “fast enough” solution that is not guaranteed to be the best or most optimal solution.
What are methods of solving NP complete problems?
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)
What is the dynamic programming paradigm relating to graphs?
1 The graph is implicit
2 Nodes are the subproblems
3 Edges are the dependencies between subproblems
In which cases would you use a dynamic programming algorithm over a divide and conquer algorithm?
When the subproblem size is not substantially smaller than the original problem or subproblem size.
What is memoization?
Within dynamic programming, storing a processed value in a hash table, indexed by its parameter values
If asked to provide/explain an algorithm, what concept paradigm works best?
A high level, logical view. Algorithms should be describable to customer for validation & should leave freedom to developers for implementation.
Within an algorithm design and analysis context, what does promising mean?
The algorithm looks good and you are on the right track.
What is a naive approach?
The simple, most obvious solution that will solve the problem but may not be optimal.
What are the attributes of a greedy algorithm?
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
What is the greedy approach?
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
What are the primary steps in a greedy algorithm?
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
What is a spanning tree?
A connected subgraph that contains all the vertices in G and is a tree.
Is it possible to have multiple MSTs per graph?
Yes
What does it mean if there are no cycles in a graph?
It is an MST
What is the difference between Kruskal and Prim’s algorithms?
Kruskal uses disjoint sets at beginning containing each vertex, Prim doesn’t. Kruskal better for sparse graphs, Prim better for dense graphs.
What was Huffman’s first name?
David, he went to MIT.
Why are there holes in a Huffman code tree?
To prevent duplicate prefixes
In Huffman encoding, what is a unique binary string representing a character called?
A code word
What is entropy?
A measure of the number of bits actually required to store data. Sometimes called a measure of surprise.
When is Huffman encoding practical?
1 The encoded string is large relative to the code table
2 We agree on the code table beforehand
How does predictability work?
More compressible means less random means more predictable
What is a prime caveat of using a greedy algorithm?
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.
What are 3 heap management algos?
1 Best fit - tightest fit for data
2 Worst fit - loosest fit for data
3 First fit - first available that fits
What are some greedy analysis strategies?
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
What is the difference between brute force and backtracking?
Backtracking only considers possible candidate solutions.
Where is backtracking usually efficient?
For many large instances of a problem
What is slack time?
The amount of time a job’s start or end can be shifted while still meeting the deadline.
Why would you want to invert jobs?
A priority change occurred
What is the idea behind clustering?
Differentiating between distinct sets.
What is backtracking?
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.
When is backtracking used?
When a feasible solution is needed rather than an optimal one
How is backtracking implemented?
A modified depth-first search of the solution space tree
What is a state space tree?
Each branch represents an “action” taken towards the solution. “Is any child of this going to be a solution?”
What is pruning?
It is a DFS of state space tree.
What is a pruned state space tree?
A subtree consisting of visited nodes.
What is a bounding function?
A procedure that “kills” live nodes in the state space tree, preventing them from being considered.
What is a goal node?
A node sought in a tree search that satisfies certain conditions, depending on the problem.
