December 5th, 2010
As I get ready to teach another session of CS 6212 (Design and Analysis of Algorithms – Graduate – earlier used to be known as CS 212) at GWU, question arises one more time – why do we study algorithms at all?
Here are some problems that arise all the time, and hopefully you can see an analogy between these problems and similar ones you have seen elsewhere.
- You have an address book consisting of 5 million records. Let us assume structure is very simple – first name, last name, phone number and company name. You can search on any of these fields, and can search partially using “begins with” syntax. For example, you can search for – first name is like “Ron…”. Another search can be – phone number like “202…”. You want the search to be super super fast, and cannot afford to make any database calls. (Btw, the telephone number is a string, not a number, right?) To test the effectiveness of your program, I will give it about 200 searches (some on first name, some on last name, some on telephone number, some on company name), and take the average response time.
- You have a network topology (setup of nodes and interconnecting edges), and would like to know if deletion of a single node is going to leave the topology disconnected.
- Looking for a text pattern in a big file. Say you have a text file that is about 10 M. You can be looking for a text “designed to efficiently support unlimited number of subscribers” or text “flexible error correction results in more efficient use of spectrum”, or something else. How can we make this search super efficient?
- Your customers are scattered across 100 cities, and you know demand from each of the 100 cities and distances between cities. You would like to open 3 warehouses (distribution centers). Where do you locate the warehouses?
- There is a competition for the best “Go” program. The first prize is $5000. You need the money.
- You are designing your company’s marketing strategy, as defined here.
If you already know the algorithms and the techniques for these problems that is a very good start. Otherwise, you should consider taking some formal classes in a school convenient to you. Or, continue your informal learning in the school of life. I will be posting some more hints and pointers in the comments section later.
[If you would like to follow the CS6212 related tweets, you can follow using twitter hashtag #cs6212gwu]