Top 4 classic Computer Science problems & how we should change
A math teacher walks into a classroom and says, “Today, we are going to start learning a new chapter, called Matrix.” The teacher proceeds with boring definitions and related concepts about matrices, such as rows, columns and element indices.
Suddenly, a curious student chips in and asks, “Teacher, why do we need to learn about matrices?” The teacher replies with somewhat a politically correct answer, “It is in the syllabus, so you need to study.”
The above mentioned scenario is what I experienced while studying in secondary school. Passion for subjects like math emanate from the ability to relate formal concepts to applications in the real world.
Despite failing to get a proper answer from my math teacher, my deep rooted passion for math since primary school and my new found love for computer programming in secondary school made me pursue computer science during my tertiary education.
It was during my tertiary education when I could find a proper answer to a question, which I asked to my secondary school math teacher. In computer programming, a concept called array is used to organize collections of data or variables.
A one dimensional array is called a vector and a two dimensional array is called a matrix. Whether one should use a vector or matrix depends entirely on the problem in hand. Simply put, a matrix could store data in a table like format using rows and columns, while a vector stores data only as a row vector or column vector.
The question continued to linger at the back of my mind…
My tryst with a mathematical concept called matrix began with an unanswered question. The question continued to linger at the back of my mind throughout my journey from secondary to tertiary education. Thank God, I could realise the beauty of not just matrices, but also many other mathematical concept while furthering my computer science education.
Normally, school students often dislike math, simply because they are unable to relate the concepts to real world applications. Teachers who shut students up with clichéd replies are the main culprits who cause students to hate subjects like math.
The way forward for school level education is to help students appreciate the beauty of subjects like math by relating formal concepts to real world applications, apart from the tradition of mindlessly going after good grades.
My conviction as a computer science practitioner is that significant contributions in the CS field emanate from the ability to successfully map or translate formal CS concepts into real world applications and vice versa. Computer scientists, especially academic researchers are often involved in solving classic Computer Science problems.
These problems are known as classic because the problems have been existing for decades, but research related to these problems have continued to formulate the classical version of the problem into newer versions with extended perspectives.
The table below shows a list of classic Computer Science problems, description of concepts related to the problem and the real world application of why each problem is relevant to laymen.
Relate the boring computer sciences problem to real world application to demonstrate the topic relevance:
| PROBLEM | DESCRIPTION | REAL WORLD APPLICATION |
|---|---|---|
| Travelling Salesman Problem (TSP) | Given a sequence of cities with pairwise distances between cities, the task is to find the optimal path to travel to all cities, so that the travel begins and ends at the same city. Optimality of path originally used to be distance, but researchers have extended this criterion to include time and cost of travel. | Anybody who wishes to travel to several places on the same day can use travel planning software powered by TSP algorithms to plan their routes.
Nowadays, short distance in kilometres may not necessarily mean short periods of travel time. Plus, we also have toll costs to worry about. TSP algorithms help laymen to identify the optimal travel route by taking into consideration of multiple criteria such as distance, time and cost. |
| Knapsack Problem | Given a knapsack with a certain capacity and a set of items denoted by their value and weight, the task is to find the optimal set of items that can be put into the knapsack.
Optimal set here refers to the set of items with the highest value combination, without overloading the knapsack capacity. |
Textbooks describe this problem using an example of a burglar who needs to decide which set of costly items can be put into his knapsack.
Another common application of this algorithm helps to determine the set of items to be included in checked baggage without overloading the allowed capacity. |
| Bin Packing Problem | Given a set of items and empty bins with a specific capacity, the task is to arrange all items into the given bins, so that the least number of bins are used. | The most apparent application of this algorithm is in logistics business. Items to be delivered come in various sizes, but logistics service providers often have a limited number of containers or bins.
Determining the optimal arrangement of items is crucial to ensure that no additional bins are used unnecessarily during a delivery. This helps to keep more spare bins available for other deliveries. |
| 8 Queens Problem | Given an 8 x 8 chessboard with 8 pieces of queen, the task is to find the optimal arrangement of queens in such a way that they do not check each other.
This problem has been extended by researchers as the N queens problem on an NXN chessboard. |
The key point in this problem is to avoid conflicts. So, applications of this algorithm belong to tasks such as VLSI chip design and deadlock prevention.
A VLSI chip contains thousands of components and all these components should be arranged so that their positions do not overlap or conflict with each other. Deadlock prevention is an algorithm which monitors the allocation of shared resources to multiple processes running on a computer. Shared resources should be provided to processes so that the resource is available to each process when it is needed. Without deadlock prevention, deadlock would occur when a resource becomes unavailable to a process when it is critically needed. |
This blog post is meant to provide a bird’s eye view to classical Computer Science problems and how formal concepts related to those problems can be applied for real world applications.
Exposing school students to CS concepts and applications is indeed one good way to make students appreciate the beauty of subjects like math. Infusing such best practices as part of T&L in school would incite students to learn math passionately, without merely going after good grades.
Are you interested to learn more about from VeecoTech? Check out these awesome articles:
About the Author
Meet VeecoTech Team sharing cutting-edge insights on web design, ecommerce, SEO, and mobile apps. We’re passionate about empowering businesses with digital success. Join us on this exciting journey towards online excellence.
Leave A Comment