Algorithms

Question 1

Properties of a Recursive Algorithm

Answer 1

• A recursive algorithm must have a termination condition.
• A recursive algorithm must change its state, and shift the state toward the termination condition.
• A recursive algorithm must be capable of calling itself.

Question 2

Define:

Euclidean algorithm

Answer 2

Euclidian algorithm is based on the principle that the greatest common divisor of two numbers does not change if the largest number is replaced by its difference with the smaller number.
Since this replacement reduces the largest of the two numbers, repeating this process gives successively smaller pairs of numbers until two numbers become equal. When that occurs, they are GCD (Greatest Common Divisor) of the original numbers.

Let d be GCD for m and n. Then m = d * a and n = d * b. So m - n ~ a--

The version of the Euclidian algorithm described above can take many substractions steps to find the GCD when one of the given numbers musch bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its reminder when divided by the smaller of the two.

wikipedia

Question 3

Basic guidelines for the constraints for an array of numbers

Answer 3

• What is the maximum number of elements in an array?
• What is the spectrum of each element?
• What are the minimum and maximum values?
• What type of information is contained in each element? Is it floating-point or integer?
• Does the array contain unique data or not?

Question 4

Basic guidelines for the constraints for an array of string

Answer 4

• What is the total number of elements in the array?
• How long are each of the strings? What is the shortest and longest length?
• Does the array contain any data that is unique?

Question 5

Basic guidelines for the constraints for a graph

Answer 5

• In the graph, how many nodes are there?
• How many edges does the graph have?
• Is the graph weighted? What is the weight range?
• Does the graph have directed edges or undirected edges?
• Does the graph have a loop?
• Does the graph have a negative sum loop?
• Are there any self-loops in the graph?

Question 6

Strategy to solve problems

Answer 6

• Constraints analysis
• Ideas generation
• Complexity analysis
• Coding
• Testing