Right
#numerical-analysis
topaz garden
rare schooner
in matlab, can i write a for loop like
for i = 5:-1:1
to have i run backwards from 5 down to 1 in each iteration
indigo musk
yes
olive phoenix
is this the right channel for this? I am pretty confused about all of this hw, just looking to be pointed in the right direction
olive phoenix
yes
acoustic slate
substitute it in for $p_{n+1}$
pine jettyBOT
kickpuncher:
olive phoenix
substitute pn+1 in the sequence formula or the function formula?
these are the two I was taught
acoustic slate
yep, that sequence formula, while noting also that for the sequence defined for pn+1 , you just add one to the subscripts
for what its worth I'm in numerical analysis 1 right now so I'm not 100% sure where to go with this lol, I just know that to do these kinds of problems we substitute the sequence in. We also know that as n → inf, f(pn) → 0
pine jettyBOT
ctooley21:
olive phoenix
well yeah I did that a little wrong, but I think you can see what I mean
olive phoenix
nw!
acoustic slate
I was hoping this would be enough to get a spark going lol
olive phoenix
yeah I think so, plus I just checked our piazza and the prof gave a tip to use taylor's theorem? so guess I'll do some research on that lol
acoustic slate
yeah that's from that first line in the screenshot
where the error term for the sequence is given by f''(xsi(p)) etc term
$f(p^) = f(p_n) + f'(p_n)(p^ - p_n) + \frac{f''(\xi (p^))}{2}(p^-p_n)^2$
where I let $p^*$ be the actual root
pine jettyBOT
kickpuncher:
acoustic slate
@olive phoenix can you go from there?
pine jettyBOT
kickpuncher:
olive phoenix
yes, thx!!
acoustic slate
sweet!
I have an exam in Numerical today lol, so I'm glad I saw your question and had the opportunity to work through it myself
olive phoenix
@acoustic slate could you help with another?
Not sure how I'm supposed to find the interval for this one
Notice the hint at the bottom
I need the interval so that I can prove my function is a contraction mapping and cont on the interval
olive phoenix
will pay 4 tutor
this hw is due tomorrow along with an exam in a separate class :/
pure jasper
Okay
brave crypt
Hi, new here,
is there not a video compression format which is lossless by the use of space filling curves? Doesn't even have to be completely digital, wouldn't the application of these curves also produce significant advantages on say old electron-beam TVs? Or is this already being used? Seems awfully efficient to me, so far it was only of interest for me in topology
Please @ me in reply, thanks
dawn viper
I doubt so
Too many turns needed for e- beam tv
I don’t quite see any possible compressing advantage tbh
finite wasp
Does anyone here have an idea of how to use tensors?
dawn viper
your question is?
rare schooner
does anyone understand the Hungarian method for the transportation problem?
the way our teacher explained it to us it feels like everyone understood what it entailed except me
spring plinth
transportation problem?
@rare schooner What's this transportation problem?
http://web.tecnico.ulisboa.pt/mcasquilho/compute/_linpro/TaylorB_module_b.pdf
Is this the formulation for the transportation problem?
spring plinth
Is there some sort of requirement of the number of sources and sinks and the total supply/demand being equal?
@rare schooner
just checking my concept on the problem first before I figure how to apply hungarian
rare schooner
yes the problem is balanced
i just don't understand what the Hungarian method IS
like what to do in it and how to do it
spring plinth
just total supply/demand being equal, I suppose
rare schooner
yes
spring plinth
Ah okay
Firstly, the main idea is
if we decrease the cost of each item in any row/column by the same amount, it would not affect the assignment
(at least, that's how I learnt it)
rare schooner
that's not the part i'm confused about
spring plinth
Then, let's jump to the part you are confused
rare schooner
what confuses me is what happens AFTER the cost matrix is reduced
like
can you give me
in your own words
a description of the algo
spring plinth
okay, so after we reduce the cost matrix, (and all entries are nonnegative), then we hope to find enough zeros scattered around to form an assignment
if there isn't we would need to transform the cost matrix some more
that's what I understand
rare schooner
well
yes obviously if there's enough zeroes to do all the assignments we need
then yeah
that's obvious
but if there aren't
then just what the fuck would we do
how do we transform the matrix
spring plinth
ah
rare schooner
and whatever we do, why is it that we do that and not something else
spring plinth
So, now, let's cover all the zeros with a minimal number of rows and columns. If the minimum number of rows and columns needed is equal to the number of things we need to assign, by Konig's there should be an assignment
(I think)
So, the uncovered elements would have nonzero entries
rare schooner
who's Konig
spring plinth
Take the smallest uncovered element and say the value is v.
For every uncovered row, subtract v
For every covered column, add v
rare schooner
NO!!! you've lost me already.
spring plinth
Here's Konig's
rare schooner
YOU'VE LOST ME.
rare schooner
So, now, let's cover all the zeros with a minimal number of rows and columns.
what does this mean
spring plinth
Ah I see why there may be a problem here
spring plinth
because typically we use Hungarian for assignment problems with the same number of sources as targets
The reason is because we want to not touch them
But here, multiple rows may be combined together. The idea is still the same
spring plinth
because we want to decrease the other elements to make 0
rare schooner
because typically we use Hungarian for assignment problems with the same number of sources as targets
why
because we want to decrease the other elements to make 0
why
spring plinth
Multiple rows of the assignment problem are combined together in the transportation problem
spring plinth
ah
rare schooner
SORRY FOR BEING RETARDED
spring plinth
maybe we should start with the assignment problem before we do the transportation problem
that might help a bit
rare schooner
but i don't want the assignment problem
i want the transportation problem
i think i remember the teacher explaining the latter in a way that didn't rely on the former
spring plinth
I'm not the teacher
rare schooner
YOU KNOW WHAT NEVERMIND I'LL JUST FAIL.
I'LL JUST FAIL THE CLASS, GET THROWN OUT OF UNI, AND DIE OF HUNGER IN THE STREETS.
spring plinth
Well, if failing is easier than understanding the assignment problem, I guess go ahead.
spring plinth
If you are retarded, let's take it slower
Let's go through the assignment problem first, okay?
rare schooner
i only have like 20 minutes before class
spring plinth
It should extend nicely
rare schooner
i only have like 20 minutes before class
spring plinth
So assignment problem is a special case of the transportation problem
rare schooner
will you be here in 4 hours
spring plinth
No though
rare schooner
well fuck
you're not gonna be able to explain both problems to be in 20 minutes
forget it
spring plinth
It's where every source supplies one and every target demands 1
that okay?
So, for now it's simple each source, we only need to pick one target
rare schooner
no
spring plinth
So, we do the hungarian algorithm until you are stuck there
rare schooner
you won't have enough time
to explain this to me
so i don't think it's worth trying
spring plinth
well, it's just a special case of the transportation problem
It's not an entirely different problem
rare schooner
why are you still trying to explain the transportation problem or the assignment problem to me
you won't have enough time for that
spring plinth
you know the transportation problem and I have shown how to express the assignment problem in terms of the transportation problem
I suppose there's no need to explain the problems now
next would be the hungarian algorithm
rare schooner
i don't know the transportation problem
i don't know how to solve it
i'm too dumb for that
spring plinth
you know the formulation?
for the special case, we want to find a bunch of rows and columns that cover all 0s
If we treat it as a bipartite graph, where each 0 is an edge, this would be a minimum vertex cover.
By Konig's, |minimum vertex cover| = |maximum matching|
So, if covering all zeros uses n rows/columns, you are done.
rare schooner
but that's a real number
rare schooner
what
no i don't get it
no
class is about to start
sorry for wasting your time on this bullshit
spring plinth
you said you had 20 minutes 6 minutes ago
rare schooner
ok well
no
it's not that class is ABOUT to start
it's that i have shit to do immediately before it
spring plinth
welp
rare schooner
sorry
sorry for wasting your time, sorry for being retarded, sorry for whining like a baby about all this
sorry
fallen echo
Hi, anyone have any idea about how to help me implement n dimensional transformations in python?
nova cedar
the main question is, why?
dusky urchin
numpy has a matrix package
just use it
rotation doesn't generalize to big dimentions in an intuitive way
n dimensional rotations are matrices of SOn(IR)
so they are orthogonal, and of determinant 1
@fallen echo
summer egret
yea if I’m understanding your question right you just need matrix multiplications so use numpy
dusky urchin
you can rotate stuff a radians along an axis with matrices like
cos a -sin a | |
sin a cos a | only zeros |
__________ |____________|
only zeros |ones on the
|diagonal( In)
.... |zeroes elsewhere
__________|
well that's a mess
summer egret
also, there’s different definitions of rotations in n-dimensions, I learned it as a linear map which is a rotation on a 2D subspace, and the identity on its orthogonal complement
(which means that the composition of two rotations may no longer be a rotation)
that’s what my linalg prof defined to be a rotation
is all I’m saying
also “along an axis” doesn’t make much sense in higher dimensions
dusky urchin
it does
dusky urchin
if {x| f(x) = x} is a line then we say the rotation f is along that line
summer egret
anyway my point was merely to point out that not everyone defines “rotation” the same way
yea but in my example that may not be a line
it will only be a line in exactly 3 dimensions
in 4 dim it’ll be a plane and so on
the dimension of the orthogonal complement of a plane is n-2-dimensional
dusky urchin
oh ye
summer egret
I think some books define what I call a rotation to be a “simple rotation”
or similar terms
dusky urchin
so it's some conjuguation of the matrix i tried to write, right?
summer egret
a permutation you mean?
dusky urchin
some P my thing P^-1 for P in GLn(IK)
dusky urchin
P in SOn yeah
summer egret
I think it may have to be angle-preserving
dusky urchin
yeah so On
summer egret
yea
dusky urchin
anyway i'm not sure he knows about all that stuff
fallen echo
Sorry I'm here now
And I don't know about all that stuff, I have seen mention of rotation matrices online a lot
I'll look further into rotation matrices but I'm honestly not quite sure at the moment about how to implement that into a function that works regardless of dimensionality
fallen echo
@summer egret
Would you be able to help me implement that in python at all?
or @dusky urchin
dusky urchin
a matrix reperesents such a function : if M is a matrix, X->MX is a function (where X is a point of your set represented by the vector of its coordinates in R^n)
when M is orthogonal and of determinant 1 it's a rotation
it's already implemented you just need to set M = numpy.array( your matrix) and X = numpy.array(your vector) and do something like M*X
see numpy doc for the actual commands
fallen echo
It's the vector part that I don't understand
Not because you're being confusing but because I haven't actually been taught that, and therefore I don't know how to arrive at a rotation matrix from n-1 angles and a center of rotation
Never mind doing that in python
dusky urchin
@fallen echo https://en.wikipedia.org/wiki/Rotation_matrix you can look at that it's pretty good
as you can see it gets hairy in just dim 3
and this for vectors https://en.wikipedia.org/wiki/Vector_space
read the second thing then the first
fallen echo
I understand vector space - thanks for the links I'll give reading about rotation matrices a shot again
fallen echo
Still doesn't help... I just can't see how to implement that n dimensionally
rustic oracle
In the ``Introduction to Algorithm'' book (p. 26), it seems that there is a mistake, but I need someone to confirm it for me.
According to the author, $n=A.length$ and the notation
[
\text{\textbf{for} } j=2 \textbf{ to } A.length
]
is the for-loop that make $j$ be equal to the values present in the interval $[2, A.length]$. However, in the computational cost analysis of the insertion sort algorithm, he states that the for loop will be executed $n$ items which I think it is false and therefore not correct. Let's suppose that the size of the list is 3, the for-loop body will be evaluated $3-1$ times, since we start iterating it starting at the second element. Thus, at line 1, $n$ mustn't be there and $n-1$ does.
\textbf{Would someone please confirm that I'm right? or perhaps I've misunderstood something}
Note that the book ``Introduction to Algorithm'' is $1$ base indexed (i.e. the initial element of a sequence is assigned the index $1$.)
pine jettyBOT
rsalva1998:
rustic oracle
UPDATE: I think I've got it. It is the total amount of time the for loop condition is evaluated. Let's suppose that a list contains 5 elements. The for-loop that goes from $2$ to $5$ will make the condition $x \leq 5$ to be evaluated $5$ times, since the last evaluation (the one that makes the for-loop to stop) is also counted.
However, if this is true, a new question arises... Why do we count the total numbers of times the for-loop condition is evaluated and not also the sum to the index, which is also a computation and therefore make the computer to perform some operations.
tall wolf
Is this the right place to ask about regular expressions?
I'm trying to find a regex that satisfies the condition (e.g. with a password) that there is at least one letter, at least one digit, and it must be at least three characters long. But I can't think of doing it without making the regex crazily long.
e.g. (([a-z]|[0-9])*[a-z]([a-z]|[0-9])*[0-9]([a-z]|[0-9])+)|(([a-z]|[0-9])*[0-9]([a-z]|[0-9])*[a-z]([a-z]|[0-9])+)
And I'm almost certain that's wrong anyway
nova cedar
it can help to think about the finite state machine, at the very least in the sense that they're quite restricted
you can either take a letter, then a digit or the reverse way around, but since a FSM doesn't have a stack there's no way to really "count"
so you are forced into making the cases really messy where you have to consider a 3rd accepting letter
tall wolf
Yeah, so would you need to tack on a + to the end, so that you either take a letter, then a digit (or the reverse way around, as you said), as well as a + (one or more) on the end, as that will make it a total of at least 3?
nova cedar
well are you accepting passwords with non letters and non numbers
like # or $ for instance
or even underscores etc
tall wolf
no
just letters a-z and numbers 0-9, it's purely theoretical
I'm not implementing it into anything
nova cedar
oh
tall wolf
it needs to be at least 3 chars long (where a char is either a-z or 0-9) and contain at least 1 digit and at least 1 letter
nova cedar
that makes a difference at least, since then you know you will only be taking alpha numeric
I think you're leaving out some cases though
kind of a mess to read the regex cause I don't do it every day but I think you are missing cases where the first two are letters and the last is a number
aa3 wouldn't accept for instance, since you're forcing the first two to contain the digit and number, actually one sec let me read it more carefully
yeah just tested it
plug your regex in and then you can type up some examples below
anything to do with counting is a hassle with regex
nova cedar
no yours is correct
it just doesn't accept aa3
it will accept a3a though
I have a solution in mind now gonna type it up one minute
tall wolf
Ok, thank you, because I'm really stuck haha... it can be very confusing staring at all the same things for so long and not seeing anything
nova cedar
([a-z]+[a-z]+[0-9]+)|([a-z]+[0-9]+[a-z]+)|([0-9]+[a-z]+[a-z]+)|([0-9]+[0-9]+[a-z]+)|([0-9]+[a-z]+[0-9]+)|([a-z]+[0-9]+[0-9]+)
you could do it a slightly different way than this, but this is probably clearest
tall wolf
ahh I see
nova cedar
it's just 6 blocks of every combination of at least one
tall wolf
so you're just iterating through the 6 potential combinations
nova cedar
yeah, we could make it like more condensed but
nova cedar
yeah it's kind of odd cause it's not like you can just do anything, but after a while you get the hang of it
there's a lot of cool stuff in my opinion with these though
tall wolf
Is there any other way to do this?
because I was given a hint to look into the two cases
but I don't understand what the hint is for
two cases being...?
nova cedar
not sure, there might be some other ways depending
tall wolf
What if you wanted at least 4 chars? It would get a lot more difficult, wouldn't it?
nova cedar
like we could put two separate paths one where the first one is a letter and one where the first one is a number
and in each of those two cases
that's like 3 and 3
letter -> number number OR number letter OR letter, number
then same but number and letter flipped
that might be how they're thinking about ti
tall wolf
and if you're drawing a finite state machine from the regex you just gave
nova cedar
yeah, ultimately when you have things to count, you're stuck
tall wolf
would you just have 6 different paths, leading to 6 separate accept states?
nova cedar
you basically have to put the counting into the machine itself
you can't make the fsm count for you
tall wolf
So would you have 6 different paths?
nova cedar
yeah
tall wolf
And there would be a unique accept state at the end of each path?
tall wolf
Yeah
nova cedar
luckily if you know how to do one case of something with a FSM
then there are a bunch of conditions that you can use like closed under union, intersection, reverse string, etc
so like you can kinda glue things together with those more higher level thinking about what's possible, if that makes sense
tall wolf
Yeah that sorta makes sense, thanks so much for the help 🙂
nova cedar
yeah, definitely if you have time this is a really fun set of lectures
first several lectures are about showing that deterministic finite state machines, nondeterministic finite state machines, and regex are the same along with some examples of what they can and can't do etc, pretty insightful stuff
tall wolf
Thank you!!
tall wolf
Maybe a bit of a simple question, but if you have some state, and it has a transition (e.g. b) that loops back into the same state, and another transition from that state to a different state, is that a NFA or DFA?
e.g. (b)*b is what I'm trying to say
Because you'd have one transition for b that loops back into the same state, and another transition that moves it along to a new state. But since there are two different transitions for the same letter, does that make it a NFA?
Just because I'm trying to compare the regex (a|b|c)*a(a|b|c)* to (b|c)*a(a|b|c)*
Is it that the first one will give a NFA whilst the second will give a DFA?
nova cedar
NFA and DFA are equivalent
you can always turn a NFA into a DFA really
so as far as what the computer does when you give it the regex, I don't know that's some kind of specific implementation detail, I don't know if modern programming languages or compilers or whatever have stuff in place to optimize it or not between what you put in and when it runs though
I don't know if that answers your question or not
when you move up the chomsky hierarchy then the difference matters, a deterministic turing machine is not equivalent to a nondeterministic turing machine for instance
in one of the lectures he actually goes through the proof of how to make a DFA from a NFA in general I believe
tall wolf
So in general there are multiple regexes that satisfy the same language?
And yes I’m somewhat familiar with the determinisation algorithm
nova cedar
yeah, definitely, that happened with your original problem
an easier example is, [a-z][a-z]* is equivalent to [a-z]+
tall wolf
Ah, yes!
But if you were to draw those two regexes as finite state machines, would the first be a NFA and the latter be a DFA?
Because you have the b looping into the same state, and b exiting the state to a new state. Does that make it a NFA?
nova cedar
I suppose, I think it depends on how you convert it into a FA
I haven't done this kind of thing in a while so I don't actually remember how to convert between the two lol
but because there's an algorithm to go from NFA to a DFA we could in principle just make our algorithm for constructing a FA from a regex always make the DFA
tall wolf
Yeah, that makes sense
So if you had a finite state machine like this, is this a NFA or a DFA by definition? That’s what’s mainly confusing me. I don’t know whether this is DFA or NFA
nova cedar
yeah it's an NFA
tall wolf
Ok, thank you 😁
nova cedar
I forget but I feel like you need an arrow for a starting state pointing to where you start and a circle for the accepting state
the fact that you have 2 of the same thing outcoming from one place is what makes it undoubtedly NFA
DFA you have no choice
tall wolf
Yeah, this was just like a subset of the whole finite state machine I was using to show my point
nova cedar
cool
tall wolf
Ok, that makes lots of sense. Thank you!
nova cedar
I guess the fun thing is remake this same thing as a DFA
haha yeah glad to help, I don't know much in this area really, so if you get further in I might try to learn stuff with you if you don't mind
tall wolf
I was just questioning it because there was only one transition going to a new state
nova cedar
what you've drawn is b* I think
nova cedar
wait, I guess b+
since you need at least one b to get to the right which I assume is the accepting state
tall wolf
Yes sorry b+ lol you’re right. I’m tired haha
tall wolf
Nahh it’s fine!
So it’s still a NFA despite only one b transition going to a new state?
How would you make a DFA for b+?
I think the latter question is better
nova cedar
yeah, because I can do b to go either way, determinism means no choice at all
yeah kind of tricky isn't it heh
part of the fun, I'll try to work it out myself and we can see
tall wolf
Is it even possible to make a DFA for b+? 😂
tall wolf
How so? Also sorry I gotta brb a couple hours but will be back after
nova cedar
every single NFA can be turned into a DFA
it's simpler than you might think, let's pretend there are only strings with a and b on them
then you can make a tree of possibilities
tall wolf
Oh wait
All you’d have to do is make the loop on the accepting state for b+ lol
Instead of the initial state
And for b* you could make the same but with the initial state also being accepting
summer egret
this should do b+ deterministically right
and this b*
(also only just learning about automata)
tall wolf
Yeah, I suppose that is more of a DFA
It depends on whether you have an alphabet including just b, or if it includes other letters, e.g. {a,b,c} in which case what you just drew was a DFA and what I drew above was a partial DFA (as not all possibilities were explicitly addressed)
summer egret
yea we so far only looked at DFAs over interesting alphabets :P
as in, at least two elements
and by at least I mean exactly but that should be without loss of generality
since you could transform {a, b, c} into {aa, bb, ab} and roughly double the size of the machine, right?
tall wolf
I mean I don’t think changing the alphabet, given the same number of elements in the alphabet, would change the size of the machine
summer egret
no I mean change it to only having two symbols
aa is now a string of two symbols. the length of every word doubles
but we’ve reduced the number of letters
I’m just trying to intuitively state that finite alphabets with more than 2 letters aren’t in some way more interesting than those with only 2 since you can just reduce to only having two letters
short thunder
I have to come up with a project idea for my special topics course of Big Data, likely involving SVD, Fourier Transforms, and or Neural networks. Anyone have recommendations?
fallen echo
Some sort of fourier forecasting vs neural network forecasting perhaps.
rare schooner
question
i need an n by n matrix consisting of 0s on the diagonal and 1s elsewhere
how much of a dirty hack is it to do that as ones(n) - eye(n) in matlab
ok actually no i have a more important question
is there a clean way to get the largest element in a matrix along with its position
vital mantle
Suppose A is the matrix.
max_value = max(max(A));
[m,n] =find(A==max_value);
This should work @rare schooner
rare schooner
too late i wrote my own function to do it
vital mantle
Okay!
rare schooner
no no i figured it out lol dw
vital mantle
Alright!
tall wolf
Do 32-bit floating point numbers satisfy the distributivity law (i.e. a*(b+c) = a*b + a*c)? I can't think of a solid way to prove it or figure it out definitively :L
My intuition tells me no but I'm not sure why
One way I could see it is if b is very large and c is very small, such that b+c=b, if a were very large it would "presumably" not work?
sage vapor
my gut says they might differ in the last binary digit
you can just take random floats and find counter examples very quickly
tall wolf
I’ll try and do that
What about the law of commutativity (a+b=b+a). For 32-bit float points I feel like that would always be true, no?
tall wolf
Thanks, and also I have a question about Galois Fields if anyone knows anything about them? Are Galois Fields only used with prime numbers, i.e. the notation GF(p)... is p only ever prime? It would make sense to me, but I think sometimes I see people write things like GF(4) when 4 isn't prime? Is that right or not?
tall wolf
How is that? GF(4) doesn't have a multiplicative inverse for 2, does it? So how can it be a field?
Or maybe I'm confused about the definition of a Galois Field
I thought GF(m) was the integers mod m?
sharp lotus
it's not
GF(4) is characteristic 2
it's a degree 2 extension of Z/2
in general GF(p^k) is characteristic p
and the unique degree k extension to Z/p
namely GF(p^k) is all the roots of x^p^k - x in Z/p
for example GF(4) is the roots of x^4-x = x(x^3-1) = x(x-1)(x^2+x+1)
so it is (Z/2 [x])/(x^2+x+1)
tall wolf
So in GF(4) you'd have elements {0, x, x-1, x^2+x+1}?
What about GF(9)?
I'm not sure I understand :L
Is what you just explained anything to do with this?:
sharp lotus
the root of x is 0
the root of x-1 is 1
there's two more elements
the roots of x^2 + x + 1
you can call one a
and the other is a+1
so you have {0,1,a,a+1}
tall wolf
Ah yeah I see, my bad
Could you help explain those addition and multiplication tables in that link I sent? I don’t understand the answer they gave
Also how does x^3-1 = (x-1)(x^2+x+1)?
sharp lotus
uhh
you just multiply lol
and for the table
you know how 0 and 1 work
so you just need to figure out what the product of the roots is
well
first off
a^2 = -a-1 = a+1
since a is the root of x^2+x+1
that's how you get the other root a+1
and then
a*(a+1) = a^2 + a = 1
and that's all the mult table
tall wolf
Sorry I see my error in multiplying by now... the effect of very little sleep lol. I think I’m getting this but thanks so much for the help! Will look at it more when I’ve had more sleep aha
Last question... why do people write B and D instead of a and a+1? It makes no sense... is it just to be confusing on purpose or “abstract” it out? You can’t actually work out the answer without doing the a & a+1 first and then replacing them with B and D, right?
sharp lotus
i dunno
it's not that "people" write B and D
it's just that particular answer
people usually write alpha for a root
and then the others are alpha + i
for i in Z/p
for a quadratic extension anyway
copper smelt
copper smelt
nvm, solved
tame trellis
cheater
copper smelt
@tame trellis
A mathematician doesn't jumps to the conclusion without going through all the facts?
quiet sparrow
we don't tolerate academic dishonesty here but I think horse was a bit too quick to jump on the gun here. apologies for that
just keep that in mind okay
copper smelt
It is not cheating. Go to their website.
copper smelt
tame trellis
asking for help in an ongoing contest in public
copper smelt
so, there you go
copper smelt
If you still think that's cheating then, I am sorry. I have love for Mathematics and would never cheat to win any competition.
tame trellis
anyway
it's an ongoing contest
it's equivalent to a test
why would you ask for help
if you think you can't solve it, ask for help after the contest ends
copper smelt
I was able to solve it.
tame trellis
it's only 2 more days anyway
I said if you think you can't solve it
fair amount of discussion on asking in public here
copper smelt
As I have said, I would never cheat in an exam. If you still think that's cheating then, I am sorry. I have love for Mathematics and would never cheat to win any competition.
Totally on you guys. Thank you for listening.
tame trellis
yes, it's ok, as long as it doesn't happen again, I have no problem, glad you are cool with it 🍻
copper smelt
Thank for giving the chance to be part of this server again!
green tinsel
tall wolf
@sharp lotus What I don’t understand is how you’d be able to work out the addition/multiplication tables for GF(4) by using arbitrary letters or symbols for the 3rd and 4th elements of the field, without first using polynomials and then replacing them with some other symbol like B and D?
Since how can you apply field laws with letters or symbols? Or am I looking at it the wrong way? Because at least with polynomials you can work with them like you would numbers
tall wolf
But how do you work out the result of B*B for example, if you have B as the third element? You can’t use normal laws to do that calculation, can you? Or do you do it with polynomials first and then replace them with B and D (or whatever else you decide to call the other elements)?
tall wolf
Could you please help me with one last thing? How do you apply the same logic for finding elements of GF(4) to finding elements of GF(9)? Based on what you said you have to get the roots of the polynomial x^9-x @sharp lotus
in Z/3
x^9-x=x(x+1)(x-1)(x^6+x^4+x^2+1)
Don't you want it in the form x(x-1)(x-2).... though? So you have the first 3 roots as 0, 1 and 2? I think I'm a bit confused. I understand it for GF(4) but not applying it to other numbers of elements, e.g. GF(9) which is characteristic 3
dawn viper
usually the construction is like GF(4)=GF(2)[x]/P where P is some irreducible degree 2 polynomial isnt it?
tall wolf
Yes
But I don't quite understand how to apply that to other non-prime finite fields, like GF(9)... how do you work out what the elements are? I know from Googling that they are {0, 1, 2, a, a+1, a+2, 2a, 2a+1, 2a+2} and the irreducible polynomial is x^2+1 but I don't understand how to work out either the irreducible polynomial or the set of elements?
dawn viper
GF(9)=GF(3^2)
Maybe first calculate |GF(p)[x]/P| where P has degree n and is irreducible
median plinth
Any irreducible polynomial works @tall wolf
It's a theorem that they'll all give you isomoprhic fields
The set of elements is always polynomials with coefficients mod p that have degree at most n-1
tall wolf
Ok, thank you so much 🙂 @median plinth
median plinth
Just remember
The ways that the polynomial will add and multiply are different than what you'd normally think
tall wolf
Yeah, because of modulo, right?
sharp lotus
Factor out the poly
You were almost there
Anyway if you let a be a root of the degree 6 poly then you can compute the rest to be 2a, a+1, 2a+1, ...
x6 + x4 + x2 + 1 = (x2 + 1)(x4+1)
Etc
tall wolf
Ok, thank you, although I don't quite understand how you link the roots 2a, a+1, 2a+1 to (x^2+1)(x^4+1) etc. (i.e. how you derive them)
tall wolf
Ok, I’m probably over complicating it. I understand it a lot more now though, thank you 😄
green merlin
need a lot of help with this problem. im not getting how im supposed to go about doing this
green merlin
<@&286206848099549185>
fallen echo
Hi, can anyone help me with this?
https://stackoverflow.com/questions/58419034/python-how-to-reflect-many-n-dimensional-points-in-two-n-dimensional-lines-cons
<@&286206848099549185>
It'd be helpful if you could ping me if you'd like to help, so I don't miss your response - thanks.
dry topaz
Could someone share some prerequisites for understanding quaternions?
Aka some research papers or good tutorials to really understand the concept/topic¨
summer egret
really, if you understand complex numbers, quaternions aren’t any more complicated, they’re just harder to visualize
https://eater.net/quaternions in terms of visualization/intuition, this is all you need
dry topaz
thank you
tall wolf
I'm aware of the proof that the language containing of words with a's followed by equal number of b's is not regular (e.g. ab, aabb, aaabbb, etc.), but I don't understand how to apply the same logic (essentially of proving there are infinitely many states in the respective DFA by contradiction) to the language containing equal numbers of a's and b's (in this case the order doesn't matter, e.g. ab, abab, aabbab, baababba, etc.)
nova cedar
that language contains the simpler language you already can't construct
so you can't construct that one either
well that's a lie
tall wolf
Is it though?
nova cedar
you have to show more than that I think
what (this bigger language) - (the smaller language)
summer egret
L ⊂ K and L not regular does not imply K not regular
nova cedar
you can remove one from the other to make it yeah
tall wolf
But isn't K non-regular in that case?
Since you'd have infinite states in its respective DFA?
summer egret
no, the language which is all words over your alphabet is regular
tall wolf
oh right
nova cedar
Sigma*
summer egret
since I didn’t name the alphabet, that notation seemed inappropriate to me
tall wolf
Say your alphabet is {a, b} you could just represent K as a single acceptance state with a and b looping back into the same state, right?
Hence K is regular
summer egret
yea
tall wolf
ok, makes sense
summer egret
uh now lemme think about the actual problem at hand
idk the solution but I’m also taking a course rn in which finite automata are a part
(we just concluded it)
pumping lemma would work
to prove it’s not regular
if you did that
tall wolf
The proof I'm thinking about for same no. of a's and b's not being regular where a's and b's are adjacent (i.e. ab, aabb, aaabbb, etc.) is that you show all states are distinct, therefore there are infinite states and therefore it's not regular
But I don't see how you can apply that for same no. of a's and b's where the order of a's and b's doesn't matter
summer egret
ah, I think you can use that too
tall wolf
I don't reaally wanna go down the route of pumping lemma
summer egret
hm okay I see the issue
ah, wait, no, here
let $x$ and $y$ be two words such that $|x|_a \neq |y|_a$ or $|x|_b \neq |y|_b$.
Show that then they have to have different states, and that therefore there must be infinitely many states
pine jettyBOT
Sascha Baer:
summer egret
(where |x|ᵢ is the number of times i appears in x)
tall wolf
Yeah, that's what I want to do
Because I can visualise that proof easier than the pumping lemma
summer egret
so you just have to find a suffix which would make x accepted and y not
tall wolf
Only one example?
summer egret
well for a generic x and y
tall wolf
So x and y are two words where the number of a's in x and the number of a's in y are different, or the number of b's in x and the number of b's in y are different.
Yeah that's what you've said
summer egret
yea, you can assume without loss of generality that the number of as are differnet
and, while this does lose generality it should be sufficient to look at pairs of words where the number of b is fixed to some integer actually
after all you only need to find an infinite set of states
not show that all words have different states
tall wolf
Yeah
How do we define the state we reach that we want to prove are distinct for two different words?
summer egret
well you know that if x and y are two words, w is a suffix and xw ∈ L, yw ∉ L, then x and y must represent different states
(as in you end up in different states when applying the simulation to those words)
tall wolf
Say, in the problem of proving ab, aabb, aaabbb, etc. is not regular, you can define one state as reading in 'm' number of a's and another as reading in 'n' number of a's, and thus they are distinct since the first state will accept 'm' number of b's but the second will reject 'm' number of b's
summer egret
that actually only proves that that particular approach doesn’t work
the way you described it
tall wolf
Yeah
summer egret
unless I misunderstood you
tall wolf
I'm not quite understanding how to adapt that approach to my more general problem though
summer egret
you want me to try and write a proof?
summer egret
I don’t like giving out full solutions but I’m having trouble seing where the problem is exactly
tall wolf
I'm really just confused as to how you define the states
summer egret
I don’t
at all
I just show that there are infintiely many of them
if you define states then you’re only proving that the automaton with those particular states doesn’t work
tall wolf
Ok so do you think it's sufficient to say what you said:
well you know that if x and y are two words, w is a suffix and xw ∈ L, yw ∉ L, then x and y must represent different states
I understand that, but is it a real "proof", does it cover all cases? It looks like it does
summer egret
that’s only one line in the proof
it’s a true statement
but it doens’t say anything about the language at hand
Assume there exists a finite automaton that recognizes $L$. Let $q_k$ be the state reached when the word $a^k$ is input into the automaton. Since the automaton is finite but $\N$ is infinite, there must exist $n \neq m$ with $q_n = q_m$ are the same state. We have $a^nb^n \in L$ but $a^mb^n \notin L$, but simulating the two words must lead us to the same state. This is a contradiction.
pine jettyBOT
Sascha Baer:
summer egret
so this particular proof works for both $L$ and for the one where the entries have to be sorted
pine jettyBOT
Sascha Baer:
summer egret
(which may seem a bit confusing, but it kinda makes sense - the issue with both languages is that we have to count arbitrarily large numbers)
tall wolf
I understand why the language is not regular but I don't understand how that proof covers when the order doesn't matter?
It seems as though the distinction between that special case and the more general case is too vague to put into words without just implying the reader understands
summer egret
the point is simply that I found an infinite set of inputs which would have to lead to different states in the automaton, and therefore the automaton can’t be finite
I chose those words myself and I happened to choose them in a particularly nice way which would also work in a proof that {aⁿbⁿ | n ∈ ℕ} is not regular, but I could’ve chosen other words
I know that the automaton has to land in an accepting state for aⁿbⁿ but in a non-accepting state for aᵐbⁿ
and I use this fact to show that for all aᵏ, it would have to be a different state (or, the way I worded it above, to derive a contradiction for m,n such that aᵐ and aⁿ lead to the same state)
tall wolf
Here's my main problem with understanding that type of proof for this situation... say you had the state (let's call it state 1) arrived at by inputting 'm' a's and 'm-1' b's. Then say you have another state (let's call it state 2) arrived at by inputting 'n' a's and 'n-1' b's. Both state 1 and state 2 reach acceptance states by inputting 1 more b, and rejecting states by inputting 1 more a. So doesn't that mean both state 1 and state 2 are equivalent?
summer egret
the fact that the automaton would be accepting for bⁿaabbababaⁿ doesn’t bother me
no, because accepting states aren’t terminal. the state reached by aⁿbⁿ is accepting, but it has outgoing paths
because when you enter another a, it has to go to another non-accepting state
you can have many accepting states
it’s not just a single “stop now” state
tall wolf
But won't the logic repeat?
summer egret
who knows
tall wolf
i.e. input another a after the b and you reach another accepting state, but this is true for both?
summer egret
I don’t know how the automaton looks
(after all it doesn’t exist)
you don’t need to know anything about the automaton other than “these infinitely many words must lead to different states, becaue otherwise the automaton will accept inputs that it shouldn’t”
what the automaton does otherwise is absolutely irrelevant
tall wolf
Sorry, I understand that but I'm really confused about how the two states I described aren't equivalent in the case of the same number of a's and b's
Say you input a word abbaa, and another word aababba, both require one more b followed by any number of a's and b's
(such that the following number of a's and b's are the same)
summer egret
yea and maybe some automatons will map those to the same state afterwards, and some won’t
it doesn’t matter
you’re getting hung up on the wrong details
and I’m not understanding your confusion
so I don’t think I can help you
tall wolf
Ok, I think I understand now
Is it just that the proofs for the language with the same numbers of a's and b's but ordered (e.g. ab, aabb, aaabbb, etc.) is the same as the proof for the language with the same number of a's and b's but not ordered (e.g. ab, abab, aabbab, etc.) except you just add an extra sentence on the end?
Or rather, the proof for the latter case is the same as the proof for the first I just named
summer egret
the proof I wrote works for L = {|x|_a = |x|_b} as well as for L = {aⁿbⁿ}
(but it doesn’t work for any language that contains the right language, which is good because then it would definitely be wrong)
(it really only hinges on the fact that aᵐbⁿ ∈ L ⇔ m=n for either language)
(so in a sense I’ve proved that any language where that statement is true can’t be regular)
tall wolf
@summer egret Ok I have one final question, sorry for bothering you about it so much. It's just that you said the reason the proof you wrote works for language K = {|x|_a = |x|_b} as well as for language L = {aⁿbⁿ} is because you've proven there are an infinite number of states in the case of the language L = {aⁿbⁿ}, and therefore there must be infinite states for K = {|x|_a = |x|_b} and thus they are both non-regular. Is this the same as saying L ⊂ K and L not regular implies K not regular? Because I know this is not true? So what is the difference, is it just that languages L and K employ the same automaton "structure"?
summer egret
no, reread the thing I wrote just before
I literally commented on that
and stated exactly what is necessary for the proof to work
tall wolf
Ohh so by "right language" you mean L?
I think that was a misread, let me just try to understand it
summer egret
right as in not left
tall wolf
That's fine
I think I'm getting it, I'll look at it in the morning. I understand it a lot more than I did a couple of hours ago. Thank you so much, I won't ask you again about this. I'll just figure it out in my own time.
tall wolf
What is the difference between aⁿbⁿ ∈ L and aⁿbⁿ ⊂ L? I get the first is “is an element of” and the latter is “is a subset of” but what’s the difference in the context of languages? They look like the same thing. Other than that I understand everything.
manic robin
I am in no way an expert in explaining the answer, it also should probably be pretty easy, but I am kinda dumb for a student.
I think, and you can prove me wrong, that it means the following.
Say x ∈ N (natural numbers), that means the element can just be a natural number.
If it is a subset of a set, it means that the whole subset is part of the set.
You probably can word this better, maybe more formal.
nova cedar
my guess is aⁿbⁿ ∈ L means the actual word for some fixed n represented by aⁿbⁿ is in the language L while aⁿbⁿ ⊂ L means the entire language aⁿbⁿ is contained in L.
tall wolf
It’s just Sascha said above that the proof illustrated for a language with the same number of a’s and b’s not being regular really only hinges on the fact that aᵐbⁿ ∈ L ⇔ m=n for either language. I don’t understand what the bit in italics really means though.
Having said “the proof I wrote works for L = {|x|_a = |x|_b} as well as for L = {aⁿbⁿ}”
summer egret
aⁿbⁿ ⊂ L
this doesn’t make sense, the lefthand-side isn’t a set
when I write “aᵐbⁿ ∈ L ⇔ m=n” I mean that an element aa…abb…b (where a appears m times and b n times) is in L if and only if m=n
and when I write {aⁿbⁿ | n∈ℕ} ⊆ L I mean “the set of all words of the shape aⁿbⁿ for a natural number n is a subset of L”
I hopefully never wrote aⁿbⁿ ⊂ L
I may have used the shorthand {aⁿbⁿ} at some point, this would just mean {aⁿbⁿ | n∈ℕ}
tall wolf
Oh that makes perfect sense! Thank you 🙏
green merlin
anyone know how to set up a simplex tableu using the big M method?
nova cedar
Seems like the place to post this question, I kind of boiled down a problem I was thinking about to this sort of example, even though I want to solve the general problem I think this explains it:
Suppose you have an alphabet of 3 letters ${a,b,c}$ and I give you a completely arbitrary string such as,
$$aacabcbbcacacbbbbcabcacbbcabcabcbcbacbacbbcccba$$
The length of the word is your starting score, the lower your score the better. You can add a new letter to your alphabet to code for a word, but it costs you 4 points plus the length of the word. So for instance, it looks like the string $cab$ appears several times, so I can call it $d$,
$$aadcbbcacacbbbbdcacbbddcbcbacbacbbcccba$$
Since $cab$ has 3 letters in it and it appeared 4 times, my score drops down by 12 points. However I had to pay 4 points to buy the new letter and an extra 3 points for each letter in the word, so I have really gone down by only 5 points. There is no limit on the number of new letters you can invent. How do you get the lowest possible score?
pine jettyBOT
Merosity:
nova cedar
any ideas are welcome
spring plinth
so you can keep buying letters for 4+word length...
it seems hard, I wonder if there is a polynomial time solution
Let's create a working algorithm first.
When must we stop?
nova cedar
the cost is arbitrary really, just some fixed constant
I think the constraints pretty much force you to stop after you can't find some kind of pattern that appears more than a few times, since you only stand to gain after some point
spring plinth
Okay, for every substring, we can choose, we can see what happens when we select that substring to replace. The first question is "how do we show we don't want to use a letter to increase the score"?
I think it would be some exchange argument
nova cedar
oh you're asking for an inequality
we have an n length string that appears m times let's say
we can trade it out for a 1 length string that appears m times
plus that base cost of 4
I'll just call the cost K for now
spring plinth
I just want to make sure there's some sort of recursive substructure
nova cedar
$mn > K + 1 + m$
pine jettyBOT
Merosity:
spring plinth
that's not what I wanted
spring plinth
what I wanted is "how do we know we shouldn't cash out when mn<=K+1+m"?
it sounds obvious, but I think we need to rigourously do that
nova cedar
actually the inequality is off, should have an n up there
this is a completely spontaneous programming problem I came up with to solve some issue I have in something I'm making
I really just want to make the algorithm itself, rigor is nice but not required
spring plinth
I need rigor to prove the algorithm is correct
nova cedar
what algorithm do you have in mind?
spring plinth
exponential time algorithm that is correct
of course I can keep checking replacing all n^2 substrings
that's about n^(2n) in the worst case
but I want to see if I can prune this
nova cedar
I can't help you; I don't know what you're talking about
spring plinth
the trivial algorithm is "try everything, select the best"
nova cedar
oh ok
spring plinth
I can't seem to prove that you should not do anything with negative benefit
nova cedar
I was considering doing something to modify huffman encoding and do it with like, different window sizes sweeping through the string but
I think like you mentioned, there's some substructure going on that we should be capitalizing on
but it's not really clear to me
in some sense, there are nested strings
maybe an outside-in or inside-out type approach works hmm just brainstorming here haha
a sort of sub problem that's not quite accurate, suppose we have a substring like abababab we can break it up into 1, 2, or 4 parts
but it seems the square root is ideal, not considering the fact that smaller strings might occur other places more often
spring plinth
Let's suppose the best sequence of replacements has a replacement X with nonpositive benefit. Then, we want to remove that replacement X. Each replacement clearly has to affect a string of length at least 2 that appears at least 2 times. So we have a replacement where (K=base cost=4) K+n>=m(n-1). (n length string, seen m times, m, n>=2) If n=2, we are only considering K>=m. Consider the next replacements that have an increased cost. A replacement that uses X k times would see (n-1)k extra characters. Over all future replacements, we incur a cost of at most m(n-1), instead of incurring the cost of K+n, which is greater or equal.
idk does this sound rigourous?
spring plinth
Okay so we have (n/2)^2 possible replacements with positive benefit at each step, and each replacement at least takes away 2 characters, so we do it at most n/2 times
That's (n/2)^n
more accurately ((n/2)!)^2
which means n<=14 is feasible so far
nova cedar
is your first thing you said proving the m*n > k+n+m formula?
nova cedar
ok that helps
I sort of see what you're getting at, but I think my brain is just turned off at this point of the day
spring plinth
okay any thing with positive benefit must get rid of at least 5 characters
tame trellis
you have (4 + L )/ (L - 1) as the minimum number of occurrences to turn profit with len L
spring plinth
what's the minimum number of characters a profitable replacement would get rid of
tame trellis
it is not required that you get rid of five you can prove by counterexample
owait, maybe it reduces to the same for two
nova cedar
the cost of 4 is just a placeholder, so as long as the argument scales and like 4 isn't just some special weird case
spring plinth
but is the cost at least 4?
nova cedar
yeah
spring plinth
I can get you better bounds if you have a lower bound on the cost
nova cedar
the cost is always going to be at least 1 I think
like, we can assume it's around 8 I think safely
spring plinth
let's work with that for bounds on time complexity of trivial algorithm
wait, 1 or 8?
nova cedar
well, 0 would make the problem trivial I think
spring plinth
not exactly
nova cedar
since you can make the entire string a letter at no cost
spring plinth
you still have to minimise the total cost
and the length of the string is part of the cost
nova cedar
yeah but everything is equal trade, I don't think you can do anything that way
idk I might ust be too tired to really think straight just slap me
spring plinth
okay let's see how many replacements at most
nova cedar
the 4 was really just put as a placeholder I believe the actual problem I want to solve is literally 8
spring plinth
okay let's solve 8 then
nova cedar
but I have similar problems so if it can be made general it's welcome
let me count to be sure it's not actually 7 or something
yep 8
spring plinth
if do replacement then k+m+n<mn
we want to find lower bound for m(n-1), where n is string length
k+n<m(n-1)
Lower bound comes when string length is short. Choose n=2
k+2<m(n-1)
So in every replacement we should see at least 11 characters removed.
At each step, we have (n/2)^2 possible replacements, and we can only do replacements n/11 times at most.
So our time complexity is (n/2)^(2n/11)
i.e. strings of length 40 should have no problem
@nova cedar
Only a few billion operations
nova cedar
hmm
my strings are on the order of about 700 to 1500 in length
I like what you're saying about your bounds
spring plinth
any more information what sort of strings they are?
nova cedar
I sort of can but it's partially arbitrary length
spring plinth
like "text-based"?
we are now moving to "pretty good but not optimal" solutions
let's try greedy out
nova cedar
yeah it's literally text
spring plinth
like words and stuff?
nova cedar
not human readable words, really it's pretty much exactly like I presented it
spring plinth
nova cedar
the letters are fairly random
spring plinth
ah random
if it's random random, then you shouldn't expect much compression beyond log n
nova cedar
they're not completely random but they're not literal words
I guess I don't have good language to describe different qualities of random haha
spring plinth
do they have lots of repeated substrings?
spring plinth
they typically have lots of repeated substrings.
nova cedar
well "blank" as in repeated space
spring plinth
?
nova cedar
I'm not sure, honestly
spring plinth
what's the original problem?
nova cedar
more than just completely random
it's kind of long and I don't want to get into it right now cause I'm about to fall asleep
I think I'm gonna head out but I can tell you tomorrow when I'm alive if you're still interested
I was planning on throwing this problem up and then falling asleep and seeing it in the morning to see if anyone bit didn't expect so soon sorry
I appreciate the help, now I'm really passing out, thanks
tame trellis
you can greedily solve by getting all substrings with count k, then removing substrings of the substrings from that.
this would give n^3
tame trellis
however, am p sure greedy won't give the best solution
spring plinth
so we can find the optimality gap?
spring plinth
let's try finding a lower bound
lean gazelle
Hi can someone please help me with this question?
robust drift
I have been working on a problem tbh. Given an array of numbers, we want to see if this array can be divided into 2 left and right arrays where all numbers in the left are smaller than all numbers in the right
Aiming for O(n)
robust drift
no no
Ill give sample input output
2 2 2 4 3 II 9 12 8 8 True
4 3 3 3 False
II is where u divide the list
median plinth
Do you want strictly smaller?
robust drift
yea
median plinth
Hm
median plinth
The condition is the same as the the min of the right side being strictly larger than the max on the left side
robust drift
def chop(L):
n = len(L)
Min = min(L) #O(n)
Max = max(L)
i = 0
j = n-1
A = []
B = []
if L[0] == Max or L[n-1] == Min:
return False
else:
while L[i] != Max:
i += 1
A.append(L[i-1])
for k in range(i, n):
B.append(L[i])
Max_list = max(A)
Min_list = min(B)
if Max_list < Min_list:
return True
else:
return False
```this doesnt work if the list is [2, 2, 3, 9, 13, 12, 8, 8] for example
median plinth
So you just put the marker to the left of the max?
robust drift
pretty much
median plinth
This isn't sorting, and I'm not sure how sorting would help here
rocky dew
It was an old message
Maybe u can use some selection algorithm for the median
And then use it as pivot
median plinth
No
He wants to see if there's a point you can split the array into the left half and the right half
So that the max of the left half is less than the min of the right half
tame trellis
I don't see the problem
just maintain two heaps
this is trivial
amortized linear solution
tame trellis
max heap for left, min heap for right
iterate through and move from right heap to left at each step
doesn't get more basic than that
actually
doing this with a heap is non trivial
you need to maintain two more heaps
but you can still do it with a set 
with a set it makes much more sense on the intuition
and then you can extend that to the linear solution with a heap
you can make it work with just two sets, so
--
ok, for linear without a heap, maintain running max from left in another array, and running min from right in another
that should solve it too
that way you can iterate through and find a point by comparing both at all indices
or prove such a point doesn't exist
daring whale
hey, not sure where to best put this but I'm having trouble with parts of my homework
just having trouble with wanting the best way to do this flowchart
and the function it uses
daring whale
🙂
heavy mango
🙂
daring whale
Please i really want to get a 100 i don’t want to lose my stuff
neon snow
Hey! How can you do a orthogonal least square regression on a parametric curve? And perhaps more instrumentally, how can I define an equation (parametric I guess) for an ellipse in 3D space that I can fit.
spring plinth
crossposted in #probability-statistics . , please move there to answer
white imp
Anyone here ever come accross Runge Kutta 3 (RK3 algorithm) To be used for matrices?
I've used it for non-linear terms
But never matrices
vital mantle
By matrices, do you mean linear ODEs? @white imp
vital mantle
Can anyone suggest some good techniques to optimize (to find global minimum) a multivariate function? The function is not that straightforward, it solves nonlinear algebraic equations numerically to calculate some values.
craggy idol
Differentiable @vital mantle?
vital mantle
It should be. At least there are no discontinuity.
Because it is describing a physical variable.
craggy idol
Newton-Raphson method can find roots of the derivatives
Which isn't quite good enough
But it's a start
vital mantle
I am using fsolve function from MATLAB
But that's not what I want
I want to optimize that function.
@craggy idol
craggy idol
Yes, im saying find the roots of the derivative matrix
vital mantle
I can't find its derivative.
craggy idol
Not even approximately?
vital mantle
Yes, I can do that.
craggy idol
Approximations will help if indeed the function is differentiable, which we're hoping it is
Unfortunately this is a necessary but not sufficient condition
vital mantle
Also, the function has infinitely many critical points
craggy idol
Oh if it's in a bounded region then the situation is better
Then you want lagrange multipliers
Is the constraint of the form f(x,y,...) <= constant
craggy idol
Is the function to be optimized multilinear?
craggy idol
Ya
vital mantle
No
craggy idol
Damn, that would have been easier
Look up "lagrange multiplier" and "slack variables"
vital mantle
I can't even explicitly write this function in terms of variables
I know what lagrange multiplier is.
craggy idol
Can't you just use them with approximate derivatives? Am i being too naive?
vital mantle
I can. But it isn't working.
I even tried fmincon function in MATLAB, but it is not able to give accurate solution.
So I was looking for some techniques like swarm optimization, but I don't have any clue about them.
craggy idol
We didn't get to that part of the book when i took the class 😭 sorry friend
vital mantle
It's okay. Thanks though.
vital mantle
I don't know anything about R 😩
craggy idol
cunning jungle
am i right in saying the complexity of Stirling Partition Numbers is O(2^n)?
im torn between it being either 2^n or k^n and can't see which one is right
cunning jungle
i know, given that it isn't memoized
sorry, shouldve mentioned that
mainly using this algorithm
n>=k
tame trellis
yes, 2^n
tall wolf
Is the complexity O(n^2logn) classed as being "polynomial time"?
My guess is yes, but I can't find any solid answer anywhere.
(since logn is "less" than n^2, so n^2 is the "resulting" complexity which is polynomial time)
supple lantern
n^2 logn < n^3
tall wolf
So anything in O(n^2logn) is in O(n^3), therefore it is polynomial time?
nimble nacelle
not sure if this is the right channel
but I have a question regarding subnetting an IP address if anyone is able to help
nimble nacelle
ok
median plinth
@tall wolf yes
tall wolf
Thank you @median plinth
tall wolf
I’m trying to prove the complexity of a program is O(n^3), where n is the length of the array the program operates on, and A is the number of a’s in the array and B is the number of b’s in the array. The program has runtime 5A^2+2B^3.
My first thought is to try and get 5A^2+2B^3 in terms of n where n=A+B
median plinth
You don't really need to do anything that difficult
tall wolf
Then to divide the runtime in terms of n by n^3 and prove O(n^3) that way showing it’s always below a constant value..
I’m not sure how else to do it though that is sufficient for a “proof” :L
median plinth
What's an easy upper bound for both A and B
tall wolf
What do you mean by that?
The upper bound of 5A^2+2B^3 is infinity, no? There is no upper bound? As A and B increase it increases?
median plinth
Is that what I asked for
tall wolf
Upper bound 7?
tall wolf
Yeah
median plinth
But this upper bound is always a function of some variable, in this case, n
tall wolf
Oh I see
So upper bound of A is n, assuming there are no b’s
And upper bound of B is also n
But how does that help?
I’m relatively new to this type of big O notation derivation
median plinth
Think about it for a bit
tall wolf
Can you say, since the upper bound of A and B is n, the upper bound of 5A^2+2B^3 is 5n^2+2n^3 which is in O(n^3)?
median plinth
Yes
tall wolf
And that’s satisfactory? You don’t need to say or assume anything else?
median plinth
Where is there anything that's not rigorous?