DAA Assignment
DAA Assignment
DAA Assignment
Q1. Difference between dynamic programming and divide and conquer? And
give examples of both approaches.
Dynamic programming and divide and conquer are two common algorithmic
techniques used to solve complex problems. Although both techniques involve
breaking down problems into smaller sub problems, there are some key
differences between them.
Divide and conquer is a technique used to solve problems by breaking them down
into smaller, non-overlapping sub problems that can be solved independently.
The solution to a divide and conquer problem involves solving each sub problem
and then combining the solutions to get the final answer. Divide and conquer can
be used to solve problems such as sorting, searching, and finding the maximum
subarray.
Here are some examples of each approach:
Dynamic Programming:
The Fibonacci sequence can be computed using dynamic programming. The sub
problem is to compute the n-th Fibonacci number, and the solution involves
storing the values of the previous two Fibonacci numbers and using them to
compute the next one.
The longest common subsequence problem can also be solved using dynamic
programming. The sub problem is to find the longest common subsequence of
two strings, and the solution involves storing the lengths of the longest common
subsequences of smaller substrings of the two strings.
Divide and Conquer:
The merge sort algorithm is an example of divide and conquer. The problem is to
sort a list of numbers, and the solution involves dividing the list in half, sorting
each half, and then merging the two sorted halves.
The binary search algorithm is another example of divide and conquer. The
problem is to find a specific value in a sorted list of numbers, and the solution
involves dividing the list in half, discarding one half based on whether the value is
greater or less than the midpoint, and repeating until the value is found or the list
is exhausted.
Q2. Find time complexity of any algorithm of your choice. Write down all steps
and explanation of algorithm complexity.
In the worst-case scenario, where all processes arrive at the same time and have
the same burst time, and the time quantum is equal to the burst time of each
process, the time complexity of the round-robin algorithm is O(n^2), where n is
the number of processes. This is because each process will execute for exactly
one-time quantum, and there will be n iterations to complete the execution of all
processes. During each iteration, all n processes need to be examined to
determine if they are ready to execute or not, resulting in a total of n^2-time
complexity.
However, in practice, the arrival and completion times of processes are usually
distributed randomly, and the time quantum is set to a smaller value than the
burst time of the processes. In such cases, the time complexity of the round-robin
algorithm can be much better than O(n^2) and closer to O(n).
Overall, the time complexity of the round-robin algorithm can vary widely
depending on the specific scenario, but it is generally considered to be efficient
and suitable for preemptive scheduling in real-time systems.