|
Very helpful thanks !
|
|
|
|
|
Member 13585107 wrote: What logic can I apply to tackle this How about comparing the values?
|
|
|
|
|
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
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
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://www.ncdc.noaa.gov/sotc/global-regions/201702
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?
|
|
|
|
|
Do you know the difference between "help" and "I did nothing; someone do it for me"?
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Member 13567142 wrote: Your task ... should you decide to accept.
|
|
|
|
|
An algorithm that would sort data such as these from least to greatest, specifically given an unsorted set of N decimal values, and the algorithm should sort them give an answer of the sorted data for this set of N=6
|
|
|
|
|
Your homework is set to test what you know, not how good you are at begging strangers on the internet to do your work for you.
Try it yourself, and you'll probably find it's not as hard as you think. After all, it will be based on the topics you have recently covered in your course.
If you genuinely don't know where to start, then talk to your teacher.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
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
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
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://www.ncdc.noaa.gov/sotc/global-regions/201702
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?
|
|
|
|
|
No, we're not doing your homework for you.
|
|
|
|
|
How can I find the number of permutation of different types of objects?Can anyone suggest the algorithm for me?thank you!
example: There is 5 walls. I have 5 cans of Yellow paint, 3 cans of Red paint and 2 cans of Blue paint.How many possible painting solutions do I have?
|
|
|
|
|
|
Hi,
you would need some algorithm to enumerate all possible permutations; you don't need an algorithm to find the number of permutations, you only need a formula (it is n! ) and a simple loop for n (different) items.
And there's an infinite number of ways to paint anything with three kinds of paint...
|
|
|
|
|
Hi everybody, i'm developing a Modified Compress Sparse Row Matrix Class (in C++, but i think this is not important for the algorithm) you can read a short explanation of the method here I wrote the constructor as follow :
template <typename T>
constexpr MCSRmatrix<T>::MCSRmatrix( std::initializer_list<std::initializer_list<T>> rows)
{
this->dim = rows.size();
auto _rows = *(rows.begin());
aa_.resize(dim+1);
ja_.resize(dim+1);
if(dim != _rows.size())
{
throw InvalidSizeException("Error in costructor! MCSR format require square matrix!");
}
itype w = 0 ;
ja_.at(w) = dim+2 ;
for(auto ii = rows.begin(), i=1; ii != rows.end() ; ++ii, i++)
{
for(auto ij = ii->begin(), j=1, elemCount = 0 ; ij != ii->end() ; ++ij, j++ )
{
if(i==j)
aa_[i-1] = *ij ;
else if( i != j && *ij != 0 )
{
ja_.push_back(j);
aa_.push_back(*ij);
elemCount++ ;
}
ja_[i] = ja_[i-1] + elemCount;
}
}
}
and it works well ! I also wrote a findIndex(i,j) method that return the value at i,j of the whole matrix and it works fine, so i'm able to print out the whole matrix using the operator overloading () who return 0 if in this position the element is zero otherwise the right value
template <typename T>
std::size_t constexpr MCSRmatrix<T>::findIndex(const itype row , const itype col) const noexcept
{
assert( row > 0 && row <= dim && col > 0 && col <= dim );
if(row == col)
{
return row-1;
}
int i = -1;
for(int i = ja_.at(row-1)-1 ; i < ja_.at(row)-1 ; i++ )
{
if( ja_.at(i) == col )
{
return i ;
}
}
return -1;
}
the operator is defined as :
template <typename T>
const T MCSRmatrix<T>::operator()(const itype r , const itype c) const noexcept
{
auto i = findIndex(r,c);
if( i != -1 && i < aa_.size() )
{
return aa_.at(i) ;
}
else
{
return 0.0 ;
}
}
Now I need to write an alghoritm that give 2 index of position is able to insert in the 2 vector the element in the right position could you help me about ?
I wrote this one but dosn't works fine !
template<typename T>
auto constexpr MCSRmatrix<T>::insertAt(itype row ,itype col , T elem) noexcept
{
if(elem == 0)
{
std::cerr << "zero element to insert ! Exit 1" << std::endl;
}
int index = findIndex(row,col);
if( index >= dim+1 || row == col)
{
aa_.at(index) = elem ;
}
else if(index == -1)
{
for(auto i=row; i< dim+1 ; i++)
{
ja_.at(i) += 1 ;
}
if(ja_.at(row) >= aa_.size() )
{
aa_.push_back(elem);
ja_.push_back(col);
}
else if ( ja_.at(row) < aa_.size() )
{
ja_.insert(ja_.begin() + dim + row , col );
aa_.insert(aa_.begin() + dim + row , elem);
}
}
}
I hope you give me a way to write down the correct way to inert element ! thanks in advance
P.S. itype is a typedef of std::size_t !
|
|
|
|
|
I am developing a project that is meant to improve feature smoothness in heightmaps that represent terrain from multiple maps at different resolutions from satellite imagery.
I know how to use the data in the maps to detect the shorelines. What I want to do however is turn shorelines into edges (lines) that do not intersect at all so that I can smooth them from the blocky look they have outside the USA where satellite resolution is not as good. Most of the time this is fairly straightforward but the lack of good resolution on some of the height maps may result in islands touching the coastline. I want to make sure that the coast on the island follows the outline of the island while the main coastline stays the main coastline. Basically I believe this would boil down to making sure they don't intersect. This area of programming is completely new to me. I want to understand the best algorithm for 'untangling' intersections when more than one coast line happens to touch.
|
|
|
|
|
A question arose here at work where they would like to find datagaps in timeline datasets. This can be from database or from images. (eg each 6 hours there's an image).
Basically they want a "pseudocode" function that would work across technologies.
in: at least an array of datetime stamps
out: a list of gaps in the list.
This is what I have so far (it's C type language, but no language in particular):
function FindGaps(DateTime dts_start, DateTime dts_end, int amount, string interval, Array list2check){
Array listreference<DateTime, boolean>;
for(DateTime dts = dts_start; dts < dts_end; dts += amount (interval)){
listreference.Add(dts, false);
}
for(int i = 0; i < list2check.length; i++){
if(KeyExists(listrefence, list2check[i])){
listrefence[list2check[i]]) = true;
}
}
return listrefence;
}
and some of my own thoughts:
problems/remarks:
* You cannot uniformally convert months, years, ... eg to milliseconds (january has different amount of milliseconds than february, ...)
* not all datasets have uniform progression (timegap difference between points)
* datasets passed should not be too large
* the key check should be on similar interval (minutes = minutes eg. 00:00 = 00:00, but 00:00 != 00:00:01)
* adding the fill value can also mark the gap as true / false / invalid eg.
* should you "remove" values that are in between gaps? eg. there are 100 values in a row = false. Should we only keep first and last value?
* This will not be very fast: can we loop from start --> end with amount (interval) and check if DateTime is in list2check? (how will we return?)
* better would be if there are points in between 2 points of the reference list, but how to do that practically? (could potentially fix point 2 to some extent)
Does anyone have experience in this? any tips or pointers?
(PS: I have a nice query that can do this in a (postgresql) database, but this does not fit file based datasets)
thanks!
|
|
|
|
|
I'm not sure I completely grok what you're trying to do, but what's wrong with comparing the difference between consecutive timestamps with your "required" interval?
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
|
|
|
|
|
Put all your "samples" in a queue.
Pop the first sample; that is your starting date/time.
"Predict" the next sample by adding the samplying rate.
"Peek" into the queue to see if your prediction was right: if not, add prediction to "missing", else pop the predicted value from the queue.
Repeat until queue exhausted.
(Memory streams can also be employed; keeping "positioning" in mind).
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
In its "Prefix sum" section, Codility proposes the following problem. I don't see how to solve it within the constraints, that are O(N+M), and O(N) for space complexity. I know I should use the prefix sum technique, but I would need more hints. I'd like to not be given the solutions, but hints that would help me guide my thought process.
--
A DNA sequence can be represented as a string consisting of the letters A, C, G and T, which correspond to the types of successive nucleotides in the sequence. Each nucleotide has an impact factor, which is an integer. Nucleotides of types A, C, G and T have impact factors of 1, 2, 3 and 4, respectively. You are going to answer several queries of the form: What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?
The DNA sequence is given as a non-empty string S = S[0]S[1]...S[N-1] consisting of N characters. There are M queries, which are given in non-empty arrays P and Q, each consisting of M integers. The K-th query (0 ≤ K < M) requires you to find the minimal impact factor of nucleotides contained in the DNA sequence between positions P[K] and Q[K] (inclusive).
For example, consider string S = CAGCCTA and arrays P, Q such that:
P[0] = 2 Q[0] = 4
P[1] = 5 Q[1] = 5
P[2] = 0 Q[2] = 6
The answers to these M = 3 queries are as follows:
The part of the DNA between positions 2 and 4 contains nucleotides G and C (twice), whose impact factors are 3 and 2 respectively, so the answer is 2.
The part between positions 5 and 5 contains a single nucleotide T, whose impact factor is 4, so the answer is 4.
The part between positions 0 and 6 (the whole string) contains all nucleotides, in particular nucleotide A whose impact factor is 1, so the answer is 1.
Write a function:
def solution(S, P, Q)
that, given a non-empty zero-indexed string S consisting of N characters and two non-empty zero-indexed arrays P and Q consisting of M integers, returns an array consisting of M integers specifying the consecutive answers to all queries.
The sequence should be returned as:
a Results structure (in C), or
a vector of integers (in C++), or
a Results record (in Pascal), or
an array of integers (in any other programming language).
For example, given the string S = CAGCCTA and arrays P, Q such that:
P[0] = 2 Q[0] = 4
P[1] = 5 Q[1] = 5
P[2] = 0 Q[2] = 6
the function should return the values [2, 4, 1], as explained above.
Assume that:
N is an integer within the range [1..100,000];
M is an integer within the range [1..50,000];
each element of arrays P, Q is an integer within the range [0..N − 1];
P[K] ≤ Q[K], where 0 ≤ K < M;
string S consists only of upper-case English letters A, C, G, T.
Complexity:
expected worst-case time complexity is O(N+M);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
modified 6-Nov-17 5:26am.
|
|
|
|
|
S is a string; or an array of characters; characters which "convert" to impact numbers.
P and Q are (3) "substring ranges" into S.
The subset / substring of S will contain one or more "MIN" impact numbers.
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Wow.
There are so many things I love about this question. I'm going to save it. And I'm going to try if not to solve it, then to demonstrate why I can't solve it, using code that consumes some finite computation space or time.
I'm mucking about with a self-modifying linear bounded automata interpreter/compiler i've built and i am crap at most math, but just good enough at the right kinds of math to know how to build this problem and it express it through that.
And you've asked what may be exactly the question I need.
How many times can someone say that?
Thank you =)
|
|
|
|
|
hi,
im pretty rusty with algorithms and i was posed this question. how do I find the most amount of pages i can buy from a list of books within a certain budget. I got as far as sorting the list based on cost, then by no. pages. then i was thinking of creating a map with the cost as key and a list of books at each price. then sorting each keys list based on no of pages. I think im headed in the right direction but iam not quite sure how to complete the exercise? can someone help me of point me in the direction of the correct algorithms i should be using? cheers!
|
|
|
|
|
This is homework, and we don't do that for you - it's an exercise to get you thinking about problems, and working out how to solve them. If we give you the "correct algorithm" then that defeats the point of giving you the homework!
So instead, sit down with a pencil and paper, and work out how you would do it for yourself manually.
Hint: would knowing the price per page help you come up with a solution?
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
its not homework. its something im trying to implement in an android app im building! its an algorithm for an in built calculator to check how many pages i can buy from a list of comics from the marvel api.
|
|
|
|
|
You at first have to think about what is important for you :
- a special order
- lowest rest money
- maximum count of books
Dependent on this selection you would build different List's.
To be able to decide which List could be the best you must build different Sub-Lists - example :
- you have 100 € and you could buy Book 1 (40 €), Book 2 (35 €), Book 3 (45 €), Book 4 (20 €)
- now one List could be Book 1,2,4 - another one could be Book 2,3,4 - or Book 1,3 ...
Now ... which List contains the best results for you ?
|
|
|
|
|
its based on most pages in a book that i can buy for a certain budget. think its the 0/1 knapsack problem.
|
|
|
|
|