ZuoTi.Pro
Question

[10 marks] Assume that we have two decimal positive numbers A and B. Both numbers have n digits. We want to know what is the

3. [10 marks] Draw all possible spanning trees of the following graph.

[10 marks] Assume that we have two decimal positive numbers A and B. Both numbers have n digits. We want to know what is the minimum number of swaps that we need in order to get from number A to B, where in each swap we choose two digits of a number and simply swap them For simplicity, we assume that A and B do not have the digit 0 in them, and that A and B have the set of digits so it is always possible to get from A to B. 5. Two examples are as follows: Example 1) A-2345 and B-5342 (n-4): The optimal strategy is swapping 2 and 5 that results in 5342. So, the minimum number of swaps is 1 Example 2) A-2345 and B-3452: 2345 -> 3245 > 3254 -> 3452 So, the minimum number of swaps is 3. Note that other sequences of swaps are also possible to get to B in 3 swaps Write a pseudocode that computes and prints the solution. (Hint: use a BFS). You can assume that the method swapDigits(x, i, j) is already implemented and you can use it. It takes number x and swaps the digits i and j and returns the result, where 1 s i,j 3 n. Also, you can assume that you always have enough memory available. It does not matter if you count the digits from left to right or vice versa.
3. [10 marks] Draw all possible spanning trees of the following graph.
engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

auane y equal to x vau datrangn for i=o to eaeh time Pob end Loop

Tree 乙

0 0
Add a comment
Know the answer?
Add Answer to:
[10 marks] Assume that we have two decimal positive numbers A and B. Both numbers have n digits. ...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • (Q2) Calculating the Distribution of Values 10 marks For a set of n real numbers {xi,...,...

    (Q2) Calculating the Distribution of Values 10 marks For a set of n real numbers {xi,..., x.J, here are a number of basic statistics we would like to know about the distribution of these numbers: ·The minimum value m = min(x 1, . .., Xn The maximum value Mmax{xi,..., x,J The average value a -^ 1x The standard deviation sx,-a)2. Write a program stats.c that calculates these values for a sequence of values it reads from stdin. The input is...

  • The input consists of n numbers a1, a2, . . . , an and a target...

    The input consists of n numbers a1, a2, . . . , an and a target value t. The goal is to determine in how many possible ways can we add up two of these numbers to get t. Formally, your program needs to find the number of pairs of indices i, j, i < j such that ai+aj = t. For example, for 2, 7, 3, 1, 5, 6 and t = 7, we can get t in two...

  • Suppose you have an array S indexed from 1 to n which contains n numbers, not...

    Suppose you have an array S indexed from 1 to n which contains n numbers, not in any particular order, and you wish to count how many times a given number x occurs in S. Consider the recursive algorithm below for this which finds the number of occurrences of x in the index range i...j in S. Of course, solving the problem would involve an initial call to the algorithm for the range 1.n: int CountOccur (int i,j) { int...

  • Pseudo-random numbers are pervasive and extremely important in modern computing and scientific applications. But how exactly...

    Pseudo-random numbers are pervasive and extremely important in modern computing and scientific applications. But how exactly is a sequence of apparently random number generated? Here we study one early method which has the benefit of being very easy to implement 1. If we take a positive integer n having k digits (k 1), then n 10*, so that n2 (10)2 02. Thus we would expt up to 2k digits in the square of the k digit number 1l So, for...

  • Introduction: Ten digit ISBN numbers are created so that the first nine digits are information digits...

    Introduction: Ten digit ISBN numbers are created so that the first nine digits are information digits and the last digit is a check digit. T his last number helps people notice and correct mistakes that might be made in recording the information digits. The same is true for thirteen digit ISBN numbers. Here is a ten digit ISBN number: 0-13-149498-8. The digit 0 indicates the book is written for English-speaking people. The number 13 and the number 149498 identify the...

  • Consider the problem where you are given an array of n digits [di] and a positive...

    Consider the problem where you are given an array of n digits [di] and a positive integer b, and you need to compute the value of the number in that base. In general, you need to compute For example: (1011)2 = 1(1) + 1(2) + 0(4) + 1(8) = 11; (1021)3 = 1(1) + 2(3) + 0(9) + 1(27) = 34, and (1023)4 = 3(1) + 2(4) + 0(16) + 1(64) = 75. In these examples, I give the digits...

  • Question 4 (10 marks) When analysing the complexity of algorithms, there are three main approaches: worst case, best ca...

    Question 4 (10 marks) When analysing the complexity of algorithms, there are three main approaches: worst case, best case and average case. As an example, consider measuring the complexity of list-merging by counting the number of comparisons used As a test example, assume the following A1: There are two ordered lists, each of length 4, say A2: Neither list contains repeats, so a! < a2 < аз < a4 and bl <b2 < b3 < b4 A3: The lists are...

  • 9. When we have two sorted lists of numbers in non-descending order, and we need to...

    9. When we have two sorted lists of numbers in non-descending order, and we need to merge them into one sorted list, we can simply compare the first two elements of the lists, extract the smaller one and attach it to the end of the new list, and repeat until one of the two original lists become empty, then we attach the remaining numbers to the end of the new list and it's done. This takes linear time. Now, try...

  • In this lab we are going to complete a profile of two sorting algorithms by running...

    In this lab we are going to complete a profile of two sorting algorithms by running some tests to collect empirical data. 1. First we need to be able to generate some random integers. You can do this by including the following library : #include Now first run the following to generate a seed : srand (time(NULL)) You can then generate a random number using the function rand() 2. We will use two sort algorithms - Selection Sort and Bubble...

  • When we have two sorted lists of numbers in non-descending order, and we need to merge...

    When we have two sorted lists of numbers in non-descending order, and we need to merge them into one sorted list, we can simply compare the first two elements of the lists, extract the smaller one and attach it to the end of the new list, and repeat until one of the two original lists become empty, then we attach the remaining numbers to the end of the new list and it's done. This takes linear time. Now, try to...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT