1.3 Introduction to algorithms Flashcards
What is an algorithm?
An algorithm describes a sequence of steps to solve a computational problem or perform a calculation.
What does a computational problem specify?
A computational problem specifies an input, a question about the input, and the desired output.
What is the input in the FindMax algorithm?
An array of integers.
What is the output of the FindMax algorithm?
The maximum integer in the input array.
What question does the FindMax algorithm answer?
What is the maximum value in the input array?
Fill in the blank: A computational problem is a problem that can be solved using a _______.
computer
What is the significance of the input in determining the frequency of a word?
The input must include a list of all words to search through and the specific word for which determining the frequency is desired.
What is the problem output when determining the frequency of a specified word?
Integer value for the frequency of specified word.
True or False: An algorithm must be written using a programming language.
False
In which domains can computational problems be found?
- E-commerce
- Internet technologies
- Biology
- Manufacturing
- Transportation
What is a common algorithm used for DNA analysis?
Longest common substring algorithm.
What is the purpose of the binary search algorithm?
To search a sorted list efficiently.
What does Dijkstra’s shortest path algorithm determine?
The shortest path from a start vertex to each vertex in a graph.
What is the characteristic of NP-complete problems?
No efficient algorithm has been found to solve an NP-complete problem.
True or False: If an efficient algorithm exists for one NP-complete problem, all NP-complete problems can be solved efficiently.
True
What is the clique decision problem?
It is a problem to determine if a set of K people who all know each other exists, and it is NP-complete.
What is the output of the clique decision problem?
Boolean value.
True or False: An efficient algorithm exists for all computational problems.
False
True or False: An algorithm with a polynomial runtime is considered efficient.
True
What is the current consensus regarding efficient algorithms for NP-complete problems?
Such an algorithm is unlikely to exist.
