# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Message body

 Emoticons View more Emoticons
 [quote="Samadhi"]Given that you're in [i]n[/i] space, and you have [i]n[/i] vectors (non scalar multiples), I know how to calculate the angle between any two, but what about the angle between those two and another vector?[/quote]
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
 Topic review
Author Message
Posted: Wed Apr 23, 2008 2:42 am    Post subject: 1

I figured it out. y 1 y 0 is present state, D 1 D 2 is next state, and z is the output.
Posted: Tue Apr 22, 2008 3:33 am    Post subject: 0

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:
Quote:
Assume D flip-flops
Interchange the bottom two rows of the state table, to obtain K-maps for D1, D2, and Z:

Which gives (and I'm not seeing how)

Can anyone clear this up for me?
mps1453
Posted: Mon Apr 14, 2008 5:32 pm    Post subject: -1

[quote="Bicho the Inhaler"]
Nsof wrote:

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

I love Wikipedia!!!
Bicho the Inhaler
Posted: Thu Apr 10, 2008 3:25 am    Post subject: -2

Nsof wrote:
Spoiler:

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

Hint 2
in particular look at section "Applications and generalizations" fifth bullet.
Unless I'm missing something, that is suboptimal for this problem.

Hint: the edge with the lowest bandwidth whose deletion doesn't separate the graph will never be used. Run with that, and you will see what the solution "looks like." As for computing it efficiently...think back to graph algorithms you learned before (assuming you have studied the basic standard graph algorithms).

Edit: clarification: the last part of the hint is intended for Samadhi, not Nsof; Nsof would definitely know about that algorithm.
Posted: Wed Apr 09, 2008 10:16 pm    Post subject: -3

That is the kind of thing that, once you see it, you think "Well, naturally!" (like velcro)
Nsof
Posted: Wed Apr 09, 2008 9:58 pm    Post subject: -4

Spoiler:

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

Hint 2
in particular look at section "Applications and generalizations" fifth bullet.
Posted: Wed Apr 09, 2008 7:52 pm    Post subject: -5

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:
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.
Posted: Fri Mar 28, 2008 2:30 am    Post subject: -6

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.
Posted: Thu Mar 27, 2008 8:39 am    Post subject: -7

Antrax wrote:
Natural? Not sure where you saw it, but it means "natural number" or "a typo and I meant to write regular", wherever it is.

Quote:
but their infinite union is {a^ib^i|i is natural} which is not regular.

[edit:] oh, i is a natural number. nm

And got it, since N is infinite you can't have a DFA or NFA that gets them all.
Posted: Thu Mar 27, 2008 8:38 am    Post subject: -8

Quote:
So, I don't think you can say C_Sigma is regular.
Well, at least not with my proof.

Also, I think I'm using definitions that I shouldn't (or need to).
(I need to show or disprove complementation, intersection, and Kleene closure)
For complementation: let L 1 in C_sigma. Is ~L 1 in C_sigma? Using the def, L 1 = ~L i (finite) therefore, from complement of complement this would be L i which is finite. A finite language can not be the complement of a finite language (this seems obvious but I probably need to prove it).

For intersection, easy DeMorgan's proves it.

Kleene. Counter example: L 1 = ~{abab}. Therefore L 1 contains {ab} and L* contains {abab} so not closed.
Antrax
Posted: Thu Mar 27, 2008 8:21 am    Post subject: -9

Natural? Not sure where you saw it, but it means "natural number" or "a typo and I meant to write regular", wherever it is.
Posted: Thu Mar 27, 2008 8:20 am    Post subject: -10

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?
Antrax
Posted: Thu Mar 27, 2008 8:10 am    Post subject: -11

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.
Posted: Thu Mar 27, 2008 7:52 am    Post subject: -12

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

No, I actually think I'm confusing myself.
Antrax
Posted: Thu Mar 27, 2008 7:44 am    Post subject: -13

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.
Posted: Thu Mar 27, 2008 7:26 am    Post subject: -14

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.
Antrax
Posted: Thu Mar 27, 2008 7:07 am    Post subject: -15

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.
Posted: Thu Mar 27, 2008 6:44 am    Post subject: -16

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.
Posted: Wed Mar 26, 2008 6:10 am    Post subject: -17

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.
Antrax
Posted: Wed Mar 26, 2008 5:59 am    Post subject: -18

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.
Posted: Wed Mar 26, 2008 5:19 am    Post subject: -19

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?
Zag
Posted: Mon Mar 24, 2008 3:41 am    Post subject: -20

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.

Oh, I didn't notice this before. That is why there is a distinction between a const int * and an int *. With the const int *, you can't modify what it points to. It was always intended that you can pass in arrays and the function will modify them. Think of a sort function -- what good would it be if it couldn't modify the array.
Posted: Thu Mar 20, 2008 12:14 am    Post subject: -21

Same one. I hate the class.
Zag
Posted: Wed Mar 19, 2008 6:11 pm    Post subject: -22

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

We will organize our C linked lists so they closely resemble Lisp lists.
Posted: Wed Mar 19, 2008 6:11 am    Post subject: -23

Got the answer. I need to use bash (/bin/bash)
Posted: Wed Mar 19, 2008 5:40 am    Post subject: -24

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.
Posted: Sat Mar 15, 2008 2:26 am    Post subject: -25

Yeah, realized about XOR when I looked at a truth table. Thanks.
Zag
Posted: Fri Mar 14, 2008 4:15 pm    Post subject: -26

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).
Posted: Fri Mar 14, 2008 2:53 am    Post subject: -27

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)
Nsof
Posted: Mon Mar 03, 2008 11:55 pm    Post subject: -28

But it feels....dangerous.

Just make sure the os doesn't feel access violated by your program
Posted: Mon Mar 03, 2008 10:11 am    Post subject: -29

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.
Posted: Mon Mar 03, 2008 5:42 am    Post subject: -30

Oh, cool. Only 2 columns. Thanks.
Bicho the Inhaler
Posted: Mon Mar 03, 2008 5:34 am    Post subject: -31

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.
Posted: Mon Mar 03, 2008 3:55 am    Post subject: -32

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.
Zag
Posted: Mon Mar 03, 2008 2:20 am    Post subject: -33

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?
Posted: Sun Mar 02, 2008 9:32 pm    Post subject: -34

Nice catch. From the specs for this project: "We will organize our C linked lists so they closely resemble Lisp lists."
Zag
Posted: Sun Mar 02, 2008 5:30 pm    Post subject: -35

C code written by a LISP programmer? An interesting mix.
Posted: Sun Mar 02, 2008 7:22 am    Post subject: -36

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).
Antrax
Posted: Sun Mar 02, 2008 6:50 am    Post subject: -37

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).