15,612,987 members
Home / Discussions / Algorithms

# Algorithms

 Re: Making a Class Schedule Using a Genetic Algorithm Richard Deeming3-Dec-19 2:10 Richard Deeming 3-Dec-19 2:10
 Find the best path Member 146753785-Dec-19 19:45 Member 14675378 5-Dec-19 19:45
 Re: Find the best path Patrice T2-Dec-19 12:28 Patrice T 2-Dec-19 12:28
 Re: Find the best path Member 146753785-Dec-19 19:45 Member 14675378 5-Dec-19 19:45
 Help w/ recursive algorithm Member 1466815525-Nov-19 16:03 Member 14668155 25-Nov-19 16:03
 Re: Help w/ recursive algorithm Gerry Schmitz26-Nov-19 6:58 Gerry Schmitz 26-Nov-19 6:58
 Re: Help w/ recursive algorithm Member 1466815526-Nov-19 15:12 Member 14668155 26-Nov-19 15:12
 Algorithm homework - Kruskal’s algorithm Member 1465409212-Nov-19 23:41 Member 14654092 12-Nov-19 23:41
 ```When automatically checking coding exercises, we often run the programs in question against test cases, which are made up of one input and one output file. As expected, the program is fed the input file and then its output is compared with the output file. If these match for all test cases, we deem the program correct. Coming up with these test cases is tricky. Specifically, we want to create test cases for the following problem: ‘Given a complete weighted graph G, compute its minimum spanning tree T’. We have already created the desired output files containing the different minimum spanning trees, we now want to find the corresponding input files. It is known that a graph can have many different MST’s. To make testing easier, we want to ensure that the minimum spanning tree in every output file is unique for the graph described in the respective input file. The test cases also need to be able to tell apart algorithms that are wrong, but happen to find the correct MST by chance. For example, if all edges not in the MST have very large weights, a naive algorithm could find the MST by including only the light edges. Of course this algorithm would be incorrect in general. To avoid this, we want the input files to contain complete graphs G whose sum of edge weights is minimum. You need to design a program that can generate these input files. Goal: Given a weighted tree T with n nodes, find the complete graph G of minimum weight such that T ⊆ G and T is the unique minimum spanning tree of G. Assume all edge weights are integer. 1. Find an algorithm whose run time is polynomial in n. 2. Improve the complexity to O(n · log n). Hint: One way to do this is by thinking of Kruskal’s algorithm and the cut property of minimum spanning trees. can you help me to find a solution ?```
 Re: Algorithm homework - Kruskal’s algorithm OriginalGriff12-Nov-19 23:44 OriginalGriff 12-Nov-19 23:44
 Algorithm homework Member 1465409212-Nov-19 23:41 Member 14654092 12-Nov-19 23:41
 Re: Algorithm homework OriginalGriff12-Nov-19 23:43 OriginalGriff 12-Nov-19 23:43
 Help to draw recursive shape inside 2d array javascript Member 146476276-Nov-19 23:00 Member 14647627 6-Nov-19 23:00
 Re: Help to draw recursive shape inside 2d array javascript Richard MacCutchan6-Nov-19 23:24 Richard MacCutchan 6-Nov-19 23:24
 anyone know how to implement arden's theorem or the state removal method to convert an FA to a regex expression? honey the codewitch21-Sep-19 7:54 honey the codewitch 21-Sep-19 7:54
 Help with algorithmic efficiency danirdd928-Sep-19 10:52 danirdd92 8-Sep-19 10:52
 Re: Help with algorithmic efficiency Richard Deeming10-Sep-19 1:22 Richard Deeming 10-Sep-19 1:22
 Re: Help with algorithmic efficiency danirdd9210-Sep-19 12:58 danirdd92 10-Sep-19 12:58
 Re: Help with algorithmic efficiency Richard Deeming11-Sep-19 23:13 Richard Deeming 11-Sep-19 23:13
 Re: Help with algorithmic efficiency Gerry Schmitz10-Sep-19 19:00 Gerry Schmitz 10-Sep-19 19:00
 Re: Help with algorithmic efficiency danirdd9210-Sep-19 22:19 danirdd92 10-Sep-19 22:19
 Re: Help with algorithmic efficiency Gerry Schmitz11-Sep-19 16:36 Gerry Schmitz 11-Sep-19 16:36
 Sorting algorithm faster than quick sort Shuji Kaya15-Aug-19 19:36 Shuji Kaya 15-Aug-19 19:36
 Re: Sorting algorithm faster than quick sort OriginalGriff15-Aug-19 19:52 OriginalGriff 15-Aug-19 19:52
 Re: Sorting algorithm faster than quick sort Shuji Kaya16-Aug-19 22:13 Shuji Kaya 16-Aug-19 22:13
 Re: Sorting algorithm faster than quick sort OriginalGriff16-Aug-19 22:22 OriginalGriff 16-Aug-19 22:22
 Last Visit: 31-Dec-99 18:00     Last Update: 27-Mar-23 23:06 Refresh ᐊ Prev1...12131415161718192021 Next ᐅ

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.