Last Updated 10 Dec 2002 [references added and "Graph Manipulator" project added].
Here are a few projects for Computer Science/Computer Engineering seniors or Masters students, or even for those that are curious, and not at the SProj stage. If you want to discuss these with me, just let me know.
A program that looks at a student's transcript and then offers advice on what courses to take and why. There are two possible approaches.
By looking at other students who were in similar situations you can offer advice. This is something like the http://www.amazon.com/ advice which says "People who purchased this book were also interested in the following other books". Thus by looking at the courses taken, and the grades received in them, we can find others who were in a similar boat and see what they did in their next quarter. Without really coming to a logical conclusion that "this person is weak in math and so should go more for software engineering rather than DSP", we can statistically give the same advice because others with similar transcripts also made that choice.
References: Here are two interesting sites that do something like this. For books go to AlexLit Home Page and then click on Department/Recommender. For websites global network of dreams .. even if you don't know what you are looking for - gnod will find it. It would be worth doing a web search for the mathematics of how this is done.
By using a rule-based approach, and by trying to gather information from the transcript, we might be able to give suggestions to a student. This can range from advice like "You got a D in .... If you want to repeat it, you better do it now, because course repetition is only allowed on the first offering", to "You need to take this course otherwise you will not have the pre-requisites to later courses, and will not be able to graduate in time" or a suggestion like "you should not leave core courses till the last quarter because a fail at that time can mean a delayed graduation", etc.
Ideally both approaches have their benefits and should be combined. The AI approach has the additional benefit that it can provide a reason for its suggestion. A measure of goodness would be how often students follow the suggested courses. A secondary benefit would be that the PCO could use this as a predictive tool. They could run the program for each and every student and be able to get a reasonable what the student will do next. This would provide an estimate of the enrollments, as well as to find pre-requisite problems, course/schedule clashes ahead of time.
I do not know the statistical techniques being used by amazon, but there has been research done in this area, and so you should be able to get some details on the web. While I may be of help in the statistical part, the for the AI part you would need to get some other project advisor.
This is more suited to Computer Engineering
We often need to transcribe tapes that were recorded for a lecture, or an interview, etc. In the olden days, there used to be a special transcription machine, which really was just a tape recorder with a foot-pedal pause and cue switch. (Cue means rewind for about 3 seconds and then start playing again. With this machine, a typist could operate the tape with his foot, and type on the keyboard at the same time.
I do not really know what the current technology is, but it is easily possible to make a much-improved version of this machine. The computer can speed up and slow down the playing speed, without causing pitch distortion. A foot switch connected to a computer as an accelerator is quite trivial to make. A full tap on the accelerator might indicate a Cue operation. To do this in real time would be the challenge.
The DSP people should be able to help you more than myself in this area. The hardware to build a foot pedal is trivial.
Since the rules for recitation of the Quran are so precise that even a person who has no understanding of the language can not only recite it, but recite it with perfection, the Quran is an ideal target for text-to-speech. This would make it possible to compress Quran audio so that the entire Quran could fit on a Palm computer.
I have done a good amount of work on this already. There is a program called MBROLA which is a pretty good text-to-speech program and has modules for various foreign languages, including Arabic. Unfortunately, it does not have Quranic Arabic, so there are some sounds that are missing. One project would be to create a module for Quranic Arabic. Modules are created by splitting sounds into di-phones, and then creating a database of these.
References: You can use many of the references of the next section in this section as well. But a few that are specific to this section are: The MBROLA PROJECT HOMEPAGE, and a general collection of links is found at Registry of All Speech stuff.
There are millions of Hafiz scattered throughout the world. Many of them memorized the Quran at a young age, and then took on studies or jobs that kept them so busy that they did not get the time to revise, and now have nearly forgotten what they had learned. When they now think of revising or relearning, it is difficult to do in a busy life with jobs and uncertain schedules. The few that can spare dedicated time still have difficulty finding a good hafiz to listen to them carefully. This problem gets worse when people are living abroad, where a hafiz is an extreme rarity. A computer program that could listen to a recitation of the Quran, and indicate any time a mistake is made would be of immense value.
This is a very large project, and I do not expect that any one group would do it, but a single group could take on one part of the project. Three possibilities that could be explored have been listed below. I think that the last one should be doable first. You should like DSP to think about doing this as a project. Some professors at FAST were willing to help in this project.
Text comparison: The recitation could be compared against the text of the Quran. Since the Quran text has complete timing and pronunciation information, this would be possible. Because of individual variation in the pronunciation of individual letters, as well as the inability of many people to correctly pronounce all letters of Arabic, the program would have to be flexible. Ideally, you may want to create something like the MSWord Grammar checker, where you can turn off the application of a particular rule. For example, you could ask the program to not warn you about the length of a madd, or the difference between the letter seen and suad. The advantage of such a program would be that it would serve as a teaching tool as well, to teach good rules of qira'at. Ideally this needs to be done in real time.
Audio comparison: The hafiz could recite once while looking at the text. The next time they could recite from memory, and the two recitations could be compared. Ideally this needs to be done real time.
Fast check: It might be difficult to accomplish the above tasks in real time. In fact, it is not essential for everything to be done in real time. But because there are many similar passages in the Quran, one common type of error is for a Hafiz to slip form one place in the Quran to an entirely different place, or to forget a passage or a section. This kind of error needs to be corrected in real time, otherwise the Hafiz may enter an infinite loop, or not recite and hence not check entire passages. Other errors are small like the mispronunciation of a letter or a vowel, or the wrong timing, etc. These, even if they are not done in real time, and marked later to be revised by the hafiz would be acceptable.
One way to accomplish this fast check is simply to keep track of the vowel sounds, and compare them with the expected vowel sequence from the text. If a Hafiz slips from the expected sequence, then there should be a whole sequence of mistakes. This is a much easier task, and should be doable in real time. Of course some level of re-sync abilities should be there, so that they can recover from a small mistake, or cough, etc, and yet be able to continue the recitation.
References: Here are a few starting points. A site that contains links to many sites that are working on speech is Speech. Getting down to implementation level, here is a site that is quite recent, containing a survey of Automatic Speech Recognition tools available on Linux Speech Recognition HOWTO. This covers the basics of the theory as well as available software and references to more details in books and on the web. Finally, a survey book (1996) about the subject is Survey of the State of the Art in Human Language Technology.
Most symmetric key cryptosystems are described using a flow diagram (for an example, see the graph shown in the Graph Manipulator project below) that indicates that data paths of the bits. Blocks with inputs and outputs serve as adders, xor boxes, multipliers, S-boxes, etc. There are no more than a dozen building blocks, which are then just hooked together. It would be nice to have a tool where one could visually build an algorithm, generate code for the encryption. More interesting would be to automatically build a decryptor from the description of the encryption. Even more useful would be to then have visual cryptanalysis tools that could use random source data, and see if there are correlations in the intermediate stages of the cryptosystem. The advantage of having the innards of a cryptosystem laid bare on a visual display, and being able to run statistical tests by simply pointing would be immense.
References: Look at the DES and the 5 AES candidates, as well as the many other entrants in the AES competition. There is also a European (List of accepted NESSIE submissions) competition going on. You will find many alternative symmetric key cryptosystems. You will see how they are usually described using graphs that represent the flow of bits.
You can find the above references using general web searches, or start from one of the many pointer sites like: Cryptography Pointers, or Cryptography, Encryption and Stenography.
You could also search for linear, differential, and linear-differential cryptanalysis, to see what kind of statistics are useful in order to find weaknesses in systems. You can find various flawed systems, and see if the workbench would be able to find these weaknesses. There is a book in the library, I think it was Cryptography; theory and practice, which provides some detailed examples of cryptanalysis of a simplified DES.
There are a number of psuedo-random number generators as well as an enormous number of randomness tests. There are no very good or user-friendly tools that allow extensive testing of random number generators. Some "FORTRAN vintage" programs are available, while others are not very intuitive to use or understand. Many times one would like to mix different generators and test the results.
As a side benefit of the above tool, you automatically create a randomness testing workbench. One of the things needed for crypto-testing is to have many of the usual tests of randomness. Many different suites of tests are available in the public domain, and can be used to test the randomness of bits being output at different points. Similarly random number generators of various kinds are needed as inputs to the above.
I envision a graphical tool with icons for generators, and icons for tests. Each generator has a dll, and each test has a dll. This allows easy addition of more generators and tests. All generators have a similar interface:
struct info getinfo(); // a function to return the name of RNG and the type and size of its seed and other parameters.
void setseed(void *seed); // sets the seed of the RNG
void setparams(void *param); // sets the parameters of the RNG
int rand(); // generates 32 bit random signed integer
int * rand(int n); // generates an array of n 32bit signed integers, needed to avoid overhead of calling dll routines.
All tests have a similar interface as well, so initially the program should check its directory to find all the dlls. Then an icon for each dll found should be created. Finally you should have a graphical tool allowing single or multiple tests to be applied to single, multiple or combination generators.
If we further add icons for operators, like "XOR", "MULTIPLY", etc. then we essentially end up with the Cryptanalysis Workbench mentioned above.
References: As part of the Cryptographic Toolkit the NIST has developed a number of Statistical Tests for Randomness that can be downloaded along with a detailed documentation. There are many others test suites, including my own DIEHARD. Web searches will find you many others. A general collection of everything statistical can be found at StatLib Index. Not that it is needed here, but a general collection of everything mathematical can similarly be found at Netlib archive.
Originally home computers were mainly used as word processors. Then came spreadsheets, using a simple two dimensional (now three dimensional) array, a concept that was simple enough for most home users to master.
While the most fundamental data type for computer programmers is a graph, and none of the above tools can handle it. I believe that if a tool is provided that makes the making, editing and using of graphs easy, it would become one of the fundamental tools that no one would be willing to do without. There are so many times when I have had to do some simple problem, and wanted that such a tool existed, that I am sure others must be in the same situation many times.
Example 1: A family tree
A family tree is a natural candidate for a tree. An individual is a node, and in that node we can have a number of properties, eg: full name, other names, phone, address, work phone, profession, date of birth, etc. Different from usual graphs, we will think of a node not as a point, but rather as a shape which has different hooks on which edges can be attached. For each hook, we want to be able to specify if it can take incoming edges, outgoing edges or both, as well as if it can take one, two or many edges. In a family tree, for example, there would be hook for father and mother, a hook for spouse(s), a hook for children and a hook for siblings. Even though they are redundant, the parent edges and sibling edges to make navigation easier. We can think of each hook as just another property of the node, which suggests that values of properties can be numeric, string, pointer to node, or a list of pointers to nodes.
Example 2: The AES crypto-system
As you can see, each "6-Round box" is itself really another graph. It will be necessary to allow this kind of encapsulation if we are to be able to see an overview of very large graphs that may result.
The same issue as in the family tree arises here as well. Each node is some kind of an operator with one or more inputs and usually only one output (but possibly more). For example a subtract node would have two inputs and one output, but the two inputs are not symmetric, because a-b is not the same as b-a.
Example 3: Digital Logic Design
IC's have particular pins that are wired with others etc. Once again each IC is a node, containing many hooks.
With these examples in mind, how do we make a system that can be of use here. Minimally, one would want to be able to
It would be important for the program to be modular so that additional layout features could be added at a later stage. Once the basics are done, it would be nice to have some simple search features, eg, create a sub-graph of all nodes that have a particular property, etc. Adding graph algorithms like shortest path would help find the relation between two individuals on a family tree.
Finally what would really be nice is if each edge and each vertex were to become active, i.e. it could send messages, change values of itself or its neighbors or the vertex. This could then be used to simulate networks, traffic flow, as well as to build P-Spice like programs, demonstrate distributed algorithms, etc. There seems to be a lot of potential, but this last part would not be as easy.
References: To find stuff for ordinary graphs, Algorithm Software on the Web, or Java-Channel - Query results are starting point. Another standard but commercial program is LiDIA (Dr. Sarmad has it). But the stuff about hooks that I mention here is more like programs that do chip and board layouts. I have not used them, but P-Spice or similar programs have something like this.
I was very curious to see some very interesting technology on mobile phones that allow e-mail messages to be typed on them. Typing on a phone with only ten buttons can be very cumbersome, with each digit having three or four letters on them. The usual phone is marked with:
2=ABC 3=DEF 4=GHI 5=JKL 6=MNO 7=PQRS 8=TUV 9=WXYZ
But some instruments allow typing as you would, and then use a dictionary to disambiguate. For example, to say HELLO you would simply type 43556 and the computer would then figure out that the possible words with this combination are GDJJM, GELJO, IFLLN, HELLO, etc... These would be ranked in order of likelihood, so we need a dictionary with some kind of frequency count to do this. The phone shows the best selection as you type, and if you are done, but not satisfied with the suggestion, you can scroll through the rest of the selections, in order of rank, or you can explicitly specify what you want typed.
What I was curious about was given a dictionary with a frequency count table, and a fixed number of keys, what would be the optimal mapping of letters to keys? What would be the number of times that a user would have to disambiguate entries?
Special purpose one-handed keyboards have been designed for people who have had injuries and are unable to use both hands. Because there is only one hand, the number of keys that are within easy reach are much less, so they have to use complicated methods. One way that they use is chording, ie. multiple keys pressed at the same time represent different letters. Could a reduced key keyboard do this job better? The best typing speeds achievable with one-hand methods is still a lot less than two-handed typing.
Another serious application would be that with miniaturization, palm PC's are getting very common. Their biggest drawback is the lack of a fast input device. A keyboard needs a person to be seated at a table. An input device that can be used while traveling in a bus, or walking would be immensely useful. Something simple, which could be gripped in one hand, with buttons accessible at the fingertips could be used. This would have to have only a few buttons, and so might benefit from the same technology.
Of course one limitation of all this is that this applies to only text. When we are using many nonsense words, or writing computer programs, this method of input may not be so good.
References: You should be able to search for handicapped one-handed keyboards. One such site to start from is Alternative Keyboards - Typing Injury FAQ. There are also word-lists on the internet, some with frequency tables attached.