Personally I think it's really cool to learn other languages. Python's limited language may limit you on types of data structure you can learn (eg pointers). For Leetcode, you'd likely spend the most of your time just practicing with algorithms anyways: learning algos is one thing, implementing them on a random problem is much more difficult.
#algos-and-data-structs
edgy gazelle
"ultimate goal of getting a job at one of the companies that do leetcode style questions?"
agile sundial
Personally I think it's really cool to learn other languages. Python's limited l...
what data structures are impossible with python's references?
edgy gazelle
I'm sure there's diversity in companies, but I'm pretty sure technical interviews with these qs are only part of the process in most companies, and a good resume/past exp or projects is needed
edgy gazelle
what data structures are impossible with python's references?
e.g. pointers
basically doesnt exist in python
agile sundial
a pointer isn't a data structure
edgy gazelle
but is useful in the implementation of DS
agile sundial
what data structure is impossible without pointers?
edgy gazelle
what data structure is impossible without pointers?
may limit you on types of data structure you can learn
never said its impossible
just ud have to implement it slightly diff from what u might find in a diff lang
agile sundial
sure, you just implied it
imo, you shouldn't learn DSA just to pass a tech interview; all devs should have some understanding of them
lean dome
but is useful in the implementation of DS
Python's references are pointers to objects. Python doesn't have null pointers, but it does have references to None which can be used instead of a null pointer in nearly every case I can think of
you can easily build, for instance, a binary tree where the left and right attributes of a Node are references to either another Node or to None
or a doubly linked list where the next and prev attributes of a Node are either references to another Node or to None
the only data structure that I can think of off the top of my head that you really can't meaningfully implement in Python is a dynamic array, because it requires manual memory allocation to implement
edgy gazelle
why am i being pinged 😭
and i meant u cant actually use pointers urself; ull just get the object it refers to
lean dome
but that is using pointers yourself
the only thing you can't do is make a reference point to no object at all - every reference needs to point to something
edgy gazelle
oh ok
haughty mountain
you can't easily do fun pointer arithmetic in python 0/10 won't use again
lilac sand
Hello, can anyone please pinpoint of this NFA to DFA transition is wrong? It's practice in class. The other NFA to DFA questions are correct however this one is not when I look at the correct answer
This is the NFA
This is the DFA I drew
State 2 is incorrect. It should be 2, 4, 3 according to the solution and sending transition a to state 4,3
haughty mountain
"these three" 
lean dome
those questions are a bit more involved than I feel like getting myself on the hook for helping with right now.
haughty mountain
isn't the tigers one just "what's the minimum discomfort if I place the x oldest tigers in the y closest cages?"
size and capacity is what defines the discomfort
I think what I suggested is the solution
dp[x][y] =
min(
dp[x][y-1],
dp[x-1][y-1] + (discomfort adding xth tiger to yth cage)
)
yes, the order is forced
and the "use x items in the first y spots" is a very common dp thing
more just a way to formulate the dp
you need to find a formulation that can be expressed in terms of smaller instances of itself, then you can optimize by not computing cases multiple times
7.1. seems similar
so you want to maximize the number of delegates
now the question is what kind of dp formulation would make that happen, it will also need to incorporate the "cooldown" of 2 days
wdym?
you don't have control over the order of things
you can choose to take all d_i or just z_i at every step, if you pick d_i then you have a cooldown
I think this is easier than your typical knapsack problem, but I guess it's similar
the overall question is if the maximum number of delegates you can get is >=floor(D/2) + 1
so you'll want to compute that maximum value
for each i you have z_i which is the number of delegates you would get by doing nothing, you can also decide to take all d_i delegates (at the cost of the cooldown)
d/2+1 isn't really important for what you want to do, you just want to maximize
computing the maximum you can achieve solves the problem, yeah
now, how can you formulate the maximization as a dp?
it's not that knapsack-like, it's simpler than that
if there was no cooldown you would just take d_i all the time
can you give some dp formulation?
haughty mountain
```
dp[x][y] =
min(
dp[x][y-1],
dp[x-1][y-1] + (discomfort adding xth ...
like the one I gave for the other problem 
haughty mountain
like the one I gave for the other problem <:this:470903994118832130>
I guess important question, what are the states?
why? why not just start at 0 and compute the maximum?
wdym?
what if picking d[i+1] is optimal?
the thing you have there might pick d[i] when it's not optimal
e.g.
d = [4, 10, 1]
z = [1, 1, 1]
what things would be part of your dp space?
as a hint the solution I imagine has 2 state variables
like, picking the right variables is key to be able to formulate a dp
e.g. in the other problem, first x tigers, first y cages
no, they are just two independent numbers, in the last problem I had the subproblem of dp[x][y] = "minimum if I allow using first x tigers and y first cages"
the key is that in this formulation you can express dp[x][y] in terms of smaller subproblems
sounds pretty vague
I mean the whole thing you described sounds pretty vague to me
it's probably not surprising that one part of the relevant dp state is "if I consider the first x contests"
elaborate?
can you formulate what you mean in the form of a dp?
like, a recursive relation for it
why would this be optimal?
huh?
I don't really know what you mean here, maybe show an example?
max?
do you mean sum?
and d_i is?
so you pick the 4
which is not optimal
what about
d = [4, 10, 1, 100]
z = [1, 1, 1, 1]
picking 10 here is not optimal
I don't think so
you seem to be trying to do something greedy
when you actually need to consider a bunch of options
if you had the answer for dp[x], can you use dp[i] for i < x to compute dp[x]
x is the same as before, "if you consider the x first contests"
expressing stuff in smaller problems is what it's all about?
though I'm asking if just having this x as a variable works or not
e.g. do you know if the value dp[x-1] is ok to use?
say I picked the d option in contest x-1
can I pick d in contest x?
no
because of the 2 day cooldown
so I have no clue if I can use dp[x-1] and pick the d option in contest x
kinda, but there is a neater way of modeling it
what if we add the cooldown as part of the state
you would have two variables in the state, let's call them x and c
considering the first x contests, and I have to wait c turns to make a d choice again
(actually maybe this could boil down to just looking two back, but this was an easier thing to imagine in my head)
like, I know the dp formulation I would do
can dp[x][...] be expressed in dp[x-1][...]?
so, c will have possible values 0, 1, 2
I'm asking if dp[x][2] can be expressed in dp[x-1][0], dp[x-1][1] and dp[x-1][2]
same question for dp[x][1] and dp[x][0]
dp[x][2] means you picked d[x], which you can only do for dp[x-1][0]
dp[x][1] means you were at dp[x-1][2] and had to pick z[x] because of the cooldown
what about dp[x][0]?
well yeah, but what action can arrive there, and from which prior states?
and from which states?
not only that one
right
and you want to pick the better option of those
ok, can we write down this as a nice dp formulation?
(so an expression for each of dp[x][0], dp[x][1] and dp[x][2])
the first one is indeed the expression for dp[x][0]
but the other ones aren't correct
actually
first one isn't quite right either
dp[x][0] = max(dp[x-1][0], dp[x-1][1]) + z[x]
dp[x][1] = dp[x-1][2] + z[x]
dp[x][2] = dp[x-1][0] + d[x]
for 0 we had two options, as discussed, both involve picking z[x]
for 1 we can only arrive from 2, picking z[x]
for 2 we can only arrive from 0, picking d[x]
(it's getting early, rather)
others here can probably help as well
in any case this is the formulation you can implement
they say that you either picked z[i] from the previous dp value
or you picked d from two steps back followed by z z
the approaches are pretty similar in the end I think
it's their dp values, and they kinda go the other direction it seems
my dp[x] was expressed in terms of smaller x
their x(i) is expressed in terms of larger i
I think both formulations are fine, slightly different ways to think about the problem
it's a thing in general, depending on how you view the problem you can find slightly different formulations that all work
(and sometimes finding any view of the problem that works as a dp is hard)
(but you spot patterns in solutions as you practice)
tight patio
what is ]
(BS, y, BL) = split(B, x)
(NS, z, NL) = split(N, y)
doing
nvm
didnt see the split func
tacit halo
for loops are just abstracted summations right
burnt trellis
for example i have this string
"!Hello!"
is there a way for me to check if there is a "!" and then another "!" after it ignoring the text between the exclamation points ?
another example would be smth like ```py
"0Python1"
i wanna check if in the string , there is sequence of a 0 and then a 1
kind of like an opening and closing bracket , the 0 acts like an opening bracket and the 1 acts like a closing bracket, i wanna check if there is that pattern of a 0 and 1 after it, meanwhile ignoring the text between both of them
haughty mountain
a summation can't print things
!e
sum(bool(print(i)) for i in range(10))
halcyon plankBOT
@haughty mountain :white_check_mark: Your 3.11 eval job has completed with return code 0.
001 | 0
002 | 1
003 | 2
004 | 3
005 | 4
006 | 5
007 | 6
008 | 7
009 | 8
010 | 9
now...a summation calling a function with side effects sounds like fun math
.latex $$f(x) = {i := i + 1, x^2}_2$$
grand havenBOT
haughty mountain
where i is a global integer
agile sundial
does math even have visibility rules? access modifiers?
haughty mountain
everything is global and public, clearly
fiery cosmos
What's the difference between the last 3 choices
vocal gorge
the last one isn't valid syntax
2 and 3 are indeed equal though, they just want you to pick the one with the same summation variable and order I guess
fringe zodiac
when sorting this arrray [1, 2, 3, 5, 4] using bubble sort, is the total number of passes 4 or 5?
agile sundial
2
fringe zodiac
when sorting this arrray [1, 2, 3, 5, 4] using bubble sort, is the total number ...
assuming it is not optimized bubble sort
agile sundial
4
fringe zodiac
why 4 though?
wouldn't it be something like this:
pass 1: 1, 2, 3, 4, 5
pass 2: 1, 2, 3, 4, 5
pass 3: 1, 2, 3, 4, 5
pass 4: 1, 2, 3, 4, 5
pass 5: 1, 2, 3, 4, 5
fiery cosmos
hey all, i am trying to show:
gaunt harbor
Hello
fiery cosmos
inductive assumption:
T(n) < cn^2
gaunt harbor
I want to ask about fcc project 1
Arithmetic formatter
gaunt harbor
One of the rule said:
Number of each side of the operator has a max of 4 digits width
Otherwhise it should return error.
I already split the string by spaces so i got 3 part
Num1 = first number
Num2 = 2nd number
Op = the operand
I write
Elif len(num1) > 4:
Return 'error'
Elif len(num2) > 4:
Return 'error'
But when it wont pass the test when num2 get assign with
'24 + 85215'
Num 1 should be 24
Num 2 should be 85215
And it should have return an 'error'well, -2cn + c = c(1-2n), so for all n>=1 that's below 0. Hence, < cn^2.
fiery cosmos
well, `-2cn + c = c(1-2n)`, so for all n>=1 that's below 0. Hence, `< cn^2`.
thank you!!
opal oriole
for loops are just abstracted summations right
Other way around. If it comes from math, it's probably the more abstract version.
haughty mountain
2 and 3 are indeed equal though, they just want you to pick the one with the sam...
I think 3 is zero
haughty mountain
T(n) < (c(n-1)^2 + n) = ((cn^2) - 2cn + c))
fwiw you dropped an n
haughty mountain
fwiw you dropped an n
.latex
$$\begin{align}
T(n) &< c(n-1)^2 + n \\
&= cn^2 - 2cn + c + n \\
\{\mathrm{if\;} c \geq 1, n \geq 1\} &\leq cn^2
\end{align}$$
haughty mountain
hey all, i am trying to show:
though this particular one is quite obvious,
T(n) = 1 + 2 + ... + n
its really not clicking for me what exactly this means
haughty mountain
-2cn + c + n <= 0, if c>=1 and n>=1
fiery cosmos
i mean, i know what in means in english, that the recurrence can be upper bounded by some function f(n) = cn^2
fiery cosmos
though this particular one is quite obvious,
```
T(n) = 1 + 2 + ... + n
```
how do you mean
so i was mowing the lawn and realized that i'm getting substitution proofs, proofs by induction, and substitutions to solve recurrences all mixed up in my head
haughty mountain
how do you mean
evaluate something like T(5) by hand
T(5) = T(4) + 5 = T(3) + 4 + 5 = ...
it's a very clear pattern
fiery cosmos
ok so how does that help me to see the answer
haughty mountain
T(n) = 1 + 2 + ... + (n-1) + n
```isn't helpful?why are you bringing summations into it
haughty mountain
because that's what this recurrence expands to
you have that
T(n) = n (n+1)/2
(assuming T(0) = 0)
which is clearly O(n²)
fiery cosmos
literally no idea what you're talking about
vocal gorge
.latex it's the case that $\sum_{i=1}^n i$ is exactly equal to $\frac{n(n+1)}{2}$
grand havenBOT
opal oriole
literally no idea what you're talking about
def foo(n):
if n == 0:
return
bar()
foo(n - 1)
``` How many times does `bar` execute if n = 2 (`foo(2)`)?2
haughty mountain
literally no idea what you're talking about
do you agree that T(5) = 1 + 2 + 3 + 4 + 5?
fiery cosmos
for which formula
haughty mountain
the one you brought up, T(n) = T(n-1) + n
fiery cosmos
don't you need a base case
fiery cosmos
CLRS 4.3-1:
show that the solution of T(n) = T(n-1) + n is O(n^2)
fiery cosmos
do you agree that T(5) = 1 + 2 + 3 + 4 + 5?
i don't see how it could evaluate to this
T(2) = 3
T(3) = 6
haughty mountain
you need to assume some base case where T(small value) evaluates to a constant, let's assume T(0) = 0 maybe better T(1) = 1
T(3) = T(2) + 3 = T(1) + 2 + 3 = 1 + 2 + 3 = 6
haughty mountain
T(3) = T(2) + 3 = T(1) + 2 + 3 = 1 + 2 + 3 = 6
in general
T(n)
= T(n-1) + n
= T(n-2) + (n-1) + n
= T(n-3) + (n-2) + (n-1) + n
= T(n-4) + (n-3) + (n-2) + (n-1) + n
= ...
= 1 + 2 + ... + (n-3) + (n-2) + (n-1) + n
15 = 1+2+3+4+5
fiery cosmos
you have that
```
T(n) = n (n+1)/2
```
so why is this clearly O(n^2)
haughty mountain
it's a quadratic...
fiery cosmos
(n^2 + n)/2
haughty mountain
e.g. it's for sure <= n²
haughty mountain
but in general all degree k polynomials are O(n^k)
fiery cosmos
yea
opal oriole
How about ```py
def foo(n):
if n == 0:
return
for i in range(3):
bar()
foo(n - 1)
Yeah, and in terms of n?
fiery cosmos
depends on if you put n in the num or the denom
if its in the denominator, then its bar() / n == 6/2 = 3
opal oriole
bar() / n = 3, bar() = 3n
Same as before, except 3n instead of 2n.
Because each time we do 3 bars, instead of 2.
fiery cosmos
bars/n yea
opal oriole
We are counting how many times bar is executed. Which is 6 in the case of n = 2, and 3n in the case of any n.
fiery cosmos
honestly i'm no closer to being able to solve any of the homeworks and i think i'd be a fool to borrow 6k to try to pass this course
opal oriole
Not bars per n. Just bars total.
fiery cosmos
the homeworks are like CLRS 2-1
just all words and variables and i immediately get confused even trying to comprehend what they're asking
opal oriole
So how about ```py
def foo(n):
if n == 0:
return
for i in range(m):
bar()
foo(n - 1)
(m could be anything)
fiery cosmos
i really appreciate you hand tailoring this lesson for me but i'm afraid my mind simply does not work in these terms, which is, disappointing
opal oriole
i really appreciate you hand tailoring this lesson for me but i'm afraid my mind...
You were able to answer the previous ones, if you can't get this one I can give you the answer and it may become more obvious.
fiery cosmos
but in the previous ones it didn't make sense to put n on the bottom as we weren't dividing anything
thats why i had to think of it as bar() per n, otherwise i'd never know to put n on the bottom
opal oriole
In the first one, it executes n times right?
The second one, bar executes 2n times, because all we did was call bar once more each time.
haughty mountain
why are we dividing by n?
fiery cosmos
how many bars / for each n
opal oriole
It's not bars per n, it's bars executed total in terms of n.
haughty mountain
don't we just want the total?
fiery cosmos
It's not bars per n, it's bars executed total in terms of n.
it has to be otherwise it'd be n/bars = isn't correct
opal oriole
it has to be otherwise it'd be n/bars = isn't correct
Look at the first one again.
fiery cosmos
bars / n makes sense mathematically, bc we can multiply both sides by n to get bars total
opal oriole
How many times does bar execute for n = 2, n = 3, n = 4, n = n?
fiery cosmos
you would have to know bars per n to work in terms of unknown n
haughty mountain
you don't
fiery cosmos
How many times does bar execute for n = 2, n = 3, n = 4, n = n?
for which expression
opal oriole
def foo(n):
if n == 0:
return
bar()
foo(n - 1)
2n, 3n, 4n, n^2
opal oriole
2n, 3n, 4n, n^2
For n = 2, bar executes 2 times.
fiery cosmos
right
opal oriole
For n = 3, n = 4?
opal oriole
Correct.
So the TOTAL number of times bar executes in foo is n times.
In general.
Not bars per n, just bars.
If n = 3, we get 3 bars, if n = n, we get n bars.
fiery cosmos
right
opal oriole
So now what if we change it to: ```py
def foo(n):
if n == 0:
return
bar()
bar()
foo(n - 1)
For many bars for n = 2, 3, 4, n?
fiery cosmos
n=2 = 4 bars, n=3 = 6 bars, n=4 = 8 bars, n=n = 2n bars
opal oriole
Correct.
So now what if: ```py
def foo(n):
if n == 0:
return
bar()
bar()
bar()
foo(n - 1)
n=2 = 6 bars, n=3 = 9 bars, n=4 = 12 bars, n=n = 3n bars
opal oriole
Correct.
Now what if: ```py
def foo(n):
if n == 0:
return
for i in range(3):
bar()
foo(n - 1)
n=2 = 6 bars, n=3 = 9 bars, n=4 = 12 bars, n=n = 3n bars
opal oriole
Correct. It's the same thing just written with a loop which makes it easier to change the number.
Notice the pattern. n is the number of times the function foo gets called, and the coefficient is the number of times bar gets called per foo call.
fiery cosmos
totally
opal oriole
For example with 3n, n is the number of times foo is called, and 3 is the number of bars per each call.
So now what if: ```py
def foo(n):
if n == 0:
return
for i in range(m):
bar()
foo(n - 1)
and 3* is the number of bars per each call.
opal oriole
Yes.
Amount of work per call.
And when you repeat some work n times, that is what multiplication is.
(Repeated addition / repeat work)
fiery cosmos
bar calls are = m*n
fiery cosmos
m^2 / n^2 whichever var youre choosing
opal oriole
(The initial n given to foo)
Correct.
So now lets go back to ```py
def foo(n):
if n == 0:
return
bar()
foo(n - 1)
The time T taken of the function is the number of bars.
T(n) = ?
fiery cosmos
n
fiery cosmos
looks like foo(n) and foo(n-1)
fiery cosmos
the bar work i suppose at each lvl
opal oriole
Yes.
So we have T(n) = n, a nice non-recursive form, and a recursive form T(n) = T(n - 1) + 1.
fiery cosmos
so reading this im seeing like the amount of work done by this recursive algo is equal to the amount of work done at this lvl + the amt of work done at the previous lvl
opal oriole
so reading this im seeing like the amount of work done by this recursive algo is...
Exactly.
Counting the amount of work at each level, plus the previous level.
And that previous level itself is also recursive.
fiery cosmos
thats where i get thrown i think. when i see T(0) or T(1) and its not defined in the problem
opal oriole
In this case it comes from the if n == 0: return
fiery cosmos
not in the LHS but on the right like something = T(1) + n and theres no T(1) to be found
opal oriole
We make sure we stop when doing the T(n - 1) until we reach T(0)
T(0) is just 0, no bars.
Because it returns before then.
T(1) = T(0) + 1
Basically foo(1) just runs 1 bar, and then calls foo(0) which does nothing, because it returns before it reaches the bar.
fiery cosmos
right ok
opal oriole
So T(0) = 0 is the base.
Base cases in code often show up as those if statements at the start that return early.
Without that if statement, it would run forever. n = -1, -2, etc.
fiery cosmos
of course
opal oriole
Which would make T(n) = inf
fiery cosmos
well this has been very helpful so far, i hope it translates to understanding the material better
opal oriole
So trying ```py
def foo(n):
if n == 0:
return
bar()
bar()
foo(n - 1)
What is the non-recursive and recursive?
T(n) = ?
(You already did the non-recursive before for this one)
fiery cosmos
T(n) = 2n and T(n) = T(n-1)+2
opal oriole
Correct.
How about ```py
def foo(n):
if n == 0:
return
for i in range(m):
bar()
foo(n - 1)
Correct.
Now notice that m is the same at each level in the recursion. So each level does the same amount of work. Which what lets us get the nice mn form, because we do m bars, n times (n levels).
If you look at the recursive version, you can see how you would get the non-recursive from it:
fiery cosmos
yeah the whole T(n) = (work at last lvl) + work at this lvl thing makes a lot of sense
at least, for recursive functions that is
opal oriole
T(n) = T(n - 1) + m
So for example n = 4:
T(4) = T(3) + m
= (T(2) + m) + m
= ((T(1) + m) + m) + m
= (((T(0) + m) + m) + m) + m
= (((0 + m) + m) + m) + m
= ((m + m) + m) + m
= (m + m + m) + m
= m + m + m + m
or 4m because multiplication is repeated addition
It expands out and combines, and in this case we can see that it always combines to nm for some n.
Each level adds m work / time.
Now m itself comes from doing bar m times, and bar counts as 1 work / time.
m is a counting of the number of bars we do per level.
So it looks like m = 1+1+1+1... (m of them (there are m bars, each worth 1)).
That is what the for loop is basically doing.
If m = 2, then the number of bars per level is 1+1 = 2.
If m = 3, then the number of bars per level is 1+1+1 = 3.
Each iteration of the for loop runs 1 bar.
fiery cosmos
what if you were given something like T(n) = T(n+1) + n
opal oriole
Yeah I was building to that.
fiery cosmos
ok
opal oriole
So right now m is the same per each level.
Each level does the same amount of work, but what if each level does different amounts of work?
What if for n = 2, the top level did 3 bars, and the second did 5?
Then the total is 3 + 5.
If we had 3 level with 9, 4, 3 bars each. Then the total is 9 + 4 + 3.
What if each level did some number of bars equal to the level it's currently on?
So level 2 (n = 2) did 2 bars, level 1 did 1 bar, level 0 did 0.
It would look like this: ```py
def foo(n):
if n == 0:
return
for i in range(n):
bar()
foo(n - 1)
The number of bars each level does depends on which level it is.
(depends on the current n at that level)
What would be the recursive T(n) for this?
fiery cosmos
T(n) = T(n) + 1?
opal oriole
That would run forever.
And also if you subtract T(n) from both sides you get 0 = 1 which can't be right.
fiery cosmos
T(n) = T(i)+1?
opal oriole
Well, i is not defined.
You have to work in terms of what you are given (n).
For n = 2, 3, 4, n?
How many bars?
fiery cosmos
lms
opal oriole
For n = 2, how much work does that level do (how many bars)? Not including the next level n = 1 and n = 0?
fiery cosmos
3 bars
fiery cosmos
oh right duh
opal oriole
For the n = 1 level how many bars?
opal oriole
For the n = n level?
fiery cosmos
n
opal oriole
And remember what m was? The work per level.
So in the recursive version, what is the work per level?
fiery cosmos
mn
opal oriole
It would look like this: ```py
def foo(n):
if n == 0:
return
for i in ra...
Work per level in this.
Remember T(n) looks something like T(n) = T(n - 1) + work per level.
The T(n - 1) is coming from the foo(n - 1).
And the work per level from the loop.
If level 2 does 2 work, and level 1 does 1 work. Then it makes sense that the nth level does?
fiery cosmos
n work
opal oriole
So T(n) = ?
fiery cosmos
T(n) = T(n-1)+n
opal oriole
Correct.
Now you have the recursive T(n) for foo.
How much work foo does for any given n.
But what about the non-recursive form?
Is there a nice one?
If level 1 does 1 work, level 2 does 2 work, level 3 does 3 work, ... level n does n work. And we want the total work. We add up the work done at each level.
Which looks something like 1 + 2 + 3 + ... + n.
If 1 + 2 + 3 + ... + n is the total work. Then T(n) = 1 + 2 + 3 + ... + n, and you may note that this is just an expansion similar to the one done before, where you just substitute over and over until you reach T(0).
fiery cosmos
be back in 2 mins. have to give cat his medicine
opal oriole
T(n) = T(n - 1) + n
For n = 3:
T(3) = T(2) + 3
= (T(1) + 2) + 3
= ((T(0) + 1) + 2) + 3
= ((0 + 1) + 2) + 3
= (1 + 2) + 3
= 1 + 2 + 3
So in general:
T(n) = 1 + 2 + 3 + ... + n
It follows that pattern.
🐱
fiery cosmos
ok so in essence if we have a recursively defined function which does n work at each level it follows the same mathematical summation as 1 + 2 + 3 + ... + n
fiery cosmos
right
opal oriole
Or the total number of bars.
Or the "time" T.
Or number of steps.
Whatever you prefer.
But we know that pattern right? 1 + 2 + 3 + ... + n.
haughty mountain
or know how to quickly derive it
opal oriole
So multiply out the numerator.
fiery cosmos
2T(n) = n*(n+1) ?
opal oriole
I meant go from n(n+1) to n^2 + n on the top.
haughty mountain
or know how to quickly derive it
S = 1 + 2 + ... + (n-1) + n
2S = 1 + 2 + ... + (n-1) + n +
n + (n-1) + ... + 2 + 1
2S = (n+1) n
S = (n+1) n / 2
We have ```
T(n) = 1 + 2 + 3 + ... + n = (n(n+1)) / 2 = (n^2 + n) / 2
Now I will split it up: ```
= n^2 / 2 + n / 2
And from this it should be pretty obvious what the big O of foo is.
fiery cosmos
right its O(n^2) bc some function c*n^2 can upper bound T(n)
opal oriole
Yes.
So now you know how to take something like foo, get its T(n), and from that its big O.
fiery cosmos
well this has been a real treatise in summations 🙂
opal oriole
And notice the route: code -> recursive T(n) -> non-recursive T(n) -> bounded big O.
If the code has no recursion then the recursive T(n) step does not apply. Although you can if you want to.
Like if you have just ```py
for i in range(n):
bar()
Which is obviously O(n).
fiery cosmos
did you see my earlier message regarding substitution proofs / induction / substitution to solve recursions
opal oriole
Which?
fiery cosmos
ill link
haughty mountain
other example function
def foo(n):
if n <= 1:
return
foo(n/2)
foo(n/2)
for i in range(n):
bar()
should be familiar as the same structure as ||merge sort||
fiery cosmos
so i was mowing the lawn and realized that i'm getting substitution proofs, proo...
this 1
opal oriole
this 1
Recurrences are relating a function to itself but with modified arguments, like T(n) = T(n - 1) + 1.
fiery cosmos
right
opal oriole
So one level to another (or multiple).
haughty mountain
you combine substitution and induction, right?
opal oriole
Induction is this neat thing where if you have a recurrence you can prove a non-recursive form by showing that you can get from one level to another by using the induction hypothesis (plus a base case).
fiery cosmos
idk do we
haughty mountain
guess the answer, substitute it in to make the thing non-recursive, and then you can do an inductive proof
fiery cosmos
guess the answer, substitute it in to make the thing non-recursive, and then you...
ooohhh
that's why you substitute
to make it non recursive!
opal oriole
Substitution is a method to show that you can get from one level to another. It's how you can get from one equation to another.
haughty mountain
yes, because recursion is often annoying to deal with in analysis
opal oriole
Substitution is a "legal step" in math when trying to show something.
opal oriole
to make it non recursive!
Yeah or in general to show that they are the same thing, the recursive and non-recursive forms.
fiery cosmos
i'm pretty good with induction to show like a base case and then set to n (or n-1) and then solve for n+1 (or n)
opal oriole
Like for example: ```
x = 10
y = x
I want to prove / show that y is 10. To do this I can use substitution:
Replace x with 10:
y = (10)
In the recurrence stuff you are trying to show that the recursive one is the same as the non-recursive one (and the other way around, it goes both ways).
fiery cosmos
eeoowwhh
opal oriole
And we want the non-recursive one because we know how to upper bound it for big O.
Math is a lot of just seeing the same thing from a different POV and the POV shift here is recursive to none-recursive.
And showing that POV shift to the reader (which includes yourself, there is a feedback loop of you writing it and reading it) step by step.
fiery cosmos
yeah its a lot of "if its true that x, then it must be true that y due to z axiom / rule / property" type thing
haughty mountain
in a recursive solution the order you solve subproblems gets handled for you, when writing it iteratively you need to follow an order such that if dp[a] depends on dp[b], then dp[b] gets computed first, usually the ordering you need is pretty obvious
opal oriole
Draw out the call tree, see what depends on what and in what order.
opal oriole
n was replaced by n+1
fiery cosmos
looks like they plugged in n+1 in some places and (n+1)^2 in others
but that has the perfect form as if you just plug in (n+1) in for n
no squaring necessary
opal oriole
Not sure.
fiery cosmos
but that has the perfect form as if you just plug in (n+1) in for n
you see this too right
like, you can get to the RHS of the implication by simply plugging in n+1 for all n
then that squared term is anomolous
opal oriole
Might be an error.
haughty mountain
then that squared term is anomolous
didn't we do this a while back and I pointed out those notes had a bunch of errors?
fiery cosmos
yeah i was getting that feeling, i just revisited it bc prof just told me to
we also did T(n) = 2T((n/2) + 17) + n is O(nlgn) IIRC
haughty mountain
fiery cosmos
ok you're right you pointed it out here
at least i'm able to see the same thing now, that's progress i guess
haughty mountain
🎊
fiery cosmos
we also did T(n) = 2T((n/2) + 17) + n is O(nlgn) IIRC
can you remind me how we did this one or just point out the msg
thanks i owe y'all so much, if it weren't for y'all i wouldn't have a chance in hell at this (i might not still but its infinitely better than i'd do in a vacuum)
haughty mountain
and there was some additional stuff earlier than that
you can search for posts from me containing 17
fiery cosmos
Ok thanks
fiery cosmos
it looks like you are allowing terms in here to be described by the O(n) term.. is that it?
haughty mountain
it looks like you are allowing terms in here to be described by the O(n) term.. ...
I'm being a bit lazy. The O(n log n) term will dominate the O(n) terms anyway
fiery cosmos
i just wonder if i'm interpreting your steps correctly. sorry if it is late where you are? what time is it?
haughty mountain
so I use the O(n) to contain terms that are at most linear so I don't have to keep writing stuff that ultimately don't matter
fiery cosmos
right
cinder moon
My first PyPI package — re-doing a readability algorithm from the original publication. I learned a few things along the way. Like, sometimes an algorithm's output is best modeled as an enum, not a number. https://github.com/public-law/new-dale-chall-readability
dark aurora
why is i&-i == rightmost bit? and what does i~&(i-1) do?
haughty mountain
why is i&-i == rightmost bit? and what does i~&(i-1) do?
for i&-i
-i is ~(i - 1) which might be more helpful
i - 1 will take the rightmost sequence ...100...000 and make it ...0111...111, everything else unchanged
Now all one bits in i correspond to a one bit in i-1 except the lowest one. So i&~(i-1) gives the lowest set bit
see how high 1 bits in i still align with 1 bits in i-1
i: 0b1010100
i-1: 0b1010011
thanks a lot I got it
dark aurora
How is it that my code passes the time limit of one second?
size, m = list(map(int, input().split()))
pairs = [list(map(int, input().split())) for i in range(m)]
lof = [[] for i in range(size+1)]
for i in pairs:
x, y = i
lof[x].append(y)
lof[y].append(x)
def func(n, lst):
if n==0:
return 1
sm = func(n-1, lst[:])
for j in lof[n]:
if lst[j]==1:
return sm
lst[n] = 1
return sm+func(n-1, lst[:])
print(func(size, [0]*(size+1)))```this task
If I copy the list every time the function is executed shouldn't it be 2**20 x 20 which over 20 million exections
and also loop through the pairs of n-1 which is at most 20
so the max should be 2**20 x 20 x 20 which way to many exections under one second for python
haughty mountain
If I copy the list every time the function is executed shouldn't it be 2**20 x 2...
first off isn't it just 20 * 2**20 you don't do any 20*20 work afaict?
there is also some early exiting going on, so maybe the worst case isn't so bad
umbral otter
It's looks so close but feels so far.
fiery cosmos
looks like by definition polynomials must have the form ax^3 + bx^2 + cx + d, but could also be degree zero polynomials, eg f(x) = x^0
degree 1 polynomial has the form f(x) = a_0 + a_1x
agile sundial
your d term there could be written dx^0
fiery cosmos
good point
public static i just saw where your name comes from, don't know what it means but its in the math text i'm reading
agile sundial
in a math text?? interesting lol, it's the main method in java
fiery cosmos
agile sundial
ah, that makes more sense
fiery cosmos
having trouble picturing what is meant in the formula
this is a great resource for people trying to convert from code to the math:
vocal gorge
wow, this would sure look nicer in a less procedural language
fiery cosmos
yea 😦
vocal gorge
like, this can be sum(math.prod(foo(i,j) for j in range(1,n+1) if j!=i) for i in range(1,n+1)) in Python
opal oriole
having trouble picturing what is meant in the formula
You can drag around P1 and P2.
opal oriole
The "current" x.
opal oriole
x1-x2 gives the x-distance between the two points.
And x2-x1 the same but negated.
So when x = x1, you have x1 - x2 in the numerator and denominator, so = 1.
Which is multiplied by y1.
The other term has x1 - x1 in the numerator, so it's 0, which is multiplied by y2.
So the end result is y1 + 0 or just y1.
So when x = x1, the y output of f is y1.
And when x = x2, the y output of f is y2.
fiery cosmos
yeah i get it so x1 causes y1 as output and x2 causes y2 as output
opal oriole
And the in between values follow the line.
fiery cosmos
by making the other terms eval to zero
fiery cosmos
did you try CLRS
idk how helpful it'd be but there is at least one chapter in there on dynamic programming if not more
how would i factor this? i asked in the maths server and got ghosted
some ppl really don't like helping with algebra haha
its supposed to wind up like this:
haughty mountain
.latex there are nicer ways to think about that last expression, it can be rewritten as
$$
y1 \frac{x - x2}{x1 - x2} + y2 \left(1 - \frac{x - x2}{x1 - x2}\right)
$$
grand havenBOT
edgy gazelle
idt this is the right place to ask but try multiplying the top/bottom of the second fraction by -1
haughty mountain
I should have had subscripts, but whatever
fiery cosmos
whats the first step i should do
i did a first step to get it in that form which im pretty sure is right
how should i proceed
haughty mountain
.latex there are nicer ways to think about that last expression, it can be rewri...
in particular, it's a case of doing a linear interpolation, e.g. t b + (1-t) a is a linear interpolation between a and b as t goes from 0 to 1
fiery cosmos
oh i see what you did, simply factored out y1 from first term and y2 from second
fiery cosmos
in particular, it's a case of doing a linear interpolation, e.g. `t b + (1-t) a`...
just trying to comprehend the algebra for now
wait where did the 1 - come from in the second term
haughty mountain
separate the terms of the denominator so you get 4 fractions total, combine the ones that contain x and combine those that don't into fractions again
haughty mountain
wait where did the 1 - come from in the second term
deadly trick, add 0x - x1 = x - x1 + (x1 - x2) - (x1 - x2) = x - x2 - (x1 - x2)and then you can separate out the x1 - x2 from the fraction
fiery cosmos
i don't know how to separate out the terms
haughty mountain
for brevity, lets define d = x1 - x2
y1 (x - x2)/(x1 - x2) + y2 (x - x1)/(x2 - x1)
= y1 (x - x2)/d - y2 (x - x1)/d
= y1 x/d - y1 x2/d - y2 x/d + y2 x1/d
= y2 x1/d - y1 x2/d + y1 x/d - y2 x/d
= (y2 x1 - y1 x2)/d + x (y1 - y2)/d
line 2->3 is separating (a-b)/c = a/c - b/c
line 3->4 is just reordering terms to have the ones with x at the end
line 4->5 factors out common factors
fiery cosmos
the second term has x2 - x1 in the denom
haughty mountain
the second term has x2 - x1 in the denom
hence the - in line 2
a/(b - c) = -a/(c - b)
opal oriole
- -1/-1 is another fancy form of 1.
(-1 / -1) * a / (b - c) = (-1 * a) / (-1 * (b - c)) = -a / (-b + c) = -a / (c - b)
fiery cosmos
line 2->3 is separating (a-b)/c = a/c - b/c
looks like you simultaneously distributed the coefficients while pulling apart the fractions
i still don't see where the 1 came from but we got to where we needed to go without it so far as i can tell
haughty mountain
looks like you simultaneously distributed the coefficients while pulling apart t...
it's really just a(b+c) = ab+ac in disguise
haughty mountain
i still don't see where the 1 came from but we got to where we needed to go with...
which 1?
opal oriole
(a-b)/c = (1/c) * (a-b)
fiery cosmos
here
opal oriole
.latex $\frac{a-b}{c} = \frac{1}{c}(a-b)$
grand havenBOT
opal oriole
.latex $= \frac{a}{c} - \frac{b}{c}$
grand havenBOT
haughty mountain
here
ah, yeah that's me rewriting into a different form, let me write some steps out
again d = x1 - x2
y1 (x - x2)/d - y2 (x - x1)/d
= y1 (x - x2)/d - y2 (x - x1 + d - d)/d
= y1 (x - x2)/d - y2 (x - x2 - d)/d
= y1 (x - x2)/d - y2 ((x - x2)/d - 1)
= y1 (x - x2)/d + y2 (1 - (x - x2)/d)
no i'm great with what we did i don't want to confuse myself 😂
haughty mountain
it's not a complicated rewrite, add 0
a/b = (a + b - b)/b = (a + b)/b - 1
coming up with the right variables and finding the formulation is hard
it's basically just practice and recognizing common patterns and tricks
I didn't learn dp doing classes or whatnot
opal oriole
haughty mountain
I did competitive programming for a few years, so I've solved a lot of problems, a fair share dp problems
though I wouldn't say I'm amazing at it
fiery cosmos
do functions map between set set domain to the set codomain? or range perhaps?
jolly mortar
functions dont need to map something to every element of the codomain, the range is the subset of the codomain containing just the elements which are actual outputs of the function
opal oriole
Range is ambiguous (either codomain or image).
fiery cosmos
range seems more concrete (just outputs) then what is codomain?
codomain or set of destination of a function is the set into which all of the output of the function is constrained to fall.
sooo
opal oriole
If you plug in some values and get some out, you have some subset of the domain A that you plugged in, and you got out some subset of the codomain B. B is the image of A under f.
And range can refer to either the codomain or the image.
In the image I gave, red is the domain, blue is the codomain, yellow is the image (when you plug in some values from the domain into f).
If someone says range they probably actually mean image.
As the term "range" can have different meanings, it is considered a good practice to define it the first time it is used in a textbook or article. Older books, when they use the word "range", tend to use it to mean what is now called the codomain.[1][2] More modern books, if they use the word "range" at all, generally use it to mean what is now called the image.[3] To avoid any confusion, a number of modern books don't use the word "range" at all
The confusion is caused by old books meaning codomain, and new ones meaning image. So new books don't use "range" at all now.
fiery cosmos
ahh this is typifying what this guy is saying in his book is that part of the difficulty in math is that the pedagogy is a bit scattered and not contained in a centralized place
what exactly is this theorem telling us:
opal oriole
ahh this is typifying what this guy is saying in his book is that part of the di...
Yeah and across languages too. Like how in English they use "identity element" and everyone else uses "neutral element".
fiery cosmos
opal oriole
For any n+1 points, there is a unique polynomial degree (at most) n that goes through all of them.
jolly mortar
eg. If you have 3 points theres always a quadratic of the form ax^2+bx+c that passes through all of them
fiery cosmos
there are 10 points at which a 9th degree polynomial crosses all of them?
grand havenBOT
jolly mortar
just one
fiery cosmos
oh wow
so if i pick 3 points in the euclidian plane, there is only a single 2nd degree polynomial which will pass through all of them, eg a single correct answer
jolly mortar
ye
fiery cosmos
thats sort of remarkable
jolly mortar
2 degree or less to be precise, if the three points are collinear then you only need a linear polynomial
fiery cosmos
2 degree or less to be precise, if the three points are collinear then you only ...
and it doesn't violate the theorem bc there is only one polynomial of that degree which passes through all
jolly mortar
the theorem says "of degree at most n"
fiery cosmos
how then is it not violated if you select 3 colinear points and connect them with a degree 2 polynomial and a linear polynomial
i guess the answer is no such two polynomials connect any 3 linear points
jolly mortar
yes the straight line is the only one, theres no other degree 2 polynomial which would pass through the 3 points
opal oriole
If you want to mess around with Lagrange polynomials: https://www.desmos.com/calculator/nkerwfajsh
@fiery cosmos
fiery cosmos
thats neat but i need to learn as much algebra as fast as i can 😭
last night the prof really took the wind out of my sails and made me feel like its not going to work. i'm going to take the course anyway and withdraw if my grades get bad enough. i don't understand bc its not an algebra course, surely i can learn enough to do the proofs / asymptotics / whatever else
just bc i haven't made a lot of progress on my own doesn't mean i can't learn during the semester. she also revealed that the uni has private tutors that are paid and only part of the engineering school? so i don't think i could get one even if i had money to throw around
opal oriole
More points for fun: https://www.desmos.com/calculator/qdb3pr3jh3
haughty mountain
I think normally algebra and some calculus are prerequisites for algo courses because of algo analysis, but I think what's needed isn't that advanced
though being used to do algebra and rewriting expressions is pretty important
vocal fiber
Algebra is needed yes
Calculus, I don't think so
Never really had to do any calculus in my Data Structures and Algos course, especially for Complexity analysis
what you do have to do a lot is solving recurrence relations
fiery cosmos
i've been practicing that quite a lot hoping it will click. algmyr and squiggle have been helping me a ton. i got some good algebra practice today with algmyr, and squiggle walked me through how summations describe perfectly the work done by functions with recursive calls
we have been running a lot of these recurrence relations by substitution
vocal fiber
yea there's like a few ways to solve them, the popular one being substitution
There's also master's theorem if you want to learn later
fiery cosmos
i am aware of that yes and hope to get more practice in it
vocal fiber
but I would put that on hold for now if you are just starting with the basics
fiery cosmos
i've been going through all these basics for around a month including practicing algebra, learning discrete math, and implementing pseudocode
vocal fiber
The special case of master's theorem is easy enough to understand, but the general thing is a beast
I have forgotten it already, it's been like 3-4 months since I had learned it
Would have to revise it again
vocal fiber
Referring to any kind of loop in the graph
There's no special name for an edge with same source and destination AFAIK
fiery cosmos
vocal fiber
I guess it is called loop
opal oriole
Graph Theory has a name for everything. Some are pretty funny.
vocal fiber
Who cares as long as the message is conveyed.
fiery cosmos
Graph Theory has a name for everything. Some are pretty funny.
you should see some of the bio terms 😂
doesn't that just sound, made up?
haughty mountain
There's no special name for an edge with same source and destination AFAIK
self-loop is a common term
fiery cosmos
last one i promise
they're just so funny
what do you call the array that a hashing function maps data to
IIRC its hash table / hash map
opal oriole
what do you call the array that a hashing function maps data to
Buckets / slots.
haughty mountain
depends what you mean, if you have chained hashing the thing containing the collisions is typically called a bucket
though there are hash tables that work differently
fiery cosmos
right
haughty mountain
e.g. python's hash table is a flat hash table, where you essentially just have an array
collisions are dealt with differently
fiery cosmos
oohh i am thinking about chaining using linked lists to avoid collision
i always forget about inbuilt libraries 🤦♂️
raven steeple
Made https://github.com/Agent-Hellboy/Visualise to visualise backtracking/recursion problem
subtle thorn
!voice-verify
languid hound
is there any function that returns all possible combinations of elements within input lists
ex: combinations([1,2,3], [4,5,6])
[[1,4], [1,5] ... [3,6]
jolly mortar
itertools.product
languid hound
itertools.product
thanks
fiery cosmos
file = open("log.txt","a")
from pynput.keyboard import Key,Listener
log = "sadsads"
def on_press(key):
print("{0}pressed.")
file.write(key)
def on_release(key):
if Key.esc:
print(1)
exit(1)
with Listener(on_press=on_press,on_release=on_release) as listener:
listener.join()
```if i do that it gives an error so i gotta make it
```import pynput
file = open("log.txt","a")
from pynput.keyboard import Key,Listener
log = "sadsads"
def on_press(key):
print("{0}basıldı.")
file.write(key)
def on_release(key):
if Key.esc:
print(1)
exit(1)
with Listener(on_press=on_press,on_release=on_release) as listener:
listener.join()
``` but when i change my code like that my file just dissappers
is this sufficient to prove T(n) = T(n-1)+n is O(n^2)?
T(n) <= cn^2 plus constants and lower order terms
haughty mountain
basically yeah, you could pick c = 1 and you have
= cn² - (n + 1) <= cn²
(any c >= 1/2 would work, actually)
fiery cosmos
well given that my expression finished as:
cn² - (2n + 1)c + n
haughty mountain
choose c = 1
= n² - (n + 1) <= n²
I picked a particular value for c
fiery cosmos
1*(2n + 1) =/= (n + 1)?
haughty mountain
-(2n + 1) + n = -(n + 1)
fiery cosmos
ok ok
haughty mountain
I pick a c large enough so that I can get rid of the +n
so I'm left with n² - (something positive)
which is clearly <= n²
fiery cosmos
right and this is where i need to keep in mind that it cannot be a negative number as asymptotics only deal with positive functions
and furthermore one cannot have negatively sized input
i've been going through my algebra book and woof.. i was really bad
haughty mountain
with c=1/2
= n²/2 - (n + 1/2) + n = n²/2 - 1/2 <= n²/2
n²/2 is pretty darn close to the actual answer
fiery cosmos
so looks like you used "dividing by number is multiplying by its reciprocal" to go in reverse from ((1/2)n^2) -> (n^2)/2
haughty mountain
one small tip, I would put <= when I do a step that actually makes something bigger, but = when I just rearrange/simplify
it makes it a lot simpler to read since you know what to expect
fiery cosmos
right right ok
haughty mountain
so looks like you used "dividing by number is multiplying by its reciprocal" to ...
I guess I'm used enough to it that I just consider those to be obviously the same
fiery cosmos
yeah i mean i should too, its obvious multiplying something by 0.5 is the same as dividing in half. i'm just in a weird place math wise
also i noticed i started the same types of substitution problems like 50 times looking through my notebooks so either i'm being impacted by stress or got covid brain or literally getting dementia of some kind. never in a million years would i have known i tried it so much
haughty mountain
right and this is where i need to keep in mind that it cannot be a negative numb...
asymptotics can totally be applied to negative functions, but as you say input size is >=0 and also we are counting operations so it's clearly >=0
fiery cosmos
i think in CLRS they make a big stink about nonnegative functions
like eg they're assuming all the functions they work with to be non negative
i need to practice problems that have like fractions / logs / exponents / functions alltogether
haughty mountain
like eg they're assuming all the functions they work with to be non negative
it's a sensible thing to assume
I guess asymptotics get a bit weird if you allow both negative and positive things
for stuff like time complexity everything is >=0 for sure though
fiery cosmos
hm ok i got some feedback apparently i need to work it until its in the exact form
fiery cosmos
how would i get from here to the exact form? Just pick a c?
can we use c=1/2 and then go from n²/2 - 1/2 <= n²/2 = ((2*(n²/2)) - 2(1/2) = n²/2) = n²-1 <= n²??
haughty mountain
how would i get from here to the exact form? Just pick a c?
wdym exact form?
what's the actual task asking for?
fiery cosmos
Idk that’s the only feedback I got. Most of these are from CLRS and they simply say “show that T(n) = expression is O(n^2)”
The question I posed was “is this enough to prove it’s O(n^2)” and the answer was no because it’s not in the exact form
haughty mountain
you're done here if you want to show that c=1/2 works
n²/2 - 1/2 <= n²/2
what is the exact phrasing of the question?
do you have a page I can look at?
fiery cosmos
Let me see
pg. 87
exercise 4.3-1
"show that the solution of T(n) = T(n-1)+n is O(n^2)"
i think we got there by taking c=1/2 and multiplying both sides by two to get (c(n^2)) - 1 <= (c(n^2))
haughty mountain
i think we got there by taking c=1/2 and multiplying both sides by two to get (c...
if you pick a specific c you shouldn't have c left in your expression
to satisfy the definition of big O you would technically need to find a c and a n0
what c to pick doesn't really matter as long as it's big enough
same for n0
fiery cosmos
Right we got it in the proper format with c=1/2 and then multiplying both sides by 2 makes the RHS in the proper form, exactly n^2 right?
haughty mountain
T(n)
= T(n-1) + n
<= c(n-1)² + n
= ...
= cn² - (2n+1)c + n
```let's pick c=1, n0=0
= n² - (n + 1)
<= n²
Ok tysm
haughty mountain
it shows the same constants work for T(n-1) and T(n), so in the end this shows the big O bound we want
dim berry
Looking for help to understand below code:
class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
queue = collections.deque([root])
How will deque convert 'root' element to queue?
haughty mountain
How will deque convert 'root' element to queue?
it doesn't
it's makes a deque from the list that contains root
dim berry
The code has deque([root]). Will [root] converts the tree to a list?
dim berry
([]) -> What does this denotes?
dim berry
Does [..] makes any variable to a list?
haughty mountain
as said, it's not a conversion, e.g. [1, 2, 3] doesn't convert the integers, it just creates a list containing the integers 1, 2 and 3
a list is just a sequence of things
fiery cosmos
course they could be variables (or any expressions) py x = 1 y = 2 lst = [x, y, 3]
fiery cosmos
Are there any types forbidden from lists? Like you can make a list of dictionaries right
agile sundial
no, yes
fervent canyon
why does this think that 4 is prime?
prime_list = []
def is_prime(num):
prime = True
for i in range(int(num/2)):
if i > 1:
if num % i == 0:
prime = False
return prime
for i in range(1,99):
if is_prime(i):
prime_list.append(i)
print(prime_list)
vestal citrus
prime_list = []
def is_prime(num):
prime = True
for i in range(int(num/...
- you don’t have to go to 1/2 of the input number; you only have to check up to the square root of the input number.
- range() with one argument creates an iterable (0 inclusive, arg exclusive). So, for the number 4, your function would have checked for divisibility by 0 and 1, except you also added the condition
i>1, so it actually doesn’t check for any divisors. - By the way, you can return a value from the function as soon as a non-trivial divisor is detected. Instead of having a variable
primeto keep track of the state, simply replaceprime = Falsewithreturn Falseandreturn primewithreturn True.
vestal citrus
Algorithmic prime generation is actually pretty interesting. Your approach works, but there are also methods like the Sieve of Eratosthenes, etc. Do further research if you are interested 😉
fervent canyon
gonna go look into that right now. thanks!
thats pretty neat-o its like backwards from what I was doing.
fervent canyon
trying my hand at algorythmizing the sieve now
such a different thought process to wrap my mind around. I come up with an idea that I think works, then it doesn't work at all 🙂
then i keep playing with it and eventually it works and i have no idea why
i am pretty sure this works up to a point then the index goes out of range
nums = [i for i in range(1,101)]
numbs = [i for i in range(1,101)]
numbz = [i for i in range(1,101)]
for x in nums:
for y in numbs:
if x % y == 0:
numbz[y] = "X"
whoops
brazen eagle
Hey everybody! I'm new to python and have an idea that I'm trying to implement. I've broken several calculations into different modules to run various situations. The problem I'm facing is that I don't quite know how to save those values to a data collector module which will be used to store the majority of re useable data. Importing every file and running instances of the classes in other modules seems... messy.
Eventually I'd like to export the data handler data to an interface and keeping it one spot seemed like the best way.
Secondly - I have a large amount of tables that I need to sort through based on a few conditions. In excel I could do index matches/vlookups and a whole bunch of stuff. How do I do that in python without programming hundreds of if else functions (which may or may not be how a couple tables work now)
Sorry this isn't necessarily the normal type of post here, it just seems that the calculator I'm building will end up having a lot more to deal with here than anywhere else.
fervent canyon
holy smokes
@brazen eagle sounds like a very ambitious project!
@brazen eagle what I would do in your situation, is try to break the problems up into small pieces. Instead of working on a module to store data, just keep it in the same file and keep it as an abbreviated list of just a part of your data set. you can surgically manipulate it from there. That way, you avoid all that pesky OOP classes and modules and blah blah blah until you know you are able to complete the computations you need to. Don't try to rush it, take your time and solve one problem at a time.
also, @brazen eagle i like your name.
ruby quail
Hey everybody! I'm new to python and have an idea that I'm trying to implement. ...
Instead of importing every module in a single file, let each module accept a DataCollector class as a parameter
You could look into pandas when working with spreadsheets in Python.
west latch
idk where should i ask this
will this code be slower or is there any good way than this?
any(list(map(lambda x: x if re.search("Ganyu", x) else None, banner)))
Basically what i wanna do is if the user input is exist on banner list
vocal gorge
idk where should i ask this
will this code be slower or is there any good way th...
to start with, there should never be a reason to do any(list(...)) instead of just any(...)
vocal gorge
and also, why not any(re.search("Ganyu", x) for x in banner)?
west latch
and also, why not `any(re.search("Ganyu", x) for x in banner)`?
idk if i can do that
aight cool
tqtq
solemn cipher
Hey everybody! I'm new to python and have an idea that I'm trying to implement. ...
You need Pandas 🐼… I started with a strong background in excel. Basically, a Pandas dataframe is like a spreadsheet, and instead of index matches and vlookups, you can do joins and merging on multiple tables or dataframes.
wheat glade
import abc
from dataclasses import dataclass
class Player(abc.ABC):
@abc.abstractproperty
def name(self) -> str:
""" """
@dataclass(frozen=True)
class Human(Player):
name: str
Human("me")
Creating the class instance fails. Is there a simple fix?
jolly mortar
!e
import abc
from dataclasses import dataclass
class Player(abc.ABC):
@abc.abstractproperty
def name(self) -> str:
""" """
@dataclass(frozen=True)
class Human(Player):
name: str
Human("me")
@jolly mortar :x: Your 3.11 eval job has completed with return code 1.
001 | Traceback (most recent call last):
002 | File "<string>", line 13, in <module>
003 | TypeError: Can't instantiate abstract class Human with abstract method name
stable pecan
```python
import abc
from dataclasses import dataclass
class Player(abc.ABC):
...
!e Probably what you want instead of an ABC is a Protocol, but if you really want to use an abstract property on your frozen dataclass, you'll have to get creative:
import abc
from dataclasses import dataclass
class Player(abc.ABC):
@abc.abstractproperty
def name(self) -> str:
""" """
@dataclass(frozen=True)
class Human(Player):
name: str
def __init__(self, name):
object.__setattr__(self, "_name", name)
@property
def name(self):
return self._name
print(Human("me"))
@stable pecan :white_check_mark: Your 3.11 eval job has completed with return code 0.
Human(name='me')
@fervent canyon Thank you for responding! It is a just a wee bit ambitious. So the calculator is a structural calculator, which will when done will encompass everything from a bit of web scraping for initial data, to analysis based on input for anything I’d need in a couple different materials, and report printing! Luckily, structural code as it is, is very module friendly, so each section is its own thing with a couple return values that are used in other parts. The couple modules I have put together run and get me good numbers! One problem at a time is great advice, this will be a long time in the making.
fiery cosmos
```
T(n)
= T(n-1) + n
<= c(n-1)² + n
= ...
= cn² - (2n+1)c + n
```let's pick ...
alg i'm not understanding what happens to these final terms. if i pick c=1 and n0 = 0, then n=1 (given by for all n greater than n0 definition), and we get n² - 2, and claim that since we end with n²-2 then T(n) <= O(n²). the same thing happens here: (queued to proper time): https://youtu.be/LC96q_6r3BQ?t=546 where he finishes with the proper notation except a single -(c-1)n term
i guess thats the "exact form" they want? it certainly makes sense that n²-2<=n²
haughty mountain
i guess thats the "exact form" they want? it certainly makes sense that n²-2<=n²
I'm not entirely convinced about the exact form part since the question asks about O(n²), it could be to find c and n0 that makes things work
There is an actual exact form
T(n) = n (n+1)/2
but that's not really what the question asks about
fiery cosmos
right. i'm really frustrated w my professors rn. they teach online school and do f***all, while we pay huge money
no wonder people turn to youtube
the answers i get via email are like "no, that's not correct"
super helpful 🙄
haughty mountain
alg i'm not understanding what happens to these final terms. if i pick c=1 and n...
we started with T(n-1) <= c (n-1)² and then we derive that T(n) <= c n² based on that
haughty mountain
the answers i get via email are like "no, that's not correct"
what's the exact thing they said?
fiery cosmos
so based on what i shared before (my handwritten expression), i sent and said is this sufficient to prove that the recursive function shown is O(n^2). their response: "no because it is not the exact form"
i also got:
"start by choosing a c and getting rid of lower order term"
which isn't helpful again, bc they're not specifying begin by choosing a c or select a c from the very beginning...
don't do online school
emailed my advisor 2 days ago, no response
how do you practice "the squeaky wheel gets the grease" not in person
haughty mountain
i also got:
"start by choosing a c and getting rid of lower order term"
that's what I did
picking a large enough c made it so we can get rid of the lower order term
opal oriole
If you want you can use induction to show that it works for c >= c0.
You kind of have to guess what the grader wants here which is pretty annoying. How formal?
haughty mountain
this is enough I think
T(n)
= T(n-1) + n
<= c(n-1)² + n
= ...
= cn² - (2n+1)c + n
```let's pick c=1, n0=0
= n² - (n + 1)
<= n²
I would think that is enough too.
haughty mountain
in short I mean to say every n >= 0 works fine
though you can pick a higher n0 and it doesn't really matter, the existence of such an n0 is the important part
opal oriole
c >= 1, n >= 0, but they seem to want a specific c, so just choose 1.
fiery cosmos
this is enough I think
```
T(n)
= T(n-1) + n
<= c(n-1)² + n
= ...
= cn² - (2n...
is there a final step here where you add (n+1) to the LHS* and claim T(n) + (n+1) <= n²? and if not how to i read those final two lines
haughty mountain
is there a final step here where you add (n+1) to the LHS* and claim T(n) + (n+1...
no, we have shown that if T(n-1) <= c (n-1)² then T(n) <= c n², for some appropriate c (and n0, though that turned out to be very boring in this case)
alternatively
T(n)
= T(n-1) + n
<= c(n-1)² + n {use assumed form of T(n-1)}
= ...
= cn² - (2n+1)c + n
<= cn² {if c >= 1/2 and n >= 0}
though finding the exact bounds for c and n seems overkill, finding some valid values is enough
fiery cosmos
its the final two steps i don't get
is it simply that n² - (some 2n constant) + n < n²?
i don't see how the final two lines there justify what we are trying to show
opal oriole
.latex For $c = \frac{1}{2}$, $$cn^{2}-(2n+1)c+n = \frac{1}{2}n^{2}-1$$
grand havenBOT
fiery cosmos
oh i think i see. i plugged in c=1/2 and n=1, and solved to get 0<=1
opal oriole
.latex $$<=\frac{1}{2}n^{2}<=n^{2}$$. For n >= 0.
grand havenBOT
agile sundial
\geq strikes again
fiery cosmos
i get (1/2)n² - 5/2 <= (1/2)n²)
brazen eagle
Instead of importing every module in a single file, let each module accept a Dat...
@ruby quail
How would a data collector class work so i wouldn’t have to write individual pass ins for every variable?
opal oriole
-1/2 yeah.
fiery cosmos
huh? and where did that - 1 come from in your RHS
opal oriole
Error.
fiery cosmos
ok
opal oriole
.latex For $c = \frac{1}{2}$, $$cn^{2}-(2n+1)c+n = \frac{1}{2}n^{2}-\frac{1}{2}$$
grand havenBOT
fiery cosmos
why are you subtracting something on the far right
you have two c's there
where is cn^2 - c from
opal oriole
.latex For $c = \frac{1}{2}$, $$cn^{2}-(2n+1)c+n = \frac{1}{2}-\frac{1}{2}*2n+\frac{1}{2}+n = \frac{1}{2}n^{2}-\frac{1}{2}$$
grand havenBOT
opal oriole
1/2 n, not 1/2
.latex For $c = \frac{1}{2}$, $$cn^{2}-(2n+1)c+n = \frac{1}{2}n-\frac{1}{2}\cdot2n+\frac{1}{2}+n = \frac{1}{2}n^{2}-\frac{1}{2}$$
grand havenBOT
agile sundial
btw you can just do \frac12 instead of \frac{1}{2}
opal oriole
Yeah I prefer {}, Also n^2 not n. Take 3:
.latex For $c = \frac{1}{2}$, $$cn^{2}-(2n+1)c+n = \frac{1}{2}n^{2}-\frac{1}{2}\cdot2n+\frac{1}{2}+n = \frac{1}{2}n^{2}-\frac{1}{2}$$
grand havenBOT
fiery cosmos
ok ok im with you idk how i got 5/2
opal oriole
.latex For $c = \frac{1}{2}$, $$cn^{2}-(2n+1)c+n = \frac{1}{2}n^{2}-\frac{1}{2}\cdot2n-\frac{1}{2}+n = \frac{1}{2}n^{2}-\frac{1}{2}$$
grand havenBOT
fiery cosmos
so it basically comes down to expression - constant k <= expression
opal oriole
expression - foo <= expression
fiery cosmos
right
opal oriole
As long as foo >= 0
fiery cosmos
ok well i'm glad we got there following the long route 🙂
this is what i need to comprehend
i'm also reading my discrete math book
set theory seems pretty straightforward
makes me want to know latex so i can write all the cool s*** i'm learning
ruby quail
<@943253295126954055>
How would a data collector class work so i wouldn’t have ...
Hard to say without knowing the data
agile sundial
makes me want to know latex so i can write all the cool s*** i'm learning
it's honestly not that hard, just takes like 15 mins to get the basics down
grand havenBOT
fiery cosmos
.latex ${A}}$
grand havenBOT
fiery cosmos
.latex ${x \mid x \text{ is positive and even}}$
grand havenBOT
agile sundial
.latex $${2x | x \in \mathbb N }$$
grand havenBOT
vocal fiber
makes me want to know latex so i can write all the cool s*** i'm learning
latex is pretty easy, at least the math part of it. The other typesetting for documents is still black magic for me
agile sundial
yeah the main problem is understanding what to write heh
fiery cosmos
.latex ${A \cap B \cap C^{c}}$
grand havenBOT
fiery cosmos
A intersect B intersect C's complement
opal oriole
A intersect B intersect C's complement
I recommend an interactive editor that lets you see the latex in real-time. So you can fix mistakes and all that. Much faster to try things out.
(Which I should have been using before rather than typing it in discord)
fiery cosmos
ok
fiery cosmos
right i need to graduate from MS word equations
agile sundial
what's this?
agile sundial
neat, i've just been using overleaf
opal oriole
Too laggy for me.
agile sundial
yeah, since it's for entire documents
opal oriole
For shared documents I sometimes use overleaf. But for my own stuff I prefer markdown for everything except latex for math.
haughty mountain
we don't want to show <= n² if we pick c = 1/2
we want to show <= n²/2
@opal oriole
if we show n² when picking c=1/2 you have an extra factor 2 which will create an exponential
opal oriole
if we show n² when picking c=1/2 you have an extra factor 2 which will create an...
Yeah. @fiery cosmos
opal oriole
The goal is cn^2, and we picked 1/2, so (n^2)/2 is the end.
fiery cosmos
haven't gotten any work done today and trying to understand set theory
brazen eagle
Hard to say without knowing the data
@ruby quail would you mind if I DM’d you? Might be easier to show that way. I have a few single value returns, and now one in a tuple! Eventually it will have strings that compare to a list for auto sizing of various components.
opal oriole
I'm not really sure what else they could mean by wanting the "exact form".
<= n^2 breaks things as @haughty mountain wrote.
haughty mountain
now i'm confused all over again
we are doing induction, we're assuming T(k) <= c k², we then show that if T(n-1) <= c(n-1)² then it follows that T(n) <= cn²
It's important that the c is the same
if I pick c=1/2 and show that if T(n-1) <= (n-1)²/2 then it follows that T(n) <= n², then I haven't proven the thing we needed to prove
fiery cosmos
hang on
when you say T(n-1), do you mean the expression on the LHS and plugging in n-1 for n? or do you mean the T(n-1) on the RHS, eg, the form of the expression we are evaluating
which is T(n-1) + n
haughty mountain
LHS
our assumed formula gives us an expression for T(n-1)
we want to verify that we get a matching expression for T(n)
fiery cosmos
i think doing this via text is adding more confusion
haughty mountain
we want to verify that we get a matching expression for T(n)
it's the point of the induction, "is this still true when we take a step up"
ok, let's step through the logic, we have this recurrence we want to show is O(n²)
(I'll use k instead of n here for a small bit to not have multiple n)
haughty mountain
we assume T(k) = c k²
haughty mountain
but k is a constant and n is a variable
huh? here k is a variable
haughty mountain
we assume T(k) = c k²
but we don't know if this is true yet, we want to verify that it's consistent with the recurrence
what I mean by "consistent" here is that if the inequality is true at some step, after taking another step it's still true
i.e. if T(n-1) <= c(n-1)² holds, then we can prove that T(n) <= cn² also holds
fiery cosmos
ok pause 1 sec
i think the RHS being equal to T(n-1) + other stuff is confusing me. bc right off the bat i can't see if you've decremented the LHS from n to n-1 and even if you did, if the RHS is just in the given form or its been generalized to ck^2 and then n-1 was plugged in
can you see why its confusing
bc you're manipulating it to be (n-1), but thats already the given form
in other words, if you change the LHS to be T(n-1) instead of T(n), then wouldn't the RHS necessarily become T(n-2)?
haughty mountain
in other words, if you change the LHS to be T(n-1) instead of T(n), then wouldn'...
it would, but it's not relevant here
T(n-1) = T(n-2) + n-1
but we only care about T(n-1) in the context of T(n) = T(n-1) + n
and we only care about replacing that recursive T(n-1) with a nicer expression, our assumed formula
fiery cosmos
so we are or are not going to change the T(n) to T(n-1) on the LHS
fiery cosmos
set equal to. bc i thought your whole thing was assume its true for the n-1 form, then show its true for n form, meaning we'd be analyzing T(n-1) = kn^2??
and i don
don't mean the T(n-1) on the RHS here
haughty mountain
we are analyzing T(n), but to do that analysis we want to make use of the bound T(n-1) <= c (n-1)²
fiery cosmos
ok so you are only talking about the expression following the equals sign
not the T(n)
do you see how it being in that form leads to so much confusion
when we're typically working with some n - 1 form
haughty mountain
not the T(n)
I mean, they are the same thing, they are equal