Those code monkeys in /dpt/ don't really understand shit and somehow ended up with 3 different /dpt/s and none have reached the bump limit yet
So let's have a thread for us more mature computer scientists
What research problems are you working on? What is your favorite CS book?
i'm researching your mom's butthole and my favorite book is the largest one i can ram up her cunt
>>52085488
lmao
>>52085488
Your gay
>>52085488
How does ramming a book in her cunt help with your butthole research?
Algorithm Design Manual is the best algorithms book
>prove me wrong
>>52085440
I got a job, fuck cs academia.
>mature computer scientists
wow, just asking for it
>>52085531
Enjoy coding your Rails webpages
Did you pass the Fizzbuzz "challenge" yet?
>>52085543
Undergrads get out
>Daily programming thread
>first one isn't 404'd within 3 days
>implying this is a fundamental problem with the concept of a daily thread
>>52085550
Don't worry senpai, I'll be doing python/java shit for 120k a year.
I passed the Huffman decoding/encoding challenge desu senpai.
>>52085596
huffman coding is cs101 stuff desu
>>52085596
>huffman encoding
|_| 31337 |=4|v|
>>52085609
>>52085652
What's the worst interview question you got asked senpai? I almost had to implement a quad tree once.
>>52085769
grep simple analogue
>>52085609
>101
here is the problem, it too basic
real interesting problems starts at courses with 3 in front
>>52085827
So a dynamic programming question pretty much?
CS?
You mean C#.
>>52086105
The only /csg/-approved languages are Scheme, Prolog, Haskell and Pascal
Daily reminder
type ProgrammingLanguage =
| C
| C++
| C#
| D
| Ocaml
| F#
| Haskell
| Shit
>>52085844
just finit automata
>>52085495
lmao
>>52085440
>implying computer scientists aren't the real code monkeys.
also
>Those code monkeys in /dpt/ don't really understand shit and somehow ended up with 3 different /dpt/s and none have reached the bump limit yet
That's the fault of people racing so they can post anime or not post anime for the next /dpt/
>>52086750
>I wonder who's behind this post
>>52086567
>>52086567
OCaml/Coq master race reporting in
inb4 french frog
>>52086567
>>52087750
What does /csg/ think of assembly?
>>52087766
>>>/eeg/
I'm learning it next semester for my cs course.
>>52085769
>quadtree
This is hard?
is it not just a binary tree with a few more nodes?
>>52085440
>computer science fag buttmad that /dpt/ is refusing to accept his tranny OPs
Go push your agenda on /b/, you degenerate piece of shit.
>>52087953
It's just a bitch to implement in an interview situation as the interviewer kept changing the specs.
When you're on the spot for an interview a lot of easier things can be hard since an interview isn't really just a technical assessment.
>>52087953
Even a binary tree is kinda hard to implement in an interview.
>>52088376
I realized tree traversal is really easy if you just do it recursively during interview. I'd have to think for a second to do it iteratively anymore, using stacks just doesn't seem as natural as recursion.
>>52088637
Besides worrying about whether you should do it recursively or iteratively, you have to worry about trying to avoid code repetition and try not to make mistakes (like forgetting to swap a leaf node for an internal node remotion).
Most of this isn't a problem if you're doing it at home, but interviews are stressful.
>>52088838
Interviews aren't going to get hung up over that.
Why do they call it "computer science" if it's not exclusively about computers and it isn't a science? Why not call it "computational theory" or "applied computation"?
>>52089066
Because it attracts the meme crowd that wants to boost their ego.
aka why coding communities are full of Hispters, SJWs and feminists.
>>52089066
it's the science you do on computers
>>52085440
kill yourself
>>52088637
using a stack is plenty natural even for tree traversala
b
c
d
e
f
g
h
i
push a so you remember where you last were
push b
push c
c has no children so you're done with that node
pop c
push d
d has no children
pop d
you're done with b
push e
you're done with e
pop e
pop a
push f
push g
push h
pop h
pop g
push i
pop i
of course it looks a bit messy with all the steps written out but it's simple, you just do it in a loop instead of a recursively called function.
fib(8) using iteration: 1 1 2 3 5 8 13 21
fib(8) using recursion:
fib(8) = fib(7) + fib(6)
fib(7) = fib(6) + fib(5)
fib(6) = fib(5) + fib(4)
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = 1
fib(1) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
which is more elegant and useful?
>>52087750
mon nègre
>>52090493
>which is more elegant and useful?
now try showing the actual code and we'll see what's more elegant
obviously doing it iteratively is way better, but in an interview you might be stressed out & stuff
>>52090493
I always make a disclaimer when I do recursive solutions that the iterative solutions have less of an overhead but I'm doing it recursively to convey the code and the idea in a much cleaner way.
Binary traversal using recursion is less then 10 lines of code, it's way more elegant.
>>52085440
So how does it feel that your only chances at employment are codemonkeying away on websites?
>>52090571
recursion:histo2 :: (UpToTwo a -> a) -> Int -> a
histo2 f = result . gen where
result (One x) = x
result (Two x _) = x
cons x Zero = One x
cons x (One y) = Two x y
cons x (Two y _) = Two x y
gen 0 = One $ f Zero
gen n = let
memo = gen (n-1)
in cons (f memo) memo
data UpToTwo a = Zero | One a | Two a a
histo2 :: (UpToTwo a -> a) -> Int -> a
fib = histo2 phi where
phi Zero = 0
phi (One _) = 1
phi (Two x y) = x + y
iteration:int fib(int n) {
if(n == 0 || n == 1) {
return n;
}
int a = 1;
int b = 1;
for(int i = 2; i < n; ++i) {
int m = a + b;
a = b;
b = m;
}
return a + b;
}
if you think the first one is more elegant i don't know what to tell you...
>>52090712
this is a joke right?
lmao
>>52090733
kill yourself
>>52090733
programming is never a joke you sick fuck
>>52087750
>coq
benis :DDD
>>52087750
>>52090520
What's it like using a language that doesn't have computation expressions?
>>52090298
>>52090742(define (fib n)
(cond
((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
There's a closed-form solution to Fibonacci you morons
Use it
>>52090802
fib(8) using your shitty way (actually it's MUCH worse than this, i just can't be bothered to spell it out for you):
fib(8) = fib(7) + fib(6)
fib(6) = fib(5) + fib(4)
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = 1
fib(1) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = fib(6) + fib(5)
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = 1
fib(1) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = fib(5) + fib(4)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = 1
fib(1) = 1
fib(3) = 2
fib(4) = 3
fib(5) = fib(4) + fib(3)
fib(3) = fib(2) + fib(1)
fib(2) = 1
fib(1) = 1
fib(3) = 2
fib(4) = fib(3) + fib(2)
fib(2) = 1
fib(3) = fib(2) + fib(1)
fib(2) = 1
fib(1) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
very elegant
much efficient
wow
>>52090802
>>52090886
and your way is not remotely elegant, not even from a readability standpoint. write out fib(n) on a piece of paper: you start with 1 1 2 3 etc etc, you don't do it fucking backwards with n - 1 and n - 2 for fuck's sake
I can't tell which dpt I'm meant to post in anymore
>>52090712
I can't believe you actually copied my joke code for the histomorphism that only keeps the most recent two results around.
>>52090911
Except you do. The mathematical definition of fib is\begin{case}
fib(n) = fib(n-1) + fib(n-2) & n > 1\\
0 & otherwise
\end{case}
>>52090712fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fib = fibs !!
>"serious" CS thread
>people discussing how to generate fibonacci numbers
Fuck you /g/
>>52092213
Recurring sequences and Fibonacci numbers are fundamental CS topics.
>>52092242
My point exactly. FUNDAMENTAL topics. This should be /sqt/ food, not /dpt/ and certainly not the topic of this thread.
>>52092270
String theory is a fundamental topic in physics.
>>52092286
No it's not. String theory is a mathematical model and will not be science (or physics) until it is falsified.
>>52092307
I think you're missing the point.
>>52092286
"String theory" is an entire subfield of physics, how to programatically generate fibonacci numbers is an incredible narrow part of CS and hardly worthy of its own thread. I came here to read about people I thought were doing CS, instead I found people being arrogant and pretentious about their implementation of a fibonacci number generator using recursion.
>>52092322
Oh yeah? Check out my fizz buzz.main = mapM_ (putStrLn . fizzbuzz) [1..100]
fizzbuzz x
| x `mod` 15 == 0 = "FizzBuzz"
| x `mod` 3 == 0 = "Fizz"
| x `mod` 5 == 0 = "Buzz"
| otherwise = show x
>>52090802let rec fib = function
| 0 | 1 as n -> n
| n -> fib (n - 1) + fib (n - 2)
Orlet fib n =
let table = Hashtbl.create 1 in
let rec fib' = function
| 0 | 1 as n -> n
| n ->
try Hashtbl.find table n' with
| Not_found -> let result = (fib' (n - 1) + fib' (n - 2)) in
Hashtbl.replace table n' result;
result
for the autists.
>>52092362
of fuck, forgot thefib' n
at the end
Has this general always been here? Fuck, Reddit is slowly taking over.
>>52092347
> `mod`
>repeating x `mod` [a] == 0 = [b]
No one posts books because illiteracy
>>52089066
"Informatics" or "computing" in non third-world countries. Props to >>52089654 for the giggle though.
can you prove bubble sort /g/?
>reading thread
>get sadder and sadder that i'll have to go through all of this just to be a code monkey
is there any hope for near burnouts like me? got an internship and they're keeping me for another year at least. what's the best way to jump straight into working without finishing school
>>52093610
Have a good portfolio by contributing to projects and making your own.
>>52092888
the proof is trivial. qed
>>52092888
I'm almost done with EE, and to be quite honest we almost never do proofs. I still have a very shaky idea on what it even means to prove something, and what is necessary to show in order to say something has been proven.
I'm perfectly familiar with the bubble sort, but what would it actually mean to prove it? Because if someone told me to prove that it worked, I would write a program to generate a random array, bubble sort it, check it to verify that it is sorted, and repeat ad infinitum.
>>52093610
>a company values your contribution and wants you to continue working for them
What about this is bad, exactly? And why do you not want to finish school?
>>52092888
Yes just use induction you faggot.
>>52093641
ok, but should i show my current company? how would employment work in a scenario like that? what about other companies? do i apply for full time entry level positions? sorry if i sound retarded, i pretty much am.
>>52093736
my goal when i started my cs degree was to graduate by 2017, i picked up this internship in the summer and i enjoyed doing it more than i enjoyed school. boss likes me and says that i've got a good chance at working there in the future. problem is, i want to continue working there but i'm afraid that if i leave to finish school, it'll be harder for me to find employment than to keep the job going.
>>52093826
Dude finish school first. You do not want to quit school to work at a company. Since you already have an internship you're already doing fine.
Start applying to companies in the fall semester of your senior year, you'll get some interviews and hopefully someone will give you an offer. Even the company you're working at currently will probably give you an offer after you graduate.
>>52093826
Holy dicks your employer expects you to finish school. That is their expectation when they hire a student.
They would more likely let you go if you DIDN'T finish school than if you go back to finish it. When your boss says
>good chance at working there in the future
By future, he/she means when you graduate.
It's also entirely possible that you can and should work there in future summers. Communicate with them. You need to value your ability more, dude. You're not the sperg you were when you left high school, you have real, concrete value that employers are looking for.
>>52093867
>>52093904
thanks for the advice, /g/entlemen. i'll finish up school asap, probably the best route to take anyway. guess i got intimidated taking "real" CS courses instead of straight up programming classes.
>>52093705
You want to prove your procedure BUBBLE is correct? Prove that given a random vector of (positive) integers A = (a_1, ..., a_n), the permutation s = BUBBLE(A) is such that when applied to A, the coordinates are well ordered. Keep in mind all what comparison-based sorts do is generate an appropriate permutation.
>>52094176
Also I'm using "random" in the intuitive sense. You obviously want to prove this is true for all vector of n positive integers. This is done by considering one such vector without using any additional hypothesis, hence my liberal use of the word "random" in case you expected the proof to contain probability theory.
I'm worried that I'm retarded and won't ever get a job
someone give me a project to do and I'll do it.
I might have to ask a few follow up questions
>>52094686
Design and implement a compiler/interpreter for an esoteric language of your choice*.
*You are restricted to languages that are more than a brainfuck clone.
>>52094821
does OCaml count as esoteric?
also should I read anything before I get started or just learn as I hit walls?
>>52094859
No. I'd count languages in these lists and others like them:
http://esolangs.org/wiki/Category:Unusable_for_programming
http://esolangs.org/wiki/Category:Usability_unknown
how do terminal-based roguelikes (using dwarf fortress as an example) keep "static" UI's? how do they update the graphical representation of the gamestate at all, now that i think about it? does it clear the screen (ie a bash clear command) and reprint every time something needs to be updated?
Rate my comic (TA here)
>>52090493
>fib(8) using recursion:
>huge mess proceeding
i mean by definition wouldn't you do fibonacci rercursively with something like
fib(n) = (n > 1) ? fib(n-1) + fib(n-2) : 1
>>52090712
nice try but algorithms were around long before programming.
otherwise, how could anyone ever make bread?
>>52096206
we couldn't have without super human bread bots
>>52095880
nonsensical Dijkstra reference/10
>>52095880
What does negative path mean? Is it a negative weight edge or a backwards edge? I think my professor taught it differently.
>>52095880
2/10, font too hard to read
>>52085440
Working on deep learning, shit is magic
>>52096362
Dijkstra's fails with negative edges. Dijkstra's only works with the assumption that the first time you visit a node, there's no better path you could've taken to that node than what you've seen "so far" by expanding outward from the source. But if there were an edge with weight -100000 that's very far away from the source, you would never see it until it was too late.
Bellman-Ford solves that problem by expanding its search everywhere at once.
>>52097012
>no better path to that node
isn't that the definition of a node?
>>52092193
the formal definition using traditional mathematical notation looks that way, but the elegant way to COMPUTE fib(n) using that definition is to start from the beginning.
>>52092322
>people being arrogant and pretentious about their implementation of a fibonacci number generator using recursion
yes this thread is fucking garbage. these neckbeards do a great injustice to true CS heroes like donald knuth among others
>>52096112
that is what the "huge mess" is doing. you don't know what fib(n-1) and fib(n-2) are so you have to go all the way down to fib(1) and fib(0) before you can actually start solving it which is horribly inefficient and inelegant. the iterative way is to start from the bottom in the first place instead of having to traveling down to the bottom like in the recursive way and with iteration you don't need fucktarded "solutions" like the histogram shit in >>52090712 that's still far less efficient than using iteration.
static int fib(int n) {
if(n == 0 || n == 1) {
System.out.println("fib(" + n + ") = " + n);
return n;
}
System.out.println("fib(" + n + ") = fib(" + (n - 2) + ") + fib(" + (n - 1) + ")");
int fibm2 = fib(n - 2);
System.out.println("fib(" + (n - 2) + ") = " + fibm2);
int fibm1 = fib(n - 1);
System.out.println("fib(" + (n - 1) + ") = " + fibm1);
return fibm2 + fibm1;
}
public static void main(String[] args) {
System.out.println("fib(8) = " + fib(8));
}>>52098535
>Error: Too many lines.
recursionfags BTFO
http://pastebin.com/uqrUaHnK
>>52095811
These, dude: https://en.wikipedia.org/wiki/ANSI_escape_code
GNU Screen and libncurses use it too. You can pretty much do anything with them. I once did a tetris in go with them. I never finished it.
static int fib(int n) {
System.out.println("fib(0) = 0");
System.out.println("fib(1) = 1");
if(n == 0 || n == 1) {
return n;
}
int a = 0;
int b = 1;
for(int i = 2; i < n; ++i) {
System.out.println("fib(" + i + ") = fib(" + (i - 2) + ") + fib(" + (i - 1) + ") = " + (a + b));
int m = a + b;
a = b;
b = m;
}
System.out.println("fib(" + n + ") = fib(" + (n - 2) + ") + fib(" + (n - 1) + ") = " + (a + b));
return a + b;
}
public static void main(String[] args) {
fib(8);
}
fib(0) = 0
fib(1) = 1
fib(2) = fib(0) + fib(1) = 1
fib(3) = fib(1) + fib(2) = 2
fib(4) = fib(2) + fib(3) = 3
fib(5) = fib(3) + fib(4) = 5
fib(6) = fib(4) + fib(5) = 8
fib(7) = fib(5) + fib(6) = 13
fib(8) = fib(6) + fib(7) = 21
>>52096112
> i mean by definition wouldn't you do fibonacci rercursively with something like
> fib(n) = (n > 1) ? fib(n-1) + fib(n-2) : 1
That's how you'd specify fibonacci, but it's horribly inefficient to implement it like that because it requires O(2^n) time rather than O(n).
E.g. fib(8) is going to calculate fib(7) and fib(6), and the call to fib(7) is also going to calculate fib(6).
If you were generating fib(n) for all n up to some limit, you might dofib[0] = fib[1] = 1;
for (int i = 2; i <= n; i++)
fib[i] = fib[i-1] + fib[i-2];
But if you only want fib(n) for a specific n, there's no need to store the entire array.
Fibonacci is often used as an introduction to dynamic programming, starting with the recursive formulation, optimising using dictionary-based memoisation, identifying the access pattern and changing it to use array-based memoisation, then identifying the expiry pattern and replacing the array with two variables holding the previous two values.
Most "real" dynamic programming problems are much harder, but the fundamental concepts are the same.
>>52098737
>dynamic programming
Interesting, thank you
>>52090712
But haskell already does memoization so what's the point of explicit memoization there?
A day later and you nigs are still discussing fucking fibonacci
Fuck you /g/, fuck you
>>52098292
Spoken like the babiest of ducks!
>>52098737
Nobody is pointing a gun to your head and forcing you to post. If you're clueless, don't hit submit.
>>52101326
> But haskell already does memoization
No it doesn't. Lazy evaluation isn't memoisation.
Lazy evaluation defers evaluation until you actually need a concrete value. Thereafter, the expression is replaced with its value.
But that only applies when all references to an expression are to the same actual expression. E.g. if a function's parameter is used repeatedly in the body of the function. The value will be passed as a (possibly unevaluated) expression which is reduced to a value the first time it's needed (if it's needed; if not, it's never evaluated).
It won't attempt to identify and consolidate distinct expressions which happen to have the same value. E.g. "fib 6" arising from "fib (n-1)" with n=7 and from "fib (n-2)" with n=8 are distinct expressions which just happen to have the same value.
If you want memoisation, you have to do it yourself.
>>52101356
there was nothing wrong with his post
>>52102302
Haskell literally does automatic memoization. Learn what you're talking about before spouting bullshit.
Of course, when /dpt/ is all about fizzbuzz, /csg/ is gonna be all about recursive implementations of first order linear recurrent sequences... I didn't have a lot of hope for this thread since it was on the wrong board to begin with.
>>52103592
>first
second
>>52102340
> Haskell literally does automatic memoization.
No it doesn't. You're confusing lazy evaluation with memoization. But that seems to be a common mistake (search for "haskell memoization" for other examples).
> Learn what you're talking about before spouting bullshit.
You should take that advice.
>>52104358
Stop projecting anytime and realize how retarded you are. Alternatively, kill yourself.
>>52085440
Having a look at some old math texts atm anon. Thanks for asking.
https://gist.github.com/bishboria/8326b17bbd652f34566a
I like this general already.
>>52085440
so what the fuck is a binary tree and what is it used for
>>52085440
I'm working on a Assembly script that makes the computer mine litecoin for me with the GPU and CPU. I am rather new to Assembly so I am having trouble but O can manage.
Google Engineer at Mountain View, and my job sucks.
AMA
>>52104875
why do you work for a literal botnet
do you read my email
>>52104875
get me a job at magic leap
>>52104875
How many binary trees did you have to reverse before you passed the interview?
>>52105018
None - they ask you those bullshit questions like 'Imagine you've shrunken to the size of a tooth and you're trapped inside a blender. How do you get out?'
>>52104918
I work in the Google Drive division, so I don't, personally. I have a few buddies in the Gmail division that have to skim over E-mails that have been flagged as spam, so they can optimise spam filters. User e-mails get caught in the filter quite a lot, so they end up reading your e-mails anyway :^)
>>52104959
lol no
>>52105104
These questions have not been used by google in over a decade.
>>52085527
>tfw skiena was my professor
>>52105487
I'm jelly desu
My algorithms professor just stared and mumbled at the blackboard
>>52105356
Apparently not, if I had to answer that very question in my interview
>>52090825
Which is essentially useless for anything other than approximation of larger numbers because of floating point errors.
>>52107659
How the fuck do you even escape from a blender, its literally impossible since the walls are plastic and vertical, assuming you avoid getting shredded in the first place
>>52107883
>what could 55.000000000000021 rounded to the nearest integer be??
>>52107883from decimal import Decimal
>>52104875
so basically youre a glorified sys admin? because gmail is a finished product you probably just monitor servers, right?
>>52108104
>>52108104
If you'd care to actually read Binet's formula, you would see that both the subtrahend and minuend in the numerator's subtraction expression are both powers of n.
Meaning that the miniscule error in the calculation of sqrt(5) is also exaggerated by the exponentiation.
I implore you implement and test Binet's formula on larger numbers.
>>52108081
Here's how it works. You're trapped in a blender, with your mass proportioanlly reduced to maintain density, right? No-one said anything scaling down the force of your muscles. Assuming the lid is open and your muscle force remains the same, you can just go ahead and jump, seeing as you can exert a greater force due to your small size.
>How the fuck do you even escape from a blender, it's literally impossible
It's retarded goyim like you that don't get and will never have a job at Google. There IS no real answer - it's analysing your thinking and approach to a situation.
>>52108264
If you'd read >>52105104, you'd know I work in the drive division. A lot of camwhores store all their nudes and videos on Google Drive for paying goyim to give up their shekels to watch, so as I develop and test features, I pretty much get paid to look at nudes.
>>52108081
Muh relative size weight etc infinite muscle power just jump.
