/sci/ - Science & Math

>>9399956
>being this envious

>>9399978
Go back to optimizing your fizzbuzz program, you brainlet computer """"""""""scientist""""""""""

>>9399978
>Half of CS jobs go to people without CS degrees
>They do a better job than those with CS degrees

Enjoy your pink slip.

>>9399978
agreed, but i still gotta participate

>>9400000
Holy shit.
Anyway, memes aside, CS is pretty great. I started studying bioinformatics this summer and all the guys with CS backgrounds are pretty smart. Maybe it's a US phenomenon where CS students are absolute brainlets.

>>9400005
The vast majority of CS majors don't actually play video games (it requires quick thinking). Also, Sisper ToC is 9th grade level material and not impressive in the least. I could teach it to motivated middle schoolers.

>>9400014
Tbh, if they say they want to be a game dev they're more than likely brainlet af

>>9400014
>CS backgrounds are pretty smart

They're not. They read wikipedia articles to sound smart but they don't actually understand shit.

>>9400014
>Maybe it's a US phenomenon where CS students are absolute brainlets.
Maybe it's a US phenominon where everyone is an absolute brainlet

>>9400000
>getting quints

>>9400024
A friend of mine does CS, he said a guy on the course who started at the same time as him has a youtube channel and wrote a minecraft clone from scratch in 48 hours. There are definitely some smart people there.

>>9400034
how from scratch? like assembly?

>>9400036
>assembly
>hard

>>9400018
probably at your Uni they don't, but here its a giant meme my dude

>>9400000
>those integers

>>9400014
Oh shit another fellow bioinformatican. How's it going?

>>9399956
Why do biocucks need to strawman this hard to make their useless trash major look better than the actual $300k starting major?

Just switched my major from Mechanical engineering to computer science. Did I fuck up?

>I have a degree in Computer Science

>>9400034
Learn some programming and realize that isn't really impressive.

>>9400000
>tfw my buddy with a BA in linguistics now works at a tech recruiting firm giving out 6 figure jobs to guys with no degree, just a few certs

Programming jobs are one hell of a meme.

Is this you, OP?

>>9400232
>I can make pretty pretty apps so who cares if I can't solve problems I've never seen before...

>>9400000
quints of truth
CS majors can enjoy getting pajeeted in five years

>>9400055
>$300k
nice try but even in SF/SD that is absurdly high for a CS bachelors
2/10 got me to reply

>>9400232
Why the hell would you need to invert a binary tree? The whole point is that it's already sorted

>>9400290
He was talking about a mathematician's starting salary you doofus

>>9400036
No, scratch the programming language.

>>9400370
Of course C"S" students would be using Scratch, lmao

>>9400353
They want to know if you can write:

void invert(Node* node){
if(!node) return;
std::swap(node->left, node->right);
invert(node->left);
invert(node->right);
}

Also, they never said it was sorted you retarded CS major.

>>9400042
>reading comprehension

>>9400379
BSTs are literally sorted by nature you retarded fucking faggot

>current node
>node with a value less than parent node to the left
>node with a value greater than parent node to the right

>>9400379
>writing C++ like C-with-classes

>>9400404

That's what you do. You don't need to pass smart pointers for something so trivial.

>>9400398
>literally sorted by nature
I hope you're joking and binary trees are not BSTs

>>9400398
>all binary trees are binary search trees
Engineering major detected

>>9400407
>>9400411
No point for regular-ass binary trees to exist.

Talk about completely useless shit. My data structures class didnt even talk about them. They just went straight to BSTs.

>>9399956
>CS is le easy

>>9400422
Dynamic programming is literally taught in your second semester java course.

>THE ABSOLUTE STATE OF COMPUTER """"""SCIENTISTS""""""

>>9400056
Yes because engineering jobs are unionized.
Chad's unionizes.

>>9400419
>I don't know a use for a binary tree so it's useless
E
Pajeet plz

>>9400434
>lol u dont know how 2 use uh binary tree or a gaynary tree or a trinary tree or a quadrinary tree of a vaginary tree
Fuck off

>>9400422
I can't tell if you're trying to mock CS or imply that this is a hard problem

>>9400444
>le easy

>>9400464
Another piss-easy C""""""""""S"""""""""" problem

Keep em comin

>>9400471
Post the solution :^)

>>9400472
Not gonna help you with your homework faggot

>>9400426
I don't really know the terminology, what is "dynamic" about this? Seems like a normal problem

>>9400014
>>9400054
Sup dudes
What are you working on?
What are the job prospects in bioinformatics (especialy in europe where I guess the first anon is from) ?

>>9400000
>00000

>>9400511
First semester here so I am working on basic math right now. Job prospects are good though, at least that's what everyone says. You might have to move because there aren't a lot of places to go for these kind of jobs.
Pay is less than CS but overall I really enjoy it this far.

>>9400018
This is not true in any universe.

>>9399956
Someone with a BS in CS doesn't know much about CS, the same way that someone with a BS in Biology doesn't know much about Biology. They only know the basics. This is true in every field.

All the smart ones go to grad school to become actual computer scientists.

>>9400475
It doesn't really refer to the problem but the algorithm used to solve it. If you can speed up an algorithm by saving the results of subproblems so that they don't have to be computed more than once, you have a DP algo.

>>9399956
This only applies in the shithole that is burgerland, in other countries its a lacerous major

>>9400464
The obvious solution is O(n^2). Is there a better one?

>>9399956
>Daily

wew lad

>>9400690
>The obvious solution is O(n^2)
Not even close to correct.

>>9400464
>CS majors think babby geometry is difficult

>>9400993
>CS
>not thinking
yeah, that's the problem

>>9400475
Nothing its a litteral buzzword. Search "name origin dynamic programming" and you will find the answer would link it but captcha tells me im a bot.

>>9399956
Started my CS degree this year, will be switching to Math asap. My courses are piss-easy

>>9399956
better version

>>9400353
>every binary tree is a search tree

>>9401181
>iterating through [math]n \choose 2[/math] possible line segments isn't [math]O(n^2)[/math]

>>9400063
I know you're exaggerating but I wouldn't be surprised if this is true. If so, could ya give a fellow anon some... tips to be a non cs major anon?

>>9402950

the landing strip doesn't have to start or end on vertices. it can run along edges too.

>>9401282

with no restrictions on the shape of the island this seems like a pretty difficult optimization problem.

>>9403191
[math]n \choose 2[/math] also contains preexisting edges, you can try extending each edge you run across.

>>9403228

i don't follow you. what do you mean "pre-existing edges"?

the problem is just to find the longest line within an arbitrary polygon, which is probably np-complete.

>>9403245
>np-complete.

*np-hard

>>9400419
>My data structures class didnt even talk about them.

Guess how I know your uni is absolute shit?

>>9400464
>>9400471
>>9400690
>>9401282
>>9401181
>>9400472
>>9400474
>>9403216
>>9402950
>>9403191

How about this...

Start somewhere on an edge.
Travel all around the shape for x iterations (as granular as you want).
For every iteration of x, iterate y degrees from start to end (for example, if there is an x point on a straight line, we are iterating 180 degrees).
Project each y iteration directly across until it hits another edge.
Calculate distance.
If larger than currently stored distance, store start and end points.

That's your brute force solution.

You could do little optimizations like not calculating distances for same pairs of start and end points but I doubt that will help as much as a solution that was not brute forced.

>>9403758
This is retarded and wont work for all cases because "as granular as you want" doesn't mean anything if you have to change the granularity for certain problems then your solution doesn't work for everything, look up ray casting you niggers.

>>9403778
Did you even read the problem, you stupid bitch? It's saying the error has to be within 10^-6 which was the reason for the granularity.

Also, you're even more of a stupid bitch since what I described was Ray casting a fucking shit ton of times around every point and every angle at thise points.

God, go fuck yourself.

>>9403790
>>9403778
And the granularity is used to describe an infinitesimal.

>tfw CS/double major student
I want to die

>>9403811
CS/Math*

>>9403811
me too

>>9399956
CS major here graduating in may and have 2 job offers already one for 80k one for 72k how is being poor other majors? I'm also doing grad school part time while I work after I graduate and will finish within 3 years and get over 100k easy any place I want to live in the U/S.

>>9403758

like a moving "radar scan" along the perimeter? that's probably not a bad approach.

i'd probably just compare the distance between every pair of vertices and checking whether there's a clear path between them, despite this not being strictly correct. if the island is a convex polygon then i think this will yield the optmal answer. if it's not convex then maybe start doing a search like yours around the most promising vertices.

>>9403758
Here's my go:
1. Loop through all pairs of vertices, time n^2
2. Loop through all edges, time n
3. If the edge of step 2 intersects the line of step 1 in the middle, then go to next iteration in step 1. If the line of step 1 may continue past a vertex, then compute the length using the intersections of step 2. Constant time?

This should work for all polygons/islands whose shoreline does not intersect with itself, but I don't think these cases are valid anyways. Total time around n^3.

>>9400059
>i have a degree in doing math without a calculator

>>9400059
>i have a degree in doing math without cross referencing to validate checking if my answers are actually correct

>>9400059
>i have a degree in being certified slower and less accurate than any automated computing device since 1970

>>9404384
>Total time around n^3.

no, O(n^2).

>This should work for all polygons/islands whose shoreline does not intersect with itself, but I don't think these cases are valid anyways.

if the island's polygon is allowed to be non-convex then i'm pretty sure it's an np-hard problem. correct me if i'm wrong though.

>took design of algorithms
>actually had to program most of them
>too much of a brainlet to program Dijkstras with a priority q
>use nearest neighbor approx instead
>get the right output for sample data
>get 100 for the assignment

>>9400000
this is god's current year way of speaking to us

>>9399956
Funny how even STEM brainlets themselves are at ends with each other.

Knowledge is a dangerous thing and the world and the human condition within that world are disproportionately fragile compared to what a few thousand or million overzealous retards with uncertain knowledge and overcertain convictions can do to them. To someone with a philosophical or metaphysical sensibility for how difficult certainty really is to come by, or any knowledge of the history of science, STEMfags look like a bull in a china shop.

It's not that they are wrong on a few key things, it's that they have the conceptual sophistication of a child and there isn't even any way to teach them anything. They are so far gone down a path of stupidity, paved with incorrect axioms and getting wronger with every step, that helping them would require deprogramming their entire worldview from the ground up. And they don't even want to be deprogrammed, because, also like children, they're filled with enthusiasm to apply their broken ideas to reality, and those broken ideas are incidentally very effective at generating self-referential and circular feedback, that is, proving themselves "correct" as a foregone conclusion.

If STEMfags were just flat wrong about one or two things, the instinct would be to correct them. The problem is that they're tangled heaps of wrongness, who also want to destroy the entire planet. I don't disagree with them ideologically because that would imply they have an ideology. They are just the useful idiots of a few diseased and long debunked ways of visualizing the universe, views that perpetuate themselves like a virus by preying on the intellectually weak and lazy. Scientism is an historic bloc that reproduces itself so that it can reproduce itself, and brings all its debunked and dangerous epistemes along for the ride.

I feel bad for you. I honestly do.

>>9404384
What do you mean by pair of vertices? Like the vertices that make an edge?

>>9404048
>>9404384
Probably will fail for something like pic related

>>9403758
This would work on pic related

>>9404475
>essay on enviro policy concerning a local watershed
>had to engage the public somehow
>literally just went through the rubric and bullshitted for each requirement
>added some in-text citations and a works cited page
>100%
woah

>>9404475
More to do with how redundantly retardedly useless most math is.

>Go on /biz/, reminded I sold Bitcoin at $100
>Go on /sci/, reminded the degree I chose is apparently shit because of course it is
>Go on /pol/, reminded there's no point anyway America is almost over
I should just read books and work at the grocery store like I did in high school. I'm not cut out for the 21st century

>>9404523
I mean any pair of distinct vertices. The idea is basically the same as >>9404048 but you also check for intersections and continue the lines past vertices if possible.

>>9404530
I would think that the method works. The attached picture shows the simplified problem; if there exists a case in which AB - which passes through only one vertex - is the longest line, then the method will not work. However, in these cases either CD or EF should(?) be longer. I tried applying cosine rule and got something, but couldn't quite complete the proof...

>>9400422
lmfao CE underman here, in our algorithms & optimization course DKP was literally the retard option for people who didn't understand how to work with TSP, and dynamic programming was like the 2nd algorithm they had to implement, which everyone already had done anyway because it was already required in a previous data structures course. At least go for PTAS.

>>9404558
>go on /fit/
>reminded girls hate men less than seven foot
>got on /g/
>reminded girls won't talk to men with green bubbles
>go on /b/
>reminded girls have penises

What's /sci/s problem with girls?

>>9405148
What is this "girls"

>>9400062
try to do it and realize that it kinda is

>>9405241
Maybe you are just a brainlet :(

>>9400419
is this even real

>>9400419
What is a binary heap.
Engineer detected

>>9404990
>which passes through only one vertex

i think any solution has to pass through at minimum one vertex, so at least that would constrain the search somewhat.

the problem is situations like the one you illustrated, where you have a solution that involves fewer than two vertices.

since it's a polygon and not an arbitrary shape, there may be some algorithm from computational geometry that solves this efficiently, but idk.

What about Computer Eng.? Is it any better?

>>9404990
>if there exists a case in which AB - which passes through only one vertex - is the longest line, then the method will not work.

AB isn't the longest line here.

if it's the case that any solution has to involve at least two vertices, then you can search every pair, "extend" their line to the perimeter, then compare lengths. similar to what i think >>9403228 meant.


if there exist solutions involving only one vertex, then it's probably a much harder problem.

>>9400464

actually, i think it's polynomial, maybe O(n^2)


if have some line within the polynomial that touches edges but no vertices, then you can always extend that line by pivoting it until it hits a vertex, and then fix it at that vertex and do the same to extend the other end point. either the end point of the line will hit a vertex, or the line will hit a vertex. so any solution seems to involve at least two vertices.


so by searching each pair of vertices, and then extending each line (straight out, not like above), you'll will find an optimal solution, i think

>>9405430
>within the polynomial

*polygon

>>9405430
>maybe O(n^2)

actually O(n^3) worst case, since you'd need to iterate through the lines again to figure out where each "extension" intersects each edge.

so
>>9404384

was correct.

>>9405410
Cosecant(theta) is strictly concave where it is positive, and sum of concave functions is concave, so the optimum solution should involve two vertices.

>>9405490
I wonder if there is some data structure that will speed up the iteration through lines, as you progress through the possible directions through a chosen vertex?

>>9405505
>so the optimum solution should involve two vertices.

yeah, that's what i figured in >>9405430


tfw wasting quint 4's on such an embarrassing misstep >>9404444


i assume that in the case where it's an area enclosed by an arbitrary smooth perimeter it would be np hard. this algorithm only works when the shape is discretized coarsely enough to make n^3 or n^2 vertices tractable

>>9405509
>through a chosen vertex?

you're dealing with pairs of vertices. since the polynomial can be non-convex, you have to attempt to extend each end of the line.


without knowing any specific algorithm offhand, i guess this would be at least linear time for every line (pair of points), if not more. solve the lines to find where they intersect, check if the solution lies within the edge, if not discard the edge, if so add it to a list. then once we have all the intersections, check which ones (for each of the two end points) are the closest, and then take that as the new line.