|
There's no real-world problem, it's just a problem haha. Any ideas on what a correct dynamic programming approach would look like?
|
|
|
|
|
I have some ideas, but your professor might not like me giving you the answer.
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
Oh, this isn't actually for school/homework. Given this, would you be willing to share your ideas?
|
|
|
|
|
"Dynamic programming" does not preclude you from iterating over every possible solution (which is limited in this case) in coming up with the best solution. Turning "big problems" into smaller ones to tackle.
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
|
|
|
|
|
Right, but in this case, aren't there a lot of possible solutions? For example, if we had S1 = {A,C}, S2={A, B}, S3={A,B,C}, S4={A,C}, S5={A,B,C} then there would be 2*2*3*2*3=72 possible solutions, and this grows quickly as the number of subsets grows. I figure you're imagining a different approach. In what ways can I limit the possible solutions that I consider?
|
|
|
|
|
72 iterations is trivial. Even thousands ... that's the "dynamic" part.
You haven't "bounded the problem". You can't go through life with "Yeah, but ...".
Incomplete specs lead to incomplete solutions. And, most of the time, you benchmark first; then ask the question: is it good enough?
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
|
|
|
|
|
Sorry, I realize that I should have given an explicit bound for the problem (I have edited the original post to reflect this now). This problem can be done in polynomial time as a function of n, whereas permuting through all possible solutions would be O(3^n). Given this constraint, do you have any advice?
|
|
|
|
|
In other words, in polynomial time without an apparent way to get there; whereas with iteration, you're able to get your head around it and it may even be "fast enough" for the practical case.
(Iteration doesn't imply redoing / not using previous calculations).
A quantum computer could probably test all paths at the same time, but I'm not sure how many qbits it would need. Probably "depends".
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
modified 19-Mar-22 13:19pm.
|
|
|
|
|
Well, yeah, but iteration is O(n*3^n). This algorithm can be done in polynomial time (given in the problem statement), so I am trying to get a solution that does this. So let's please assume O(n*3^n) isn't fast enough in this context.
|
|
|
|
|
All algorithms for MST I meet, uses indirect graph and search minimum weight.
I need a bit other: my graph is directed, weights are unimportant, all are = 1.
Is not necessary find minimal tree, but ANY tree without cycles, although tree with minimal number of edges will be nice.
Most important is - graph must be directed.
|
|
|
|
|
Problem is with directed graph, because is possible many vertex links to one. It is reverse tree. This means,that is impossible leaving spanning tree.
Question is another: how detect cycles and remove all cycles?
|
|
|
|
|
#include<stdio.h>
#include<conio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]= {
0
}
,min,mincost=0,cost[10][10];
void main() {
clrscr();
printf("\n Enter the number of nodes:");
scanf("%d",&n);
printf("\n Enter the adjacency matrix:\n");
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) {
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
visited[1]=1;
printf("\n");
while(ne<n) {
for (i=1,min=999;i<=n;i++)
for (j=1;j<=n;j++)
if(cost[i][j]<min)
if(visited[i]!=0) {
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0) {
printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n Minimun cost=%d",mincost);
getch();
}
|
|
|
|
|
Hello
I have a home-made program that generates 4 BMP files (top inside, top outside, back inside, back outside) with contour lines for my luthier activity as a hobbyist from another BMP with the contour of the arch and the center line, and the height of the arch. It perfectly works, I crafted 3 violins and 3 cellos with original shapes, they work perfectly.
Now, as the program computes the altitude of each point, I would like to generate 3D models from the results.
At first, I look from a 2D point of view:
I make a list of consecutive 2D vertices (separated at a quite constant distance) that draws the contour of the instrument. I'd like a simple triangulation of the whole instrument, ie. make a 2D mesh inside the contour. I know there are algorithms like Delaunay, but I wanted to know if there is a simple way to do that.
See this picture:
https://i.servimg.com/u/f88/17/72/22/03/triang10.png
- the blue line is the contour I want to fill
- the black grid is a grid whose square size depends on the precision I want - I would triangulate the inner part of the instrument with squares (made of 2 triangles) like the green ones
- the red line show the case when the 3 vertices of a triangle would be inside the contour but should'nt be drawn as part of it is outside of the contour
Now I have 2 questions:
- Is there an easy way to detect these triangles that are partly outside of the contour, but have their summit inside?
- Is there an easy way to triangulate the remaining parts between the contour and the fully inside squares without using a complicated algorithm like Delaunay?
Thank you
David
|
|
|
|
|
I have some large scale digital maps I "transform" (uniform colors; removing noise). I can sample and rewrite 100,000,000 pixels in "no time at all". You (just) need to get some hits on different colors in your polygons.
You also have an (apparent) "adjacency rule" happening.
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
modified 10-Mar-22 22:33pm.
|
|
|
|
|
Sorry, was it an answer for me about triangulation?
|
|
|
|
|
Yeah ... dots inside your triangles.
You wanted "simple".
"Before entering on an understanding, I have meditated for a long time, and have foreseen what might happen. It is not genius which reveals to me suddenly, secretly, what I have to say or to do in a circumstance unexpected by other people; it is reflection, it is meditation." - Napoleon I
|
|
|
|
|
Sure, but I'm sorry I don't understand your answer so. Is there somewhere an explanation of that, please?
|
|
|
|
|
Writing a Sorting Algorithm
Total points 4
1.
Question 1
Assignment overview
This assignment is an opportunity for you to develop an
algorithm of your own and have someone else execute it to give you
feedback on its correctness and specificity.
You will write an
algorithm that sorts temperature data from least to greatest. To do
this, you will work through the first four of the Seven Steps.
Introduction to the data
NOAA's National Centers for Environmental Information collects global
climate data and aggregates this data to provide information on climate
trends and variability. One product they offer is a monthly regional
analysis. The following table gives "anomaly" data by continent for
January 2017. "Anomaly" means the value is the temperature difference
from the average temperature from years 1910–2000.
Continent
Anomaly (C)
North America
3.18
South America
1.36
Europe
-0.12
Africa
0.53
Asia
1.92
Oceania
0.98
Source: https://www.ncdc.noaa.gov/sotc/global-regions/201701
Assignment task
Your task is to develop an algorithm that would sort data such as these
from least to greatest. Specifically, given an unsorted set of N decimal
values, your algorithm should sort them to give an answer of the sorted
data. For this set of N = 6, your algorithm should produce:
-0.12
0.53
0.98
1.36
1.92
3.18
Step 1: Work an example by hand
Take the list
of values, and sort them by hand. Sort them the way that comes most
naturally to you. Do not research sorting algorithms or try to figure
out the most efficient method—that is not the point of this assignment.
Step 2: Write down exactly what you did
Think
carefully about how you performed the sort by hand. What values did you
compare? In what order? How did you know when you were done? Write down
these steps exactly.
Step 3: Generalize
Look for patterns in the steps you wrote down for Step 2. If you
repeated sets of steps, how could you count repetitions? If you swapped
certain values under certain conditions, what were they? Are there
variables you need to name in order to reuse? Write down your
step-by-step generalized algorithm.
Step 4: Test your algorithm
Execute
your algorithm for a different set of data, such as a subset of the
given data, data you make up, or another month's climate data, such as
February 2017: https:
Does your algorithm work for any N? Have you thought of corner cases it might need to handle, such as N = 0 or N = 1?
How to submit:
Enter your algorithm in the text box. You can work
in another program and copy/paste into the box, or you can type your
algorithm directly.
Your algorithm should be written in clear English, not C code.
1 point
What do you think?
Your answer cannot be more than 10000 characters.
|
|
|
|
|
So, did you have a question or a problem with your code?
|
|
|
|
|
I am currently taking a exercise is the shaker sort algorithm.Instead of separating two for loops, I have included a for-j loop inside a for-i loop. Please check my code.
public static void shakerSort(int array[], int n)
{
boolean swapped = true;
while (swapped)
{
swapped = false;
for (int i = 0; i < n - 1; i++)
{
if (array[i] > array[i + 1])
{
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
swapped = true;
}
if (i == n - 2)
{
if (!swappped)
{
break;
}
else
{
swapped = false;
for (int j = n - 1; j > 0; j--)
{
if (array[j - 1] > array[j])
{
int temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
swapped = true;
}
}
if (!swapped)
{
break;
}
}
}
}
}
Output:
-5
-3
5
9
11
12
15
18
I hope you can rate my code .Thank you very much
|
|
|
|
|
Member 15233409 wrote: I hope you can rate my code .
I give your code a 4.5 rating. You're welcome.
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
Hi Everyone!
I have an interesting question and I do believe this is the best resource I have for asking this about this type of problem.
I've been a SysAdmin for close to 15 years now and alot has transpired throughout these last few years due to COVID. Alot of situations have been brought to light from a political standpoint in a world where I really did not consider myself involved in (and still not too much now).
It does seem that there's alot of Skepticism on resultsets that don't favor one's position, even going as far as to weaponizing Skepticism as a premise for rejecting results.
These thoughts have lead me down the path of confronting an idea of this possible outcome verification problem that can arise depending on the subject matter and as most of you may be aware with our own US elections (But can apply to anything really). I really want to stay strongly on topic as this is specifically an Algorithm subject for me.
My question I believe is in the neighborhood of the idea of SSL, but I was wondering is there a specific Algorithm or tweak of one that can be used to verify if such a idea is possible.
My example is as follows.
We have over 330,000,000 people that currently live in the united states (maybe a lot more, I originally thought we were around 430,000,000 but should not matter as this needs to scale).
We can treat each person like a node.
If at the start of a public survey, vote, or poll can a "Public key" be published to the public a week before a Poll is rendered.
Each individual at the time of placing their vote would get assigned a HashValue and a position in line. That HashValue is a computed value that is at the time of inception of the Poll/vote/inquiry is being rolled based on the individuals unique ID (if needed) and the value selected they have chosen from the last known hashvalue from the previous vote place by the person inline before them. Once Polling/voting is closed, the ending key is also published to the public.
Now for example if you have a trusted family member in another state where one placed their value near the start of the polling and the other trusted family member placed their own value near the end (It does not have to be this way, they can place it closer), is there a such an algorithm that can be leveraged where both these members can get the publicly documented keys (both start key and the key calculated in the end), enter it into an offline system that can then run the algorithm and determine if any of the data at all or INBETWEEN The two values being placed in the chain have been altered?
I think as I am typing this out I feel like I'm describing a crypto blockchain perhaps?
Any suggestions or ideas would be appreciated! (I apologize if I am burning anyones time asking this question and hope not to trigger anyone on the subject as I specifically would like to maintain this question in the realm of Algorithms)
Thank you!
|
|
|
|
|
|
XxKeldecknightxX wrote: Now for example if you have a trusted family member in another state where one placed their value near the start of the polling and the other trusted family member placed their own value near the end (It does not have to be this way, they can place it closer), is there a such an algorithm that can be leveraged where both these members can get the publicly documented keys (both start key and the key calculated in the end), enter it into an offline system that can then run the algorithm and determine if any of the data at all or INBETWEEN The two values being placed in the chain have been altered?
If you use USB sticks, then yes. No one would trust the outcome, but technically doable.
There would not be an in "BETWEEN" on the ledger. Typically, a transaction isn't valid until it is verified by a number of clients with access to the ledger.
--edit
Basic idea of how a blockchain works;
Building A Blockchain In .NET Core - Basic Blockchain[^]
Simplest Blockchain in C#[^]
Bastard Programmer from Hell 
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
modified 9-Feb-22 18:20pm.
|
|
|
|
|
I'm writing a small routine to match strings using simple wildcards, namely "?" and "*".
So I have this dilemma:
Take the wildcard string "abc*xyz".
In your opinion, do you think that string should match only strings that begin with "abc" and end with "xyz", with any number of characters between?
Or, should that string match anything that begins with "abc" and the "xyz" at the end is irrelevant because the star matches anything that comes after "abc"?
The second case would be easy to code, and I imagine the first case would be more difficult. Which way would YOU expect the matching to work?
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
