Samadhi's school help thread

[Antrax]

The second post was an attempt to make you see the principal problem with the program. You were making a function call that effectively made no change to the state of the computer (except stealing a few bytes of memory).
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Samadhi]

Well, as much as I appreciate the help, such vision was entirely unnecessary. I fully understand the difference between an assignment and an expression. I made a stupid mistake (TYPO).
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Zag]

C code written by a LISP programmer? An interesting mix.

[Samadhi]

Nice catch. From the specs for this project: "We will organize our C linked lists so they closely resemble Lisp lists."
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Zag]

Ahh, so it's not your fault, then. It merely demonstrates that your professor is an idiot. Not an uncommon condition for CS professors. After all, if they were any good at the profession, wouldn't they be out in the actual marketplace? I mean, this isn't ancient Greek literature we are talking about.

Lisp is an write-only language that is interesting to academics only, not to any of us that work in the real world of software. The only thing worse than trying to make your C code look like Lisp is trying to make it look like SmallTalk. Lisp failed in the marketplace where C succeeded. Shouldn't that tell you something?

[Samadhi]

Haha. I only heard about smalltalk when I started this class.

Here's one syntax problem I'm having though. I'm trying to pass an array int to some methods (he's ridiculously particular about using methods for EVERYTHING.....even for one line print statements).

Anyway, for this I want to pass a two dimensional array to a method, do some stuff and return the worked array.

Suppose I have a method 'partition' that I want to pass the array to. I've tried various prototypes and such and I always get grief.

int partitionArray (int x); --This gives me an error when I try to treat x like an array (cannot dereference pointer type).

int partitionArray (int x[][]);-- Warning null dimension x
and also 'cannot do pointer arithmetic on operand of unknown size' when I try to do stuff with it in the method.

I'm used to java where you can pass something regardless of size as long as it matches the expected type, so I'm not sure what I'm doing wrong here.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Bicho the Inhaler]

I think the easiest way is to pass a pointer to the first element of the array along with the number of rows an columns, and then inside the function, do index arithmetic to get the elements (instead of array[m][n], you'd need array[m*cols + n]). In C++, you have other options, but C is sort of crippled when it comes to multidimensional arrays whose dimensions are not known statically. The reason your plausible-looking code doesn't work is manifest in the expression array[m*cols + n]: the compiler needs to know the number columns in order to index a two-dimensional array. That information can't be determined just by looking at the array (an array is literally just a bunch of items stored contiguously in memory; it doesn't carry any meta-information whatsoever), so the number of columns has to be told to the function separately somehow unless it is known statically.

If the number of columns is known statically (say, 5), then you can actually declare the function parameter as int array[][5] and treat it normally as a two-dimensional array.

[Samadhi]

Oh, cool. Only 2 columns. Thanks.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Samadhi]

Hmm, I just discovered that I can alter the passed array and don't have to return it. That makes sense since C is all about memory locations and pointers. But it feels....dangerous.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Nsof]

[Samadhi]

Anyone know a better way to selectively flip a bit (or not) than this? (the triangles with the bubble on top are tri-state buffers)

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

[Zag]

Yeah. Just run them both into an XOR. Also, your solution is wrong because you didn't reverse S1 anywhere. Your result is 0 if S1 is 1 (because the ground will win when it is a fight between the two, which you have) and floating if S1 is 0 (which usually means 1, but often only after a few latches of your circuit).

[Samadhi]

Yeah, realized about XOR when I looked at a truth table. Thanks.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Samadhi]

So apparently one of professors loves lisp.
I'm trying to use the 'clisp' command at the unix prompt but it's giving me grief when I follow his instructions. I haven't found any help from google. If anyone knows instructions for running lisp commands like (+ 1 2); in a unix environment, I'd love the help.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Samadhi]

Got the answer. I need to use bash (/bin/bash)
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Zag]

Is it the same professor as this one? (Or do you have TWO idiot programming professors?)

[Samadhi]

Same one. I hate the class.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Zag]

[Samadhi]

God this guys killing me. Now I have to:
(a) Write lisp code to find the first prime >2zyxwv where zyxwv are the last 5 of my phone number.
(b) Find the sum of [10000..11000], [3^7..3^20]
(c) find the 30th fibonacci number.
(d) rewrite the C code insert from my last project into lisp
(e) rewrite the sort
(f) some stupid length code stuff

Argh! Why does he insist on teaching this dead language?
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Antrax]

Because he believes many live concepts can be taught by that. I studied PDP-11 assembly language, which is a processor that was "alive" in the 70s, and it was still very helpful.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Samadhi]

I think that my main annoyance comes from the fact that all online references and the book talk about Common Lisp or Scheme, and he wants us to do this in Lisp.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Samadhi]

Could anyone give me a good example of what cofinite means? Wiki wasn't very clear to me. If it helps I'm working on automata theory. IE, ∑ be an alphabet (a, etc). Let C _∑ be the collection of all cofinite languages over ∑. (a language is a set of acceptable words made from the alphabet).

I'm thinking a cofinite language is not necessarily itself finite.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Antrax]

All natural numbers except for 0 is a cofinite subset (of N), because its complement, {0}, is finite.
All even natural numbers is not a cofinite subset of N, because its complement, all odd numbers, is infinite.
Every subset of {1, 2, 3} is cofinite.
etc.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Samadhi]

That clears it up. In my case, the cofinite languages will be infinite. That narrows it down considerably, and I believe I have it:
A finite language can be accepted by a DFA--> (def of DFA)
Finite languages are regular. (def of regular)
The complement of a regular language is regular-->C _∑ is regular (def of C _∑ )
Regular languages are closed under complementation, intersection, and Kleene closure, so C _∑ is closed under those properties.

I need to throw in some more justifications (where the book doesn't explicity say it), but that's good enough for now.

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

[Antrax]

I'm not sure how you got from the fact that any language in C_Sigma is regular to "C_Sigma is regular". Regular languages are not closed under infinite union.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Samadhi]

Ah. I see, if L ₁ is {aa} and L ₂ is {bb} then ~L ₁ contains {bb} and ~L ₂ contains {aa}. Therefore ~L ₁ U ~L ₂ is not closed over the coinfinite set.

[Edit]No, I actually think I'm confusing myself.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Antrax]

If A1 is regular and A2 is regular, then A1 U A2 is regular. From here you can continue with induction and reach the conclusion that any FINITE union of regular languages is still regular (and it makes sense - you can just keep combining the automatons).
However, that doesn't mean that an INFINITE union of regular language is regular, mostly because it's incorrect. For example, consider the family of languages Li = {a^ib^i}. Each contains a single word, and thus is regular, but their infinite union is {a^ib^i|i is natural} which is not regular. So, I don't think you can say C_Sigma is regular.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Samadhi]

I haven't encountered the definition of natural with respect to DFA and can't find it on line. Do you have a good definition?
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Antrax]

Natural? Not sure where you saw it, but it means "natural number" or "a typo and I meant to write regular", wherever it is.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Samadhi]

[Samadhi]

[Samadhi]

Wow, I made a bonehead mistake on the second two. Sets dummy! Luckily I ran my answers by my professor before class and he pointed out my error.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Samadhi]

This is a graph problem. I have it, I'm just not well able to explain my proof and I'm doubtful that my algorithm is terribly efficient.

You have a network of n computers and the bandwidth between any two is distinct. The issue is to find the quickest path between any two computers and the limiting (though not entirely realistic) factor is the lowest bandwidth between any edges on the path. IE finding a path that had 1000 computers on it but the lowest bandwidth was 10 foos/s, that would be better than a direct link between the computers that was 9 foos/s.

(my solution/idea)It's a traversal of sorts. You can start anywhere but you want to recursively connect the highest (lowest weight) edge first. However, you always have to process the highest available, which may be back a few levels in the tree. Basically, since you are always connecting the best available first nothing will have a path in the tree except through its best connection. I'm not sure how to prove that. Counter proof?

Anyway.

Here's my thoughts so far on the algorithm.....ugly I know:
Make an array of all nodes with 'visited' and 'complete' as fields.
Choose any node (they should be linked lists of connections with weighting, and hopefully ordered for God's sake).

ProcessNode(node foo, node lowest){ //lowest is null if no low passed
mark node as visited in array
if ((node N =FindLowest(foo))==null)
set array for node to complete, return;
if (N<lowest) ProcessNode(lowest, ?); //I'd need comparable here but you the idea
if ((node M =FindNextLowest(foo))<lowest) ProcessNode(N, lowest);
ProcessNode(N, M);
}

I'm not sure I'm keeping track of things well in the recursion (and I missed the connection bit IE...the freaking tree).
In English what I'm thinking is:
You start with any node.
If it has no unprocessed connections, done.
Else, find its best and next best connections (null for second if only one).
Attach that node to your beginning node.
Mark it as visited.
Find the best connection for this node.
If it's better than the second from the 'parent':
Find the next best for this node and pass the better of that and the second from the parent to be processed.
Else process the next best.

It just seems like mins and maxes can easily get lost unless I make a stack or rely on an array with all the edge weights.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Nsof]

Spoiler:

Hint 1
Look at: en.wikipedia.org/wiki/Floyd-Warshall_algorithm

Hint 2
in particular look at section "Applications and generalizations" fifth bullet.

_________________
Will sell this place for beer

[Samadhi]

That is the kind of thing that, once you see it, you think "Well, naturally!" (like velcro)
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.

[Bicho the Inhaler]

[mps1453]

[quote="Bicho the Inhaler"]

[Samadhi]

This is a question about some on line notes: http://www-rohan.sdsu.edu/~taoxie/cs370/Lecture17.pdf
Specifically, page 21-24 (if you want to see the notes). It's specifically the explanation on page 24 that I'm not parsing. Here's the synopsis.
This is about "present states" and creating a truth table for the inputs. IE suppose you had present states (A, B, C, D) and depending on the input (0, 1) you move to a new state and have an output (0, 1). Here's the example in the notes.

Basically this will accept the input of 1101 (output=1 typically means accept).

Then on the next page there's the simple substitution of (00,01,10,11) for the states which gives:


Page 23 is just another way of doing the above (for optimization of the K map).

Here's where I get lost:

[Samadhi]

I figured it out. y ₁ y ₀ is present state, D ₁ D ₂ is next state, and z is the output.
_________________
And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.