Samadhi's school help thread

[MatthewV]

I suppose it could be the Multiplicative Identity and the definition of division.

given: a =b, c/c = 1

a = a * c/c = b so... a * c = b * c

beautifully sloppy

[Samadhi]

Good point. Since the "standard" properties are sufficient, it shouldn't be its own property.

Instead, I guess it would be a theorem.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Antrax]

One of the properties a set with two binary operations need to hold to be a field is the following: a(b+c) = ab+ac. Using this, you can easily prove what you were interested in.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Samadhi]

Yeah, distributive. Highly useful in some proofs that seem to only involve multiplicative properties. I think mattv's approach takes less steps though in this case.

To clarify, I'm not trying to prove this. I'm just curious. My professor did a hand wave when he had to do a = c --> ab = cb.
This is for Advanced Calculus: "Completeness of the real numbers and its consequences, sequences of real numbers, continuity, differentiability and integrability of functions of one real variable."

I'm looking forward to this class.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Samadhi]

I'm not worried about any classes this semester except "Systems Programming":
Design and implementation of system software. Relationship between software design and machine architecture. Topics from assemblers, loaders and linkers, macro processors, compilers, debuggers, editors. Introduction to software engineering and review of programming fundamentals and object oriented concepts. Large project in object oriented programming is required.

Allegedly there are two prerequisites both of which I got ~95%. The prereqs were assembly (like butter) and data structures (all in java). This professor likes C though. I'd rather write in assembly than in C. Sure it'd take me x10 to x1000 lines, but I'd be 100% certain what is happening.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[CzarJ]

[Antrax]

I don't understand what relation there is between compilers/preprocessors/linkers/loaders and software engineering. They're on the exact opposite ends of the scale.
In any case, if there's a connection between these two halves of the course, you won't be able to use Java, as you don't really get access to the hardware when working with it, at least to the best of my knowledge. C is much more bare-bones this way.
And even if I'm wrong, learn C already. It's really, really useful.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Samadhi]

Any of my descriptions were straight from the manual. Perhaps I should have disclaimed (IE I don't know the relationships either...I haven't taken the classes yet).

I've wanted to take a course that teaches C (it's in the manual), but they never seem to offer it (well not for 3 semesters, maybe some time soon). This is quite odd since many classes require "intimate" knowledge of C. I've ordered a book on "how to C", I hope that will help.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Antrax]

"A Book on C" is considered very good.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Samadhi]

I wrote a poker program in C (this is school independent, but important). I had trouble doing multiple calls. Such as, I pass two arrays to a function and then it returns the result from passing those two arrays to another function.

Was it because I declared them constant? I left some old code commented in the f1 function for critique.

I would have enjoyed using the results to call an array of dereferenced functions, but that's maybe for next time. Well, next to next. Next is programming the draw.

I'm sure there are many ways to stream line this (and probably some pitfalls I missed). I would really, really enjoy criticism. It's long, but I tried to make the comments and most of the variable/function names friendly.

The file

[Antrax]

First of all, a challenge to you: write a more efficient shuffling algorithm. The one you come up with should run at O(n) time, where n is the size of the array, and guarantee a uniform distribution.
(This is not only something you sometimes need to use in real life, it's also a common work interview question. Plus, it's fun).
Secondly, if all you want is to deal cards and then evaluate the hand, it seems you're doing too much work. Just choose five random unique ints from 0 to 51 and you're set.
Thirdly, sorting seems odd. It simplifies finding pairs, but doesn't help anything else.
Haven't read everything yet, though.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Antrax]

Oh, and after reading your commented out code, it's just a syntax issue. Your functions take "int const []" parameters, which are in fact constant pointers to integers. So, to pass them around, say from f1 to f2, you shouldn't do (f2(arr[])) which is a syntax error I think, but rather (f2(arr)), as arr is the pointer, and not arr[].
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Samadhi]

I thought my shuffling algorithm was O(n)?

In re: second. I'm prepping to scale up to a program that deals multiple hands and allows for redraws. To me, this seems to require the overhead of a shuffled array.
But, if I only needed to choose 5 randomly selected numbers from 0 to 51:

[Samadhi]

I thought my shuffling algorithm was O(n)?

In re: second. I'm prepping to scale up to a program that deals multiple hands and allows for redraws. To me, this seems to require the overhead of a shuffled array.
But, if I only needed to choose 5 randomly selected numbers from 0 to 51:

[Antrax]

[Samadhi]

It was easy, sue me.

[Antrax]

I think you can actually prove the output isn't uniform. Not sure. There's a more elegant way, in any case.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Samadhi]

...and it is?
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Samadhi]

The counter proof is almost trivial. Consider n = 3. There are 3! possibilities with equal probability. For the swap algorithm to work in this case all iterated possibilities must be equal. If we don't ignore self swapping, the number of branches for this algorithm is 27, which is not divisible by 6. If we ignore self swapping, the branches for this algorithm is 8, also not divisible by 6.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Antrax]

Below is the random permutation code I use in one of my crypto projects. get_rand(int max) return a random integer in [0, max) (you can use rand() % max, I had to use something else)

[Samadhi]

That seems to randomize well but it seriously screws up my hand analyzing algorithms and gives me random segmentation faults. I'm not entirely clear what yours does, so I don't think I'll use it.

I went with this instead:

[Bicho the Inhaler]

That still isn't uniform, Samadhi.

Here's a more natural way to express Antrax's algorithm (which is the random permutation algorithm as far as I'm concerned):

[Samadhi]

I'm strained to understand why that's not uniform, but I'll take your word for it. At least until I dis/prove it.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Samadhi]

Ugh.

Prove that any nonzero integer may be uniquely represented in the form
n = c _s 3 ^s +...+c ₀ 3 ⁰ . Where c _i is either -1, 0, or 1.

This should be similar to the proof for bases but that -1 is screwing me up.

For existence I'm thinking of using:
If n > 0 then it can be written as a _s k ^s +...+a ₀ k ⁰ where k = 3 and 0 <= a < k. (bases theorem). And each a can be written as either 0, 1 or 3 -1. But that gets hairy.

I suppose I could try to use the fact that if 1*3 ^s +...+1*3 ⁰ + 1 = 1*3 ^s+1 + -1*3 ^s +...+ -1*3 ⁰ (provable by induction)
then show that f(n) [the number of representations of n] equals 1 for all n.

Am I on the right track at least?
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Bicho the Inhaler]

[Samadhi]

Thanks, that's what I thought of this morning.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Bicho the Inhaler]

For your new problem: this is actually much easier than you're making it out to be. How would you compute c ₀ , ..., c _s ? If you do it the right way (the easy way), it will follow immediately that each digit is uniquely determined. The hardest part may be showing that the computation terminates, but that isn't hard.

[Samadhi]

3 divides either n, n-1, or n+1. If 3|n, then c ₀ = 0. If 3|n-1, then c ₀ = 1. If 3|n+1, then c ₀ = -1.

For c ₁ do the same but use n/3, (n+1)/3, or (n-1)/3 as appropriate.

So, existence: *hand wave* (I'm not sure how to clearly state this)
Uniqueness: Assume that n can be written as a set of a's and a set of b's where at least one of the elements differ. But this implies that at some point during the set up the number and one more than or one less than the number would be divisible by 3, which is impossible. So the set a must equal the set b. (I'm not sure how rigorous that is)

Thanks for the hint.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Sam*]

Q. A nonempty set of integers J that fulfills the following two conditions is called an integral ideal:
(a) If n, m are in J, then n + m and n - m are in J; and
(b) If n is in J and r is any integer, then rn is in J.

Further, for any integer m let J _m = {mk : k ∈Z}, the set of all integer multiples of m. You may assume that J _m is an integral ideal.

Prove that every integral ideal J is, in fact, equal to J _m for some m ∈Z

I went with this:
Let m > n. --> since m - n ∈J, J contains positive integers. From the least positive integer theorem (or something like that) there exists a smallest positive integer. Call this value m.
By property b, rm (r ∈Z) ∈J.
Thus J = J _m

Is that sufficient? It kind of felt like a hand wave there at the end. Should I have proved they're subsets of each other?

[Sam*]

Here's one that a friend is working on for his Algorithms class:

How can you rearrange the following pair of equations so that you only need to perform three total multiplications?
x = ab + bc + cd - cc
y = ab + cc + cd

[kevinatilusa]

Sam,

In your integral ideal question, you right that you need to show that they're subsets of each other.

What you've done is exhibit some m for which you think J=J_m, then show that any element in J_m is also in J. You still need to show that if something is in J, then it's also in your J_m.

One other little catch to watch out for...you began by assuming that J contained two elements such that m>n. Are you completely sure that J has to contain two different integers like that? You should be able to come up with at least one ideal that doesn't...

[Samadhi]

k:

[kevinatilusa]

The "showing isn't things are equal by showing each is a subset of the other" isn't really a method so much as it is a definition. Most ways of showing two groups/rings/etc. are equal (e.g. working with generators) comes down in some way to showing that they contain the same elements.

In many of my classes it was just assumed beforehand that we knew this. Even though we never explicitly went over the method in class, we still were expected to use it in homework.

[Antrax]

What kevinailusa said. Showing inclusion both ways is almost the only way used to prove sets are equal.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Samadhi]

I will keep that in mind. It's weird that I only heard of this recently.

I figured out my friends problem:

x= ab + c (b + d - c)
y= ab + c (c + d)
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Samadhi]

For the ideal problem:

Trivial case: J = {0} = J ₀
(1)
J ∈J ₀ . ∀m, n ∈J --> m - n ∈J. Every m or n is 0, so every m - n is 0 ∈ J ₀ (0k)
(2)
J ₀ ∈ J. From the definition J ₀ = {0k : k ∈Z}. Which for every k = 0. And from b, J contains 0 and 0 times any Z = zero.
Since the two are subsets of each other they are equal.

Non trivial: J = J _m where m ≠ 0.
(1) [J ∈J _m ]From (b) there are infinitely many members of this set and they are well ordered (integers). Therefore ∃ o, n ∈J | o-n > 0. This implies that J contains positive integers. Since the integers are well ordered there must be a smallest positive integer in J. Let this be called m. Since (b) is identical to the definition for J _m and we have defined it as m, J ∈J _m
(2) [J _m ∈J] Since (b) and the definition for J _m are identical it would be left to show (a)
Let m ₁ = k ₁ m, m ₂ = k ₂ m for some k ₁ , k ₂ ∈Z. Therefore m ₁ - m ₂ = m (k ₁ -k ₂ ). Since k _{1, 2} ∈Z and Z is closed is a field --> m (k ₁ -k ₂ ) = mk ₃ with k ₃ ∈Z --> [J m ∈J] from (b)

I think I might have engaged in overkill.
[Edit: this was for last week's quiz and it took 95% of my time (the other questions were easy IMO). I just want to hone my skills.]
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Samadhi]

Merde. I transcribed the earlier algorithm problem incorrectly.
It should be:
x = ab + bc + ad - cc (vice cd)
y = ab + cc + cd

Allegedly this can be done but the only detail I recall is adding x and y together....but that's a hornet's nest and I don't see how that could simplify things. It's not for school, maybe I should post it in VSP.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Samadhi]

Could someone take me through the steps to solve for the general solution of the following?

x' = x (1 - x) - h. For all h > 0
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Samadhi]

Nevermind. I found a good site that step by steps it. Refresher = good.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Samadhi]

I know I've seen this problem before and that's annoying. But it's for next week's homework so it goes here.

Find three real number x, y, z such that
-2 < (x ² + y ² + z ² )/(xy + xz + yz) < 1

Or prove no such numbers exist.

I hope my computer model wasn't badly designed because I believe no such numbers exist. Following that lead...

Obvious:
At least one variable needs to have a different value than the other two.
We can focus on each variable being on or around +-1, since anything else can be factored out.
We can set x = 1 and let the others be relative.

Proof by cases: (surely there's something better?)
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.