at least that's how it was for my friends
#algos-and-data-structs
mint jewel
you have to understand something to be able to spout mathy BS about it
mint jewel
now, I personally do think in mathy BS. But afaik most people don't
agile sundial
otherwise someone's gonna ask you something and you'll be like "uhhhhh, idk, i didn't memorize that"
old rover
i'm not trying to memorize
raw zealot
1)didn't understand
2)read it
3) analyzed it
Read from 2
old rover
i am trying to understand
mint jewel
a big problem with big O is how stupid the notation is
old rover
wdym
mint jewel
conventionally, a(b) means perform an action of a on the value of b
old rover
well big O is standing between me and the way of my career
raw zealot
No
mint jewel
back to the topic at hand
raw zealot
_we need a better example _
mint jewel
well, back to big O with mutiple input values
old rover
what does drop non dominant terms mean??
raw zealot
Btw what's that dollar symbol
old rover
Btw what's that dollar symbol
idek
oh god i have to learn big omega and theta too????
F
agile sundial
i mean, the concepts are basically exactly the same
mint jewel
once you have big O, the other 2 are pretty easy
old rover
ok ok ok
mint jewel
one is avg, another is least
agile sundial
hmmm, what
old rover
hang on someone recommended this book called groking algorithms
i am checking it out to see if it clicks
old rover
public static void recommended one
agile sundial
it is not python specific
old rover
oh he said python my bad
raw zealot
Python specific books would use python programs as their examples
So it would be easier for me to
Understand
😔
old rover
Python specific books would use python programs as their examples
hey i found one
agile sundial
i don't know of any. most are just in pseudocode
raw zealot
This one
old rover
This one
Python Data Structures and Algorithms.pdfhttps://www.rgonzo.us › shiny › books › Python Data Str...
uhhh idk why that link sent weird
uneven jungle
this one is good aswell
halcyon plankBOT
Hey @old rover!
old rover
ok good
raw zealot
Then it should have that big O 😂
modern plinth
hello?
raw zealot
this one is good aswell
Thx, will check it out
modern plinth
I was wondering are there any tips on how to learn typing faster
raw zealot
Your pinky should support you, that's it 🥲
old rover
there's this book called grokking algorithms @raw zealot
it's like algorithm explanations w drawings
maybe check it out??
raw zealot
there's this book called grokking algorithms <@!722075505230348358>
Lemme see on amazon
old rover
Lemme see on amazon
no just google grokking algorithm pdf
unless you don't like e books
raw zealot
Found
old rover
great!
old rover
Thx! , Will compare both and start reading the better
ofc dude send me a friend request so we can work together on this stuff
raw zealot
Sure
old rover
so
old rover
it took me an hour of learning to finally say that big O is how fast your algorithm runs
old rover
First one has 500+ pages
i don't really like gigantic walls of texts in coding books i like lots of examples
grizzled schooner
it took me an hour of learning to finally say that big O is how fast your algori...
big O isn’t really how fast the algorithm runs though
uneven jungle
it's how runtime scales on the size of n.
uneven jungle
yes
old rover
yeah i think they said the original definition for beginners
to simplify the concept
so
nested loops are bad for big O
bigger runtime???
uneven jungle
at least if you iterate over the same thing
old rover
every algorithm book i look at has hella gigantic walls of text
what is the difference between space and time complexity???
uneven jungle
space is the memory needed
while time is the time needed
if you have programmed something lower level, like C you know fairly good how bad memory allocation affects the program.
while you are in python, it's the same but not obvious if you don't think about it
uneven jungle
Even if it's largely off topic and very long, I recommend this to appreciate what the space complexity boundaries were back in the days. https://www.youtube.com/watch?v=aMcJ1Jvtef0&t=1s&ab_channel=GDC
old rover
Even if it's largely off topic and very long, I recommend this to appreciate wha...
perhaps when i'm eating lunch yeah
old rover
Even if it's largely off topic and very long, I recommend this to appreciate wha...
can you recommend a good data structure/algorithms book that doesn't have gigantic walls of text
uneven jungle
@old rover anything that's not Macgraw Hill. American publishers tend to pay per word or something like that. Haven't read many programming books at all, I have bought a few but I don't open them. The Goodrich/Goldwasser book i suggested earlier is 770 pages (pdf avail) but comes with a quite extensive github repo https://github.com/mjwestcott/Goodrich
old rover
@uneven jungle thank you so much!
@uneven jungle does it matter if I learn how O(n) works in another language? I’d prefer it to be python
uneven jungle
It's not for any language
it's just algorithm analysis
so it's language agnostic
lean dome
"language agnostic" means not specific to any one language
Definition 3b on https://www.merriam-webster.com/dictionary/agnostic
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/ is a course on Data Structures and Algorithms that has been recommended here before.
I've also heard good things about https://www.amazon.com/Cracking-Coding-Interview-Programming-Questions/dp/098478280X/
old rover
oh god no cracking the coding interview for big O is bad
that's where i first started learning it
it just assumes you know sorting algorithms before it introduces big O
dapper sapphire
<@!567030124306759710> anything that's not Macgraw Hill. American publishers ten...
How is this github repo done for Goodrich's book? What I mean is does the github showcase some of the examples from Goodrich's book?
old rover
How is this github repo done for Goodrich's book? What I mean is does the github...
i found a PDF of the book
dapper sapphire
https://www.pdfdrive.com/data-structures-and-algorithms-in-python-d25119593.html
Yeah, I had the pdf. I wasnt able to find the epub, but the link you posted also has an epub. Thanks for the link!!
old rover
Yeah, I had the pdf. I wasnt able to find the epub, but the link you posted also...
any time
old rover
Yeah, I had the pdf. I wasnt able to find the epub, but the link you posted also...
big O starts on page 145
nvm this book gives me a headache too
dapper sapphire
But how does the github repo compliment the book? I looked at the book and github repo for Linked List portion and it looks like it shows some of the coding examples from the book.
dapper sapphire
nvm this book gives me a headache too
lol why does it give you a headache?
old rover
lol why does it give you a headache?
a lot of pages before big O and then by the time it gets to big O it's all math
i don't care about the math
i think youtube videos help me learn better
mint jewel
most book resources do try to teach the formal big O, which is only math, since it is a mathematical concept on functions
it is not even all that related to CS aside from common use
mint jewel
ye, try to find some more informal description
agile sundial
<https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-i...
my friend's in that class :o
old rover
ye, try to find some more informal description
i said that big O is just how fast an algorithm runs and someone said i was wrong?? i heard it from a youtube video
mint jewel
that is indeed wrong
bigO can also apply to space
and it is not how fast
it is how much slower does it run as the input gets bigger
it is entirely relative
lean dome
you're missing an __init__.py in auth, and in ec2, and in iam, and in aim/datatypes
add an empty __init__.py to each of those and it'll work.
lean dome
it is entirely relative
Right - specifically, a O(n) algorithm can often be faster than a O(1) algorithm, for small enough n. The only thing knowing that one is O(n) and the other is O(1) tells you is that, for a sufficiently large number of elements, you will reach a tipping point where the O(1) algorithm becomes faster.
dapper sapphire
Or is bigO how fast, slow and how much space the algorithm takes?
lean dome
it is how the performance or memory usage of the algorithm changes as the size of the input grows.
lean dome
running time or space usage, yeah.
old rover
then what is time usage
dapper sapphire
a lot of pages before big O and then by the time it gets to big O it's all math
Do you know and understand how to implement different data structures that you are reading the bigO for?
old rover
Do you know and understand how to implement different data structures that you a...
no i haven't gotten up to that point
lean dome
big o notation is used to describe many different things - the growth rate in terms of number of bytes of memory as the input size grows, the growth rate in terms of running time of the algorithm as the input size grows, the growth rate in terms of number of instructions executed by the algorithm as the input size grows
old rover
everyone starts w big O when they're learning DS/algo
lean dome
the number of bytes of memory one is commonly just called "space complexity", and the running time or number of instructions are both called "time complexity" (even though they're technically measuring different things, those two things are directly correlated with each other)
so: space complexity is how much memory the algorithm needs as the input grows towards infinitely large, expressed as some multiple of the of size of the input.
Time complexity is how long the algorithm takes to run as the input grows towards infinitely large, expressed as some multiple of the size of the input.
old rover
TLDR
lean dome
🤷
old rover
kidding
lean dome
I'm not sure it can be condensed much more than that.
lean dome
I can give practical examples for a O(n) algorithm running faster than a O(1) one (hash tables are slower than linear searches for a small enough collection of items), or of a O(log n) algorithm running slower than a O(n) one (linear scans can be faster than binary searches, for a small enough number of items)
in the first case, it's because the fixed overhead of hashing is expensive, and many items could be linearly searched in the amount of time it takes to hash something.
In the second case it's because locality of reference and caching makes it faster to look at items in a linear order rather than skipping around, for a small enough amount of data.
dapper sapphire
Actually what @lean dome said is a good definition of space and time complexity.
Space complexity would be how much space the algorithm takes.
Time complexity would be how long in time the algorithm takes to run.
lean dome
as the input grows.
it's "how much space the algorithm takes as the input grows" and "how long the algorithm takes to run as the input grows"
dapper sapphire
I dont know why, but I see as the input grows to be a given. But I can see where some wouldnt understand the definition.
lean dome
The use case for big O is: imagine you've got an algorithm that's working on 100 elements and runs in 1 second. You want to know how much slower it will be if you use the same algorithm across 100,000 elements.
If it's O(1) then it will still run in 1 second.
If it's O(log n) then it will run in 2.5 seconds.
If it's O(n), then it will take 17 minutes.
If it's O(n**2) then it will take over a day.
OK. It's off topic for this channel. I'd suggest opening a help channel. See #❓｜how-to-get-help
old rover
hey @lean dome would you recommend that MIT course you linked?
i might actually use it
agile sundial
I'm no godlygeek but I would
lean dome
I haven't taken it, but others in the server who have have recommended it.
old rover
ok i will take a look
agile sundial
it uses python too
lean dome
and, going back to the point about the big o complexity of an algorithm only being relative, not being absolute: if all you know is that the algorithm is O(1), you have no idea that it always takes 1 second to run. It could instead always take 1000 seconds, or always take 1 microsecond. Big O only tells you how the space usage or number of instructions scale, not what they are in absolute terms.
old rover
why are people putting inaccurate info
mint jewel
it tells you how many more operations if the input gets bigger
mint jewel
because they have no idea what big O is
mint jewel
most programmers never actually learn big O, they just infer its meaning based on how its used
which is fine generally, since it mostly an approximation
old rover
then why am I torturing myself
mint jewel
because you don't want to look like a fool when someone asks you about it
old rover
i have seen like 5-10 different definitions about the same damn thing
mint jewel
the formal definition is quite complex
old rover
big O is how running time grows as input size grows
mint jewel
yes
old rover
why can't people just say that
mint jewel
or any other function, not just running time.
I can say that printing something requires O(n) write calls
old rover
write calls????
mint jewel
if I want to print 80 things, I need to call some magical write function 80 times
dapper sapphire
i have seen like 5-10 different definitions about the same damn thing
When you say you saw 5-10 different definitions, how many of those definitions are from reliable text/book sources?
old rover
When you say you saw 5-10 different definitions, how many of those definitions a...
most are from videos
mint jewel
I don't think they are arguing that big O is ill defined, I think they are just lamenting how people are bad at defining big O
old rover
well cracking the coding interview's definition is like a paragraph long
O (big 0): In academia, big O describes an upper bound on the time. An algorithm that prints all the values in an array could be described as O(N), but it could also be described as O(N2), O(N3), or 0(2N) (or many other big O times). The algorithm is at least as fast as each of these; therefore they are upper bounds on the runtime. This is similar to a less-than-or-equal-to relationship. If Bob is X years old (I'll assume no one lives past age 130), then you could say X .$. 130. It would also be correct to say that X .$. 1, 000 or X .$. 1,000,000. It's technically true (although not terribly useful). Likewise, a simple algorithm to print the values in an array is O(N) as well as O(N3 ) or any runtime bigger than O(N).
mint jewel
https://en.wikipedia.org/wiki/Big_O_notation#Formal_definition this is pretty accurate
old rover
maybe cracking the coding interview is not the best resource
mint jewel
if you are familiar with how functions work, it may help
mint jewel
ye, that is limits
old rover
the whole constants don't matter bc the input is really big reminds me of limits
mint jewel
but less computing limits and more the theoretical idea of limits
ye, that is related to it
old rover
so big O is just limits
mint jewel
to an extent
old rover
why has my mind just gotten used to checking out when i see a big wall of text
mint jewel
the last paragraph is probably the easiest definition
old rover
which last paragraph?
mint jewel
of the formal definition link
mint jewel
f(x) = O(g(x)) if there exist 2 positive integers M and n0 for which f(n) < Mg(n) holds for all n > n0
mint jewel
interestingly, mergesort can be said to be of O(N^N) complexity, since the definition just requires the function be greater, not the lowest class that is still greater. Generally, you do want the lowest class for which it still holds
brisk saddle
@mint jewel what do you mean "how many more if the input gets bigger"?
a best case O(n) algorithm will always run n times.
so how does it only describe it when the input is bigger
i do not understand.
mint jewel
what does run n times mean?
brisk saddle
operations.
mint jewel
but what is a single operation
brisk saddle
sorry, it will always have n operations, sorry.
well take Bubble Sort for example, an "operation" is a shifting of two elements.
mint jewel
big O isn't about algorithms, big O is about functions
old rover
me metaphorically eating popcorn and watching this argument
brisk saddle
this is not an argument. it was a question.
old rover
kek discussion then
mint jewel
consider something like
def reverse_inplace(S):
l = len(S)
for i in range(l // 2):
S[i], S[-i-1] = S[-i-1], S[i]
``` this doesn't do len(S) operation, but half that(may have an off by one error)
but it is still O(n)
what that means is that if I give it an an array twice as long, it will take twice the "time"
mint jewel
ye
brisk saddle
ah, alright.
mint jewel
it is about growth, not actual size
brisk saddle
yee, i see now. thank you.
uneven jungle
speaking of, what is an accurate library for measuring runtime?
mint jewel
timeit is as good as it really gets
brisk saddle
i took a bit of time to think about it, that actually does make a lot more sense.
mint jewel
especially in ipython
vocal gorge
I'd recommend timerit
uneven jungle
what if your cpu is pausing?
vocal gorge
It's the closest thing to the IPython %timeit line magic command you can get outside of IPython
the builtin timeit doesn't Just Work like it.
uneven jungle
like I had a measurement going for 30 minutes then my computer hibernated
is there a way to measure used cycles?
I believe that would be more accurate
brisk saddle
wait so,
if you have an O(n^2) algorithm, it means that a dataset double in size to the previous one will take the previous time squared to complete.
right?
uneven jungle
no
vocal gorge
basically
brisk saddle
🤨
vocal gorge
it would take 2^2=4 times to complete
brisk saddle
what that means is that if I give it an an array twice as long, it will take twice the "time"
vocal gorge
that's O(n)
uneven jungle
it means that if you put in something really really big, the order of time scale is about squared
vocal gorge
the strictly formal definition, though, is that a function f is O(g) if there exists a C such that, for all n past a certain point, f(n) <= C g(n).
For example a function f is O(n) if for big enough C, f <= C n for all n past a certain point.
So it grows linearly or slower than that.
that's how you can think about it - an algorithm is O(n^2) if it scales about quadratically for big n.
brisk saddle
got it, thanks.
uneven jungle
-> BIG-O notation, not SMALL-O notation
brisk saddle
oh, scaled quadratically 
vocal gorge
yes, but it's less CS-related
uneven jungle
implicitly, for small O you need to consider every other part of the algorithm that adds time.
I guess
vocal gorge
both of them come from math, and are in their original definition about functions in general
vocal gorge
implicitly, for small O you need to consider every other part of the algorithm t...
not sure what you mean by that. Are you talking about T(n), maybe, the total time?
uneven jungle
hmm so might be, Im just thinking out loud. big-O dont care about the small parts, so small-O should do that... since a smaller O isn't affected by exponential growth
vocal gorge
AFAIK the little-o notation is basically "grows strictly slower than*. Formally, f(n) is o(g(n)) iff for any positive C (no matter how small), there exists an N high enough that, for all n>=N, f(n) <= C g(n)
For example, n is o(n^2) (and o(n^3), and o(2^n)...).
uneven jungle
aha... ok, then there might be that thing. I just used my own logic
vocal gorge
yeah, you're probably thinking about T(n) - the exact (not asymptotic) complexity
uneven jungle
that
vocal gorge
it's rarely actually used though, because it is more annoying to calculate
and also, well, not asymptotic, so if one algorithm is n^2 and the other is n^2/2, the former will be 2 times slower, no big deal
in comparison, an O(n^2) algorithm will be arbitrarily slower than an O(n) one for high enough n.
old rover
i lied this vid has poor production quality
but it's also like his second or third video ever
uneven jungle
This is the real effect of Big, Big O.
dapper sapphire
So using solar energy would be the way to mine bitcoin.
old rover
don't guess the big O off the code shape....
dapper sapphire
jk
old rover
so then what the hell do you figure off the O(N) from????
vocal gorge
from analyzing the code
dapper sapphire
I would say maybe implement couple of data structures and then think about the space and time complexity.
vocal gorge
consider how many elementary operations it does, depending on N
old rover
well i can stare at the code as much as i want it's not gonna give me the big O(n)
hang on
ok for example this code right here
in the video this guy just says oh yeah look it's two for loops and they're not nested inside each other
but that's using the SHAPE of code
uneven jungle
just make analysis of every row instead
old rover
idk what that means
uneven jungle
row 2
errant valley
The loops
old rover
the loops are part of code shape
agile sundial
welp, code is part of code shape, can't read the code
old rover
the same way a nested loop is O(N^2) which is also "code shape"
agile sundial
your loop iterates array.length times, which is N
old rover
your loop iterates `array.length` times, which is `N`
bc the length of the array (the input) can vary?
uneven jungle
well i can have for x in [1,2]: for x in [1]: for x in [1]: , does not make it n^3, does it?
old rover
idk
also what's best case, worst case, and average case?? do time complexities change for those??
old rover
only algorithm i know is binary search
uneven jungle
worst, it's a mess
agile sundial
eh, worst case is sorted in reverse order
uneven jungle
that would depend on the algorithm
agile sundial
i'm pretty sure that's the case for most out of the box algos
old rover
what's an out of the box algo
uneven jungle
sure
old rover
is there somewhere i can look at code
agile sundial
bc the length of the array (the input) can vary?
time complexity is based on the input, remember? in this case, we call the length of the input array N
old rover
and say what the big O is?
old rover
time complexity is based on the input, remember? in this case, we call the lengt...
yeah
errant valley
Binary search isn't a very good algorithm to understand big O with
lean dome
best case just tells you what the bounds on the algorithm are when it does the minimum amount of work, worst case tells you what the bounds are when it does the maximum amount of work, and average case is what the bounds on it are for typical input of a given size.
the time complexities don't necessarily change between the worst and the best case, but they can, depending on the algorithm. There are algorithms that perform much better on typical input than on worst-case input.
old rover
but i don't know how to look at code and confidently say what the best case, worst case, and average case is
lean dome
yep, that depends on the specifics of a particular algorithm.
topaz pulsar
usually you only need to detmine worts case but it just comes down to looking at what parts of the code's execution time depends on the input and going from there
old rover
guess i should start doing leetcode and then talking about the big O along w the best case, average. case,a nd worst case
that would be a more efficient use of my time
topaz pulsar
it's just experiance at the end of the day, the more you do it the better you will get at it
old rover
yeah definitely
errant valley
Look at something like bubble sort
old rover
Look at something like bubble sort
so look at code where bubble sort is used and predict the space/time complexity along w best case, average case, and worst case?
errant valley
Look at a basic bubble sort algorithm and think about what the input would be that would be the best case
topaz pulsar
like you said, code 'shape' can be a good indication in many cases of time complexity but not always, for example ```py
import numpy as np
x = np.arange(9).reshape(3, 3)
list(map(sum, x))
[3, 12, 21]```that code isO(n^2)for anxnmatrix
old rover
like you said, code 'shape' can be a good indication in many cases of time compl...
idk dude the last guy whose vid i watched said to not use code shape at all that you should just "know how they work"
this vid near the end
i am sorry for asking so many questions here
lean dome
bubble sort is a good example of an algorithm with an obvious best case. It takes up to N passes through the array to sort it, but it can take a minimum of 1 pass through the array if there was nothing out of place.
old rover
i'm just trying to learn
topaz pulsar
like I said, it can be a good indication, for algorithms like bubble sort where you just have 2 for loops and all other operations are O(1) then the shape gives it away, but in reality thats not always goig to work
errant valley
Bubble sort is also easy to visualize
topaz pulsar
I find recursive algorithms quite hard to find time complexities of
old rover
do best case, worst case, and average case exist for both space and time complexity?
lean dome
potentially, yeah.
errant valley
Space is a little weird but yes
topaz pulsar
apart from the standard algorithms like merge sort which you can remember easily, other recursive algorithms I think are quite hard because you need to try work out what is happening to the input on each recursive call and see what the function is working towards
lean dome
most algorithms use either a constant amount of memory, or a constant amount per input element. But it's possible to imagine an algorithm where that's not true - like, a sort algorithm that checks if the input is already sorted, and if so returns immediately, and otherwise allocates some temporary space before sorting, let's say.
old rover
kidding
lean dome
that would have a O(1) space complexity best case, but maybe O(N) average case.
old rover
me not knowing what a sort algorithm even is
mint jewel
there are some cases in which O complexity is hard to determine
old rover
i am currentlly looking at the bubble sort algoriithm
errant valley
Average case is usually the hardest I think
old rover
well the interviewers are gonna ask me
agile sundial
yeah, it often requires probabilistic analysis which is 🤢
old rover
it's apparently "very impressive"
something about knowing algo/DS is a turn on for them
there are harder things in CS that you need to know
lean dome
average case requires assumptions about your specific data, as well.
mint jewel
for example, the worst case time complexity of the optimal algorithm for the problem which 3 numbers in a list sum to a number (also called 3SUM) is O(n^2/(logn/loglogn)^(2/3)) which is just hilarious imo
old rover
how do you even figure that out
mint jewel
oh wait, there is an ever better algo now
discovered 3 years ago
no wonder I didn't know about it
agile sundial
not up to date in the literature of 3sum 😔
topaz pulsar
what does it even mean when its to the power of O(1)
agile sundial
to some constant
vocal gorge
it's log(log(n)) to the power of some function that is asymptotically bounded by a constant. So yeah, pretty much "log log n to some power".
old rover
huh i guess this is my existence now
i asked my friend in Hofstra CS what big O meant and she was like lesser or greater???
at least i'm not that bad
topaz pulsar
ah ok, is there a reason they can't use k? or would that be mistaken for something else, never looked this much as O notation and now i don't think i want to anymore
old rover
what if they ask me the big O in another language
am i just supposed to be able to do it
yes i think so
errant valley
It's pretty much the same for every language
lean dome
the big O of an algorithm is the same, regardless of what language is used to implement that algorithm.
agile sundial
the only thing you'd have to think about is hidden operations that aren't immediately obvious, like sum in python
old rover
bUt pYtHoN iS sO sLoW
agile sundial
huh?
lean dome
but big O doesn't have anything to do with how fast something is.
old rover
yeah i know
errant valley
It sort of does
agile sundial
not really
vocal gorge
asymptotically 😛
lean dome
it tells you something about how the speed changes. It tells you nothing about the speed.
lean dome
How the speed of an algorithm changes is the same in any language, regardless of whether that language is faster or slower than another.
vocal gorge
https://en.wikipedia.org/wiki/Schönhage–Strassen_algorithm is not used for all multiplication for a reason, even though it's better than normal multiplication for large enough n.
(apparently Python uses it for big enough ints).
errant valley
A lot of good algorithms are slower than basic ones for common inputs
agile sundial
In practice the Schönhage–Strassen algorithm starts to outperform older methods such as Karatsuba and Toom–Cook multiplication for numbers beyond 2215 to 2217 (10,000 to 40,000 decimal digits)
agile sundial
<https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm> is not...
that sounds like a waste of time lol
old rover
i mean hey if i can learn algos and data structures what else is gonna stand in my way between me and a cs job
errant valley
vocal gorge
tbh in Python using a set for in checks can be faster than a list even for pretty small n, say
agile sundial
that's why good implementations will special case small inputs with faster algorithms
vocal gorge
I think I got like 5-10 when I tested it?
errant valley
Does that depend on what type of elements are in the set?
lean dome
remember that a Python list isn't an array, also - or, it is, but indirected. Searching for an item in an array is faster than searching for one in a list.
agile sundial
what's their definition 🧐
old rover
and now they're big mad
you're gonna laugh
"You want to use Big O to determine in the worst case how long will your code take to finish."
lean dome
that's not a definition
old rover
Big O denotes worst case complexity
when analyzing whether or not your code is efficient
lean dome
"You want to use Big O to determine in the worst case how long will your code ta...
this isn't wrong - it's a relatively accurate description of one thing that big O is used for. You know the big O complexity of some algorithm, and you know how long it takes to run on some N elements, so you can compute how long it would take to run for some different N.
but it's not a definition of what big O is, or what it means.
lean dome
yeah, that ain't right.
old rover
in good news i think i understand bubble sort
vocal gorge
it's definitely not part of definition, because an algorithm will generally have different Os in the average, best, and worst cases.
(and there can be more complex cases like amortized worst)
agile sundial
whatever he says though, it's not very diplomatic to just say someone is wrong
old rover
i watched a 2 minute video
old rover
whatever he says though, it's not very diplomatic to just say someone is wrong
yeah uh he's big mad at me
HOW IS SOME SOPH IN BUSINESS TELLING ME A CS MAJOR THAT I'M WRONG
lean dome
whatever he says though, it's not very diplomatic to just say someone is wrong
you sound just like my boss 😄
old rover
yes "soph in business" refers to me
errant valley
Algorithm performance is so weird
old rover
ok guys
i have made up my mind
i will be doing the MIT opencourseware class
maybe doing some of the work on the website too
dapper sapphire
@old rover when did you start learning big O?
old rover
<@!567030124306759710> when did you start learning big O?
today
am noob
but i am trying to improve
dapper sapphire
For how long have you been programming for?
onyx root
@old rover if you want MIT courses, edx.org has them online, which might be easier than opencourseware
old rover
<@!567030124306759710> if you want MIT courses, edx.org has them online, which m...
eh it's not that bad there's a whole youtube playlist for the course and i can see the work from the course page
old rover
For how long have you been programming for?
2 years (very inconsistently)
vocal gorge
what is uni-level discrete math about, anyway?
old rover
god knows but the stanford course recommends that i know discrete math
vocal gorge
that's the thing, it seems like it's just a bit of number theory and whatnot
oh, for that matter, since I'm in #algos-and-data-structs...
Does anyone have an idea how can one implement a hashing function on n x n matrices (of ints, say) such that it is invariant with regards to the 8 possible rotations/mirrors of the matrix?
I want hashing that gives
A B C
D E F
G H I
and
G D A
H E B
I F C
and the 6 other variants the same hash, for example.
(here using matrices of chars instead of ints)
old rover
laughs in his first day of learning big O
MIT opencourseware is good
it would be better if they explained big O first
errant valley
Does anyone have an idea how can one implement a hashing function on `n x n` mat...
That's not really hashing
You just want to rotate and mirror it just like you said
old rover
where can i practice just figuring out the big O from code?
doing leetcode questions??
agile sundial
the problem with that is you actually have to solve them first
you could look at common algorithms or data structures and compute the big O of operations on them
vocal gorge
That's not really hashing
No, I do need a hash function - I want to be able to quickly check if a matrix like this one is in a set, say. But I need the function to count some matrices as the same, because I don't actually care about the rotation.
Alternatively, I need a way to "reduce" a matrix to a representation that's invariant with regards to rotations and mirrors.
old rover
the problem with that is you actually have to solve them first
not me reading cracking the coding interview for the 10th time and it actually makes more sense
errant valley
Alternatively, I need a way to "reduce" a matrix to a representation that's inva...
Is the matrix always 3x3?
vocal gorge
nope, nxn
errant valley
The sum function?
old rover
what does the sum function do??
agile sundial
the code is right there
old rover
stupid question
errant valley
It is pretty much a basic summation
It adds every number from 0 to n
sum(3) = 3 + 2 + 1 + 0
vocal gorge
heh, something something master theorhem
EDIT: ah, no, non-applicable
errant valley
It tells you exactly why it is O(n) space
Each call to sum takes up memory. You call it n times so it's O(n)
old rover
ok
i am starting to love cracking the coding interview
this actually makes sense
so n is just a variable right?
it can be any letter
errant valley
n is the de facto
agile sundial
yeah, but n is the convention
errant valley
Convention, that's the word I wanted
old rover
but them writing O(A+B) is correct
agile sundial
sure
old rover
depending on that code on the left
agile sundial
they define A and B, so they can use them
errant valley
Oh yes
old rover
what the heck is amortized???
old rover
yeah i just googled it
i've heard of lists and arrays
but i've never heard of an arrraylist
errant valley
It's kind of a Java thing
old rover
CTCI says when the array is full the arraylist class will create a new array w double the capacity and copy all the elements over into the new one
agile sundial
sure, that sounds reasonable
errant valley
It's not always double the capacity
old rover
i don't get what amortized and time has to do w each other
agile sundial
it might be a different constant like 3/2, but the idea is the same
it allows for constant time append operations
by overallocating some space, on average, most appends will not require copying the array
old rover
not the place
errant valley
Amortized is just another way to say the total cost of a function, right?
errant valley
If I'm correct (don't count on it), then that would be the total cost
Over the lifetime of the algorithm
agile sundial
not really
if we keep using the arraylist example, sometimes, and append operation will cause the entire array to be copied to a larger buffer. this operation is O(n)
torpid crown
!warn 719794129042800661 Don't post random images that have nothing to do with the topic at hand.
halcyon plankBOT
:incoming_envelope: :ok_hand: applied warning to @pine coral.
agile sundial
however, by overallocating a bit of space, we don't have to copy the array as often, leading to O(1) appends on average
@old rover make sense?
old rover
<@!567030124306759710> make sense?
yeah sorta just my first time seeing this concept
is there amortized space too?
errant valley
Wikipedia for Amortized says time or memory
errant valley
So amortized analysis is unrelated to big O?
agile sundial
it is related
agile sundial
can't they just say time complexity
because the clarification that it is amortized is important, just like it's important to say whether you're referring to best, worst, or average case
agile sundial
the wikipedia page for it has 2 nice examples
errant valley
So it's similar to average complexity
agile sundial
sure
errant valley
How have I never heard of this
kindred coyote
let's say i have this info:
m = 4
n = 5
a = ['R1','R2,'R4']
b = ['C1,'C3']
This is a grid. m is the number of rows, n is the number of columns:
_ _ _ _ _
_ _ _ _ _
_ _ _ _ _
_ _ _ _ _
Each value in a is the row that is highlighted. For example. Rows 1, 2, and 4 are highlighted. Each value in b is the column that is highlighted. For example Column 1 and 3 are highlighted. Given the highlighted columns and rows, how would I count how many squares are intersection
brave oak
```
m = 4
n = 5
a = ['R1','R2,'R4']
b = ['C1,'C3']
```
This is a grid. `m` is th...
isn’t it just len(a) * len(b)
winged gazelle
please someone address this issue..
from sklearn.model_selection import StratifiedKFold
RSEED = 60
accuracy=[]
skf = StratifiedKFold(n_splits =10, shuffle = False, random_state = RSEED)
for train_index, test_index in skf.split(X,y):
print('Train:',train_index, 'Validation', test_index)
X1_train, X1_test = X.iloc[train_index], X.iloc[test_index]
y1_train, y1_test = y.iloc[train_index], y.iloc[test_index]
classifier.fit(X1_train, y1_train)
prediction = classifier.predict(X1_test)
score = accuracy_score(prediction, y1_test)
accuracy.append(score)
print(accuracy)
getting error:
NameError: name 'classifier' is not defined
low sun
does anyone know of any good books, like physical ones, on data structures and algorithms?
old rover
@low sun cracking the coding interview, CSSLR
CSSLR if you really want to go into the depths of it
low sun
alright, thank you I'll check them out
agile sundial
what's csslr? @old rover
low sun
oh lmao
old rover
Yeah it’s been a long day
dapper sapphire
is there a way to pass in a class property to a method as a default value, so something like this
class LinkedList:
def __init__(self):
self.head = None
self.length = 0
def pop(self, target_index = self.length):
... rest of the code ...
No. Default arguments are attached to the function itself.
dapper sapphire
No. Default arguments are attached to the function itself.
so do you mean we have to assign an actual value, so target_index = None or target_index = -1?
lean dome
I mean that you can assign any object at all, but that object has to already exist at the time when the function is defined.
dapper sapphire
yeah self.length is already initialized in init.
lean dome
it's set when __init__ is called, but __init__ has never been called when pop is defined.
dapper sapphire
so when we do linked_list = LinkedList() wouldnt that remedy that? wouldnt that call __init__?
oh ok
lean dome
no - because the default arguments are set when the function is defined, not when it's called.
dapper sapphire
ok ok I see what you mean.
While we are still creating the method pop in the parameter it wouldnt know what self.length is?
lean dome
right - when the function is created, the class doesn't even exist yet, so there cannot possibly be any instances of it
dapper sapphire
But of course inside the method we can have access to the properties set inside __init__
lean dome
!e ```py
class C1:
length = 42
self = C1()
class C2:
def init(self):
self.length = 0
def pop(self, target_index=self.length):
pass
print(C2.pop.defaults)
@lean dome :white_check_mark: Your eval job has completed with return code 0.
(42,)
when pop is defined, it looks up self.length, finds 42, and stores that as part of the function itself. When pop is called, if target_index isn't passed, it will use that 42 that was set when the method was defined, instead.
dapper sapphire
wait did you just create an instance called self and then you passed that in as a default value for pop method for target_index
I see what is actually happening.
lean dome
yep. If I didn't create that first, then you'd just get an error - no variable named self would exist at the time the function is defined.
!e ```py
class C2:
def init(self):
self.length = 0
def pop(self, target_index=self.length):
pass
@lean dome :x: Your eval job has completed with return code 1.
001 | Traceback (most recent call last):
002 | File "<string>", line 1, in <module>
003 | File "<string>", line 4, in C2
004 | NameError: name 'self' is not defined
!e Which isn't any different than if you tried to do:
def foo(x, y=x.attr):
pass
@lean dome :x: Your eval job has completed with return code 1.
001 | Traceback (most recent call last):
002 | File "<string>", line 1, in <module>
003 | NameError: name 'x' is not defined
How does the self instance not interfere with the self parameter in __init__(self) and pop(self)?
lean dome
the self that is passed into the function is not the self that is looked up when the function is defined.
the default values you provide when defining the function are resolved when the function is created. The parameters passed into the function are resolved when the function is called.
!e ```py
x = 10
def foo(x, y=x):
print(x, y)
foo(42)
@lean dome :white_check_mark: Your eval job has completed with return code 0.
42 10
I actually understand what you did and it makes sense logically too. But is the following a good practice?
class C1:
length = 42
self = C1()
not at all; I was just trying to create a variable named self with an attribute named length that would exist and be in scope where pop was being defined
as a way to demonstrate what it was looking up.
dapper sapphire
ok wow thanks man!!
wow I had no idea you could do something like this. That was really helpful! Thanks @lean dome
by the way which one would you suggest of the two:
def pop(self, target_index=None):
def pop(self, target_index=-1):
None, definitely.
unless you also intend to support -2 and -3 etc to allow specifying an index from the back
dapper sapphire
ok I'll use None, I can see how -1 can lead to confusion.
No, I dont intend on supporting negative numbers at the moment. But maybe in the future.
lean dome
then I'd definitely use None instead, to avoid making it seem like there's some significance to negative numbers.
dapper sapphire
What do you think of this implementation of Linked List pop:
def pop(self, target_index = None):
self.length = self.length - 1
if(target_index == None):
target_index = self.length
current = self.head
previous = None
while(target_index):
target_index = target_index - 1
previous = current
current = current.next
popped_value = current.data
if(previous == None):
self.head = current.next # current.next will always be None if target_index is not passed
else:
previous.next = current.next # current.next will always be None if target_index is not passed
return(popped_value)
It was a lot cleaner until I decided to handle the optional target_index parameter.
errant valley
Linked lists usually don't know their length I believe
dapper sapphire
We dont have length property, so we dont increment and decrement it every time we add and remove an element. But we have a method called size() that gives us the number of elements there are in the linked list?
errant valley
If you need the length you probably shouldn't use a linked list
Unless it's an elegant solution I guess
dapper sapphire
What would we use if we need the length?
because in a linked list we have access to the head and we traverse through the list using the head, so we dont have a need for calculating the length or size of the list?
uneven jungle
If you have infinite memory, size does not matter. Then the problem is that if you have an infinitely long linked list, you are unable to reach the last element, so the premise falsifies the assumption that the size is irrelevant.
mint jewel
in most cases, an array list or hash map with consecutive integer keys is easier to work with than a linked list. They are mostly used for lazy generators in functional languages and for parsing.
wet kestrel
how would you list out all the unique permutation of the given string? Like an example: '101' would have unique permutation of ['101','110','011']
slim vault
you can use itertools and consume them into a set to avoid duplicates:
>>> import itertools
>>>
>>> set(itertools.permutations("101"))
{('1', '0', '1'), ('1', '1', '0'), ('0', '1', '1')}
how would you do it without itertools?
mint jewel
there are algorithms for generating permutations, this one is probably the simplest https://en.wikipedia.org/wiki/Steinhaus–Johnson–Trotter_algorithm
wet kestrel
I will take a look into it, thanks
old rover
ok what even is itertools?
mariosis said you can one line leetcode problems with itertools
halcyon plankBOT
agile sundial
itertools is awesome
old rover
i will check it out
agile sundial
i have
old rover
my idea is to look at the data structures there in code and figure out the O(n)
agile sundial
ok
agile sundial
the best case doesn't happen that often
it's not as useful as average and worst
you don't want to assume best case performance
old rover
oh
ok
so that means i need to learn less
isn't the best case just O(1) constant time?
agile sundial
not always?
agile sundial
¯_(ツ)_/¯
agile sundial
it depends based on the structure of course
old rover
of code?
uneven jungle
you cannot sort something in constant time as you have to iterate at least (n) times to verify the sort. As someone mentioned yesterday, the datatype can have like a bool that confirms it's sorted, then a sorting algorithm can have a best case of O(1)
old rover
or course?
old rover
the data structure you're considering
oh sorry i forgot the context
nova holly
def long_char(sentence):
last_char = ""
chars = []
for letter in range(len(sentence)):
if sentence[letter] not in last_char:
last_char += sentence[letter]
else:
chars.append(len(last_char))
last_char = sentence[letter]
return max(chars)
print(long_char("abrkaabcdefghijjxxx"))
Is the time complexity or this program O(n) or a little more ?
mint jewel
that looks like O(n)
nova holly
because im not sure if the if else statements and the max() add more time to it
ok thx
mint jewel
well, max() is O(n), but O(n+n)=O(n)
and the not in is O(1) since last char is always a single character
it could just be ==
nova holly
oh ye I learned that we thow away little things thats doesnt matter when n becomes very big
vocal gorge
hmm
I'm thinking if there's a case that can make it O(n^2) due to that in check
it seems to me that there is
vocal gorge
on a sentence of all unique symbols it will be O(n^2), since for each letter, a linear search is performed over last_char
agile sundial
last_char increases in size so it's not O(n) exactly
vocal gorge
and last_char will never be reset.
So yeah, it can be O(n^2).
test it on something like
test_str = "".join(chr(i) for i in range(32,1000))
buoyant herald
big-o notation
vocal gorge
it should be pretty slow.
(can plot the performance over size of unique-char string)
mint jewel
there is definitely an O(n) implementation possible
buoyant herald
sorry cache was loaded
vocal gorge
there is definitely an O(n) implementation possible
that's true, just use a set instead.
mint jewel
but yeah, this one isn't it
nova holly
and `last_char` will never be reset.
wdym it will never be reset
if there is the same letter in last_char we will make last_char to the last letter and append last char
so it is a reset
vocal gorge
it's reset when a character is found that's already in it. If the string is all unique characters, that'll never happen - it'll keep growing.
nova holly
but won't that be time complexity for space ?
because the algorithms will iterate over the list only 1 time
vocal gorge
I'm not talking about space complexity. I'm saying that it will be O(n^2) time.
Because in is not a constant-time operation on lists - it depends on the list's (string's, in this case) size.
With the right input, it will perform the in check n times, on a string that is growing to size n, for a total of O(n^2) operations.
nova holly
so if I use a set instead of string what will the be the time complexity ?
because I dont need the letters in order, I just need their lengh
vocal gorge
Checking in with sets is O(1) always* (that's their main usage), so it will be O(n) indeed.
*unless there's consistent hash collisions, but that doesn't really happen in reality
nova holly
def long_char(sentence):
last_char = set()
chars = []
for letter in range(len(sentence)):
if sentence[letter] not in last_char:
last_char.add(sentence[letter])
else:
chars.append(len(last_char))
last_char = {sentence[letter]}
if chars:
return max(chars)
return 1
print(long_char("abrkaabcdefghijjxxx"))
Hey @fiery cosmos!
sour ibex
hi guys im new to python and i want to know if this class is properly made please
agile sundial
probably
vocal gorge
sure
old rover
i googled it and on stack overflow it says it's called a depth first search algorithm
vocal gorge
that's just the complexity to generate all N-length strings of N symbols, for example
old rover
idk i thought it was interesting
vocal gorge
it's called a depth first search algorithm
I sure hope not lol
old rover
vocal gorge
DFS is a normal graph search algorithm, no scary complexities
old rover
long n_to_the_power_of_m(int n, int m) {
if(m == 0) return 1;
long sum = 0;
for(int i = 0; i < n; ++i)
sum += n_to_the_power_of_m(n, m-1);
return sum;
}
here's the code
agile sundial
should be like, O(V + E) i think
vocal gorge
Ah, that's just because that's how fast the number of possible positions increases with the number of moves.
It's a property of the graph, not of the algorithm
old rover
so then what is the time complexity of this code
vocal gorge
long n_to_the_power_of_m(int n, int m) {
if(m == 0) return 1;
long sum = 0;
for(int i = 0; i < n; ++i)
sum += n_to_the_power_of_m(n, m-1);
return sum;
}
it calls n_to_the_power_of_m(n,m-1) n times
agile sundial
huh, m times right
vocal gorge
so we can write a recurrency equation for the complexity
vocal gorge
~~huh, `m` times right~~
i < n, so n
agile sundial
😔
vocal gorge
T(n,m) = n * T(n,m-1)
and also T(n,0) = 1 (it returns immediately)
the solution for this equation is T(n,m) = n^m
so it's O(n^m)
vocal gorge
How is it related?
agile sundial
if n is always less than m it's not wrong, but it wouldn't hurt to be a bit more specific
old rover
ok
wet parrot
im sorry its not this topic related but can someone redirect to me to someone/somewhere that can help me with installing pynput and/or activating conda enviroment
old rover
im sorry its not this topic related but can someone redirect to me to someone/so...
#editors-ides maybe this channel however is for algos and data structures
wet parrot
ok thank you
old rover
yeah no problem
fiery cosmos
That is said: A program for which the maximum running time is bounded by the length of the program is said to run in constant time. I've looked for it in Internet but didn't get satisfaction. What's the meaning behind it? let's consider math.factorial(50) and math.factorial(1230) it'll take much more time.
how could it take constant time?
agile sundial
if you consider a rudimentary implementation of factorial
def factorial(n):
p = 1
for i in range(1, n + 1):
p *= i
return p
can you see how it would take longer for n=1230 compared to n=50?
fiery cosmos
to calculate, actually.
agile sundial
wdym?
fiery cosmos
If I write factorial(100), the out will come in a second.
But if I write factorial(10000) I have to wait hell of a long time.
agile sundial
yep
fiery cosmos
vocal gorge
that's a million, not 10000
fiery cosmos
You got the idea.
agile sundial
yeah, but the point is still the same
fiery cosmos
So, how can we say that it is constant time running?
agile sundial
it's not
vocal gorge
I have no idea where you got that weird definition of constant time.
agile sundial
it's technically correct, i guess, but super weird
agile sundial
clrs?
fiery cosmos
A program for which the maximum running time is bounded by the length of the program is said to run in constant time. This doesn't mean that each time of the program is run it executes the same number of steps. It means that there exists a constant, k, such that the program is guaranteed to take no more than k steps to run. This implies that the running time does not grow with the size of the input to the program.
size of input in the function factorial does matter .
hmm.
vocal gorge
It means that there exists a constant, k, such that the program is guaranteed to take no more than k steps to run. This implies that the running time does not grow with the size of the input to the program.
now that's true, that's the right definition of constant time.
mint jewel
what would be an example of such a program? Does the book have one
fiery cosmos
what would be an example of such a program? Does the book have one
unfortunately not.
old rover
Uhhhh what book?
fiery cosmos
introduction to computation and programming using python
.
old rover
Oh I haven’t seen that one yet
dapper sapphire
So I have this list append method that adds an element to the end of the list:
def append(self, new_data):
current = self.head
if(current == None):
self.head = Node(new_data)
else:
while(current.next != None):
current = current.next
# current.next is None
current.next = Node(new_data)
In the last line right before we current.next = Node(new_data), value of current.next is None
In the last line we create a new node and set it equal to current.next
What I dont understand is that how are we not doing something like current.next.next = None after the last line
Because current.next was in a way overwritten from None to a new Node...
spring jasper
Im guessing the default next value for a new node is None
dapper sapphire
I'm thinking about this in terms of add:
- create a new node
- point new node's next to self.head
- self.head becomes newNode
so ```python
def add(self, item):
new_node = Node(item)
new_node.next = self.head # self.head would be None first time, so next node is None
self.head = new_node # self.head will have the new value now. Let's say 1.
Your node class looks like this, right
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
Pretty close:
class Node:
def __init__(self, value):
self.value = value
self.next = None
sorry made some corrections there in the Node class. But that's what it looks I dont have next=None as a parameter.
spring jasper
Well same difference, every new node you make will have a None next value by default
So you dont have to be explicit about it on every append
dapper sapphire
so then is it doing something like this
current.next = Node(new_data)
current.next.next = None # is this what's happeneing in the background?
yes
flat flax
hi
verbal turtle
help me(((
Write the expression given by the formula in a form suitable for the Python language
swift wren
@verbal turtle are you asking for math help? Confused what your question is
verbal turtle
<@515265307787526165> are you asking for math help? Confused what your question ...
Write the expression given by the formula in a form suitable for the Python language
swift wren
I presume x is a variable passed as a parameter?
verbal turtle
I presume x is a variable passed as a parameter?
I don't know 😢
swift wren
I'm guessing since you're solving for y, you would be passing x as a parameter. So now you know you'll be passing x as a parameter, what do you think you should do next? I'm not trying to be a dick, just want to work with you to solve it rather than simply solve it for you
verbal turtle
I'm guessing since you're solving for y, you would be passing x as a parameter. ...
That's nice of you. The problem is that I don't know how to do it at all, I'm a total zero in math.
And that's it 
swift wren
No worries, we can work through this together. So let's think of this as a math problem instead. Personally, when I look at this, I would break up the problem into two parts- the log portion and then that large fraction
So, let's look at the first part- the logarithm. We have a log with a base of 1+x^2. Now, look up some documentation on how to do a log in Python
verbal turtle
So, let's look at the first part- the logarithm. We have a log with a base of 1+...
np.log(1 + x**2)
Right? 😥
swift wren
I'm not familiar with lumpy specifically but iirc, if you need to calculate a log with, say, base 7 such that logbase7 of 4, you can also calculate it by doing logbase(e) of 4 divided by logbase(e) of 7
vocal gorge
!docs numpy.log
halcyon plankBOT
vocal gorge
looks like it doesn't have a base parameter, so yeah, divide by the log of the base
verbal turtle
God, my brain is melting
swift wren
@vocal gorge thanks lol, been a while since I've dealt with non-natural or base 2 logs
vocal gorge
by the way, I highly suspect there's a typo here
I suspect that this was meant to be x^15, not x^1 5
swift wren
Lmao good catch
verbal turtle
possibly
vocal gorge
and the person writing the latex forgot to encase the power in {}s
swift wren
@verbal turtle so you have the general idea of how to solve that first part of the equation, right?
vocal gorge
break it into parts and figure out in what order are they evaluated
for example, do this part first
this is an exponent of something. So it's just np.exp. Of what? Of this:
swift wren
Yup, like @vocal gorge is saying, now we're just going to start following the order of operations for math
vocal gorge
What's this? One over something. So you get np.exp(1/()), where the () is the denominator. What's the denominator? This:
and so on
verbal turtle
What's this? One over something. So you get `np.exp(1/())`, where the `()` is th...
np.exp(1 / (np.sin(x + 1))
right?
vocal gorge
nope
well, it's somewhat ambigous, but I believe
is meant to be sin(x) + 1, not sin(x+1)
verbal turtle
I'm a fool. Got it
swift wren
Nah, you're not a cool. It's poorly written, should be more explicit
vocal gorge
usually when parantheses are omitted like that ( 😠 ) it's meant to be binding only to one token
swift wren
Fool* not cool
vocal gorge
I prefer to never omit them
verbal turtle
y = np.log(1 + x**2) * np.exp(1 / (np.sin(x) + 1)
Very good start but got a few things we need to still work with. The log portion is still wrong (the parameter you gave is the base but that's not what the parameter is supposed to be). The next thing we're looking at here is going to be that some of the other part of the equation is missing (was that intentional?)
verbal turtle
5 / 4 + 1 / x**15
vocal gorge
perhaps it's not clear from the formula, but 1+x^2 is a subscript, so it's the base
so it's not log(1+x^2) times something - the entire formula is a base-1+x^2-logarithm of something.
verbal turtle
I don't understand (((
vocal gorge
Uhh, you know that logarithms can have bases, right?
verbal turtle
Uhh, you know that logarithms can have bases, right?
No
swift wren
@verbal turtle I would highly recommend learning them first. I believe Khan academy has several videos on logarithms. I'm no math teacher so I think I would do more harm than good in trying to teach it
verbal turtle
<@515265307787526165> I would highly recommend learning them first. I believe Kh...
Yes, you're right
I'm going to study math)
Thank you so much!!!❤️
swift wren
Happy to help! When you're feeling a bit more comfortable with it, feel free to hop in here again and tag me in the post or else I probably won't see it
old rover
i actually found a book called algorithms unlocked
and it's only like 200 something pages
It won't go as in depth as CRLS or whatever but at least i'll have a base understanding
buoyant garden
ok forgive me here
but im having issues with the following code
its an attempt to make a real simply linear regression model, im just playing around
but after 4 epochs, it gets infinity, everytime
sometimes it also produces a overflow error randomly
nvm nvm nvm
nova sierra
Help
spring jasper
a s k
buoyant garden
ok this is a basic question
but ```python
e**(-z)
what does this mean
the two asterisks
agile sundial
exponentiation
buoyant garden
ok thx
dapper sapphire
Is the program execution slow if the program takes more space?
agile sundial
maybe?
the amount of memory something uses isn't related that much to the speed
unless you're caching a ton of things i guess ?
dapper sapphire
Actually you make a good point with caching.
agile sundial
or maybe if you're storing large amounts of data, which means operations on that data may take proportionally longer
it's impossible to know, really ¯_(ツ)_/¯
dapper sapphire
I have heard that how you can use more space to make certain algorithms fast/efficient.
So there's a trade off
agile sundial
yeah
uneven jungle
is it possible to make quicksort iterative and in-place at the same time?
mint jewel
yes
uneven jungle
then how, doesnt the extra data structure you need to hold the simulated callstack disqualify it as in-place?
half lotus
Depends on what the interpretation of the term in place is
If you interpret it in the perhaps strictest sense of using constant memory, then you're right, the stack used makes it not in place
mint jewel
I mean, if an in place quicksort is possible, an iterative in place quicksort is possible. Just because the call stack isn't explicit doesn't make it not an auxilary data structure.
uneven jungle
lot's of negations there... can you clear it?
mint jewel
essentially, if you use recursion without tail call optimalization, you are using an auxillary data structure, the call stack
uneven jungle
so... that's not in-place then, and if i use a simulated call stack it is even more obvious it is an auxillary data structure
mint jewel
it is somewhat debatable
the space complexity is Ologn
but you are storing indicies, not array elements
so, in practice it may as well be in place, but in theory it isnt
uneven jungle
🙃
half lotus
There is apparently a true constant memory implementation but I don't have access to the papers
mint jewel
oh, neat
half lotus
Sure
uneven jungle
you have blocked all type of comms
half lotus
I thought it was just a link. If not then never mind
uneven jungle
you don't have the library access so you can't get it
topaz pulsar
do you call the function?
digital tendon
Doesn't this function allow for a user to use anyone else's password as long as it's in the database? Or does your code attach a specific password to a specified user when an account is created?
buoyant garden
def __cost(self,x,y, weights):
z = np.dot(x, weights)
sig = myMath.sigmoid(z)
p1 = y * np.log(sig)
p0 = (1-y) * np.log(1-sig)
final = -sum(p1 + p0) / len(x)
return final
``` this is my cost function for a logistic regression model, but i encounter issues with the `np.log(1-sig)` as it gets NaNim not the best at math lol....
*my sigmoid function is correct, im certain
gusty grove
does your sigmoid function returns values [0, 1[? @buoyant garden
oblique panther
gusty grove
does your sigmoid function returns values [0, 1[? <@!507724355917053963>
log will give NaN if your input is 0 or less
buoyant garden
lemme see
sigmoid returns 1
this gets -inf
sooooooooooooo, how do i remedy this
nova holly
So I understand how to determine the time complexity of a function, example this one is O(n)
def reverse_alpha(n):
l = list(n)
word = []
for i in range(len(l)):
if l[i].isalpha():
word.append(l[i])
l[i] = 0
reversed_word = iter(word[::-1])
for j in range(len(l)):
if not l[j]:
l[j] = next(reversed_word)
return "".join(l)
but how to get the space complexity ?
old rover
oh well my newfound technique doesn't even work bc CRLS doesn't have much bolded text
guess I'll just go screw myself then
vapid crescent
Doesn't this function allow for a user to use anyone else's password as long as ...
it allows for anyone to enter a name/password as long as it is stored in the txt file -obviously not the best to use but generally its good as this is isnt for a proper thing
carmine bison
Hello im a newbie in python, started codeacedemy guide a few months ago with html. I'm trying progressing on Python now, to get internship (unpaid) and i got a few tasks to complete. Is anyone feeling in a mood to help me explain those tasks and how to solve them. I already solved the problems, but to be honest i dont understand how to describe the solution. If this is a wrong chanell i appologise.
old rover
old rover
Hello im a newbie in python, started codeacedemy guide a few months ago with htm...
- don't work for free 2. what are the tasks? 3. Is it algo/DS related?
can someone re write this in python and explain why it's O(n^2)?
nova holly
it is O(n^2) because it is looping inside a loop
old rover
but that's using code shape
agile sundial
def combons(L):
res = []
for i in L:
for j in L:
res.append((i, j))
because it is looping over the list over each item of the list
so if the list is of lengh 10 it will loop 100 times
old rover
so if you have a list of [1,2,3]
nova holly
the result will be [(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)]
agile sundial
the inner loop executes N times, because it runs on each iteration of the outer loop
old rover
oh i think i got it
ok now it makes sense
it makes sense now
thanks guys
hey what do you know big O actually is starting to make sense
carmine bison
1. don't work for free 2. what are the tasks? 3. Is it algo/DS related?
im still a student. Well 1st task is write a tree (" * ") - lets say a christmas tree. If i type in number 5, the program would create a tree made out of *. first row is *, 2nd ** and so on untill it reaches 5 rows.
buoyant garden
sooooooooooooo, how do i remedy this
anyone know howw i can fix this
old rover
doesn't matter if you're a student or not
don't do work for free period
but I digress this is not the correct channel for advice like that
carmine bison
I cant get paid with 0 knowledge 😄 I apologise, for disturbing this chanel
inland iron
Im trying to make an alternative to the min() and max() functions, and I already figured out the algorithm for it mostly, but im stumped on the min part cause I dunno what to initially assign the "smallest" variable to, or else i cant print the min number in a looped user input list.
jolly mortar
Im trying to make an alternative to the min() and max() functions, and I already...
the same way you set biggest?
the first user input
agile sundial
then what is best case?
for min and max?
old rover
for `min` and `max`?
oh no i'm speaking in general
agile sundial
wdym in general, you can't have a general time complexity
old rover
inland iron
the first user input
that breaks the looped user input tho, you'd have an extra required input
old rover
oh no here comes "that is not the correct definition of big O"
jolly mortar
that breaks the looped user input tho, you'd have an extra required input
just set smallest = biggest = int(input...)
agile sundial
oh no here comes "that is not the correct definition of big O"
it's ok, tbh. except the part about "is determined by how long the algorithm takes to ... " part
old rover
it's ok, tbh. except the part about "is determined by how long the algorithm tak...
I just don't want to embarrass myself in front of an interviewer