Understanding Algorithms and Their Analysis

Explain the difference between a deterministic and a non-deterministic algorithm.

• Deterministic algorithms can handle more complex problems than non-deterministic algorithms.

• Non-deterministic algorithms always produce the same output.

• Deterministic algorithms yield consistent results, while non-deterministic algorithms can yield varied results for the same input.

• Deterministic algorithms are faster than non-deterministic algorithms.

What is a greedy algorithm? Provide an example.

• A greedy algorithm always finds the optimal solution for any problem.

• An example of a greedy algorithm is the Coin Change Problem, where the goal is to make change for a given amount using the fewest coins possible. The algorithm selects the largest denomination coin that does not exceed the remaining amount until the total is reached.

• A greedy algorithm is one that uses dynamic programming to solve problems.

• An example of a greedy algorithm is sorting a list in ascending order.

Describe the divide and conquer strategy in algorithms.

• It solves the entire problem at once without breaking it down.

• It only works for problems that can be solved in linear time.

• It combines all subproblems into one large problem before solving.

• Divide and conquer is an algorithmic strategy that divides a problem into smaller subproblems, solves them independently, and combines their solutions.

Explain the difference between a stack and a queue.

• A stack uses FIFO, while a queue uses LIFO.

• Both stack and queue use LIFO.

• A stack allows random access, while a queue does not.

• A stack uses LIFO, while a queue uses FIFO.

What is dynamic programming? Give an example of its application.

• An example of dynamic programming is the Fibonacci sequence calculation, where each number is the sum of the two preceding ones. Instead of recalculating Fibonacci numbers multiple times, dynamic programming stores previously computed values.

• An example of dynamic programming is calculating the area of a rectangle.

• Dynamic programming is used to create random number generators.

• Dynamic programming is a method for sorting arrays efficiently.

What is the significance of the Master Theorem in algorithm analysis?

• The Master Theorem is used to analyze iterative algorithms.

• The Master Theorem provides a way to optimize sorting algorithms directly.

• The Master Theorem is primarily focused on graph algorithms.

• The Master Theorem simplifies the analysis of divide-and-conquer algorithms by providing a method to solve recurrences.

How does a binary search algorithm work?

• A binary search algorithm sorts the array before searching.

• A binary search algorithm finds the position of a target value within a sorted array by dividing the search interval in half repeatedly.

• A binary search algorithm requires the array to be unsorted.

• A binary search algorithm checks each element one by one.

What are the advantages of using a linked list over an array?

• Fixed size allocation

• Requires more memory overhead

• Advantages of using a linked list over an array include dynamic size, efficient insertions/deletions, and no need for contiguous memory allocation.

• Slower access times for elements

What is the role of a sorting algorithm in data processing?

• To compress data to save storage space.

• The role of a sorting algorithm in data processing is to organize data in a specific order to improve efficiency in searching and managing data.

• To visualize data in graphical formats.

• To encrypt data for security purposes.

What is the primary difference between a binary tree and a binary search tree?

• A binary tree allows duplicate values, while a binary search tree does not.

• A binary search tree is a type of binary tree that maintains a specific order for its nodes.

• Binary trees are always balanced, whereas binary search trees can be unbalanced.

• Binary trees can only have two children, while binary search trees can have more.