A question came into my mind today. I was wondering what is the fewest number of words you need to know in order to understand the entire dictionary. The dictionary is a big circular reference, each word can be looked up and is defined by other words. There must be a certain number of words that you already know in order to understand the dictionary. This problem seems like a graph theory problem, where each word is a vertex, and two words are connected by a *directed* edge if the first is used to define the second. I wonder if there is an algorithm to seek out the fewest number of words required to be able to define the whole dictionary.
I think I came up with a test to determine if a set of words is sufficient to define the whole dictionary. Ok, first let me be clear about which way the arrows on my digraph go. For example, the word "bird" would have an edge connecting to "sparrow" because sparrow is defined as "a type of bird". The arrow (the direction of the edge) would go FROM bird TO sparrow. The edge is said to be an "outgoing edge from bird" and an "incoming edge to sparrow". (These are my termonologies and convensions for this problem).
Assume all edges and verticies are colored black. Then we take the initial set of words and color each of them green. Any outgoing edge from our initial set is this colored green. Then we check all verticies that are black, and if all the incoming edges are green (that is, if all the words used to define the word are defined), then we color that vertex green, and we also color all its out-going edges green. We repeat this process until we hit the point where we color no new edges green.
I am fairly certain that if this method colors everything green, then we have managed to define the whole dictionary. I am not positive, however, if this method will always work. It could be possible we could have a set of words that define the whole dictionary and this method would not color everything. If someone has a proof or a counter example, please tell me.
Anyhow, now that you have skipped over reading my math problem because it got boring, I guess I should post a little bit about Germany. The weather here has been absolutely wonderful. I hate having to wear pants. It got up to 60 degrees today! And people were still wearing jackets. I wanted to be out in shorts and a T-Shirt, but society has decided that I have to wear long pants and long-sleeve shirts. When I was explaining to a friend (in German) last night that I normally never wear long pants she couldn't believe that I normally wear less than I was wearing then (I had no jacket, only a sweatshirt, no hat, and no gloves).
I don't think I posted about this yet, but if I did, oh well. I went for a walk in the Black Forest with my peer advisor (Carina) and a couple Connecticut students. When we left Freiburg there were a couple inches of snow on the ground, and it was snowing a little bit, by the time we got where we were going in the Black Forest, there was a good foot and a half of snow and more was falling from the sky at a rapid rate. So, we went through the snow and took in the fine German landscape. We walked up to Titisee, which is a lake that is currently froozen over. I've seen some pictures of it in the summer, and it looks like one of those stupid overly-good-looking postcard pictures. I'm too cheap to send postcards or scan postcards, so once it becomes summer, I will go out there again and take a picture.
I must also jump up and down now. It appears that the course "Algebraic Topology" does NOT require any pre-reqs (except for intro math courses). Yahoo!!! Now when I leave UConn I will have a nice diverse background (topology, differential geometry, real and complex analysis, number theory, graduate algebra, combinatorics (including graph theory), and linear algebra). Hopefully I'll be able to get into graduate school.
Anyhow, for those of you back in Connecticut. Enjoy your cold weather.
~Mike
Archived comments:
Anna:
It is cold here. Cold, cold, cold. It's not really that it's bitterly cold, but it's constantly cold. My feeling is that after Christmas, or at least the New Year, the weather should start warming up. Appearantly the weather does not think this is the way it should behave.
Also, my classes are such that I probably spend the maximum time possible outside walking in the cold windy weather. I don't know how much you remember of CCSU, but this is what I do on MWF: I park in the new garage, then my first class is in willard, my second is in copernicus, my third is in willard, and then my fourth is in copernicus again. I don't think I could've chosen classes further away from each other. It's not so bad, but I feel like complaining about the cold-certainly-not-60-degree weather.
chewchild2000:
the math problem looks good. maybe you'll get the Nobel Prize for mathematics and english at once. tell me when you have finished working on it...think about it for your Graduate project. that would be cool.
weather stinks, i need to turn it off, that way things won't be hot or cold,they will just be.
oh hey, remember when i poisoned my blood and went to the children's hospital to get it fixed? well i am eligible for a 2,500 dollar grant from them towards college. how cool is that?
Anna, what is your AIM screen name?
No comments:
Post a Comment