Concepts Flashcards
Algorithms & Data Structure concepts
What is a greedy algorithm?
A greedy algorithm builds up a solution by choosing the option that looks the best (eg: maximum or minimum of something) at every step.
Ex: giving someone an amount using the minimum number of coins
Sometimes, greedy algorithms doesn’t provide the optimal solution to a problem.
What is “divide and conquer”?
It is the act of breaking the problem down into two or more subproblems, solve them, and then use that solution to solve the original problem.
What is an Abstract Data Type (ADT)? Give 3 examples.
It is a mathematical model for a data type, defined by its behaviors from the point of view of the user of the data (not the implementor). Defines the possible operations, behaviors and values of the data type.
Ex: Integer, Tree, Stack, Map
What is a Data Structure?
It is a data organization and storage format that implements one or more Abstract Data Type.
What is an algorithm?
It is a procedure to accomplish a specific task.
What are heuristics?
They are a set of rules that may achieve a good result for a task but it is not guaranteed.
Think of as a Rule of Thumb.
What is the best way to disprove the correctness of a heuristics?
By finding a counter example.
According to Skiena, what is the most important single step towards a solution to a problem?
Modeling it in terms of well defined structures and algorithms.
Ex: it is a problem of: permutation, subset, trees, graphs, points, polygons, strings
What are the 3 notations used for algorithm complexity analysts?
O (bigOh) - represents an upper bound for an algorithm time
Big Omega - represents a lower bound
Big Theta - represents an upper an lower bound.
For those 3, we say that the real function is in the bounds given a constant and after a certain value of n (the input size), this is the assymptotic
What does it mean to say a time complexity function dominates another one?
It means it grows faster
Ex: n^2»_space; n
What is the best way to solve an “unbounded” Knapsack problem?
Using a iterative approach with memoization using an array.
Starting from capacity 1 iterate until W.
For each capacity, iterate over all items.
If the item weight is less then capacity get the maximum of: itemVal + knapsack(W-itemweight)
What does polynomial time mean?
Mean a time that is O(n^k) for some k. Where N is the size of input.
Ex: O(n^2) is polynomial (selection sort)
O(n!) is not polynomial (traveling salesman)
In time complexity analysis, what does “size of input to a problem” mean?
The size of input to a problem is the number of bits required to write out that input.
What does pseudo polynomial time complexity mean?
Means that the runtime is some polynomial in the numeric value of the input, and not in the number of bits of the input.
What types of problems can be solved using backtracking?
Problems which admit the concept of a “partial candidate solution” and a relatively quick test of whether it can possibly be completed to a valid solution.
