Optimal merge pattern

 

Optimal merge pattern is a pattern that relates to the merging of two or more sorted files in a single sorted file. Here, we merge a set of sorted files of different length into a single sorted file. We need to find an optimal solution, where the resultant file will be generated in minimum time.

If the number of sorted files are given, there are many ways to merge them into a single sorted file. This merge can be performed pair wise. Hence, this type of merging is called as 2-way merge patterns. As, different pairings require different amounts of time, in this strategy we want to determine an optimal way of merging many files together. At each step, two shortest sequences are merged.

If we have two files of sizes m and n, the total computation time will be m+n. Here, we use the greedy strategy by merging the two smallest size files among all the files present.

Let’s illustrate with examples:-

 

1. Find optimal merge tree for the given unsorted files -5, 3, 2, 7, 9, 13. Also find the total cost of merging.

Let’s name the unsorted files as :-

A   B   C   D   E   F

5   3   2   7   9   13

 

Now to find the optimal solution we first need to sort the given data and arrange it in sequential manner, as this allows us to find the shortest path and thus the optimal solution.

 

    C       B       A       D       E         F

    2       3       5       7        9        13

 

Let us now apply optimal merging on the given data:-

 

Hence, merge operations can be performed on this sequence

 

M1 = merge C and B => 2 + 3 = 5

M2 = merge M1 and A => 5 + 5 = 10

M3 = merge M2 and F => 10 + 13 = 23

M4 = merge D and E => 7+ 9 = 16

M5= merge M4 and M3 => 23 + 16 = 39

Therefore, Total Cost:-5+10+16+23+39=93.

Which is the optimal solution using optimal merge pattern.

 

2. Find the optimal merge tree for ten files whose length is :- 28,32,121,84,53,91,35,3 and 11 Also find its weighted external path length.

 

To find the optimal solution we first sort the given data and arrange it in ascending order as:-

3          5      11        12           28             32         35          53         84           91

     

       Now let’s apply the merge on the sorted data to get the optimal merge tree.

3          5      11        12           28             32         35          53         84           91

The weighted external path length = 8+19+31+59+67+112+151+203+354=1004

 

___________________________________________________________________________________Submitted By;

Ankita Kakade

Roll No:45

 

 

 

                  

 

 

THE CONCEPT OF BACKTRACKING

Let’s imagine you are trapped in a complex maze and trying to solve it by choosing different paths leading to dead ends and then forcing you to backtrack and try again. This trial and error method is similar to backtracking algorithm use in computer science.

The backtracking can be define as the problem solving algorithm technique that involves finding a solution by incrementing and trying different paths and undoing them if they lead to dead end. Backtracking name itself suggests that we are going back and coming forward; if it satisfies the condition, then return success, else we go back again. It is used to solve a problem in which a sequence of objects is chosen from a specified set so that the sequence satisfies some criteria.

Use of Backtracking:

 It is commonly used in situations where you need to explore multiple possibilities to solve a problem, like:-

• Solving Puzzles:

Backtracking is used in solving puzzles such as sudoku, crossword or word search. A backtracking algorithm can solve by trying different options for each element, checking if they are valid, and moving on to the next element. If an options leads to a dead end, then algorithm can backtrack to previous element and try another option, until it finds solution.

 

• Generating permutations and combinations:

Backtracking Algorithms is use in generating all possible permutations and combinations of a given set of items.

 

• Finding Paths and cycles:

Backtracking Algorithms can also be used to find paths and cycles in graphs, which are structures that consist of nodes and edges.

 

• Optimizing resources and costs:

Another use case for backtracking algorithms is optimizing the allocation of resources or the minimization of costs in various scenarios, such as scheduling, assignment, or packing problems.

 

• Searching for patterns and matches:

Backtracking algorithms can also be used to be search for patterns and matches in strings, which are sequences of characters.

Types of Backtracking

Backtracking is categorized into three types are as follows:-

• Decision Problems

In this we search for feasible solution.

• Optimization Problems

In this we search for best solution.

• Enumeration Problems

In this we find set of all possible feasible solutions to the problems of this type.

 It How Does Works? 

This is a graphic representation of the Backtracking algorithm. The representation is a tree, its first node represents the initial state of the algorithm. The first node has tree child nodes, each one of them with two nodes.

Keep in mind that the Backtracking algorithm always starts from the top, and goes from the left first.

 

 

In this representation we can see the algorithm working, supposing that we want to find the string "123", the scanner will advance to the next node (C1 or Checkpoint 1) if the character found is equal to 1, and back off to try with another node if it is not. This process will be recursively repeated many times, until the algorithm match the string "123".

 

Application of Backtracking:

 Here are five different fields in which backtracking can be used to solve problems:

Computer Science: Backtracking is commonly used in computer science to solve a wide range of problems, including search algorithms, constraint satisfaction problems, and combinatorial optimization problems.

Mathematics: Backtracking can be used in mathematics to solve a variety of problems, including those related to graph theory, number theory.

Artificial Intelligence: Backtracking is a key technique used in artificial intelligence to solve problems related to planning, decision-making, and optimization. Examples include path finding, route planning, and constraint satisfaction problems in robotics and other AI applications.

Natural Language Processing: Backtracking can be used in natural language processing to solve problems related to parsing and semantic analysis.

 

Name: Ritika S. Govindwar

Branch: SY-CSE(AI)

Roll no: 34

 

 

 

 

 

 

SOLVING A RECURRENCE RELATION USING AN ITERATIVE METHOD

 

1. A recurrence relation is like a rule that tells us how to find the value of a function based on its previous values.
2. There are different methods for doing this, which basically involve finding patterns and using mathematical techniques to come up with the solution.
3. In this approach, we repeatedly replace smaller terms with their values until we reach the simplest form. Eventually, we can substitute the base term with its value, allowing us to find the overall value of the expression.
4. Iteration methods involve expanding a recurrence relation by expressing it as a sum of terms involving n and initial conditions.
5. This approach helps understand how the function grows with increasing input size n, making it easier to analyse its behaviour and time complexity.

This can be understood with the help of an example as follows :

 

Example1:

·       The Fibonacci sequence is defined recursively as : F(n) = F(n−1) + F(n−2) with base cases : F(0) = 0, F(1)= 1 where F(5) = ?

Solution : To solve this recurrence relation iteratively, we start with the base cases and work our way up to the desired term. Let's find F(5) using iteration:

1.    Base cases provide starting points for the sequence. Here, F(0) and F(1) are given directly, which we can use to build up the sequence.

2.    We use a loop to calculate Fibonacci numbers iteratively, starting from F(2) up to the desired value, in this case, F(5)

·       For each n, calculate F(n) by adding the previous two Fibonacci numbers : F(n) = F(n−1) + F(n−2).

·       For example : F(2) = F(1)+F(0) when n=2 and F(3) = F(2)+F(1) for n=3.

3.    Using this approach, we find:

        F(2) = F(1)+F(0) = 1+0 = 1

        F(3) = F(2)+F(1) = 1+1 = 2

        F(4) = F(3)+F(2) = 2+1 = 3

        F(5) = F(4)+F(3) = 3+2 =5

4.    After completing the iterations, we find the desired Fibonacci number, in this case F(5) = 5.

 

Example 2:

·       The Fibonacci sequence is defined recursively as : an​     = an−1​  + 2 with base case :  a0  ​= 1, Find  a5​ ​.

Solution :

1.    To solve this recurrence relation iteratively, we start with the base cases same as per the above example. Here, Let's find a5 using iteration:

2.    We then use a loop to calculate Fibonacci numbers iteratively, starting from n=1 up to the desired value, in this case, a5.

·       For each n, we use the recurrence relation an​  = an−1​ + 2 to find the next term.

      (We incrementally build up the sequence by adding 2 to the previous term.)

3.    In each iteration, we update the value of an−1​ to the current value of an​ and proceed to the next iteration.

4.    Let's perform the iterations:

• a1 = a0+2 = 1+2 =3
• a2 ​= a1 +2 = 3+2 = 5
• a3 = a2 ​+2 = 5+2 = 7
• a4 ​= a3 +2 = 7+2 = 9
• a5 = a4 ​​+2 = 9+2 = 11

    Hence we found the desired output, a5 ​= 11.

    In this way, we can solve recurrence relations iteratively by directly calculating each term based on the previous term and the given recurrence relation.

 

Now let us understand the time complexity. The time complexity of the iterative algorithm is typically easier to analyze than the recursive one because there’s no additional overhead from function calls. You can often express it directly in terms of the number of iterations or the operations performed in the loops.

 

Example : Find the time complexity for the following recurrence relation : T(N) = T(N-1) + N, T(1) = 1

Solution : Here T(N) = T(N-1) + N implies T(N-1) = T(N-2) + N-1.

Thus,

          T(N) = (T(N-2) + (N-1))  + N

          T(N) = T(N-2) + N + (N-1)

          T(N) = T(N-3) + N + (N-1) + (N-2)

          From the above pattern, we get

          T(N) = T(N-k) + N + (N-1) + (N-2) + … (N-(k-1))

          T(N) = T(1) + N + (N-1) + (N-2) + … (2) and since T(1)=1,

          T(N) = N + (N-1) + (N-2) + … (1)

          T(N) = N x (N-1)/2 = O(N*N)

Thus the time complexity is O(N²)

      

Top of Form

 

 

Meenal S. Shelar

S.Y. (AI) Rollno. 17