discrete-math

[coral raven]

can anyone help me with part c

i did part a and b fine but i don't see any way to apply them here

i can't prove the hint; even assuming the hint, i can't prove the result

[coral raven]

oh i'm stupid; i proved the hint at least

[coral raven]

ok i got it (with some help)

jesus christ

[left island]

Set values for each and see if it works.
P = I leave work early
Q = wife mad cause I'm making less money
R = wife happy cause I come home early
If it were an And (/) instead of Or (/) then by DeMorgans law both would be true.
Or I have no idea what I'm talking about cause I speed-ran a critical thinking course on Sophia Learning in 2 days ...

[tough sand]

Ok so consider this recursive definition of B := { set of all (rooted) binary trees }. I should emphasize, we're trying to uniquely define the set recursively.
(1) ∅ ∈ B
(2) If T ≠ ∅, then there exists a vertex, v, we'll call the root such that
T1 -- v -- T2

we see there's something wrong here right? how do we propose to fix it?

[tropic moth]

er whats wrong with it

[opal plank]

any recommendations for books I can find on discrete maths I just started learning mind you as I wanna get an idea before I start my first year in cs and I got nothing to do anyways

[soft void]

https://discrete.openmathbooks.org/dmoi4.html

my class uses this

[opal plank]

thanks

[oblique pelican]

Discrete Math and it's Applications by Kenneth Rosen is very popular

[wispy raven]

Hello, I'm currently revising for Boolean Algebra chapter. I'm not sure if I got the questions right, can someone help me confirm?

[still vortex]

did you swap the symbol for AND and OR gate?

[grand totem]

<@&268886789983436800>

[grim flicker]

does anyone know how I to do this?

like do I need to get rid of all non n^3 terms?

how do i do that

[cerulean radish]

Step 3 (replacing 3 by 3n^2 in the denominator) doesn’t seem right

Performing the polynomial division is a good start

[grim flicker]

wait doesn’t it work if i say k=1 tho (liek for n >= k = 1)

idk i think thats what my ta said

[grim flicker]

wair how come

[cerulean radish]

,w (4n^5 + 6n^2)/(7n^2 - 3) when n=2

,w (4n^5 + 6n^2)/(7n^2 - 3n^2) when n=2

,w 152/25 <= 19/2

Ah nvm

I missed the negative sign

[grim flicker]

bc if n>=1, ur making the denom smaller

yeaa

[cerulean radish]

Let me recheck

Yeah what you wrote is correct, you can finish by saying n^3 + 3/2 <= n^3 + 3n^3/2 = 5n^3/2

[grim flicker]

OHH okok

tysm!!

[coral raven]

where does the first equality come from?

what is (n)_i?

it must be a typo but i can't think what the correct thing is

where does 2i come from?

or is it just some obscure notation i don't know

i mean what is the number of cycles on i vertices i guess

[naive delta]

lmk if this is against group rules (will delete), but i'm looking for someone to just help sense check my group theory work leading up to my exam, and help me understand the intuition behind what i'm writing - happy to compensate you for your time and everything

[misty storm]

hi i need some help with q8b
i already got -9 = 2mod17 for q8a
but now i’m unsure how to tackle q8b
any guidance is much appreciated

[tired summit]

Use the hint at the top, and notice the repeated '17's in the base

Then, reduce the base and use problem 8a to help

[misty storm]

i’m still unsure how to answer it, could maybe give me the first step to start?

[tired summit]

Find the inverse of 1717171726 mod 17 first, this is just the inverse of 26 mod 17 which you can now use 8a

[misty storm]

yess i managed to solve it!

thanks a lot for your help!

[spare epoch]

for this question about the random graph Gn,p, I've used markovs to show that if E(X) < n/4 then P(X > n/2) < 1/2, but im not sure how to bound E(X) by n/4

[coral raven]

oh, this looks like it could be something like the probabilistic method

try considering how many cycles there could possibly be of such length

and the probability that each one exists

[spare epoch]

it looks like this thanks ! https://en.wikipedia.org/wiki/Probabilistic_method#Second_example

[final cliff]

Roy's Problem

[bitter ermine]

Hello can anyone help me with this question ?

With my approach I am getting particular solution's coefficient as 1/20 but in the book it is 49/20

what am i doing wrong

[little prism]

49/20 = 49*1/20 = 7^2*1/20 so you are probably just off by 2 in the indices

(havent looked through your work)

[robust monolith]

Hello, could you tell me which books it is please?

[lone bridge]

You replaced n with n+2
So at last when you did a_n = 7^n/o(b), there you should do a_n = 7^(n+2)/o(b)

I haven't solved these types of problems so idk what you are doing exactly but I noticed this thing after staring at it for 5 min

@bitter ermine

[oblique pelican]

That is Discrete Math and It's Applications by Kenneth Rosen

[chrome sand]

Someone knows how the hesse diagram looks for this relation
R={(0,0),(0,1),(0,3),(0,4),(1,1),(2,1),(2,2),(2,3),(3,3),(4,1),(4,4)

[bitter ermine]

Thanks

[bitter ermine]

It's this one

[copper sand]

Can we ask set theory questions here or is there a better place to ask them?

[clever sail]

depends what type of set theory question, if it's like naive set theory here is probably fine but otherwise might wanna go to the foundations channel

[coral parcel]

"Elementary" set theory is probably a better term than "naive".
In either case, that would also be at home in #proofs-and-logic.

(Namely, "naive set theory" sometimes means set theory with unrestricted comprehension, which is inconsistent).

[grim flicker]

can someone explain how to do the 2nd part of part c

[quick folio]

well by defintion of big O notation, it suffices to show that the limit of x^3/(x^2 + 4x + 23) at infinity diverges

[grim flicker]

I was thinking smth like this? but how do I show this more formally

[quick folio]

that's not far off from the limit proof, it looks good

[grim flicker]

ah okok

is writing “infinity <= C” okay, idk i thought it was kinda informal

is there a better way to write this

[quick folio]

yeah it is

you can use the rigorous definition of limits to formalise it properly

but your proof is good enough

[grim flicker]

oh okay, like an epsilon delta thing to show that the limit dne?

also is there a way to do this without limits, like only inequalities and algebra

or no

[quick folio]

yeah, you can do it algebraicaly as well

an equivalent form your claim is to say that there exists a C and k such that the inequality is always true

so, fix k and C and give a contradiction

or in other words, this is basically a standard epsilon delta proof

[grim flicker]

wait dym choosing specific values for C and k?

[quick folio]

no, you fix them

i.e. treat them as constants

[grim flicker]

how does that work, idt we’re doing this in my course

[quick folio]

yeah, from the looks of it this is a theoretical CS / discrete math class?

it's not a discrete math topic lol

[grim flicker]

yeaa “discrete math for cs”

[quick folio]

one proof using that method could look like this:

[quick folio]

Suppose for a contradiction that there existed a $C$ and $k$ such that $x \geq k$ implies $|x^3| \leq C|x^2 + 4x + 23|$.
\vspace{6pt}

Suppose that $x>0$, so the inequality becomes $x^3 \leq C(x^2 + 4x + 23)$. Now let $N>0$ be a big enough number such that $x > N$ implies $x^2 > 4x$ and $x^2 > 23$, so we get $x^3 \leq C(x^2 + 4x + 23) < 3Cx^3$.
\vspace{6pt}

But then if $x > 3C$ then $x^3 > 3Cx^2$, so the inequality fails when $x > \max(k,N,3C,0) > k$, which is a contradiction. $\blacksquare$

[vital dew]

HChan

[grim flicker]

tyty!

where did the 3C come from (why not like 28C)
and whats the difference between N and k here

[quick folio]

C(x^2 + 4x + 23) < C(x^2 + x^2 + x^2) = 3Cx^2

the trick is to find a number big enough number N such that the inequalities x^2 > 4x and x^2 > 23 become true

(it would be more rigorous to prove why such a number exists but I don't think you need that here)

the main idea here is that x^3 and x^2 + 4x + 23 are hard to compare, but x^3 and x^2 are really easy to compare. so if we can reduce the problem into that it becomes easy

[grim flicker]

ohh wait ok its 3Cx^2, sorry got confused bc it said 3Cx^3 in one part

what does k represent here (is N different from k?), and how come we have to take x > max(k, N, 3C, 0) and not just x > 3C

tysm btw!

[quick folio]

k is some random number that we start with

we don't know anything about it, all we know is that it exists

[grim flicker]

ah okay

[quick folio]

so the goal is to construct a number, bigger than or equal to k, such that the inequality fails

[grim flicker]

do we have to include 0 in max(k, N, 3C, 0)? (i thought C has to be positive? or can it be negative)

[quick folio]

there's no reason why C can't be negative

and there's no reason not to include it

[grim flicker]

okokk

is there a better way to write this or is this okay?

[quick folio]

remind me what \Omega means again

[grim flicker]

f(x) is a lower bound for g(x)

[quick folio]

I'm gonna be honest all of this becomes really simple if you use the limit definition

but let me look at this

[grim flicker]

acc I think this is better?

[grim flicker]

i wish my prof went over this 🫠

[quick folio]

Wait, that doesn’t look right… you haven’t used your definition of omega

It looks like you’ve proved that g(x) = O(f(x)) iff f(x) = O(g(x))

[grim flicker]

wait hm wdym?

this is like what I meant

[grim flicker]

does this seem correct 🥲

[cerulean radish]

Everything is correct except for v, you can give a smaller n

[grim flicker]

how do i know which one grows faster between x^3 and (logx)^4

[quick folio]

You can differentiate them a bunch of times

[quick folio]

Or actually, compare x^3/4 versus log x, that should be easier

[grim flicker]

ah okay

what if it was (logx)^k where k is a bigger number, like lets say 40

how would i know then, without graphing

[quick folio]

Same thing, you’re still comparing x^p/q to log x

[grim flicker]

but in this case, logx seems to exceed x^(p/k) after around x=17

also for these does it suffice to show a big n (eg n=100) where n! > 2^n and n^n > n!

like can i just use these values for a counterexample and call it a day lol

[quick folio]

Yeah, add a line about the rate of change and it’s good enough

[cerulean radish]

(logx)^n is always O(x)

[cerulean radish]

This does not contribute a counterexample

To show that a function f is not O(g), you should show that for every C > 0 and N, there exists n > N such that f(x) > Cg(x) (or with || if that’s the definition you are using)

[grim flicker]

wait so how do i do that

[grim flicker]

wait dym like take the limit as x->inf of ((logx)^k)/(x^m)
to see which one grows faster?

and use lhopital’s rule to do that?

[cerulean ore]

How do you prove the solutions of sliding window problems? For example this one? https://leetcode.com/problems/count-subarrays-where-max-element-appears-at-least-k-times/

I was able to solve it in a go, but I couldn't prove why my solution works.

Update: I was able to prove it. Thanks!!

[buoyant vale]

im trying to translate this sentence into mathematical operations, is the absolute value necessary here or i can drop it?

[oblique pelican]

Nah it looks right to me

You need the absolute value since you don't know which value is bigger/smaller

[grim flicker]

do the natural numbers include 0 in discrete math 🧍‍♀️

[cerulean radish]

It’s still up to convention

[hidden totem]

you can count starting from 1, in which case the convention would usually then not include 0

but technically, counting, if you want it to behave well and be well-founded, in most cases you want to start at 0, which would include it in the naturals

[plucky wedge]

am I approaching this wrong

[coral parcel]

It's still well-founded if it starts from 1, to be honest...

[spare slate]

Ngl I’d just consider what values x(4-x) can take on

[plucky wedge]

hmm I see what you mean

ehh im still a bit confused

how could I go about it by just algebraic manipulation

[coral parcel]

I don't think you can.

[spare slate]

Complete the square on x(4-x) and reverse engineer to start from trivial inequality and get to x(4-x)

Then take the reciprocal and multiply by 4

@plucky wedge @coral parcel

[coral parcel]

Hmm, I suppose that works.

[plucky wedge]

ill try that

[coral parcel]

Hmm, not completely algebraic manipulation; you need a separate argument that the denominator doesn't get negative.

[spare slate]

Eh that’s trivial though

Just put a little note to the side

Actually

[coral parcel]

Yeah, sure, but I don't think Branshi will get away with a completely symbolic argument without words.

[spare slate]

Oh that’s what they want

Yeah I can see that in hindsight

[hidden totem]

do you mean like just reassigning the names of like 1,2,3 or do you mean like structurally you can make that make sense?

[coral parcel]

I mean: the < order on {1,2,3,...} is a well-order, as is the < order on {0,1,2,3,...}.

[hidden totem]

sure, ill give an example

we can define cardinality of a set as n if there exists a bijection between the set and the von neumann set representing n

so like empty set is 0

in this way, how would you define 1? feels like no matter how you define 1 you get a impredicative definition

basically its like saying

what does it mean to have 3 things

the definition references 3

[coral parcel]

I wouldn't say that has much to do with what I'd understand by "well-founded".

[hidden totem]

ah right technical wording

so i think the word im looking for is regularity?

[coral parcel]

But still that's a pretty technical set-theoretical consideration that doesn't seem to dictate a choice for which set you call \mathbb{N}.

[hidden totem]

ok i think that answers my question then

i think youre right

[plucky wedge]

Do you think this question is asking me to prove the biconditional

or maybe just try to reason why B isnt invovled

[cerulean wind]

it is asking you to show the biconditional statement. it is just pointing out that its interesting that a condition for equality to hold is independent of B

[plucky wedge]

idk if my wording or format is all there but this is what I got so far, does it seem correct?

[cerulean wind]

it's correct... but its written confusingly.
assume that the LHS is true. pick an arbitrary c in C and show that c is in A

[weary tiger]

sorry for the hand writing. are my answers correct????

[plucky wedge]

Do they specify "sets mentioned in this section only" so that the set E wouldn't represent the set that contains all sets?

or could E never be that in the first place

[coral parcel]

There's no set that contains all sets, so E cannot be that.

What they mean is: When reading this section, assume that we have once and for all chosen some set E, and that all the sets we talk about happen to be subsets of E.

Also, writing $\epsilon'$ for $\notin$ should be a crime. (But that's not your fault).

[vital dew]

Troposphere

[plucky wedge]

oh ok I see, I also want to make sure I understand the difference between belonging and containing.
"for every set x there exist X such that x belongs to X" declares a set of all sets, can't happen
"for every set x there exists X such that x is a subset of X" doesnt delcare a set of all sets and is valid?

becaues if we have X in X is what causess the contradiction in the first one right
but X subset X is perfectly find I think so theres nothing wrong with defining a set like the second one?

[coral parcel]

Both of these are true claims (assuming that 'contained in' means 'is a subset of').

When you say "for every x there exists X", it is allowed to have a different X for each x.

[plucky wedge]

oh thats true

it should be there exists X for every x? and that would be false?

[coral parcel]

"Contains" is an awkward word because sometimes people say "B contains A" to mean "A is an element of B" and sometimes they mean "A is a subset of B". You'll need to figure out the meaning from context each time.

[plucky wedge]

ah ok

[coral parcel]

These are both false claims:

There exists X such that for every x, x is an element of X.
There exists X such that for every x, x is a subset of X.

[plucky wedge]

ok I can see why the first is false but let me try thinking about why the second would be false

[plucky wedge]

could it be because if we assume such a set X exist then take the set {X} it must be that {X} is a subset of X, then X belongs to X which leads to Russell's Paradox?

[coral parcel]

Simply having a set that is an element of itself does not lead to Russell's paradox.

It's more primitively that if every set is a subset of X, the in particular every {a} is subset of X, so every a would be an element of X, so X is the set of all sets, which we know doesn't exist.

(All this assumes we're working in ZFC set theory).

[plucky wedge]

oh that makes sense

[robust monolith]

Which year is this?

[weary tiger]

umm this is my finals in second year in computer science

algorithm and complexity!

[plucky wedge]

What does the word "temporarily" mean, in "temporarily absolute complement" here?

[coral parcel]

Bad and confusing wording.

They seem to be insisting on saying "absolute complement" about "a complement operation where we don't specify with respect to what", in contrast to the "relative complement" B \ A.
Then "temporarily" is their way of saying "we don't specify with respect to what because it's implicitly whatever base set we have decided to temporarily call E".

[robust monolith]

Thanks a lot!

[weary tiger]

np. have you taken this or are you about to take it? anyways my results just came i got an 80/85 so yeah

[plucky wedge]

ohhhh ok that makes more sense

[zinc vale]

Can I ask help here

[sullen thistle]

U can here https://discord.com/channels/268882317391429632/488120190538743810

[agile magnet]

yes, just ask your question instead of just asking if you can ask

[lavish geode]

Help pls

[true venture]

Do you need to just evaluate this, or are you trying to simplify ?

[tidal ibex]

what's the exercise's question here?

[weary tiger]

What is discredit math

Discrete*

[dreamy coral]

Study of structures that are either countable or distinct/separable

[weary tiger]

Fractional and stocasgit calculus where

[dreamy coral]

I don't think that stuff is discrete math

But it might be idk

[coral parcel]

Whatever math the CS majors at Our Glorious University need to learn.

[tired summit]

Git calculus

[still vortex]

its math that you don't get credit for

[steep spoke]

Do you guys know where I could get started in Discrete Mathematics? I'm self learning. I have V.K Balakrishnan's book on introductory to Discree Mathematics tbut that's really all I have as of now.

[shut ivy]

is this the correct recurrence relation

if so is this the same as the fibonacci sequence?

[little prism]

its not the same recurrence as the fibonacci sequence

or what do you mean

ok yes I see what you mean. yes. but prove it

[shut ivy]

is the recurrence relation correct?

[dawn junco]

can someone help me spot my mistake? im tryna solve for 7^644 mod 645 using the algo im using is attached below, im getting 79 but answer is 436

[vivid tulip]

I think this is the right channel.... I'm pretty sure after a lot of work the answer is the 16th odd number squared, which is 961... I can't prove it yet but if i use integers 1, .., 5 there is 1^2 octuple that works, aka (1,2,2,3,3,4,4,5) and if I counted correctly there are 9 octuples that work, (2,3,3,4,4,5,5,6), being one for the case of 1,...,6, and if i counted correctly there are 25 octuples that work for the case there of 1, ... ,7, one of them being (3,4,4,5,5,6,6,7). Continuing up to 1,2,...,20, one of the octuples is (16,17,17,18,18,19,19,20). If you know it a yes or no will suffice since I want to get it myself.. i might ask for a hint if I'm super stuck later

[oblique pelican]

you shoulve gotten r=466 on the first 1 bit

x starts at 7 then
i = 0 -> x = 49
i = 1 -> x = 466
i = 2 -> r = 466 then x = 436

[vivid tulip]

Been counting things up like this:

[vivid tulip]

So for integers 1,...,7 for the A's and B's, I keep counting 25 "paths" (would be nice to know the technical GT term for it .)

[true venture]

You could think of what gaps are possible when picking the 4 a's

Then the choices for b are the gap+1

Ex choosing 1 4 7 15 has gaps 2, 2, 8, 5. So for that choice of a's there are 3* 3* 8* 5 choices of bs

This would still be tedious to find all gaps for choices of a, but could be coded.

Are you looking for a closed form solution?

[vivid tulip]

Yeah, I need a number. They tell me that AI has said it's 20 choose 8 which I know is wrong. I have to correct the AI

I've never studied combinatorics lol

[true venture]

Is this one of those ai contract jobs?

[vivid tulip]

Yeah

[true venture]

Lol

To get a number I'd write code to find all a choices as 4 tuples. Then take the product of the differences +1 of those.

Maybe there is a cleaner expression but I don't see it rn

[vivid tulip]

Ok

I was just curious if this is a somewhat famous problem/ or kind of approach, since I've never studied this branch of math

Thank you 🙏🏻

[vivid tulip]

Did you mean 2×2×8×5

Choices

[true venture]

No because b can be less than or equal to the next a

[vivid tulip]

Gotcha

Ok I get now

[true venture]

I see the approach of 20 choose 8

But the b choices can be the same as the next larger a choice

[vivid tulip]

Huh! Really??

Ahh

[true venture]

Yea don't see a clean formula still

[vivid tulip]

I'll work on some code

[true venture]

But don't want to think too long as your the one getting paid!

[vivid tulip]

Absolutely not

[true venture]

Your not getting paid?

[vivid tulip]

Noo

I meant I don't want you to do it

Since you aren't

Technically I'm not for this it's just onboarding

[true venture]

Oh no worries, just usually the questions are ppls hw

[vivid tulip]

But it's still something I want to get right

I'm really scared of getting it wrong since I started yesterday

All the newbs are panicking lol

Including me

[true venture]

Yea, should be easy to code and for n=20 doesn't need to be that optimized or anything

[vivid tulip]

Thanks 🙏🏻

[true venture]

Good luck with on boarding

[vivid tulip]

Thank you

[true venture]

In a tree how are leaf nodes that have the same direct parent node referred to?

Is there a common name, like sibling leafs or something?

[weary tiger]

What about intersection when I is empty?

I think it should be universe of discourse

Which is just set of all these A alpha here

But I am not able to prove it rigorously using axioms

I guess it should be like set of all objects will be the ans

Because it's vacuously true

But then in standard ZF set theory

We don't have set of all sets

So it should be just our mentioned universe

But what about here? What's our universe here?

[weary tiger]

No it's not cause then intersection would be empty

So like I guess we can't define any universal set here right?

[odd heart]

Yeah, if you've got a fixed space (i.e. all your sets are implicitly assumed to be subsets of some set X), then the intersection of an empty family is defined by convention as being all of X, because that makes it the most consistent with the other properties of intersections (such as "intersecting over a larger family gives you a smaller set")

If you don't have a space, then indeed an intersection of an empty family would vacuously be a "set of everything", but that doesn't really work, so I'm not sure that even can be defined.

[past rivet]

one motivation for this is that the intersection of an empty family should be an "identity" or "unit" wrt intersection

you want it to be the case that, for two families $F$ and $G$, $(\bigcap F) \cap (\bigcap G) = \bigcap (F \cup G)$

[vital dew]

Pseudonium

[past rivet]

I.e. it doesn't matter whether you intersect them sequentially, or all at once

setting $F = \emptyset$ implies that $(\bigcap \emptyset) \cap (\bigcap G) = \bigcap G$

[vital dew]

Pseudonium

[odd heart]

Yep.

[past rivet]

in other words, $\bigcap \emptyset$ should be a set that, for any other set $A$ you're considering in the collection, $(\bigcap \emptyset) \cap A = A$

[vital dew]

Pseudonium

[past rivet]

the natural contender for this is the "parent" set

you can also extend this argument more generally for whenever you're doing some operation on an "empty" family, like empty sum, empty product, empty union

[odd heart]

Yep, but you do need one, so in the purely abstracct set theory the intersection of an empty family can't really be defined.

[past rivet]

in all cases, you want the result to be the "identity" or "unit" of the operation

[odd heart]

Since it would need to be the "set of everything" which isn't a thing in ZFC

[past rivet]

yep, ofc

[past rivet]

hence an empty sum is 0, an empty product is 1, an empty union is the empty set

etc etc

[odd heart]

Also note that it's not a serious difficulty, since you would hardly ever want to work at such a level.

Almost always the sets you're working with are all contained in some space that makes sense.

[past rivet]

mhm mhm

to put it another way, $\cap$ is often considered as an operation on $\textit{subsets}$ rather than arbitrary sets

[vital dew]

Pseudonium

[past rivet]

in terms of how it's used in practice

[odd heart]

Yeah, that's a very good way to put it; virtually every time you work with sets you start with a set that interests you, and any other sets you work with are subsets of it (or sets built from it in some other way, but those would also be subsets of some well-defined set, like all functions from X to X are subsets of X times X)

[weary tiger]

Thank-you both of you 😇 @past rivet @odd heart

[past rivet]

no problem!

and it’s good to see you again, outsider :)

[weary tiger]

@past rivet what are you pursuing? Like PhD?

[past rivet]

Currently doing a PhD in condensed matter physics!

[weary tiger]

Ohh ..I don't know much about it but When I was studying topology..I kinda studied topological phases of matter as well ..a Lil bit ...it was interesting

[weary tiger]

That must be toughhhh but interesting..
U have always wanted to do this? Like physics!!

[past rivet]

Well I think I’ve always liked physics, but I did do a math degree

And there’s certainly parts of math I like

But over the course of my degree I got increasingly pushed to applied math and theoretical physics

[weary tiger]

And you loveeee physicsssss!! So it's all goooddd

[past rivet]

Indeed, I love it very very much💝

[weary tiger]

😇😇😁🤍🤍

That's awesome!!

[shut ivy]

How can I prove if a recurrence relation of a sequence is the same as the fibonacci sequence

Do i use induction?

[clever sail]

Can you post the actual problem?

I mean the recurrence relation tells you how f_i is related to f_i+1

So if you can reduce your expression to f_i+1 = f_i-1 + f_i and the first two terms are 1 then it’s the fibonacci sequence

[clever sail]

Oh i see i thought they’d already given you a recurrence relation

Yeah I guess it would be an induction argument for this

So what have you tried so far

if you’re stuck try messing with the example they gave you of s_5 and figure out how you get s_6 from that

the shape of the argument should become clear

[shut ivy]

For the induction step I assume that $s_k = s_{k-1} + s_{k-2}$
How do I show $s_{k+1} = s_k + s_{k-1}$

[vital dew]

rabbits_advocate

[clever sail]

Well you can’t assume that cause that’s the thing you’re trying to prove

and s_k = s_k-1 + s_k-2 and s_k+1 = s_k + s_k-1 are just reindexed versions of the same thing

[clever sail]

I would suggest looking at the sums for 5 and notice how you can turn each of these into a sum for 6

it’s the same reasoning for any k and k+1 but if you’re having trouble seeing it then the example could help

[proper sun]

Chat what's the best channel to study discrete maths

[cerulean wind]

definitely not this one

[random sparrow]

can someone explain what vacuous truth is

[odd heart]

Every element of the empty set can explain that!

[coral parcel]

"Vacuous truth" is the fact that $\forall x: p(x) \to q(x)$ is true when $p(x)$ never holds, no matter what $q(x)$ is.
You can also state it as $\forall x\in A: q(x)$ is true when $A$ is the empty set, again no matter what $q(x)$ is.

[vital dew]

Troposphere

[coral parcel]

For example: "every negative perfect square is a multiple of 13" is vacuously true because there are no negative perfect squares.

[agile magnet]

For a less silly example, intuitively we would like the following statement to be true:

"For every prime p, p > 2 implies p is odd"

So we want our definition of implies to agree with our intuition that such a statement is true

[coral parcel]

That's not vacuous, though, because there are primes larger than 2.

[agile magnet]

right but we want it to be true for all p

[coral parcel]

Ah yes.

[agile magnet]

so like if you consider p = 2, then the statement is vacuously true

[agile magnet]

remember this is all just about making our definition of implies agree with how we want to think about logical statements

[coral parcel]

Hmm, I think one usually only calls it "vacuous truth" when there are no elements where the antecedent is true.

[agile magnet]

Really? I've always known it as any time we have to consider F -> T it's vacuous truth

not just when there are no elements

If you have a better not-silly example which is for no elements, that'd probably be a better example

[coral parcel]

(In case of doubt: Spamakin and I agree how the formal logic works, the disagreement is only about when the words "vacuous truth" apply).

[agile magnet]

I found when TAing discrete math these silly examples never really helped students understand why we define F -> T to be true

[past rivet]

empty set is a subset of everything

[agile magnet]

but actual examples that agree with how they think about basic things they know mathematically (such as even / odd number statements) help

[coral parcel]

Yes, I agree that an example like yours is better for motivating the truth table -- that's also what I've written down in https://math.stackexchange.com/a/4385559

[agile magnet]

true, but often in discrete math classes students are taught basic logic before set theory

[past rivet]

mhm mhm

[coral parcel]

The fact that forall x in Ø: whatever is true is a (perhaps unexpected) consequence of that truth table, but not in itself really motivating.

[past rivet]

in my case i found thinking in terms of subsets fixed my intuition with regards to implies

since in set land implies is just $\subset$

[vital dew]

Pseudonium

[past rivet]

and that's a lot easier to understand visually

[agile magnet]

yea I agree, just you have to pedagogically deal with this issue still

hence why I think even / odd number type statements are more useful

[past rivet]

mhm, sure

[agile magnet]

I think a silly statement like this would be a nice quiz or homework question or something, but not good for explaining the intuition behind the definition of logical implication

[coral parcel]

I agree, but I don't think "vacuous truth" needs refer to examples that are good for explaining that intuition.

[agile magnet]

in this context, explaining to someone who is probably new to this material, it should refer to such examples

[random sparrow]

100 messages and nobody pinged me

[coral parcel]

Hmm. It is proved that every odd perfect number has at least 10 distinct prime factors. If it is proved that odd perfect numbers don't exist, this fact will not stop being true -- but it will have been revealed to have been a vacuous truth all the time.

[agile magnet]

That's fun

Although needs explaining what a perfect number is + taking some stuff on faith

(I am being very nitpicky sorry)

[agile magnet]

sorry, I thought someone already did and I didn't want to spam pings

[agile magnet]

the first few messages here from me and Tropo are really the relevant ones, the rest is just follow up not fully relevant discussion

[coral parcel]

Perhaps it's more useful to think in terms of standard indirect proofs. Along the way we're saying things like "if p/q is a fraction in lowest terms such that (p/q)² = 2, then p and q are both even". Since we've proved that, it had better be true -- and it is, but turns out to be vacuously so.

[hidden totem]

my favorite way to think about vacuous truths is this:

a contradiction "kills" the proof, by principle of explosion

vacuous truths don't affect the proof one way or another, so by saying it is true, it functionally keeps the argument alive even though it may not move towards the desired conclusion at all

and this is analogous to multiplying by 0 and 1, the values we typically use in place of boolean values

every statement of a proof has to be true, S1 and S2 and S3 etc

so this is just 1 times 1 times 1 etc

the moment a statement is false, its like you multiply by 0

[weary tiger]

lemma 3.4.10: prove that if X is a set then powwr set of this set is a set..

Conversely, show that power set Axiom can be deduced the preceding axioms of set theory if one
accepts Lemma 3.4.10 as an axiom..
Let X, Y be sets. Define a partial function from X to Y to be any function f : M →
N whose domain M is a subset of X, and whose codomainN is a subset of Y . Show that the
collection of all partial functions from X to Y is itself a set...

how do I prove this twoooo....I am just not able to do this

[dreamy coral]

im a big fan of vacuous truth

thats how you prove that the empty set is unique as far as i know

or i should say that the empty set is a subset of every set more specifically

[lone bridge]

@flint sentinel you still need help with that problem?

ignore the name and tell me if you understand this

[gusty dome]

I am trying to prove if $A$ is finite then $f:A\to A$ is injective iff surjective

[vital dew]

Linear Afzal

[gusty dome]

Suppose $A={1,2,\ldots ,n}$, and let $f:A\to A$ be injective. We shall use induction on $n$ to prove $f$ is surjective. If $n=1$, there is nothing to prove. Assume the statement holds for some $n$, now if $A={1,2,\ldots ,n+1}$ then there is some unique $1\leq k\leq n+1$ in $A$ such that $f(1)=k$. Define $g:A\backslash {1}\to A\backslash {k}$ as $g(x):=f(x)$ for $x\in A\backslash{1}$. Certainly $g$ is surjective by inductive hypothesis and $f(1)=k$ so for each $x\in A$ there is some $y\in A$ such that $f(y)=x$.

[vital dew]

Linear Afzal

[gusty dome]

does it look fine? (one direction)

[little prism]

you havent even used the word injective in the proof

[gusty dome]

oh i see

[quick folio]

induction looks unnecessay for this direction. If f: A->B is injective then |f(A)| >= |A|

[gusty dome]

assuming author hasnt introduced cardinality yet

but yes, if injective then |A| <= |A|. But not surjective so |A|<|A| a contradiction

[copper plover]

hi there, i havea question regarding the proof of this:

log (n!) = Theta(n* log(n))

thoose are landau symbols: here the definition:
https://de.wikipedia.org/wiki/Landau-Symbole

its a question from a modul named algorithm and data structures but i mean its math...

i got as far as beeing able to determine c1 which i defined as the upper closing function:

but i struggle developing a c1 for n* log(n) to a lower limit for log(n!)

[cerulean wind]

it’s not a direct result of your inductive hypothesis that g is surjective since your inductive hypothesis deals with maps between a finite set and itself

[gusty dome]

I see. I got it, there is other nice way to prove it

[cerulean wind]

induction is fine, i was just noting that you need to be careful

the argument that HChan suggested is concise

i’m sure there are other ways to prove this, but idk that they would be any simpler than the ones given already

[coral parcel]

Hint: when n is large enough, at least half of the factors of n! are larger than sqrt(n).

[nimble nexus]

i heared a guy saying that he can proof by discrete-maths that if n persons are gay, so n+1 are gay too. How this is possible?

[oblique pelican]

Fundamental Theorem of Gay Theory

[cerulean wind]

it's June

[nimble nexus]

i am serious guys😭 is there any type that we can proof that?

[abstract breach]

I mean it would be some form of induction most likely but without any details of the proof there’s no way to know what he was talking about cause it’s not a mathematical thing lol

[cerulean wind]

he was trolling lol

[nimble nexus]

i would like to see someone trying that bcs i cant😭

[cerulean wind]

you can't troll... pfp checks out

[nimble nexus]

nooooooooooo😭

[odd heart]

It was probably a reworded version of the "All horses are the same color" fallacy: https://en.wikipedia.org/wiki/All_horses_are_the_same_color

[cerulean wind]

holy crap

can’t believe you made that connection

[oblique pelican]

You know what, that's exactly what I was thinking

Because there's no base case

Well I guess that specific example of horses is different, but I remember learning a similar example about cats in my discrete math class that went wrong because there was no base case

Might be in How To Prove It

Wait nah I think this is the same thing. Anyways

[odd heart]

Well, in this case there is a base case, because there is a gay person; the error is specifically in the P(1) -> P(2) argument

Everything else works fine, P(1) can be established (there is one horse of the same color, and there is one gay person; hello!), and the P(n) -> P(n+1) argument is valid if n is 2 or more

[oblique pelican]

Yeah makes sense

A sneaky argument

[vivid osprey]

I have not a lot of experience with rings, but is it a correct statement that the binomial theorem holds for any commutative ring? I feel like most statements of the theorem I've seen forget to mention that xy=yx, and forget to mention what x and y are even elements of (x and y are the variables whose sum we raise to the power of some natural number). I'm looking for the most encompassing description for which the binomial theorem holds. Maybe it is as simple as "it holds for any binomial, i.e. a polynomial in two variables which is the sum of two monomials". But then if we use that description, what are the conditions on the underlying field?

[past rivet]

It holds whenever X and Y commute, and multiplication distributed over addition (and is associative)

With addition suitably nice too

The orbit-stabiliser proof makes this apparent I think

[flint sentinel]

Which question was it?

[lone bridge]

@flint sentinel

[flint sentinel]

Oh no thank you, our prof already did this one last friday :)

[lone bridge]

ok np

[flint sentinel]

really appreciate it tho!

[past rivet]

<@&268886789983436800>

[tawdry plank]

does anyone know of any good video resources to review/study discrete math content?

[crude shore]

hi folks 🙂 say we know T(n) = T(n/2 - 1) + h(n), where h:N -> N is in O(n), and T(1) = 47. other than plain guessing the functional form of T, and without using akra-bazzi (i want to show how this can be solved manually) what resources would one use to conclude that T is in O(n)?

(i'd like to be as formal as possible 🙂 i'm showing kids how to prove these things rigorously)

[coral parcel]

That's what the (grandiosely named) "master theorem" is for.

[crude shore]

nah this doesn't fall into the hypotheses of that theorem

(the recurrence isnt of the form T(n) = aT(n/b) + f(n) for any a, b, f)

akra-bazzi, a generalization of that theorem, does cover this, but i dont want to use that bazooka 🙂

[coral parcel]

It is if you rewrite it in terms of U(n) = T(n-2)

[crude shore]

can you elaborate on this please?

oh, i think i see what you mean

[coral parcel]

Set U(n) = T(n-2).
Then you have U(n) = T(n-2) = T((n-2)/2 - 1) + h(n-2) = T(n/2-2) + h(n-2) = U(n/2) + h(n-2).
And h(n-2) is as O(n) as h(n) is.

[crude shore]

U(n) = T(n-2) = T((n-2)/2 - 1) + h(n-2) = T(n/2 - 1 - 1)+ h(n-2) = T(n/2 - 2) + h(n-2) = U(n/2) + h(n-2)

ok, that's one way, a little bit of a magic trick where U comes from, but it's generalizable a bit, so probably worth it

[coral parcel]

I found it by having a hunch that I could make the -1 go away with a constant offset, so I set U(n)=T(n+a) and carried that a through the calculation far enough that I could solve for the a that would let me get just U(n/2) at the end.

[crude shore]

is there an easy way to show that if U is in O(n log n), then T must also be? U(n) = T(n-2), in this case T(n) = 2T(n/2 - 1) + h(n). i already proved that if we write U(n) = 2U(n/2) + g(n), with g(n) = h(n-2), then g is also in Theta(n), as is h.

[crude shore]

(i proved it by hand using the definitions of those sets, wondering if there's a similarly slick trick)

[vale cairn]

My lazy method would be to note for n big enough, n/2 <= n + a <= 2n, so log(n+a) = log(n) + O(1) and (n+a)log(n+a) = (n + O(1))(log(n) + O(1)) = n log(n) + O(n)

[weary tiger]

idk if this is the right channel but Ill ask anyway since the others dont seem much more suitable
suppose that the sequence a_i is the same for all i.
Is this exponentiation for x > 0? And if it is, do you define all hyperoperations bigger than 3 this way?

(Note: the a_1 at the bottom should be a_i)

[tall comet]

The top limit is a + a + a ... x many times gives you a * x
You are then computing a + a + a ... ax many times
so you get a(a*x) = (a^2)x. So i dont think this is correct.

[weary tiger]

youre right, considering what you said I think that it needs an x amount of sums as the upper bound
thank you

[analog oak]

Let $\sum_{i=1}^{exp(a)}(a_{i})=a^{x}$, $\forall i \in \mbb{N}: a_{i}=a$

[vital dew]

Enterlessguy

[analog oak]

@weary tiger Is this what you're trying to do?

Where exp(a) is an expression in terms of a

[weary tiger]

Yeah, im trying to express exponentiation as repeated addition without using ...

[tall comet]

i think u can define it recursively as Sum from 1 to a^x-1 of a = a^x ?

[analog oak]

Well exp(a) has to equal to a^{x-1}

And I guess if you repeat that x times

You can define it that way?

[weary tiger]

that should work since im multiplying with a each time

[analog oak]

Use $\Pi_{i=1}^{x}(a_{i})$ instead

[vital dew]

Enterlessguy

[analog oak]

That ruined the whole point

https://cdn.discordapp.com/attachments/1165428384059379762/1353543919937388595/caption.gif

[flint sentinel]

I must proof this but I cant really find a function for it yet

this is what I got so far

or maybe f: X -> Y , f(C,D,E) = (?, N \ {D u E}, D u E)

[tropic moth]

how? remove leafs/terminal nodes/endpoints and contradiction with cycle?

[flint sentinel]

we started with a longest path. n >= 2 and then did some explanations why degree = 1 or >= 3

I can send the answer of our prof to your dms if you want

[neon cloud]

$\prod$

[vital dew]

knief

[tropic moth]

just post it here, others can learn. i think another way would be to remove all leafs, which is removing all deg1 nodes which means now all nodes have deg >=2 (because its 1 or >=3) so its at least 2 regular so there must be a cycle which contradicts tree

sorta my idea

[hidden totem]

do you have to make a combinatorial proof? have you tried an algebraic proof?

[vivid tulip]

Is this where I ask about basic combo

*combino

[true venture]

Yes

[true venture]

Or you can use a help channel

[vivid tulip]

I'm not looking for help how to solve it, I'm just wondering if there's a theorem or other mathematical tool I can use without bruteforcing it by computer

[vivid tulip]

If it wasn't obvious the situation describes an undirected graph

[tropic moth]

i wonder if an adjacency matrix would get it

16x16 matrix

iirc something something markov chains initial+final state + transition matrix

he said undirected

that means you can go 1,1 to 2-2 then back left 2-1

ie. starting at base, go up right, then left (because theres a bridge

[vivid tulip]

Yeah

The bridge doesn't collapse after you cross it, though that would make a different interesting problem

[tropic moth]

it does collapse

it says you cant cross it twice

[vivid tulip]

Oh derp

yeah lol

[tropic moth]

if it didnt, just keep going back and forth forever lol

[vivid tulip]

I wrote the problem and forgot

hahaha that's funny

[true venture]

Troposphere prob knows lol

[coral parcel]

Bridges don't collapse, they are burned.

[tropic moth]

ok so i wonder if its possible to break it down as a recurrence

but like over and over

so f(4,4) = f(4,3) + f(3,3)

then f(4,3) = f( ) bla bla bla

and its like a super nested recurrence

[true venture]

I know how to count paths from one node to the next without the no same step twice

[coral parcel]

You can't use each bridge more than once, but you can cross your track on an island, right?

[vivid tulip]

You mean, can I revisit an island

[coral parcel]

Yes

[vivid tulip]

Yeah, that's what I meant to say

You can revist islands not cross bridges twice

Was just curious if there was a slick result

[coral parcel]

That seems to make it very tricky to get any traction with a recurrence.

[true venture]

So every step you can take goes forward in the x axis, right?

[coral parcel]

It's undirected, so you can go backwards too.

[true venture]

Oh I see

[coral parcel]

Otherwise there would be just 1 viable path from 1,1 to 4,4.

[true venture]

Oh yea so the only way to get to 4,4 is the diagonal

[tropic moth]

what? no

(1,1) - (2,2) - (1,2) - (2,3) - (3,1) - (2,4) - (3,4) - (4,4)

zig zag up left then horizontal right

[true venture]

Then each path the goes backward has to start on the diagonal?

[tropic moth]

you can go left or downleft from (4,4)

2 ways

[true venture]

2,2 to 1,2 I don't think is allowed?

[coral parcel]

You can avoid the diagonal entirely except for the endpoints, eg 11 - 21 - 32 - 23 - 34 - 44.

[tropic moth]

why wouldnt it be allowed?

1,2 had a bridge upright, right, downright

so yea you can go 22 to 12

[true venture]

Oh yea

[true venture]

I didn't get it

[tropic moth]

to make it easier, just picture this

every lattice point does this

way too many combinations to count by hand

[true venture]

Yea I was just thinking that you had to step forward in one of those three directions

[tropic moth]

i think theres gotta be a way by recurrence, reversing from the top almost like a telescoping but nothing telescopes

so 44 = 34 + 33

then 34 = 24 + 23 and 33 = i dont know

and just continue on

and eventually itll be some big ass f(a,b) with low a,b but with coefficients

[coral parcel]

The trouble with a recurrence is you need to keep track of which bridges are already ised.

[tropic moth]

but we'd only have to count those f(a,b) that show up in the ""polynomial""

tbf theyre roman bridges

so they actually dont collapse

and the problem is actually miswritten

[true venture]

Seems hard 😕

[tropic moth]

lets start with bounds

theres at least 2 ways

[true venture]

Tru

Seems like a walk from (1,1) to (4,4) with steps (1,1) (1,0) (1,-1) (-1,1) (-1,0) (-1,-1) that can visit the same point more than once but any edge only once

Or number of such walks

[flint sentinel]

It must be combinatorial

[dire walrus]

Take a set $A$ with $|A|=n$ and then count the size of ${(R,S,T)\mid R\subseteq A, S\subseteq A, T\subseteq R, |R|=r, |S|=s-i, |T|=r-i}$.

[vital dew]

Nekory

[dire walrus]

For the rhs, first pick $T\cup S$, then $T$, then build your $R$.

[vital dew]

Nekory

[weary tiger]

I need to prove Cartesian products of two sets X and Y is a set..
I am starting with definition of ordered pair
if a and b are two objects then we define (a,b) = {{a},{a,b}} , now this is indeed a set ..by pair set axiom

Now I am taking P(P(X U Y)), basically the power set of power set of X union Y
This is indeed a set because of power set axiom
Now from specification axiom
I am taking all those objects which looks like {{x},{x,y}} where x is from X and y if from Y , so Cartesian product is indeed a set

Is this correct?

[dire walrus]

That works, and is the standard proof. Well done!

[weary tiger]

thanksssssss

[vivid raptor]

Hello, I started UND's Math 208 Discrete Math and was wondering if anyone had tips/tricks for Chapter 4 rules of inference. I can follow the logic of the proofs so far but it seems all over the place with using equivalencies and inference. Does it just require someone to memorize them all or do you constantly reference back to them in order to get to the conclusion? Thanks for any suggestions

[dire walrus]

Can you elaborate a little more on what you mean by memorizing? Memorizing what exactly? And what do you mean by equivalences and inference here?

[vivid raptor]

What do you mean by “what do you mean by memorizing?” I’m not sure what you’re confused about by “rules of inference” “equivalencies”. Can you expand?

[dire walrus]

Like, are you using these terms as we do in informal proofs, or formal proofs in logic? I am just trying to get some more context

[vivid raptor]

I'm using them in terms of formal proofs

[dire walrus]

Ah okay. So it really depends on the context. Logics with only a handful of axioms and inference rules, we just memorize. If it's a complicated logic system, then we refer back because it becomes nigh impossible to remember all the rules.

[fossil mural]

if possible i'd suggest trying to remember the axioms and rules based on what makes sense instead of purely as piles of symbols

but this depends a bit on exactly how they presented the axioms

if you're dealing with something like Meredith's axiom $$((((\varphi \to \psi) \to (\neg \chi \to \neg \theta)) \to \chi) \to \tau) \to ((\tau \to \varphi) \to (\theta \to \varphi)))$$ then i don't think there's any reasonably achievable level of understanding of logic where you can write this down without even having really tried to memorise it because it's just obvious

[vital dew]

bee [it/its]

[fossil mural]

but if you have a set of axioms like $\varphi \land \psi \to \varphi$, $\varphi \land \psi \to \psi$, $(\varphi \to (\psi \to \chi)) \to (\varphi \land \psi \to \chi)$, then if you kind of just think about it enough you can see how this expresses exactly what $\land$ means

[vital dew]

bee [it/its]

[vivid raptor]

this is mostly what i'm working with right now. We just got into Rules of Inference for Quantified Statements:

I take the rules pretty literal so for simplification, it doesn't mention that you can use the rule even if q is ¬q

[dire walrus]

So the equivalences are things you get used to after using them for a while. They are really the formalization of how we reason using natural language

The rules of inferences, they might take a little more time. Keep them close for a while and you will see you have them come to you naturally after some time

[dire walrus]

This is called instantiation of an axiom. These axioms/inference rules are technically schematas. They hold if you replace any of the variables by a well formed propositional formula.

[weary tiger]

Is this true for rationals? (if it is I may need to recheck the definition of rationals as I've lost all intuition because of this)

[cloud rampart]

well we can see that with two terms we have
[ \frac1{a_1} + \frac1{a_2} = \frac{a_1 + a_2}{a_1 a_2} ]
but with 3 terms we have
[ \frac1{a_1} + \frac1{a_2} + \frac1{a_3} = \frac{a_1 a_2 + a_2 a_3 + a_3 a_1}{a_1 a_2 a_3} ]
which isn't quite so nice

[dire walrus]

try an example

[vital dew]

cloud

[weary tiger]

this makes way more sense
How would you describe it for n divisors though? Or what field do I have to look into to learn more about this? (all I can find online is examples with n = 2 or 3) From what Ive seen its just multiplying the elements of the cartesian product with each other without having them being equal.

[cloud rampart]

well in order to get them all on a common denominator, you'd have to multiply each one by every a_i except itself

so you would be left with the sum of the products of every term except one on top

[coral parcel]

And most often one would go the other way and simplify that horrible numerator to (a1a2···an)(1/a1 + 1/a2 + ... + 1/an).

[dire walrus]

To expand on cloud's answer, it would look something like

$$\frac{\sum_{j=1}^n\prod_{\substack{k=1\ k\ne j}}^na_k}{\prod_{\ell=1}^n a_\ell}$$

horrible typesetting wtf

[weary tiger]

wait you can put restrictions on the product?

[dire walrus]

it's just a symbol

[vital dew]

Nekory

[cloud rampart]

you can notate the conditions on sums and products essentially any way you want as long as it's clear what is and isn't included

[weary tiger]

I havent had such an its not that deep feeling in ages
thanks for the answers yall

[gusty dome]

i wanna prove injective maps have left inverse

Let $f:A\to B$ be injective, so for each $y\in f(A)$ there exists a unique $x\in A$ such that $y=f(x)$. Also, we assume $A\neq \emptyset$ so there exists $a_0\in A$. Define $g:B\to A$ as
[g(y):=
\begin{cases}
x,&\text{ if $y=f(x)$ for some $x\in A$}\
a_0,& \text{ otherwise}
\end{cases}.
]
It is easy to see $g$ is well defined. Now $g\circ f(x)= x$ by the definition of $g$.

[vital dew]

Linear Afzal

[gusty dome]

am i going in the right way?

[dire walrus]

Yes

Nice

[gusty dome]

yeye

thank you so much

[flint sentinel]

Why is C = E\ D and not C = E \ (D n E) ?

[stray reef]

uhhh

wait that doesnt even make a difference does it

[odd heart]

It doesn't, those two operations define the same set

[dusky kettle]

$$\begin{aligned}E-(D\cap E)=E\cap(D\cap E)^{c}&=E\cap(D^{c}\cup E^{c})\&=(E\cap D^{c})\cup(E\cap E^{c})\&=E\cap D^{c}\&= E-D\end{aligned}$$

[vital dew]

oz1442

[stray reef]

ok well in that case idk why @flint sentinel's teacher was so anal about it

[flint sentinel]

Hmmm but if it is the same

where did I make a mistake with proving my inverse exists?

[chrome osprey]

@jade halo ask here ur graph thingy

oh i probably cant help much i dont rly remember anything useful

but someone else probably could

[jade halo]

ah right thanks - i believe i got it, it was just some nitpicky detail

[tropic moth]

i like how this one is pretty intuitive after a moment

[vale aurora]

hey there guys, i'm solving some time complexity homework

"A faster computer vs. a better algorithm":
If algorithm A runs in
O(n²) and algorithm B in O(nlogn) ,
how much faster must Computer X (running B) be than Computer Y (running A) to process 1 million items faster?
it is in homework
i think there is some issue with the text of the problem
if not which computer is faster is it X or Y

[twin zealot]

Can't you just solve this by plugging in 1,000,000, and then compare the ratios of the 2 algorithms?

This is excluding any constants or anything like that, so like 0(n^2) is just as valid on n^2 as it is on an^2 + bn + c where a,b,c are abitrary constants

[dire walrus]

It depends a lot on the constants. If A has a constant of 2 and B has a constant of, I don't know Tree(3), then what

Computer X would take like innumerable number of universal lifetimes to even finish processing 1 item

[twin zealot]

Thats why I wouldn't even want to deal with constants. Makes the thing to complicated.

[vale aurora]

let's say that both with constants 1

[twin zealot]

Just work with n^2

[twin zealot]

Then just take the ratio

[dire walrus]

Such questions just don't have good answers then, given that galactic algorithms exist

I would just write a note to whoever set the question to clarify more

[twin zealot]

Yea, they don't lmao. More clarification is needed.

[vale aurora]

when i take the ratio i get that X needs to be faster by 10^6/20 than Y

to be faster? but the result seems to me illogical

[twin zealot]

computer x running algorithm b should be faster, as nlogn is better then n^2

[dire walrus]

Did you take the ratio in the wrong order?

[dire walrus]

My prof when he is not amused by my sorting algorithm of just checking every pair

[twin zealot]

Brute force is always the answer

[dire walrus]

Time to do O(\infty) then using miracle sort

[vale aurora]

bogosort seems to suit me better

[dire walrus]

Technically speaking, bogosort is the best you can do when doing pessimistic algorithms

(why technically is because you can recurse bogosort to get bogobogosort and higher things, but they are still bogosort at the end of the day).

[lofty cloud]

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

No need to ask “Can I ask…?” or “Does anyone know about…?”—it’s faster for everyone if you just ask your question! See https://dontasktoask.com/

[grim flicker]

does this look okay

[dire walrus]

I haven't checked the calcs in detail, but there seems to be no error on a first skim

[shut agate]

Is this good

[gritty sinew]

Looks good to me

[grim flicker]

how do you find the tightest big O bound for this

ok wait I think my prof meant to reset j to 1 after each inner while is complete

[dire walrus]

there's a modification to the question?

[grim flicker]

i think so? bc if j isn’t reset to 1 after line 8, then “hello” is printed exactly n^2 times so it’s O(n^2)
but somehow my prof got O(n^6) ?

did my prof do it right.. bc even if you reset j=1 after line 8, i got O(n^4)

[cerulean radish]

You’re right

[zenith holly]

hi y’all! I’m taking this class my first semester of college in the upcoming fall, and I want to know what I can do to adequately prepare myself for this! any resources/recommendations would be greatly appreciated. (and no, I do not know what possessed me to do this to myself as one of my first classes on campus)

[cerulean wind]

learn how to write a proof, some propositional logic.
if you have time, look at some basic combinatorics and graph theory.

a commonly recommended book for learning how to write a proof is titled How to Prove It (i forget the author)

this covers terminology, basic set theory and prop. logic, and a few standard ways to prove mathematical statements like direct proof, contradiction, contraposition, (strong) induction, etc

[zenith holly]

omg thank u so much!! 🙌 I will for sure look into all of this <3

[flint sentinel]

How can I show that (D n E) U (E\D) = E ?

wait

that is pretty trivial

mb

[dire walrus]

Indicator functions provide a slick proof : \begin{align*}\chi_{D\cap E}+\chi_{E\setminus D}-\chi_{D\cap E\cap (E\setminus D)}&=\chi_{D\cap E}+\chi_E-\chi_{D\cap E}-\chi_D\chi_E(\chi_E-\chi_{D\cap E})\ &=\chi_E-\chi_D\chi_E+\chi_D\chi_E\&=\chi_E\end{align*}

[vital dew]

Nekory

[heady oak]

Is this swaping of sums done correct?

[cerulean radish]

Yeah

[heady oak]

@cerulean radish when does swaping of sums can cause a problem?

[cerulean radish]

If the bounds of the inner sum are dependent on the variable from the outer sum

[proven coral]

would this be the correct approach to this problem?

[cerulean wind]

could you rewrite this more neatly? or type it? that would help

[crude shore]

hi folks 🙂 is there an easy way to see why, in a planar graph, every face has at least 3 edges? that's clear to me for inner faces, but not for the outer, or "infinite" face. if we have something like a 2-edge graph with 3 vertices, are we counting each edge twice when counting the number of edges of the infinite face? if so, how are we defining this face and the edges of a face, so that this double-counting is correct?

[dire walrus]

If you look at the example you give, this has no faces. It is much more easy to see if you think of planar graphs as drawings on a sphere than a plane. Note that there is no bounded face now (but if you had three edges, you would have had two faces).

[crude shore]

it does have a face

i dont think a planar graph can even have "no faces"

[dire walrus]

If it had a face, then what does Euler's formula give you?

[cerulean wind]

the graph G = (R^2, empty) has no faces since its complement is empty lol

[dire walrus]

I intentionally made an invalid argument to make the OP realise how to define a face (this was a cool trick our discrete math prof showed us)

[cerulean wind]

aren't faces just connected components of the complement of the graph? so wouldn't this have one face?

[dire walrus]

A planar graph itself does not have any face.

A drawing of a planar graph does

[cerulean wind]

complement in R^2

its planar lol

[dire walrus]

I like to define them as the path connected components of the graph minus the edge arcs of a drawing

[cerulean wind]

wdym by minus the edge arcs?

that just sounds like you took away all of the edges, which just leaves the vertices

[dire walrus]

Since we are talking about simple graphs, this immediately implies that if the face is bounded, it must have at least three edge (arcs) and if it is unbounded then well, even zero edges suffice

[dire walrus]

Throw the vertices away too from the drawing

Then you look at the path connected components

[cerulean wind]

so...throw away the edges and the vertices?

[dire walrus]

Yup

[cerulean wind]

thats the same thing lol

[dire walrus]

Oh, you meant complement as in set complement

[cerulean wind]

yea

[dire walrus]

Not graph complement

[cerulean wind]

yea lol

[dire walrus]

Lol, misunderstood you

[cerulean wind]

all g

right, but connected/path connected is equivalent for nice graphs since they are closed subsets of the plane

[dire walrus]

I think it is mostly because R^2 is nice enough

Finite graphs are always good :p

[cerulean wind]

path connected and connected are the same for open subsets of a top space as long as the space has a basis of locally path-connected sets

so as long as there is an embedding of the graph such that its image in R^2 is closed, then you're good

so yea, i agree, R^2 is one of those nice spaces where our definitions agree

[crude shore]

v - e + f = 2, in this case v = 3, e = 2, so v - e = 1, and 1 + f = 2, so f = 1

so indeed it has a face

even if you have just one vertex in the middle of nowhere, 1 - 0 + f = 2, so 1 face

[dire walrus]

Yup, so you see, however you add edges, you always have one face (and it is the infinite face)

[crude shore]

i never doubted this

you're the one who wrote If you look at the example you give, this has no faces.

(when it does, in fact, have a face)

[dire walrus]

...

[crude shore]

..

[dire walrus]

Take this as the basis of your definition for a face then

[crude shore]

this does not help, since it does not define it in any useful way to count the number of edges in its boundary, in general

[dire walrus]

If you have no edges or just edges that don't bound anything, then you still have one face. This face is path connected

[crude shore]

it's just saying that "there must exist something that euler's formula calls a face"

im guessing it's double-counting edges

i.e. both edges in my example graph are counted twice

and the infinite face has 4 edges on its boundary, even though only 2 edges exist

[cerulean wind]

double counting is never okay in this context. what is your working definition of a face, if you have one?

[crude shore]

i have none that is workable enough to understand why "every face has three edges", given that only two edges exist. we must be double-counting.

(or perhaps making-up edges, but that seems even more suspect.)

[cerulean wind]

okay, so i will give you one. given a planar graph G embedded in the plane, a face of G is a connected component of R^2 - G

one example that might make this definition be sensible is if G is a triangle, 3 vertices and 3 edges

the complement of this graph has two components

each of them is a face

one is bounded, the other is not

[crude shore]

and how do you define its boundary, such that the (single) face in the graph i gave has at least 3 edges?

surely it is not a set, then, but a sequence

(or, if you want, a multiset)

[cerulean wind]

this definition is convenient because the boundary of a face is just its topological boundary

[crude shore]

(i suppose one could also define it by arbitrarily assigning orientations to the otherwise undirected edges, and using edges in both directions)

[dire walrus]

The infinite face does not need to have 3 edges bounding it. Can you tell me where you have seen this? (Generally we only prove this assuming the graph has at least 3 edges)

[cerulean wind]

yea, your graph needs to have at least three edges

there are counter-examples otherwise

as you have shown

[crude shore]

https://www.eecs.northwestern.edu/~nickle/310/2011/lec8.pdf

[dire walrus]

Ah, the proof is just assuming there are at least 3 edges. It skipped the obvious part of less than 3 edges. Because in that case you can just check it by hand

This is quite a valid complaint I have seen over the years

[cerulean wind]

if n is less than 3 2, 3n - 6 is negative

as a sanity check

[crude shore]

not n but m

in this graph, 3n is 9

the claim does hold for my graph, just not this proof

[cerulean wind]

right, my b

[dire walrus]

If you have less than 3 edges and the graph is connected, then you have at most 3 vertices. Now just enumerate and check.

That handles the edge case

[crude shore]

i guess having handled this case specifically, one can use induction

[dire walrus]

Maybe induction works (I haven't worked it out myself) but the handshaking proof is standard.

[crude shore]

first create a spanning tree, then add edges one by one, and count how many edges each face has

mm it's not completely trivial, because we can add an edge, that removes a bunch of edges from the external face (and gives them to a new cycle we create)

(and so it's not obvious that we couldn't add edges in such a way that the external face now has only 2 edges, e.g.)

oh sorry i meant the proof that the external face always has at least 3 edges

[cerulean wind]

there should be somewhere in the proof where they use m >= 3

[crude shore]

(to the deleted message; i realize my wording is confusing)

[cerulean wind]

i guess its like, staring us in the face. they literally say

Each face has at least 3 edges
so they have to be missing the assumption that there are at least 3 edges

[crude shore]

to be clear, the proposition im still not sure how to prove is: for every connected planar graph, with >= 3 edges, all planar embeddings have the external face with at least three edges

[cerulean wind]

ah, okay

[crude shore]

(i totally buy that all inner faces, that is all faces except the external ones, have at least three edges; they must be cycles-plus-possibly-juttings-of-trees-inside-them, and the cycle already gives them at least three edges)

(i guess they dont need to be trees specifically, one could have two nested cycles, joined by an edge, but i buy it nonetheless lol)

[cerulean wind]

is there anything wrong with this?

the external face has only two edges

[dire walrus]

Is there a vertex at the bottom?

[cerulean wind]

yea

[dire walrus]

And it is connected via two edges to the top vertex?

[cerulean wind]

no, one vetex at the bottom, with one edge connecting it to the diamond

sorry, the drawing was bad

[dire walrus]

give a better drawing maybe?

[cerulean wind]

but it wouldn't really matter either way i don't think

[dire walrus]

it's a little hard to parse what all the edges are

[cerulean wind]

sure

[crude shore]

uhh

isnt that a multigraph

(not a graph)

[dire walrus]

that is why I asked for a better drawing lmao, I am not sure which vertex connects where

[crude shore]

yeah multigraph

i dont think it holds there

same with loops

[dire walrus]

your top and bottom vertex has two edges connecting them

this is not a simple graph

[crude shore]

just have a single vertex and a loop that goes from it to it, now you have 1 edge faces lol

[cerulean wind]

ah, okay okay

and if you remove the bottom edge and vertex, its not planar

[dire walrus]

There is a trick we can use I think. You agree that every bounded face has at least 3 edges arpund it, right?

[crude shore]

yeah. i dont know how to prove it, but i'd eat a shoe if it weren't true

[dire walrus]

it's true

Okay, so we will convert the unbounded face into a bounded face

Take whatever embedding you want and inverse stereographically project to the sphere. Now take a point in the image of any of the old bounded faces and stereographically project it using that point. This face now becomes the unbounded face

So if the unbounded face had less than three edges, an inner face now has less than 3 edges, which is absurd

hopefully this works

[cerulean wind]

if there are less than three edges for a single face, then the graph either isn't simple (the boundary of the face is two parallel edges) or isn't planar (the boundary of the face is a loop)

[crude shore]

i think it works but it's overpowered af

[dire walrus]

planar embeddings are after all embeddings on a sphere, R^2 just makes it neater

[crude shore]

(i'll go back to my topology class to remember how those projections are defined lol)

[dire walrus]

in fact, euler's formula and the polyhedron classification are all because of spheres

[cerulean wind]

what is wrong with this?

[crude shore]

i "buy" it too but it aint rigorous... like, just cause i cant imagine something that violates that doesnt mean someone else wont

[cerulean wind]

what is un-rigorous about it lol

[dire walrus]

euler's formula literally says that you can build a sphere with two points, then two arcs joining those two points, then two discs attached to the two arcs. So the euler characteristic is 2-2+2=2 which is exactly the rhs of euler.

[crude shore]

i guess without a rigorous definition of boundary and face, most arguments are going to be nonrigorous

[cerulean wind]

i have rigorous definitions for face and boundary

[crude shore]

which is where the ugly fact that planarity is a topological, not combinatorial, condition rears its head

[dire walrus]

That is cool, not ugly

[cerulean wind]

if you would like, try to poke a hole in my proof and ill rebuke it

[crude shore]

can you use that to prove that if there are 1 or 2 edges in the boundary, then they must be loops or parallel edges?

[dire walrus]

Which is why embedding graphs in different surfaces is such an interesting question

[crude shore]

(i buy intuitively that that's precisely what 1 and 2 edge faces are; loops and multi edges)

[crude shore]

is the stereographic thing basically plopping the plane drawing on a sphere, then looking at any other cycle, and stretching the rest of the graph to the other side of the sphere than the one im looking at (which just contains the cycle)? i'm imagining it like one of those escher drawings

[cerulean wind]

sure. everything i talk about with respect to a graph will be about the graph embedded in R^2 subject to the rules here.
let G be a graph embedded in R^2. so we have a face F. its a connected component of the boundary of G. the topological boundary of f is a subset of G. if it weren't, then that wouldn't make sense if F were the only face, and otherwise, it would mean that two connected are in fact not separated (the closure of one is disjoint from the other)

the boundary of f is actually a subgraph of G since it is a closed subset of G. This subgraph can either have less than three edges or more than three.
if it has 1 edge, then we see that G is not planar since it has a non-planar subgraph. if it has two edges, then it is not simple.

only one thing to smooth out. the reasoning here is wrong

but the boundary of a face should be a subgraph of G

[dire walrus]

This is the hyperbolic metric in the poincare disk model

[crude shore]

i know some of those words

[crude shore]

i dont quite follow "the topological boundary of f is a subset of G"

G is a plane drawing of the graph, right?

[cerulean wind]

yes

okay, so if F is the only face, then we can decompose R^2 into disjoint sets G and R^2 - G

but R^2 - G is just F

so the boundary of F has to be in G, otherwise, R^2 would be disconnected

as F would be open and closed

if there is more than one face and the boundary of F wasn't contained in G, then either it is contained in F, which leads us to the same conclusion as before (F would be open and closed, so R^2 is disconnected)
or it intersects some other face F'. since F and F' are connected components of R^2 - G, then they are separated, and so the closure of F is disjoint from F', which is a contradiction

[crude shore]

(reading and going back to definitions)

[cerulean wind]

here is a more streamlined argument: if F is a face of G, then the boundary of F can't be contained in F, since F would be open and closed, which would mean R^2 is not connected (F is non-empty since G is not all of R^2 and F is not all of R^2 since G is not empty). the boundary of F can't intersect a face different from F since distinct connected components are separated [two sets A and B are separated if cl(A) disjoint from B and A is disjoint from cl(B)]

so the boundary of F must be contained in G

[dire walrus]

@cerulean wind Sorry for the ping, but can you put your topological argument in one place for convenience? I want to verify it agrees with what I have in mind.

[cerulean wind]

yea, ill type it all out in one spot

[dire walrus]

Thank you for agreeing to my awkward request :D

[cerulean wind]

im going to just prove the entire thing in as much detail as i can

im going to cite one lemma from a book

[dire walrus]

sure sure, this is so much fun :p

Honestly I never thought of this question before, i just took it for granted given how simple it looks

maybe my personal bias towards considering embeddings on the sphere made it easier to visualize why it seems trivial

[cerulean wind]

this is taking a while

typing up a latex document

might finish tmrw as it is late here

[cerulean wind]

yea, agreed

[eternal vigil]

{n k} denotes the stirling number of the second kind and [x^{n-k}]{f(x)} denotes the coefficient of x^{n-k} in the series f(x). Why is it possible that [x^{n-k}] can be placed inside the summation like in (1.6.7)??

[dire walrus]

If you think about it, you have a sum of polynomials. So the coefficient of something in a sum is the sum of those coefficients.

[hardy zinc]

Sorry, pasted something

Accidentally

[hollow token]

Hi all, I'm not sure if this fits into this channel (Graph Theory), but it's also a tall ask maybe. I'm wondering how exactly I'm supposed to go about solving this task. The task translates to:

For the given graph defined by a list/table of neighbours, determine all the distances starting from vertex c. Write down the algorithm used and explain your steps.

In general I understand how depth/distances work, but I'm more-so asking how I'm meant to visualize the graph itself so I can begin tracing steps for depth. I assume I can just create it as a Tree of sorts, or?

[oblique pelican]

I would draw 7 vertices in a circle (like the vertices of a septagon), label then a b c d e f g, and then draw the connections one at a time

[spring hound]

Pick an algorithm to use from this: https://en.wikipedia.org/wiki/Shortest_path_problem.

[cerulean wind]

dude proving some of the lemmas needed for this is such a pain

like, so many tedious details lmao

the jordan curve theorem for polygons is used as a stepping stone

this lemma specifically is troublesome

i have an outline, but its gross

[dire walrus]

Just leave it as a lemma and move on lmao

[cerulean wind]

the guy wanted the dets lmao

[rocky torrent]

hello

help me

i just don't understand it

what the hell is this

[azure elm]

Hii i have been studying the book how to prove it and there was a statement written by the author
‘premises cannot all be true without the conclusion being true' which as the author has stated makes a valid argument.

But I m confused

1. because arguments don't tend to be cleanly written there are a lot of nuances .

2. how do we know which arguments are fit for this form and which aren't in math? It would be great if someone could provide me examples .

3. why are some arguments considered valid and some are not?
   What's the purpose behind this and it's reason for existing in math?

Sorry this is my first time posting

[coral parcel]

It sounds like the kind of handwavy motivatio some authors like to say before they get into an actual technical discussion, so if it doesn't resonate with you, just skip over it until you get to technical stuff and the probably get back to it afterwards if you still care.

[hollow token]

Is this a correct way to do the BFS algorithm for graph theory? I see my classmates using a similar but more convoluted method through tables, and I'm unsure if what I'm doing is wrong (even though i get the correct result)

[hollow token]

For each vertex I ignore neighbours that have previously been revisited somewhere. Q represents a queue of vertices that haven't been visited yet. In the end, 9, 8 and 1 are not visited since they have no unique/unvisited neighbours by the time they're up for processing.

[dire walrus]

Can you provide your neighborhood list please? It's hard to see given they have been crossed out

[hollow token]

1 -> {2,8}
2 -> {1,8,3}
3 -> {2,9,4,6}
4 -> {3,5,6}
5 -> {4,6}
6 -> {5,4,3,7}
7 -> {8,9,6}
8 -> {1,2,9,7}
9 -> {8,7,3}

[dire walrus]

Thanks

[dire walrus]

And you are starting the BFS from which vertex?

[hollow token]

Vertex 5

Sorry, forgot to mention that

[dire walrus]

cool cool, no worries

[dire walrus]

it's not that 9 8 and 1 are not visited, but you visit them but don't visit anywhere else from them

And I think you are doing it correctly (at least your queue sequences agree with mine)

[hollow token]

It's just that 9 8 and 1 don't have any neighbours that have yet to be visited

At least that's how I figured it works

[dire walrus]

9 is visited via 3, 8 is visited via 7 and 1 is visited via 2

[hollow token]

Yes

[dire walrus]

So you still visit them

Your algorithm never stops before the queue is empty

[hollow token]

Well, yeah, because they might have neighbours on their own that need to be visited

[dire walrus]

yup. So when you clear your queue, you are visiting them

popping from the queue is akin to visiting

[hollow token]

Is it invalid to just write down that they don't have any neighbours, so visiting them is not necessary, or should I write down 9: no unvisited neighbours, 8: no unvisited neighbours, etc?

[dire walrus]

none of that. You just write down the sequence in which you visited your vertices

that is, the sequence of pops from the queue

[hollow token]

Do you mind elaborating what you mean?

Or like, providing some visual for this

[dire walrus]

Your ultimate goal is to find the BFS sequence, right?

The sequence in which you visited vertices?

[hollow token]

It's to find the distances of all vertices to the vertex 5

At the end I write a top-to-bottom list of all distances, like this:

5 -> 5 : 0
4 -> 5 : 1
6 -> 5 : 1
3 -> 5 : 2
7 -> 5 : 2
2 -> 5 : 3
9 -> 5 : 3
8 -> 5 : 3
1 -> 5 : 4

[dire walrus]

right, okay

bear with me, this might be long.

[hollow token]

It's alright, I gotta prepare for my exam on Tuesday :P

[dire walrus]

I will outline the procedure I follow, you tell me if it is okay for you

alright?

[hollow token]

Sounds good

[dire walrus]

Right

So for distances, I start with 4 things :

A visited list with the vertices in order

Visited : 1 2 3 4 5 6 7 8 9

A result list, initially empty. This will finally have the BFS sequence.

Result :

A Queue, initially empty. The algorithm stops the moment the queue becomes empty again.

Queue :

A distance list, initially empty. We will fill it as we go along. The n-th item in this list contains the distance from the starting vertex to n-th item in Result.

Distance :

Is this setup agreeable to you?

[hollow token]

Yes

[dire walrus]

Cool, let's start now.

The first vertex is 5, push it to the queue. I can't cross anything here, so I will just delete that number from the Visited list.

So now we have:

Visited : 1 2 3 4 5 6 7 8 9
Result :
Queue : 5
Distance : 0

So 5 has 0 distance from 5

Next we pop this from the queue and add its neighbors in the queue, mark the distances of these vertices as 1.. Since we popped it from the queue, we visited 5 so delete it from Visited and add it to Result.

I just edited a little to make the order of operations a little clearer

So we now have
Visited : 1 2 3 4 6 7 8 9 (Observe no 5)
Result : 5
Queue : 4 6
Distance : 0 1 1

Does this make sense?

[hollow token]

Yep I'm following

So then we'll pop 4 and add its neighbours that are still in Visited to the queue

[dire walrus]

Cool, now we pop 4, add its neighbors (that haven't yet been visited) to the queue, mark the new distance as 2 (since we deleted a vertex with distance 1), mark it visited and add it to result.

[hollow token]

Then add 4 to result, and remove it from Visited

[dire walrus]

yup, and a few more things

Visited : 1 2 3 6 7 8 9 (Observe no 4)
Result : 5 4
Queue : 6 3
Distance : 0 1 1 2

Next we pop 6, add its neighbors (that haven't yet been visited) to the queue, mark the new distance as 2 (since we deleted a vertex with distance 1), mark it visited and add it to result.

Visited : 1 2 3 7 8 9 (Observe no 6)
Result : 5 4 6
Queue : 3 7
Distance : 0 1 1 2 2

Next we pop 7 3, add its neighbors (that haven't yet been visited) to the queue, mark the new distance as 3 (since we deleted a vertex with distance 2), mark it visited and add it to result.

[hollow token]

I think we pop 3 now, right?

[dire walrus]

nice, yes. We pop 3

paying attention

Visited : 1 2 7 8 9 (Observe no 3)
Result : 5 4 6 3
Queue : 7 2 9
Distance : 0 1 1 2 2 3 3

Next we pop 7, add its neighbors (that haven't yet been visited) to the queue, mark the new distance as 3 (since we deleted a vertex with distance 2), mark it visited and add it to result.

Visited : 1 2 8 9
Result : 5 4 6 3 7
Queue : 2 9 8
Distance : 0 1 1 2 2 3 3 3

Next we pop 2, add its neighbors (that haven't yet been visited) to the queue, mark the new distance as 4 (since we deleted a vertex with distance 1), mark it visited and add it to result.

Visited : 1 8 9
Result : 5 4 6 3 7 2
Queue : 9 8 1
Distance : 0 1 1 2 2 3 3 3 4

[hollow token]

Now we'd pop 9, add no new neighbours (since all of them have already been visited), same for 8 and 1

[dire walrus]

yup

so they just go into result one by one

[hollow token]

So queue will be empty but result will be a list of [5, 4, 6, 3, 7, 2, 9, 8, 1]

[dire walrus]

yup

[hollow token]

And visited as well []

[dire walrus]

yes, because your graph was connected

if it was not, something might have stayed in visited

[hollow token]

Yeah, if there was an empty vertex (no edges) it'd stay there

[dire walrus]

Not just empty vertex. Think of just another graph to which there is no path from 5

you can never reach there using bfs by starting at 5

[hollow token]

I see

[dire walrus]

anyways

now the distance list holds the distances to [5, 4, 6, 3, 7, 2, 9, 8, 1] from 5 in order

[hollow token]

Yeah, that makes sense to me

So my method is analogous to this?

Well, "my method" more like my approach I mean

[dire walrus]

yes

it's essentially the same

The method I showed you is literally how a computer does it

[hollow token]

I implemented A* for pathfinding before

But yeah I did watch a lot of videos on BFS in CS

[dire walrus]

I think dasgupta has nice expositions on DFS and BFS

[hollow token]

It just confuses me when it's outside of code, since I can define the algorithm more abstractly instead of unrolling it into manual steps (just how my brain works, idk why), which I seem to have to do for my math class. DFS though I'm struggling to still figure out how to do on paper, we also have something called Prime's and Cruscal's

[dire walrus]

did you mean Prim and Kruskal?

[hollow token]

Yes

[dire walrus]

MSTs... somehow most books don't tell you that almost all MST algorithms are part of a bigger meta-algorithm

[hollow token]

We can get a task that asks us to determine a tree of a minimum range using these algorithms