Algorithm of your Choice

1. Find an algorithm you think is interesting. You may look for your algorithm on the Internet, in a book, journal article, conference proceedings, etc. The algorithm should be something you haven't seen in this class or in Data Structures. Send me ( djimenez@ringer.cs.utsa.edu) an e-mail message with a brief description of the algorithm and where you found it. I'll respond, letting you know whether your choice is OK. If it isn't, I'll give you suggestions on how you might improve your topic or find another one. I'd really like to see you pick an algorithm related to your particular computer science interests, if possible. This e-mail assignment is due Tuesday, April 7, 1998 by midnight.
2. Submit an article to our class newsgroup, utsa.cs.3343.d , describing your algorithm. Depending on the algorithm, you may wish to emphasize the methods used, implementation details, analysis, applications or any combination of these. Your report may be as long as you wish, but should be at least two screenfulls on a VT100 terminal single-spaced, or about 50 lines. You may include pseudocode for the algorithm, but don't include the length of the pseudocode in the 50 lines; I really want to see what you have to say about the algorithm. Make the first few lines of your report an abstract, giving the basic idea of what you are writing. At the end of your report, give a bibliography citing your sources (you should have at least one). If the reference is a web site, give the URL, name of the page, and name of the author. This newsgroup assignment is due Tuesday, April 14, 1998 by midnight.
3. Read everyone elses' reports from the newsgroup. You will see some of the facts from these reports as True/False questions on the final exam. You don't need to remember all the details, but you should be familiar with the main ideas. Here are some ideas to get you started:
   • Graphics algorithms. For example, finding the convex hull of a set of points, shading algorithms, algorithms traversing weird representations of polygons, etc.
   • Genetic algorithms. These algorithms try to find optimal solutions to problems by imitating evolution.
   • Searching algorithms. For example, exhaustive search of a space using minimax, searching with pruning, depth or breadth first search that use domain knowledge to speed up the search, extensions to B-trees or other searching data structures, etc.
   • Math algorithms. For example, algorithms to speed up matrix operations, algorithms for symbolically manipulating mathematical expressions, the latest integer factorization algorithms, algorithms for generating pseudorandom numbers, etc. (some of this might overlap stuff we do in class; I'll let you know...)
   • Algorithms for systems (as opposed to appplications). For example, process scheduling in a multitasking operating system, register allocation for compilers, paging algorithms for virtual memory systems, memory allocation (e.g. malloc()) algorithms, etc.
   • Approximation algorithms for solving "hard" problems, i.e., situations where solving a problem exactly is impracticle, but a solution that is "pretty good" or "almost right" will do. For example, the travelling salesman problem.
   • Exact algorithms for solving "hard" problems, i.e., algorithms that do better than "brute force" but still take a long time to finish. For example, the travelling salesman again: it can be solved in n! time, but there is another algorithm that can do it in n2ⁿ; still pretty bad, but better than factorial time.
   • Algorithms that run on impossible or weird hardware. For example, algorithms running on quantum computers, nondeterministic machines, DNA computers, optical computers, oracle machines.
   • Algorithms to do signal processing, e.g., image processing, sound (music) processing, compression of signals.
   • Randomized algorithms. These are algorithms that use a source of random (or pseudorandom) numbers and can often have better running times than traditional algorithms for the same problems. For example, numerical integration in two or more variables is difficult or impossible without a randomized "Monte-Carlo" algorithm.
   Good places to look for information about algorithms are:
   • The AltaVista search engine. Type in words related to your algorithm (e.g. minimal spanning tree) and get links to lots of web pages with information.
   • The DejaNews newsgroup archive. Search for keywords related to your algorithm and see every Usenet article that has been written on the subject since about 1995 (you'll have to choose the "old" database for best results).
   • NCSTRL at Cornell. This is a goldmine of computer science technical reports you can search and download from universities all over the world. Some of the articles are only available as optically recognized text (i.e., bad quality) or PostScript level 2 images (i.e., enormous files), but many are available as normal PostScript files you can print or view from the Suns with pageview.
   • The UTSA Libraries. You can click on it, but it's more productive to just go over to the JPL and start looking through computer science journals. Any journal with IEEE or ACM in its title is likely to have something that can give you ideas. Check out the QA76 section in the stacks, too, for computer science books. (Southwest Texas State University and UT Austin have very good CS collections in their libraries if you want to take a trip.)