discrete-math

[spark field]

Try and write each in equivalent forms on the side and then substitute so you can slowly remove the brackets

Like (q and p) is already simplified

So I would work on simplifying the part inside the not, and then once it's simple then negate it

Like this

((2+(4-3))÷3) looks complicated
But I can simplify (4-3)=1
So (2+(4-3))=(2+1)=3
And so on

The hardest part is identifying which parentheses go together, some color coding or drawing brackets on the bottom can help with that

[sinful tundra]

Okay

Thank you!

[steady crescent]

A general question. How does formal logic as taught in a Philosophy department compare to logic in Discrete Mathematics for example

This is very familiar to me only with a Philosophy background. So I'm curious about the extent of the similarities

[thin hinge]

if you graph the function as a bunch if dots, its discrete
if you graph the function as a connected curve, its continuous

[quick spade]

So yea it’s a discrete since I have you a point

And uses f(output)=input

[thin hinge]

the function itself isnt discrete, its continuous like every other function

thats is continuous

[quick spade]

Ok

Can anyone graph this

[thin hinge]

anyone can

as points $(x,f(x))$ and $(x,g(x))$

[vital dew]

Potus

[thin hinge]

oh damn just realised this isnt a help channel

yeah what youve just mentioned is just highschool maths

like, the very early stages

[latent raven]

guys can someone can give a formal proof of this:

$\exists x \in \mathbb{N} : p(x)$

[vital dew]

Owasan

[latent raven]

I need a formal proof

please help

[pine marlin]

What is p(x)

[latent raven]

p(x) is a predicate

sorry

[pine marlin]

If p(x) is always false then this can't be proven

[latent raven]

I said def

[pine marlin]

It depends on what is p(x)

[latent raven]

p(x), x is even

[latent raven]

here x is true and x is even '

[pine marlin]

So p(x) is the predicate "x is even"?

If so, just give an example of an even number

[latent raven]

yes

[latent raven]

ok but I needed a formal format proof

I can't write proofs but I understand

[faint jungle]

I mean, going overboard with this one, but you could use the fact that N is closed under addition

Let $n\in\mathbb N$

Since $\mathbb{N}$ is closed under addition

$n+n = 2n \in \mathbb{N}$

[vital dew]

Blackdeath39

[faint jungle]

Not sure if I misunderstood the question

[spark field]

We just need the existence of one, so
\begin{proof} $2 \in \NN$, and 2 is even, so $p(2)$ is true. Therefore $\exists x \in \NN : p(x)$
\end{proof}

[vital dew]

Coolempire93

[silk sable]

why do i need discrete math for computational science, im like 3 lessons in, still dont get it

[spark field]

Some of the stuff you'll learn later is applicable to CS (algorithms, strings, etc.)

The earlier stuff is more relevant to theory though

Understanding what you're working with, etc.

First-order logic can help you simplify your code a lot

e.g. de morgan's law so that you know that if !(a or b) is the same as if !a and !b

[silk sable]

hmmm, oki

[spark field]

Also if you do physical stuff it's relevant for digital design

[silk sable]

im doing computational neuroscience (so im in medical school and doing math/CS on the side), and i need to cut as much work in math as possible, try to be efficient yk

is discrete math worth it to learn?

[spark field]

Likely not

Not for that

imo

[silk sable]

im also thinking about learning ai tho

do you need discrete maths for that?

[spark field]

No, not really at all

[silk sable]

oh

[spark field]

If you want to understand it mathematically types are slightly relevant but a linera algebra course would be more helpful

[silk sable]

ahh

i see

thank you!!!

[spark field]

No problem 🙂

[azure smelt]

Translate each of the following statements into predicate logic using appropriate
predicates and quantifiers. Clearly state what each predicate means, and
clearly specify the domain of each variable.
i. “Every lecturer who gives clear notes is liked by all students in the
class.”
ii. “Some student in this class has submitted every assignment on time.”
iii. “No hacker can access every secure server.”
iv. “For every real number there is a larger real number whose square is
still less than 100.”

Can someone pls tell if I can use maybe two or three predicates for these parts. I tried checking from AI but it came up with so many predicates

For i) this is what i got which seems overly complex. Can someone help

[spark field]

No that seems correct, did you read it through?

For all x, if x is a lecturer and x gives clear notes, then for all y, if y is a student, then y likes x
Which means
if x is a lecturer and x gives clear notes <-> if x is a lecturerer who gives clear notes
for all y, if y is a student, then y likes x <-> all students like the aforementioned lecturer

Which is exactly what (i) said

[spark field]

I would suggest for your process you write it out like this

And then you will see all the predicates appear

Every lecturer who gives clear notes is liked by all students in the class

1. Identify nouns: lecturer, student in the class
2. Give them variables: lecturer will be x, student will be y

So now our statement is
for all x who gives clear notes, x is liked by all y

3. Identify verbs: give clear notes, liked
4. Turn those into predicates: C(x) will be lecturer gives clear notes, L(x,y) means x is liked by y
   You need to be careful with step 4, make sure you are clear about the domain of the functions - of course, only lecturers give notes, so the variable for C is x. For likes, we have lecturers being liked by students (in the original text), which translates to L(x,y) = x is liked by y (after step 2)

So now our statement is
For all x who C(x), L(x,y) for all y

5. Change any connection words into formal speech
   We don't say "who" we say 'such that', and we write for all before the predicate. But for all x such that C(x), for all y, L(x,y) sounds wrong. Why? Because this is an implication, we have to recognize that we sometimes use the comma for this in english. You just have to look at the sentence and see that this is cause-and-effect (see statement after step 4, or the original)

So our final answer is
∀x[C(x) -> ∀yL(x,y)]
With the domains x are lecturers and y are students in the class

@azure smelt these steps will help you get the simplest form

Noting that in the last step, ∀x must have [] to extend over the whole expression, because x is used in L(x,y) and if we just wrote ∀xC(x) -> ∀yL(x,y), the x in the second half would be undefined

[thorn hemlock]

How did you get the quantifier?

[spark field]

Keywords

"Every", "All", "Any" -> for all
"there is", "for some" -> exists

[thorn hemlock]

Yes sorry,meant how you could type the quantifier symbol on your keyboard?

[spark field]

Ah I just looked them up in Google and grabbed them

[thorn hemlock]

Oh cool,I didn’t know you could just simply grab them

Thanks then. I’ll take a look

[stray reef]

you wanted a proof that an even number exists?

behold:

6

[worldly sable]

SAY THE VALUE OF π

[latent raven]

I needed a formal proof

writting method that's why I gave an easy exaample

[latent raven]

I won't say you much cause I don't want to be banned

[stray reef]

i don't see the correlation

[latent raven]

[stray reef]

if you're going to say something that gets you banned, it won't be because you spoke to me specifically.

so why are you now treating me as somebody to walk on eggshells around?

[latent raven]

you're f girl

[stray reef]

i am a girl, yes... what's an "f girl"?

[latent raven]

you don't talk like that

[stray reef]

what?

[pine marlin]

sexism?

[latent raven]

no

[stray reef]

i don't understand what you mean.

i don't talk like "that"? what's "that"?

[latent raven]

I just wanted a formal format for wrting proofs any of you guys didn't help me

and you guys now making fun for that much easy question

is that my fault?

[stray reef]

i am not making fun of anybody here.

you still haven't explained what "f girl" means

[latent raven]

ok then I am sorry I hope you didn't mind

[latent raven]

sorry for that

[stray reef]

dude.

you're dodging my questions here.

[latent raven]

I meant f**king

[stray reef]

ah, so you meant "you're a fucking girl"

mmmm.

[latent raven]

wait

no sensors?

[stray reef]

you can say fuck here.

[latent raven]

ohh

[stray reef]

slurs are censored.

you can't say things like the N-word (insulting word for black people)

[stray reef]

i mean yeah that does sound pretty damn sexist.

but i guess you apologized for it now.

[latent raven]

yes I did and I hope you forgave me

I sometime say that things

sorry for that

I have problem with me actually,

[spare slate]

<@&268886789983436800> spammed across channels

[cosmic lake]

how you guys study it subject

[latent raven]

which sub?

[marsh osprey]

Discrete mathematics ofc

[latent raven]

why? you don't like it?

[marsh osprey]

i do

[latent raven]

so?

so you want resource?

or soemthing else?

[marsh osprey]

I don't know , ask the original questioner fam 😔

[latent raven]

I have a great resource

[marsh osprey]

I'd aooreciate it

[latent raven]

https://youtu.be/sbpCTjmw85g?si=d6fr-3NPwcVW6l4L

[vernal wave]

Is there a difference between a sequence and a list?

Sequences are functions with domain equal to N. I'm not sure if or how lists are formally defined, either by mathy people or CS people.

[stray reef]

"list" typically implies finiteness but there isn't that much of a difference besides

[stiff flint]

Hello peps

I haven't finished this yet, but I think the idea is already done. I also have another year before I was required to do a research paper and the paper they want is not for mathematical research but achieving the Sustainable Development Goals through applying stat not innovating on top of it.

So this probably won't get published though, so better just spread the idea to people. I hope everyone can benefit from this

[scarlet atlas]

For years now I've been trying to formalize a proper theory about "grids" you know like the sudoku/tic tac toe once

Ive tried writing proper papers about it but Im pretty unqualified

im gonna send my papers here to see if someone helps (or not)

[simple solstice]

Okay so, was going through my probability text's combinatorics section and stumbled upon this question (nothing assumed related to probability, just a raw combinatorics question)--

Given a group of four people, how many ways are there to break the people into two teams of two?

It said that the solution is three. Isn't it a more logical to arrive at \binom{4}{2} + \binom{2}{2} = 7 by the addition principle?

[quick folio]

the correct formula is 1/2 (4 2) * (2 2), which is indeed equal to 3

[simple solstice]

Oh

OH

[pine marlin]

You choose who goes in the first group and divide by two to remove overcounting since the two groups don't have an order between them

[simple solstice]

So, not even addition principle, just using the multiplication principle and computing those combinations.

AND EVEN THE OVERCOUNTING!

Thanks for the help guys.

[karmic summit]

So, what's considered discreet math?

[spare slate]

as per the channel description,

[karmic summit]

The automata theory part does hit, but what about Discrete calculus?

[spare slate]

I'd say that falls under "discrete subjects", but it's surely not restricted to this channel

just don't post the same thing in more than one channel

you have freedom to pick which channel you use though

[karmic summit]

Fair.

[odd heart]

It's when you do math but tell no one about it

[simple solstice]

It's math that is careful

[karmic summit]

discete.

[next flare]

Pls someone explain this
And don't think to say it's basic

How is this proved ?

[turbid sleet]

Assume that i'm working with maximal planar graph with minimum degree of 5. In this case, how can i show that there is a vertex v and neighbors v2, v4 such that there is no special vertex in V_v - {v,v2,v4}. I was using infinite decent, but it fails when v3 is outside the cycle v,v2,v4.

[haughty garden]

since the graph is planar, the sum of the degree of the regions is equal to twice the number of edges (i.e. 2|E| = sum of deg of each region) but degree of each region >= 3 (a closed region in a simple planar graph contains at least three edges incident to it) so 2|E| = sum of deg >= 3R

[haughty garden]

you basically obtain a handshaking lemma kind of argument but on planar graphs

[west kindle]

what degree do U do

[next flare]

Bachelor's in computer science.

[west kindle]

oh I see thanks 🙏👍

what year?

[flat lintel]

Me too

[flat lintel]

I already finished

[west kindle]

have you gotten a job?

what career do you wish to pursue?

[flat lintel]

Yes, I work at a sustainable company as a software engineer

[next flare]

I'm in third year 6th sem

[flat lintel]

That is... Complicated. My dream career would be studying things that I'm interested in and being payed for it and also have guidance but of course that doesn't exist x)

And also I couldn't have a positive impact on the environment, could I?😅

[next flare]

Have you tried gate

[flat lintel]

What?

[next flare]

Sorry where are u From

Ps

[flat lintel]

Portugal

[next flare]

Ok fine my bad
I ask why don't you join any research programs or PhD

[flat lintel]

I also thought about that but... Idk...

Here in Portugal research is very precarious unless I would do part time

But I also really love the company and the people 🙁

[next flare]

I see I'm from India I'm preparing for exam called gate
It is for higher studies like masters and PhD in better institute that why I asked you

[flat lintel]

Ah I see

Well, I can always study things by myself whenever I want, although yes, it's hard because I don't have professional guidance😅

Also, do you know the app obsidian? 🙂

[next flare]

No what is it

[flat lintel]

Is an app to take notes😊

[next flare]

Can I DM you don't you think we could be banned from here
Meanwhile mods are counting unwanted msg limit and then ban

[flat lintel]

Sure

[west kindle]

oh nice

did you recently graduate?

[west kindle]

ah i see. and is your bachelor's 4 years long?

[west kindle]

sounds like academic research

ngl i feel like my dream job would be teaching but the pay is so off-putting

[west kindle]

i had no idea postgraduate programmes had admission exams 😂

im not that old yet

i finished high school but im not in university yet

[flat lintel]

@next flare In 2023

[west kindle]

hmmm i see

were you guaranteed a job when you graduated or did you have to spend long searching?

software engineering is one of the pathways im interested in

[flat lintel]

I waited a little then got admitted then got fired because of a stupid attitude I had then waited a VERY long time then I got at this company by the help of an autism organization😅

[west kindle]

wut

well you made it atleast

[flat lintel]

Yeah, it's weird

Yes😊

[west kindle]

do you earn a good pay rn?

[flat lintel]

Not really, it's like 1200€ and something but, you know, I'm happy where I am

I'm in a not for profit company btw

[west kindle]

how

oh

[flat lintel]

How? Pay is shit in here mostly😂

[west kindle]

😂 lol

[flat lintel]

Poortugal

I really wanted my country to invest more in science instead of shitty turism but oh well🤷‍♀️

Well, I'm gonna sleep, it's like 5:51 am, lol

[west kindle]

lol

[quick spade]

Hey

[dim lion]

hey

[charred totem]

hello

[carmine vector]

Anyone doing the MIT math for CS Spring 2024 course?

[fluid quail]

@quick oak

[burnt meadow]

uhh

can anyone provide me with resources or give me directions as to how to start my journey of discrete maths

lets just say I really want to keep my basics strong and also be able to solve creative and in depth analytical problems

[robust monolith]

What

[hidden totem]

you can also try asking #book-recommendations

might be helpful to provide a bit more about your background, that way users can find the resource that best fits you

[willow oriole]

Please don't post AI slop here, it clogs the channel @cerulean wind

[cerulean wind]

who said it was AI???

[cerulean wind]

i’m glad at least you got a laugh out of that lmao

the AI is not learning me, I’m learning the AI

[torpid scaffold]

In this book, Discrete Mathematical Structures with Applications to Computer Science, Tremblay and Manohar defines, Elementary Products in the following way :

A product of the variables and their negations ina formula is called elementary product (1-3.1, 1997 Tata McGraw-Hill)

Similarly, they define, elementary sum.

But when I looked at other sources in the Internet, I found, the following definition for the same:

finite conjunction of distinct literals with no variables repeated.

Now I'm confused, which is is true and when I asked chatgpt, it said both are true. Can someone please clarify and explain me what is going on.

[coral parcel]

(Answered in #proofs-and-logic -- please don't crosspost the same question to several channels; that just leads to a potential for wasted work if someone spends time typing out a reply with points that have already been made elsewhere).

[eager mesa]

Could someone help me with this question? Apparently the answers are F,T,T,T, but I have no idea why

I get that b is a vacuous truth

I keep trying to explain my logic and getting confused 😭

Okay, so the first conditional statement is false since q is false. The second is true since q is true. I don't get how the third one is true if both the hypothesis and conclusion are false

I also don't get how the truth value of the fourth conditional statement is true. q is false, so shouldn't it follow the same logic as the first conditional statement and be false?

[quick folio]

this is the unintuitive thing about logical conditionals

as long as the predicate is false, then the conditional is true regardless of whatever follows

so I can put any sentence into "If monkeys can fly, then ________" and it would be logically valid

[winged delta]

A conditional is a promise - it can only be false if the condition is true but you break the promise

If I say “If I win the lottery, I’ll give you ten dollars”, and then I don’t win, I don’t have to give you ten dollars

But if I do win, then the statement is false if I don’t give you the money

[eager mesa]

Huh

[eager mesa]

That does make a little more sense

[winged delta]

Oh good, hopefully my discrete students feel the same way this semester

[quick folio]

the big reason why this is unintuitive, is that in normal language when we say an "if then" statement the two events are causally linked and all the relevant information is present (ie there is no other thing not mentioned that can potentially cause the same result)

so what do I mean, consider "If i do not study hard, then I will fail the exam"

if I say this in a conversation, then the implict thing that I am also telling you as well is that if i do study hard, then I will not fail the exam

but logically that is not entirely true - it is hypothetically possible that I studied really hard for the exam, but during the exam the teacher found out that I snuck in a cheat sheet

in that case I am still definitely failing the exam

so really, in terms of pure logic, when I say "If i do not study hard, then I will fail the exam", I am telling you absolutely nothing about how well I will do on the exam in the situation where I do study hard

even if in real life that is not how humans talk

[eager mesa]

But I thought that the logic for the fourth conditional in the problem didn't matter. Since the predicate is false, the conditional is false, regardless of the logic?

[quick folio]

it's the other way around, if the predicate is false then the conditional is true regardless of the logic

[eager mesa]

You're helping some random student online at 9pm with discrete even though you already teach the subject?? King 👑

[winged delta]

I start next week, and my time zone is much earlier than 9pm

[eager mesa]

Oh. Why did you bring up the example about studying and failing an exam though?

[winged delta]

But I appreciate it 💜

[quick folio]

if you didnt understand it then nevermind, lol

I'll avoid complicating things further

[eager mesa]

Nooo you were writing something lol

Okay haha

That's probably for the better

Thank you both for helping me 🙏

[burnt meadow]

btw I wanted to ask as the AI provides different books than the books put in the mathematics book suggestions
Is following the book suggestions better than reading the books suggested by AI?
And if so then why?

Also how does the book suggestion work?
Like how do they know that this book is better than the other books?
Since AI can literally scan a whole book faster than a human can read a book

Im just being logical

or factual

no offense

[hidden totem]

the general rule is never to trust any output from an LLM. you should always verify their information firsthand, and if you can't, probably don't trust it or ask it in the first place

LLMs are computational, so no matter how much computation they do, they never interface with "reality", they can't tell you how true something is because not only can they not perform experiments to validate their claims, they don't even really understand what truth is

so when an AI suggests you a book, it could just be a generic book for the topic or the wrong book or a bad book or it could even be a made up book that doesn't exist, and it has no way to validate how good that book really is

if you actually come into this discord and ask humans for book suggestions, they will likely ask for your background, how much math you know, what you're looking for, your preferences, in order to find the right fit for you

and they might even give you caveats, telling you what to watch out for or what mindset to have while approaching any of the content

[burnt meadow]

.

wont this work as a background

Im trying to get into ICPC

and I think dm is pretty necessary

also for my undergrad studies too

also my first time for any type of competition actually or contest

and I really want my dm basics to not be only strong but also as much best as it can get

while also yea creativity and in depth understanding

Im in a dire need tbh

and dw bout time

I can manage somehow

also lets just say Im a total beginner or newbie

would really appreciate any help possible

Please feel free to ping me

if u do indeed reply

also personally even if ICPC might not require me to understand why number theory is used or how a graph works

I still would love to know bout them

[haughty garden]

if you want to get into ICPC, take an algorithms and data structures course

[burnt meadow]

But as far as I have seen

DM is like the foundation of dsa

Like maps graphs algos

I also want to make my own algos

When needed

[haughty garden]

what is DM?

[burnt meadow]

Discrete maths

[haughty garden]

oh right

yes you should learn discrete math too

[burnt meadow]

I would love some book suggestions

[burnt meadow]

Also why

Won't books work better

Than some courses?

Tbh I really cant buy courses bcz of some issues

So if there is any other better and alternative way

I would honestly appreciate such

[haughty garden]

Discrete Mathematics and its Applications by Rosen is good

[burnt meadow]

Rosen def popular

[haughty garden]

The one by Epp is also quite good

[burnt meadow]

But is it better to read

[burnt meadow]

I did start with that

But then again it was recommended by AI

So yea

I actually used gpt grok and gemini

To find best books

They recommended both epp(starters) and rosen(mediocres)

[haughty garden]

interesting

there are plenty of better sources with recommendations

[burnt meadow]

Like?

[haughty garden]

you can just search up “discrete math textbook recommendations” and there will be a collection of book recs written by people on sites like StackExchange

[burnt meadow]

As long as it doesnt have a war

And recommends some mitcoursewave videos

Like reddit did

For the first time I made a reddit id

Just to get some recommendations

[haughty garden]

what’s wrong with MITOCW

[burnt meadow]

Mitocw?

Im new to reddit too..

[haughty garden]

anyways https://math.stackexchange.com/questions/1533/what-is-the-best-book-for-studying-discrete-mathematics

[burnt meadow]

I also wanted to know how good is libretext

[haughty garden]

I don’t personally use it

[burnt meadow]

Ah damn

After finishing dm

I wanna start a whole calc journey

From beginning

Asap

[haughty garden]

It depends on how you learn. If you learn better from a textbook, then consult a textbook; if you learn better through a professor, then use courses. You can also do a mix too

[burnt meadow]

I prefer textbook for some reason

How do I say

Once

During my exam

Like there was this one sir who always would make questions bout snth which we did not even have in the book

The official book*

So sir gave us a question of friction

Now I only heard it like in vid or stuffs

So after reading the whole question

I just somehow answered that question

Ofc using logic

I derived a whole equation

Then sir said that my answer was correct

So yea if that helps

I like to derive equations

I did it a lot

Ngl I never really paid attention to classes

I always did whatever the hardest math books recommended

So yea

[burnt meadow]

I know i know u might ask how I know the book is hardest but lets just say there is a traditional thingy

So yea

[burnt meadow]

eitherways do let me know if u guys would prefer me a math book

it can also be R&D related

I wouldnt worry much

[bitter vortex]

where can i prepare for midterm

[simple solstice]

Honestly, if you want textbooks that are adopted into any courses. I would presonally recommend Book of Proof by Richard Hammack because its free, and so you do not have to go surfing around the internet for PDFs. It's also really well written and helps the reader develop a good understanding of proofs (important highlight of discrete math)

Honestly, for hard books. You should try to balance them with foundational books.

For example, I'm studying number theory through a very rigorous text that's ultimately meant for cryptographers cause that's what I'm thinking about doing. Unfortunately, that book doesn't go over important stuff like Diophantine equations and other foundational topics, so I occasionally use a foundational number theory text to fill that gap.

[burnt meadow]

ohh

that is a good perspective

[pearl gazelle]

when is it not okay to assume the law of excluded middle?

[grand totem]

When you're doing constructive mathematics

[pearl gazelle]

hmmmm
icic

[fossil mural]

yeah it's basically just... if you assume the law of excluded middle, then you will only have proven your results assuming LEM

so if you want to know if something is provable without LEM, you should not assume LEM while trying to prove it

[pulsar arch]

can anyone explain to me the steps to solving a congruence with an x variable? as in smthg like 16x ≡ 2 (mod23)?

[lusty fog]

ax ≡ b (mod m)

1. gcd(a, m). If gcd ≠ 1 nø solution or many solutions.
2. Inverse of a mod m
3. Multiply both sides by inverse
4. Simplify to mod m

[pulsar arch]

thanks

[lusty fog]

Sorry for bad handwriting im in bed but yeah

[pulsar arch]

this 100% made it clearer than what i had seen previously, though i saw also saw a faster way but im wondering if it works for all cases, which is we get 8x = 1 mod23, so in words we need to find the x that multiplied by 8 gives after dividing by 23, 1, so multiply by 1,2,...,k till we get a number that x = 1x23+1 in which case is when 8x3 so x = 3 mod 23

idk if it has flaws or not

[lusty fog]

The trial and error method is not efficient for large numbers

[spark field]

The process is ultimately the same for that (you can use extended euclidean alg to find that the inverse of 8 is 3 [just like how kragen found inverse of 16 is 13]) and then like you said, multiply

-# Important to note as well that the division by 2 is only possible because (2,23) = 1

[pulsar arch]

what would you consider large in this scenario

i got my exam tmrw but from what ive seen from past ones i dont think they'll go that big tbh

[lusty fog]

I mean for cartography the number get min 6 digits

In this case small would probably be 1-1k

[pulsar arch]

thanks

[pulsar arch]

then i should be good by trial and error, thanks for the explanation man

[lusty fog]

Yes it is sufficient for introductory discrete math

Ultimately it’s your preference

[eager mesa]

Why is the answer for b) ?

If it's the negation of a contradiction, shouldn't it be \neg C(x)? Why is the negation of the x inside the tautology predicate?

[spark field]

Looks like they just wrote it in an interesting way:

Let $x$ be a proposition. If $x$ is a contradiction, then $\neg x$ is a tautology. \

We can state this as
\begin{center}
For all propositions x, if x is a contradiction, then (not x) is a tautology
\end{center}
which, in symbols, is what's written as your answer for b

[vital dew]

Coolempire93

[spark field]

Using the predicates
C(x): x is a contradiction
T(x): x is a tautology

So we have x is a contradiction -> negation of x is a tautology

Which is the same as saying that the negation of a contradiction is a tautology (i.e., when you negate a contradiction, you get a tautology, which is another way to state the above implication)

[eager mesa]

That makes so much more sense! Thank you!

[spark field]

No problem!

[flat grotto]

Here

I am going to use E and A to denote the respective quantifiers, since it would be easier on my end

You can do:
¬Ex:X(P) => Ax:X(¬P) => Ex:X(¬P) => ¬Ax:X(P)

You cannot do this backwards, but the middle step in my set of "rules" works

Ax:X(¬P) I can do: ¬P[x<-x] which then Ex:X(¬P)

[light spear]

any textbook reccs for discrete math? i already took a intro to math structures class that was kinda like a intro to discrete i think

[prisma lily]

rosen

[robust monolith]

Hello, in the expression ${x + 1 : x \in \mathbb{Z}} = {x + 2 : x \in \mathbb{Z}}$, the scope of $x$ covers both sides of the expression or the $x$s on both sides are independent?

[vital dew]

Mor Bras

[past rivet]

should be thought of as independent

[robust monolith]

So the expression can be rewritten as ${x + 1 : x \in \mathbb{Z}} = {y + 2 : y \in \mathbb{Z}}$?

[vital dew]

Mor Bras

[cerulean wind]

are you familiar with local scoping in programming?

[robust monolith]

Yes

[cerulean wind]

it’s like that

you can have two functions that both refer to a variable x

but x is locally scoped

so that each instance is independent

and doesn’t interfere with one another

[robust monolith]

So in this case x is contained locally in both sets, independent of each other

[cerulean wind]

yea, it’s not specified outside of those sets in this context

it would be different if we were to say fix some constant integer x. now consider the sets {x + 1 : y in Z} and {y + 2 : y in Z}.

the first set is just {x + 1}, since x + 1 is independent of y, and x is a fixed constant. the second set is all of Z

[robust monolith]

Certainly

[hexed gust]

Given a 2^n by 2^n checkerboard with one square removed, is there only one way to cover it in l shaped trominoes?

[spark field]

I think there's multiple because you can take a 3x2 block filled by two triominoes and flip them both to fill the same block again

These two tilings of an 8x8 are the same except for the orange block that I've flipped both triominoes

[robust monolith]

Hello, can tuples always be represented as nested ordered pairs?

[vestal bronze]

i don't understand the question, show an example

[spark field]

I believe so

$\RR^2 \cong \RR \cross \RR$, and $\RR^3 \cong \RR^2 \cross \RR \cong \RR \cross \RR^2 \cong \RR \cross \RR \cross \RR$ and so on

[vital dew]

Coolempire93

[robust monolith]

For example, $(1,2,3) = (1,(2,3)) = ((1,2),3)$.

[vital dew]

Mor Bras

[vestal bronze]

sure

[hexed gust]

Oh true

Could you have them in different places though?

[spark field]

Yeah, just take the 6x6 box in the bottom right and rotate the whole thing 90°

Now the tetrominoes are actually in different places

Another way to do it is to tile four 4x4 with corner removed boxes

Which would give you a canonically different one

I believe this method will always yield a solution as you increase n no matter where the square is removed with some argumentation but I’d have to think it out

[hexed gust]

yeah we used that to prove you can always cover a 2^n board

[cloud solar]

Hi, I have a very specific or a very general question about complete weighted graphs.
Are there any theorems or lemma about SHP's (shortest hamiltonian path's) first and last vertices?

I would appreciate some direction as to where to look for it as well.

[eager mesa]

Is this question asking for one domain for both x and y?

a) is true for positive real numbers and false for natural numbers.
b) is true for real numbers and false for integers.

I'm especially lost on c

[stuck trout]

How is f(n) = omega(g(n))? g(n) is not a lower bound

[eager mesa]

Hey, it looks like you're ahead of me in discrete. Could you help me out 😭

[stuck trout]

is

a) Z ?
b) R ?
b) R ?

In other words

a) Integers
b & c) Reals

idk i tried

[eager mesa]

But a) would be false for integers. If you set x=2, then there isn't any integer value of y that y^2=2

[stuck trout]

Yea tru, but I think that will be r then

because if you set \sqrt(2) then it will work

[eager mesa]

but then what about -sqrt(2)?

[stuck trout]

same thing

[eager mesa]

*what if you set x = -2

[stuck trout]

oh

[eager mesa]

no value of y^2 would give a negative number

yee

[stuck trout]

you then go to C

[eager mesa]

C?

[stuck trout]

complex numbers

wait let me double check

[eager mesa]

The thing is that we haven't covered complex numbers yet so I'm pretty sure we aren't supposed to use them for the answer 😭

[stuck trout]

yea C should work

[stuck trout]

then id say for all int greater than 2

the question is vague tbh, I tried

what domains we are able to use

[rocky torrent]

hi

im having hard time with graphs

is there a 9 point pair graph?

and why

cuz i dont understand

[spark field]

Although I can't prove it with the formal definition that I know for asymptotic notation (using a positive constant multiple), this makes sense to me intuitively because g(n) has same or lower order of growth compared to f(n)

g(n) having constant order of growth every function should be = Omega(1)

[spark field]

This is provable with squeeze theorem and the limit definition though

[spark field]

Likely so

[spark field]

a is good
b is good
c you could be creative on

Think about smaller sets

(note: Complex is also a fine answer for a, but yours is fine; I could say the same about rationals for b)

[eager mesa]

So like {1,2,3}?

[spark field]

Yes! I was thinking {-1,0,1} but any 3 real numbers work tbh

[eager mesa]

I know from the textbook that a finite set works, but wouldn't real numbers work as well?

[spark field]

Not all real numbers

As in not the set R

Think about what the statement says

There exists an x such that for all y and z, if y < z, then x is between y and z (inclusive)

In other words

I must select x and I can take any y and z and x will be between them
Select 0, then [-2,-1] is a counterexample, and so on

More generally if I select x, I can choose y and z << x and x will not be on the interval

[eager mesa]

ooh I forgot about the all y and z

[spark field]

The reason a set of 3 elements works is because I can't do this

If I choose y and z, one of them will be x, or I chose the two elements with x in between

[stuck trout]

U cant prove it cuz its indeterminant

[spark field]

That's what the squeeze theorem is for

Since |sin(x)| is bounded

[eager mesa]

That makes sense. Thank you cool empire!!

[stuck trout]

Yea but has a upper bound of 1

[spark field]

Correct

[stuck trout]

G is 2

[spark field]

No problem!

[stuck trout]

And its omega(2)

[spark field]

Remember order of growth uses a constant multiple

[stuck trout]

Oh i see

I might need to go over

[spark field]

But for the limit so you can see

$\lim_{n \rightarrow \infty}\frac{0}{2} \leq \lim_{n \rightarrow \infty}\frac{|sin(x)|}{2} \leq \lim_{n \rightarrow \infty}\frac{1}{2}$

[vital dew]

Coolempire93

[spark field]

The left hand limit goes to 0, in which case 2 has a smaller order of growth, the right hand limit goes to a constant, in which case 2 has same order of growth

By definition, f(n) = Omega(g(n)) if g(n) has same or less order of growth

[high skiff]

ngl everyone, discrete math for me has been the most important math course i ever took, better than calc1, calc2, stat, linear algebra

linear algebra made since in big part because i took discrete math

these engineers/physicists don't have a clue how awesome it is to prove a result

right now, am studying calc3, been a while since i took a "continuous" course, it is indeed a bit fun, and discrete math has given me a way to formalize my thoughts while studying it, still it is no discrete math, the combinatorics sections in Rosen's book is freaking legendary, only automata theory has exceeded the beauty that my discrete math exuded

[spark field]

@wicked bolt look someone likes combinatorics

[wicked bolt]

combinatorics is good

[high skiff]

am not kidding man, i once spent half my summer holiday studying the heck out of the combinatorics section of Rosen's discrete math

counting problems have been ingrained

[wicked bolt]

amen

[high skiff]

i learned to solve these counting problems using recurrence relations (which are also the goat)

this helped in algorithm design tooooo

[wicked bolt]

[spark field]

This guy can probably count the number of ways to tile of a 2^n by 2^n checkerboard with the corner removed with L-shaped triominoes

[spark field]

True

[high skiff]

nice to find a person who likes counting

[high skiff]

what you mean man, this problem seems fun

[wicked bolt]

there’s nothing easier to count than that

you don’t have to do anything

[spark field]

Scroll up in the channel someone asked a (slighly more complicated version) but I was interested in the full count with the corner because I was able to find more than one when n > 2

I never got time to sit down and think about it though

[wicked bolt]

seems tough to count

even just when n = 5

[high skiff]

am gonna try to find a recursion for this count

seems interesting, hopefully i still got my combinatorics muscle memory

[high skiff]

you already gave it to me, this is beautiful man

[spark field]

The problem is that's only one way

There are others

That does give us a lower bound of 1 for our count though 🥹

[high skiff]

let me calculate some things, i have no problems staying late for a lovely combinatorics problem

[wicked bolt]

did this get edited to triominoes from dominoes or

[high skiff]

again i say, the engineers are missing out on the good stuff

[wicked bolt]

amen

[spark field]

Should have been triominoes from the start

[high skiff]

let there be a checkerboard of size 2^n 2^n with the either on of the 4 corners removed (due to rotational symmetry, they are all equivalent, right)

let f(n) be the number of ways to fill the grid of size 2^n 2^n with those L shapes (name weird okey).

due to the construction replied to above, we can construct a grid of size 2^n 2^n out of subgrids of size 2^(n - 1) 2^(n - 1)

since the count of ways to fill each subgrid is f(n), and we constructed the full grid out of 4 such identical subgrids, the final count should...

f(n) = f(n-1) * f(n - 1) * f(n - 1) * f(n - 1) (using the multiplication rule for counting)

f(n) = f(n - 1) ^4

you would think this recursion works wonders, but nooooooo

let the base case be n = 1, which gives us the 2 by 2 grid, there is only one way to fill it up

and because of that, this freaking means that there is only 1 way to fill any grid of size 2^n * 2^n, which is clearly false

damn, recurrences failed me

[high skiff]

this is the counter example

where is Terence Tao when you need him????

anyways, the previous count didn't account for ways to fill L shapes between the subgrids, which is probably why it failed

you truly can't expect a CS undergrad to do proper maths

anyone here got better ideas of how to tackle this problem?

[spark field]

You're telling me 😆

[cs-math double major, started in cs]

[spark field]

My first plan was basically to run through all the symmetries for a lower bound

Since each block of 2x3 can be flipped

And each 6x6 can be rotated

[maiden roost]

Hello, I am looking for a MOOC course on discrete math (BA - entry course) with 5 ECTS credits. It would be great if it started at the beginning of the year and was entirely online. Thank you very much!

[wicked bolt]

for small n you could count with dynamic programming

[spark field]

That's probably what I would do for the computational side if this were research and I was looking for a sequence in OEIS

[wicked bolt]

it seems like such a pain to write that though honestly

[spark field]

I mean not particularly depending on your definition of dynamic

If it has to be the exact same problem yeah

But if it's just tiling a surface (no need to be rectangular) it's straightforward

[wicked bolt]

the problem is number of ways to tile a 2^n x 2^n chessboard with a punctured corner with triominoes?

[spark field]

with L-shaped triominoes

[wicked bolt]

oh yea forgot straight triominoes existed

[spark field]

yeah it's hard to remember that non-gays are here

[wicked bolt]

i’m right here you silly goose

[spark field]

Yeah

[wicked bolt]

there are a bunch of ways to fill in each partially completed row and it just sounds annoying to enumerate everything

[spark field]

I'm gonna put it together once I finish this chapter of the networking book

[wicked bolt]

ok

i will disappear to my uncle’s house for many hours

[stuck trout]

I am very confused on this question

its 5a btw

[spark field]

What are you confused about

[stuck trout]

just the question itself, like I think its false because the running time means average time right> So like it doesnt matter want the input is it would run (a) claims that Y will run at O(n^2logn), but that Y actually is tightly bounded by Theta(nlogn). nlogn is less than n^2logn thus that cant be tru.

But I think I am wrong/unsure

[spark field]

Running time doesn't mean average time, running time means [using the language using in the image] the number of steps that the algorithm runs for given an input of size n

Your interpretation of the second bullet point is almost correct

What it says is that the worst case running time is tightly bounded by Theta(nlogn)

We can treat this as meaning that the actual run time is in O(nlogn)

[stuck trout]

OKay I understand, but like what is the diff when someone "running time" rather than "avg or worse or best case running time"

[spark field]

Your reasnong is correct though

n^2logn has a higher order of growth than the maximum possible time (worst case), therefore it is impossible

[stuck trout]

okay, how would I prove it? I would use the limit definition in order to show that O(nlogn) ~= O(n^2logn) ?

[spark field]

The difference is:

Running time: how many steps the algorithm runs given an input of size n
Call running time T(n), then:

Worst case running time: the maximum number of steps an algorithm can run given an input of size n. T(n) = O(worst case run time)

Best case running time: the minimum number of steps an algorithm can run given an input of size n. T(n) = Omega(best case run time)

Average case running time: the number of steps the algorithm takes on average given an input of size n

[haughty garden]

Average-case is a bit more nuanced than that but it is morally correct

[spark field]

Yes you can do that

Well really that n^2logn = Omega(nlogn) but same difference

[haughty garden]

I think the better way to informally state average-case is that it’s the running time taken by the algorithm when you “average over all of the possible inputs”

rather than “given an input”

[spark field]

Ah that's interesting

Wow you're right that's actually exactly what we did typically

I always wondered why it would be accurate to do that

Turns out my definition was wrong 😂

[haughty garden]

The formal description is that it’s the expected time of the algorithm given an input that is sampled over a distribution

[spark field]

Oh hello fello combinatorics role haver 👋

paired with TCS supercool

[spark field]

Yeah that's even more accurate to what we did

[haughty garden]

yuhhh I do theoretical cs stuff :]

[spark field]

It's crazy how I completely had the wrong definition but followed blindly the process

[haughty garden]

easy mistake tbh cos you don’t often use average-case complexity

and when people say average-case, they often mean expected time complexity or amortised time

[spark field]

I wanted to get into it (did CS/math double major) but never really got the chance and now I'm basically squarely in combi

[haughty garden]

well luckily for you, combinatorics is used a lot in theoretical cs

circuit complexity borrows concepts from extremal combinatorics for example

I think the sunflower lemma is used when doing some construction for monotone circuit lower bounds

randomised algorithms uses tools in algebraic combinatorics (see: combinatorial nullstellensatz)

[spark field]

Interesting

[spark field]

This is interesting

[haughty garden]

there’s some other stuff too that I probably forget but you can check out Jukna’s book for a suite of examples

It’s also written with the theoretical cs student in mind so lots of examples are motivated on that end while still keeping the material purely combinatorial

so not too hard to get into theoretical cs if you’ve come from a combinatorics background methinks

[stuck trout]

wait I would take the limit of nlogn/n^2logn right? I m confused wether to put that or do I write Big O

[spark field]

That limit will work

WOah you're right I didn't notice it was big O in (a)

That changes my interpretation

Yes so your original plan was correct

Continue as you had been intending to go 👍 with the big O

We will end up with ||worst case = O(n^2logn)||
Since ||runtime = O(nlogn) = O(n^2logn)|| we can say the runtime of algorithm Y is ||O(n^2logn)||

[fickle stone]

i do cs too

but i had pre medical background

so yea it sucks

[stuck trout]

oh okay. lowkey idk what my original intention was for the project but I would show that lim O(nlogn)/O(n^2logn) ~= O(n^2logn) ?

[spark field]

This is a second-order (non-homogeneous) linear recurrence so it can be solved with quadratic formula if that helps

[spark field]

👍

[spark field]

Ah your teachers are evil

[high skiff]

average case complexity is freaking evil man

the average case complexity of quicksort gives me nightmares

@spark field any progress in the L shape thingy puzzle?

[spark field]

I finished all the preliminary code last night, now I actually have to implement the "try all possibilities randomly" algorithm

[high skiff]

does an algo count man?

formula would have been much nicer

i spent today somehow constructing geometric objects using euclidea

geometry is freaking hard

this is one of the weirdest side quests i ever went through

[spark field]

The algorithm is to give me a sequence that I can put into oeis, see if it exists, and then ideally prove a bijection between whatever object the existing sequence counts

[spark field]

Love euclidea and pythagorea

[high skiff]

insane behavior ngl

i learned about that sequence encyclopedia thingy like last week

[spark field]

This is the standard procedure [after trying mathematically] for research in enumerative

[high skiff]

euclidea made me wanna pick a geometry textbook, this stuff is fun ngl

also, ngl my angle chasing skills suck at the moment

as much as i hate geometry, it comes up sadly often, especially in physics, so fixing that weak point my prove helpful

but am scared of picking up the elements, that book is old man, i can barely understand a textbook written 30 years ago

[spark field]

I don't think anyone would suggest you read from a book written before mathematics was formalized

Our euclidean geometry textbook begins with a chapter about formalization and throughout the book we critique why euclid's proofs had holes, and how to fix them

[high skiff]

i might be able to do that, am half decent in backtracking/recursive problems, my favorite leetcode type problem for sure

[spark field]

I recommend the geometry book we used which is like a handbook it's called Roads to Geometry

[high skiff]

niceeeeeee

about mathmatics in general, even though am a cs major, i might attend graph theory classes taught in the math department

[spark field]

@wicked bolt 🙌 look he even likes graph theory too

As you should

Graph theory is where I'll likely end up in

[wicked bolt]

nice

[spark field]

Although I really do love enumerative

[spark field]

Actually yesterday I basically streamed all the coding I did

[hybrid quiver]

graph theory sounded so cool to learn until i learnt a bit of it

[spark field]

real

[high skiff]

it is still cool though, specially the algorithm side of thinks

[wicked bolt]

graph theory is a high aura field

[spark field]

Be ramsey

[high skiff]

when Dijkestra clicked, i experienced nirvana

[hybrid quiver]

i didn't learn much so i am biased, but i expected algorithms and didn't see any of it really

instead it was the most boring shi

[high skiff]

my textbook had a nice induction with contradiction in the inductive case proof of the algo

[hybrid quiver]

prove that if every non adjacent set of vertices has degree sum >= n in an undirected loop fre bla bla it was so boring man

[high skiff]

in the fun factor, maybe stuff like calc and physics might be more fun

but discrete math is the bomb too

[hybrid quiver]

we got @cursive aurora now we got @high skiff

[hybrid quiver]

true

especially combinatorics

[high skiff]

combinatorics is a gem man

[spark field]

The combinatorics club keeps growing

[hybrid quiver]

is peak math

[high skiff]

the formal techniques in combinatorics are especially fun

for example, you can prove some combination identities using generating functions

generating functions in general are like magic

[stuck trout]

what u need diff eq for combinatorics?

[stuck trout]

Hol up wont the limit just go to 0, thus O(nlogn) = O(n^2logn)?

[spark field]

That is the point yes

[spark field]

No they just use all the same names (just with discrete difference instead of differentials)

The techniques are similar but different

Neither is required for the other though

[stuck trout]

wait okay so if I do say it is tru, does that make the statement a true statement?

I said it was false

[spark field]

Yes ultimately it's true because they used big O

[stuck trout]

oh I see

[spark field]

Which is why I said this

And that I hadn't noticed it the first time I read

[stuck trout]

okay okay I see

[high skiff]

@spark field

i was going to sleep, than i thought about the algo you talked about

if i remember correctly, you said you fill the grid randomely

won't that be too slow for say, n = 10

a more systematic method might be appropriate, doesn't even need to be polymoial, just enough pruning to make the runtime bearable

anyways, back to sleep, gonna try to contructibly trisect an arbitrarily angle in my dreams, wish me luck mates.

[spark field]

Oh it's too slow for even n = 3

I was planning on switching it to something more systematic, but that gave me an idea on how to investigate it by hand

So I switched to a little actual math investigation

Such is the interplay between writing combinatorial code and doing combinatorics

[high skiff]

yeah, am pretty sure i became a better comp programmer (i still suck) after studying combanitorics.

[hidden totem]

combinatorics also leads you to some info hazards

you'll quickly realize that the entire world has been counting wrong, because they count from 1 not 0

programmers got it right because they had to, but then when they stop programming they immediately go back to the wrong way again

[jovial sail]

woke people count from 0 to n - 1 or n

[stuck trout]

Is my answer correct?

My thought process behind this is that it is try because Z has a Theta(logn) for all inputs while Y has a worst case O(nlogn). If I show that Z is not the upper bound of Y, that shows that Z is faster than Y

[spark field]

Mm not necessarily

Z is faster than the worst case of Y

The best case of Y could be better than Z

Meaning that there could exist an input for which Y runs faster than Z

Although I will say the problem here really isn't you it's the abysmal choice of notation here

[stuck trout]

well but doesnt Theta mean the algo is tightly bounded to nlogn for Y and for Z its logn? So suppose you take the best case for Y is n, wont Z run faster because its logn??

[spark field]

That's why I say the notation is abysmal

The worst case is bounded Theta(nlogn)

The best case could be Theta(1) for all we know

[stuck trout]

Yea ig, my TA said that for the class Theta and O are treated the same. But intuitively I dont get their POV

[stuck trout]

oh hmm can you explain how you can claim to be a constant time? Because for some n value that is int, u cant really get nlogn = 1

[spark field]

The worst case is Theta(nlogn)

Consider the bubblesort algorithm (a sorting algorithm)

Its worst case is Theta(n²)

Its best case is Theta(n)

[stuck trout]

okay I think I get it now

[spark field]

If I ask it to sort a backwards sorted array, it will always take n² (no matter the n)

And if it's already sorted, thats the best case it will take n (no matter the n)

[stuck trout]

so depending in the input n the function will asymptotically converge to some complexity. So if n was the best case for some algo then that means that algo would have like O(logn) but for the worse case input n the algo could have O(n^2)

is my understanding correct?

[stuck trout]

okay, so when they say "worst-case" it means that if the give n is the worst input it will have a time complexity of n^2. If it said the "running time" is O(n) that means for some random n you would get O(n) ?

[spark field]

Depending on the input size n, yes
If n is the best case we have
Theta(n) for the best case
Omega(n) for all inputs
Who knows about the worst case

So yes it could be n² then

Same situation for Algorithm Y
It has worst case Theta(nlogn)
So it has O(nlogn) for all inputs
And we don't know what the best case is

[stuck trout]

ah okay I see

[spark field]

When they say worst case it means when you give it the input that makes running time the longest

[stuck trout]

when they say just "running time" is it the avg case?

[spark field]

[Depending on how predictable the algorithm is, that can vary - for stable algorithms though, you'll always be able to say worst case running time is Theta something]

[spark field]

It would mean for all inputs

Doesn't necessarily mean average case but the average case will be equal to whatever the for all inputs is

[stuck trout]

okay so do those algo have "worse case" inputs then?

[spark field]

We can't know

[stuck trout]

ah i c

[spark field]

We assume they exist though, given that we have a worst case running time

[stuck trout]

okay, but for all we know for some given input (even though it could be the worse input), the "running time" metric just says it will bounded by some asym func

[spark field]

Yes 👍

[stuck trout]

ah okay thx!!

[spark field]

No problem!

[stuck trout]

Is my proof to show that this program halts correct? I am not sure if my implications and logical are correct.

[spark field]

Yes

You really don't even need that much since they give you the properties

But yes you are correct

[stuck trout]

Yea I didnt realize after i finished the proof

[stuck trout]

Alr so this I am unsure if my answer is correct. Im pretty sure this question is about bubble sort. Now at each swap, I don't think S_i will decrease by one. Here is my example

A = [5,2,10,-5,4]
A_s = [-5,2,4,5,10]

First pass

A' = [2,5,10,-5,4]
S_i is still n. Although A' does swap the elements indicies don't match the sorted array indices

When I wrote this, I assumed I wont get an array like that

[spark field]

You should ahve S_i decreasing, maybe you chose the wrong S_i

Let me read

Ah no you chose the correct S_i

It's almost bubble sort but they don't tell you what j and k are

[spark field]

You are correct we have S_{i+1} <= S_i

It can stay the same, decrease by 1 or decrease by 2

The question is more, can it stay the same forever (it may not halt), or at some point will you have to put something in order?

The answer being simple:

Continue performing the swaps

Higher elements only go up, lower elements only go down (because you can't swap out of order)

If you perform them so that no element ends up in its final position, you'll reach the point where you can't perform any moves without placing something in its final position

For example
begin with 3 4 2 1
I can't swap 1 and 3
I can't swap 2 and 3
I can't swap 4 and 1
I can't swap 4 and 2

Every option puts an element in its final position

Even if I begin with 4 3 2 1
I might go 3 4 2 1
but I can't perform any more swaps
If I instead go
4 1 2 3
2 1 4 3
Now I can't perform any swaps

In general we have:
Notice that every element has to stay between its initial position (where it started in the array) and its final position (the sorted position), since we can only sort the elements towards their positions
Let S_i be sum of distances between elements' final and initial positions.
This must decrease with every swap
Therefore we converge to B

[hybrid quiver]

<@&268886789983436800> you should pin this so everyone gets money

[stuck trout]

what was the message 👀

[stuck trout]

wait how is this almost bubble sort? In bubble sort I don't think they tell you what j and k are

[spark field]

Bubble sort is a stable algorithm, so everything is predetermined

So yes, you know what j and k are

Specifically, you move repeatedly from left to right

[stuck trout]

tru, but cant you swap 3 and 1, 4 and 2, 4 and 3?

[spark field]

So j = 1, k = 2, then j = 2, k = 3, ... j = n-1, k = n
And then you do it again

[spark field]

Which situation are you referring to

[stuck trout]

Situtation where you are able to get 1234

from the array you gave

[spark field]

I can get 1234 from any of them

[stuck trout]

but you claim "Every option puts an element in its final position" for 3421

[spark field]

Ah yes

Every possible option does

Remembering you can't swap elements like 4 and 3 from there, because 3 < 4 (they are already in order)

By the rules of the algorithm, you can only swap elements that are out of order

That's why the reasoning works that they must keep getting closer to their final positions

[stuck trout]

okay but cant you have k to be j+2 so then you would swap 3 and 2?

[spark field]

I can't swap 3 and 2, that puts 3 in its final position

So S_i goes from 4 to 3

[stuck trout]

it doesnt strictly say that k is at most a value of 1 greater than j

[stuck trout]

wait isnt that the point? To put it in its final position or am I missing something?

[spark field]

.

We want to show that S_i must decrease eventually

So we attempt to make only moves so that S_i doesn't decrease, and realize that it is impossible to keep doing so

[stuck trout]

ah wait I think I missed this part of the question "A[1, ..., n] are increasing order" and we can only pick 2 elements that are out of order to swap

[spark field]

We hit a roadblock that there end up with no moves such that S_i doesn't decrease

Therefore S_i must decrease eventually

And now we can say that the algorithm halts

[stuck trout]

oh I see

so at some point you will decrease in S_i because atleast one will be out of order

[spark field]

Otherwise we just have S_{i+1} <= S_i which may not halt if S_{i+1} can = S_i at every iteration

Exactly yes

[stuck trout]

does that mean atmost there can only have n out of order elements for a given array?

[spark field]

If the array is length n then we can have at most n out of order elements, which is when the array is in decreasing order

All elements are out of order

[stuck trout]

okay that makes sense

thx!

[spark field]

Np!

[hybrid quiver]

scam msg

[stuck trout]

Is my answer correct? Technically if the process ran inf it will converge to 376 but im not sure if my answer is wrong

[spark field]

Ah forgot to come back and look

[spark field]

Looks good based on the property you were given

This is basically a description of zeno's paradox, where if you travel half and then half and then half you only reach there infinitely, never finitely

So the only "fixed amount" that you decrease by every single time is O(0) that is, there is none

So yes your conclusion is correct 👍

The important thing in the proof is that property 2 doesn't say it is exactly a fixed positive alount

Just that it's at least a fixed positive amount

What you we would need to show is that the difference S_{i+1} - S_i tends to 0, i.e. there is no positive lower bound

In the change

[terse quartz]

For this problem - I kinda messed it up when I handed it in bc sleep deprived (here’s my soln - see last line ) but idk if I’m tripping now, can my argument be fixed by just disconnecting all of the vertices in D to get N(D) = 0 and then we have a matching on S’ so we’d still have a matching on S’ in the OG graph because S’ and D are disjoint

[terse quartz]

Nvm this is indeed incorrect

[spark field]

Oh I forgot to come back and look at this

I saw it and then forgot

[terse quartz]

Nws

It's because If you delete D then |N(S' U D)| is no longer necessarily geq |S' U D| - d

And I need to sleep!

TA said the solution involves adding vertices to V2 so Ill try that once my brain fjnctions

[lunar nexus]

Can someone tell me whats the best way to learn algebra?

[spark field]

#prealg-and-algebra or #linear-algebra are a good place to start 👍

[lunar nexus]

Ok thanks

why are the channels dead nobody is talking

[spark field]

All the channels won't be active 24/7

Often those who are interest in certain topics only subscribe to those channels, and show up only when someone else has something to say in them

[lunar nexus]

🙃 makes sense

[stuck trout]

Is my proof correct?

[spark field]

I'll look over it when I get back to my computer

[stuck trout]

nvm that I think what I have is correct, but i have other questions that I am unsure

[spark field]

You can still ask, I should be back soon

[stuck trout]

This one right here, talking to ppl around I think this wouldn't halt

you see the problem says you may turn any 1 or 2 coin of your choice. So if they decide to turn 2 heads then the potential function will increase

[spark field]

Yeah

You must reach the situation where there are 202 tails and 1 heads

But then once you reach there you could flip the head and the tails

Leaving you with 202 tails and 1 heads

Then you could flip the head and a tails

Leaving you with 202 tails and 1 heads

And so on

If you choose incorrectly (and don't just flip the remaining single heads coin to be done) you don't have to halt

I'll be honest the first time you sent it I really only read your proof (which was correct), but of course the proof breaks if the assumptions made (that the potential function always decreases) are wrong

So your proof was good but I didn't check the situation to actually make sure it matched

[stuck trout]

its this

[quick spade]

|x - 3| + |x-5| = 0 how would u do this and also vs |x - 3| = |x-5|

[spark field]

Yeah I remember what you suggested

Which is true if you pick that specific choice but it doesn't have to be that specific one

So it might not always halt

[spark field]

Beginning with $|x - 3| + |x - 5| = 0$, what do you know about absolute value?

[vital dew]

Coolempire93

[young night]

does anyone has discrete mathematic tutorial on logic, induction and recursion, relation, graph and tree for practice

[spark field]

For practice? I mean I can recommend textbooks ~ rosen discrete math been a prime one filled with examples and touching on each of your mentioned topics

[young night]

thankies!!

[spark field]

No problem!

[quick spade]

Set each other equal to zero

[south grove]

i need resources for permutations and combinations, anyone got any book/video recommendations

[spark field]

Yeah, since absolute value can never be negative, both of the insides here would have to be equal to zero cor the equation to be true

[novel spire]

Is this the right channel to ask a thing about the Master Theorem? I have an alternate way of expressing it that I came up with and I want to make sure I'm not missing any cases.

[spark field]

You could ask here yes

[novel spire]

Okay cool. Lemme type it up.

[spark field]

I also see a lot of complexity problems in #calculus

For some reason

[novel spire]

Here's the version of the Master Theorem in the book the students are using. I'm doing an interview for a tenure track position, and this is the lesson they want me to teach.

[spark field]

If no one comes by don't worry because I'll be back in not too long and I'll be able to answer if anything

[novel spire]

But the thing is, the last time I taught the Master Theorem some number of years ago ... maybe 5 years ago I think? ... I had a different way of expressing it

I defined the degree of a function f as:

$$\deg f=\lim\limits_{x\to\infty}\frac{\log |f(x)|}{\log x}$$

[vital dew]

Solid Angles

[novel spire]

(Basically the limit of the d(log y)/d(log x))

Then for the version I know of the Master Theorem, let's say you have $$T(n)=aT\left(\frac nb\right)+f(n).$$
Let $d=\log_b a$.

If $\deg f<d$, then $T(n)\in\Theta(n^d)$.

If $\deg f>d$, then $T(n)\in\Theta(f(n))$.

If $\deg f=d$, then $T(n)\in\Theta(f(n)\log n)$.

[vital dew]

Solid Angles

[novel spire]

So what I'm asking is, is this formulation equivalent? Or are there cases that I'm not covering here?

(The thought was that appealing to the degree greatly simplifies things, because factors of log n don't matter when computing it)

[spark field]

I think our book used a bix of both of these XD

How fun

Well like I said someone will probably come by
If not I'll just come later and verify they're both the same as mine

[novel spire]

Oh, I suppose I haven't included the regularity condition in my version...

[fossil mural]

this feels somewhat like overly-technical nickpicking, but there are functions that meet the conditions for the master theorem from here but for which the degree is not defined, because the limit doesn't exist, and so your formulation doesn't manage to apply to them

for instance if you take $a = b = 2$ and $f(n) = n^{5+\sin(n)}$

[vital dew]

bee [it/its]

[novel spire]

Oh interesting

I wonder if there’s a way to salvage it.

[fossil mural]

this counterexample still satisfies the weaker condition that, for some sufficiently large $N$, $\frac{\log |f(x)|}{\log x}$ is always greater than $d$ for $x > N$, which is equivalent to ``the limit is greater than $d$'' if the limit exists but still makes sense if it doesn't

[vital dew]

bee [it/its]

[novel spire]

Could that be phrased in terms of lim sup/inf?

[fossil mural]

oh yeah probably

yeah i think this is actually just the same as saying that the lim inf is > d

and the corresponding condition for "deg f < d" would be that the lim sup is < d

[novel spire]

Yeah I figure that would flip

Is there something that could happen in the “middle” case then…

[fossil mural]

...in a sense it's kind of just like, for some functions instead of the limit being a point it's an entire interval, with the property that it eventually lands in that interval but then can't be squeezed any further

[novel spire]

For example if d = 5 and f(n) is as you said

[fossil mural]

the lim inf and lim sup are the two boundary points of that interval, and all we actually care about is that the entire interval is > d or < d, not whether it has that property and is also only a single point

[novel spire]

Or maybe that’s so weird it doesn’t apply 😛

[fossil mural]

well then it's not \Theta(n^5) so the formulation of the master theorem you had from earlier doesn't apply to it

[novel spire]

Yeah, that's what I figured

[fossil mural]

honestly i suspect what actually happens in that case will depend on weird details of the exact recurrence and not just the asymptotic behaviour of the function

[novel spire]

Can the "regularity condition" be wrapped into talking about the lim inf?

Since passing to a limit (or something like one) seems to take care of this idea of needing to find a sufficiently large n

[fossil mural]

i mean you can definitely phrase it as some sort of limit

like i think $\limsup_{n \to \infty} \frac{af(\frac nb)}{f(n)} < 1$ is equivalent

[vital dew]

bee [it/its]

[novel spire]

Okay I'm glad to know I wasn't far off here

Thank you ❤️

(Of course now the ultimate question ... I need to decide whether I'll teach it this way XD)

[dawn finch]

Hey, I'm struggling to understand how to transform an assignation problem into a minimal cut problem. In exercises I have, I see they exchange the costs associated with an assignation and its counterpart. For example in the graph I sent the cost to assign task 1 to A is 6, and to B it's 4. Yet on the graph they set the capacity of A->1 to 4 and 1->B to 6. Why do we need to do that?

[sullen thorn]

When dealing with NFAs, does every node have an implicit ε transition to (REJECT)? Or am I overthinking it?
I'm not talking about for school or anything, I'm trying to do weird things with NFAs for a hobby project

In the NFA ∂(s0, g) -> ACCEPT, I know there's an implicit ∂(s0, ∑ - {g}) -> REJECT transition, but does that mean in the conversion to a DFA I should consider it as having a "null string" transition to REJECT?
I'm asking because I'm specifically trying to do something weird with that "null case", so it's not just "an empty string" but rather "a condition that's always true".

Wait but that's what the epsilon transition is regardless, right? Anything in ∑ satisfies ∂(s, ε), no matter what it is, right? So I guess I don't have anything to worry about?

[haughty garden]

this generally accounts for the behaviour when an NFA finishes parsing a string and does not end in an accept state. We reject a string if it does not end in an accepting state so any time we reach a non-accept state at the end of the string computation, we reject it (which is to say we implicitly have an epsilon transition to a reject state)

[sullen thorn]

Makes sense, that's what I figured. When making the DFA though, does that mean the- oh yeah no of course every single state that isn't an accept state is a reject state, so every state being a conjunction with the reject state makes sense. Reject states aren't even part of the tuple, are they?

[haughty garden]

we generally don’t have reject states, it’s encoded in the definition of accepting a string in the language that it has to end in an accept state

[sullen thorn]

Thanks

[haughty garden]

the standard reduction is to reduce the assignment problem into a mincost flow problem as follows: construct a source vertex s and a sink vertex t, a vertex for each agent, and a vertex for each task. Construct an arc from s to each agent i with no cost and capacity c_i, construct an arc from each task j to t with no cost and capacity d_j, and for each agent i and task j, construct an edge from i to j with cost A[i][j] and unit capacity

[stuck trout]

Does this work????

[haughty garden]

you have the right working, you can make it a bit more airtight with your explanation. Since Y has worst-case running time equal to Theta(nlogn), there exists an input of size n such that T_Y(n) runs in Omega(nlogn) time and then you can use the rest of your argument to basically conclude the answer

[stuck trout]

Yea thx for pointing it out, i fixed it. Thoughts? Also is my proof to show that Z is faster correct?

[flat grotto]

I can definitely do this, but i am not sure how to bring up r if I start from the hypothesis of (y,x) E in s^-1

[grand totem]

In order to show that (y, x) in (r; s)^{-1}, i.e. that (x, y) is in r; s, it suffices to show that (x, x') in r and (x', y) in s for some choice of x'. Now choosing x' to be x would seem like an obvious idea and indeed you already know that (x, y) in s (by assumption). Can you see how reflexivity of r comes into play now?

[spark field]

What is this notation, I've never seen it before

[grand totem]

which part specifically

[spark field]

(r; s)

[grand totem]

ah, a semicolon is sometimes used to denote composition in diagrammatic order (in this case composition of relations)

i.e. f; g = g \circ f

[spark field]

Ah

Good to know 👌

[twin basin]

Is combinatorics a subset of discrete math

oh nvm

it's in the description

just goes to show I need to brush up on my discrete math lol

[sullen thorn]

How far can you stretch the definition of deterministic finite automata to where its properties still hold? Is it enough to state "any token has one and only one transition outward from any given state, even if those transitions are selected in a different deterministic fashion", or does it specifically have to use pattern matching on a finite alphabet to select a transition?

Actually, would anyone be willing to look over my abstraction and tear it to shreds peer-review it? I don't want to dox myself on a public forum, but I'd love to share it privately.

[round jackal]

b) ¬(¬(p ∧ q) → (p → ¬q)) Do you guys know how to approach this problem from the beginning what are some tips and tricks to watch out for

[sullen thorn]

Are you just trying to simplify it? Think of it like a standard math equation and use your order of operations: items in parentheses first; then "not", then "and", then "or", then "implies".

Apply your laws you learned in class (like ¬(p and q) = ¬p or ¬q) to simplify each part in parentheses, bringing the ones in parentheses up to the top level. I haven't taken it in a while, but you should have learned laws for converting "implies" to an "and/or" expression as well.

Once things are on the top level, find your redundancies and eliminate them from the equation. Like how (p or ¬p) is just "true", so it can be removed entirely. Or (p and ¬p) would be nonsense, so it's a DNE iirc.

[cosmic pagoda]

trying to speedrun this course. Anyone got a good playlist orvideo recommendation?

[flat grotto]

I think everyone's course is different. depends on what it contains

[flat grotto]

Thank you, sorry i didn't reply, but this helped me

take the fact that i didn't reply as a compliment to the understanding you gave me :p

[fading schooner]

can anyone help me with like getting intuition for graph theory

For me some proofs are really hard and I need to learn to reason a proof

how do you study those proofs, is there a pattern etc

[worthy willow]

Yo guys I can't find Legendre's Formula in Niven's NT book

If anyone knows if the book has it or not, please let me know

[stuck trout]

Do I need to do an inductive proof for this question to show the correctness of my algorithm?

[spark field]

I would, yes

There may be a simpler mathematical argument though using the expression and formula given at the top

Someone with more experience will probably come along and comment

[stuck trout]

okay nvm it says I dont need a fomral induction proof

[stuck trout]

wait is my even case correct? nvm sorry

is it just x*x

[feral kestrel]

ts so nerdy 🥀

[jovial sail]

the humble truth table:

or you could just use logic laws wtv

[final cliff]

NFAs, regular expressions and regular grammars seem like a pretty far stretch from DFAs in the sense that they are all pretty distinct from DFAs while still having the same computational power.

So I guess in that sense you can get pretty far from what the usual DFA definition looks like.

You can also take the usual dfa definition and slightly tweak your notion of string inputs/acceptance to get strictly more powerful computational objects.

Buchi automata are an example of this.

I guess my point is you are asking a sorta fuzzy question with a probably kinda complicated (but interesting) answer.

[sullen thorn]

But the core facet of each of the ones you mentioned is that they are directly convertible to a DFA

EDIT: Oh, I guess when they were originally proposed they were considered modifications of a DFA. I keep forgetting that just because I was taught all of them at once doesn't mean they were invented that way.

[sullen thorn]

Oh, that's what I was talking about!

[grand totem]

<@&268886789983436800>

[final cliff]

Yeah, the convertibility/equivalence here is kinda my point. You can modify DFAs into things very unrecognizable without changing computational power. But you can also make pretty small tweaks to DFAs and their notion of computation in ways that change their computational power quite a lot.

[sullen thorn]

Definitely. I DM'd you my abstraction btw, do you think it holds?

I'm worried about losing the useful properties of DFAs, like composability, concatenation, etc

It's very much based on "what I remember from discrete math class", but it seems logical to me

[final cliff]

I think you're kinda forced into having to check whatever useful properties you think hold. What you sent me seems kinda nitty gritty and long so I don't want to reas it beyond a quick skim. You kinda just have to prove things when you start dealing with structures like this.

I think in general you might want to familiarize yourself with more of past research in automata and formal language theory. For example, your general goal of extending automata to larger classes of objects is not new, see tree automata as a similar goal/idea. It is very natural to assume people would have already considered "well what about graphs?" and so by proxy basically most finite structures. I do not know for sure as formal language theory/automata is not an area I specialize in.

People also have been studying more algebraic/language theoretic variations of these topics for a long time. Kleene algebras generalize regular expression. Primitive/partial recursive functions can be thought of as a form of this relating to turing machines (which also generalize DFAs) in the context of maps from N to itself as another example.

Not trying to discourage you ofc. Just saying it's worth looking into what things people have already done!

[mystic dragon]

Could i get some some advice on writing this proof (im kinda new to writing proofs since i just started)

"Show that at any party, there are always at least two people with exactly the same number of friends at that party."

Let there be n people at the party. There are n-1 possible friends for each person, so by the pigeonhole principle, there are more people at the party than possible friends, so at least two people must have the same number of friends at the party.

[slim geode]

Each person can have at least 0 and at most n-1 friends which gives n options, so pigeonhole principle isn't enough of an argument.

[mystic dragon]

but if someone has 0 then the most would be n-2? And if someone has n-1 friends then someone cannot have 0 friends, so n-1 options right

[spark field]

I guess they're saying you would need to mention that

Let there be n people at the party, with k of those having no friends. If k = 0, then all n people have n-1 choices of friends each, so by PHP at least two must have the same number. If k = 1, then n-1 people have n-2 choices of friends each so by PHP at least two must have the same number. Else if k >= 2, at least two people have 0 friends.

You could even just generalize all the cases and say that n-k people have n-k-1 choices of friends each

But I'm not particularly familiar with PHP proofs so idk if it's really necessary or not

[slim geode]

Exactly, miku didn't say it

[mystic dragon]

ok gotcha

[fading delta]

I want to solve a discrete optimization problem: choose (x \in \mathbb{Z}{\ge 0}^{10}) with (\sum{i=1}^{10} x_i = 100) that maximizes the number of opponents it defeats in a Blotto-style game. Exhaustive search is infeasible, so I’m building a branch-and-bound style method using monotonicity: increasing troops in any coordinate cannot reduce the number of castles won against a fixed opponent.

I therefore use dominance envelopes (u \in \mathbb{Z}{\ge 0}^{10}) with (\sum{i=1}^{10} u_i > 100). Each envelope (u) represents the subset
[
\left{ x \in \mathbb{Z}{\ge 0}^{10} ;:; \sum{i=1}^{10} x_i = 100,; x \le u \right}.
]
Monotonicity lets me compute an upper bound on the maximum fitness achievable within that subset. I want to design envelopes that partition (or nearly partition) the feasible space with minimal overlap, and that can be split into smaller envelopes for progressive refinement until reaching exact 100-sum vectors.

[vital dew]

AndrewFPV

[solemn canyon]

@hasty sable hello let's dm since you do not know anything about me except one or two messages from before or discord

[craggy flint]

Guys im having a problem with interpreting questions regarding like combination/permutation/ or just probability in general,,, I feel like theres no linear way of interpreting questions, can someone help me on how I can improve on this

[spark field]

Linear?

What do you mean 🤔

[mystic dragon]

when i write a proof involving rational numbers do i just assume that the rational number p/q can be in simplest form?

[spark field]

You state that you assume it yes

Example in the proof that square root of 2 is irrational:
Suppose square root of 2 is irrational. Then we can write square root of 2 = m/n, where m and n are integers and n does not divide m
or
Then we can write square root of 2 = m/n, where m and n are integers and m and n are coprime
or
Then we can write square root of 2 = m/n, where m and n are integers and only one of m or n is odd
etc.

Three common definitions I've seen

All of these imply 'simplest form' but actually give you something to work with mathematically

Otherwise if you don't need to actually work with it then you likely don't need to mention it anyway

[craggy flint]

i mightve worded it really bad but basically i mean, for example in calc2, I think the questions are straightforward because it might jsut be something like "find the area in this function"

but for some reason in questions regarding like combinations/permutations/probabilities,, i find myself dissecting what the english is saying and trying to figure out how to interpret it