By Dr. Carol Browning
Professor of computer science and mathematics
As a faculty member, one thing I enjoy is helping students choose careers, select majors and schedule their courses. It can take creativity to schedule all of the courses that students need, taking into account study abroad, team practices and internships. Each semester, I am reminded of how much better people are than computers at many difficult problem-solving tasks.
It is a common misconception that if today’s computers get fast enough, we’ll be able to use them to solve any problem. In fact, many problems are so hard that even very fast computers would take too long to find the answer. Let’s look at two kinds of difficult problems: scheduling problems and factoring problems.
Why are scheduling problems so complex? Suppose a sales representative needs to schedule visits to several cities. In what order should the visits be conducted to minimize travel costs? If there are ten cities, there are over three million ways of ordering the cities. A computer program can quickly figure out the cost for each of these routes and find the route with the smallest cost. However, if there are 20 cities, there are over 2,000,000,000,000,000,000 possible routes. Even a very fast computer cannot get the answer in a reasonable amount of time. If there are many more cities, it would take a fast computer centuries to find the best route.
Computer science is the study of algorithms, or lists of instructions for computers to perform in order to find an answer to a problem. In our Drury computer science classes, we teach a variety of techniques for getting “good” schedules when it isn’t possible to get “the best” schedule. Many of the techniques we study can be applied to scheduling problems from different domains. I began my research in scheduling when I worked for NASA developing software to help scientists create schedules for spacecraft. Some computer scientists study how to schedule baseball games for a league to minimize travel costs and meet a variety of other constraints. Similar methods can be used to find good schedules for widely varying domains, including travel routes, spacecraft activities and baseball games.
Another type of difficult problem is factoring large numbers. If the number is large enough, it takes a computer too long to try all the possible factors. As it turns out, this is a good thing! The security of information sent over the Internet today relies heavily on the bad guys being unable to factor large numbers. Last year, one of our Drury computer science seniors, Matt Duncan, conducted prize-winning research on this problem. If quantum computing becomes a reality, it may be possible to factor large numbers in a reasonable amount of time. In that case, we will need to find an entirely different way of securing information in our digital society.
If a new paradigm for computing ever does come to exist, perhaps a computer could be programmed to create a perfect schedule for a student. But for now, I take pleasure in helping each of my students craft great course schedules.