FINDING ABSTRACTION
Often, finding a good abstraction can be quite difficult because we are forced to confront the fundamental limitations on the tasks computers can perform and the speed with which computers can perform those tasks.
Computer Science - The Mechanization of Abstraction
The book Foundations of Computer Science by Al Aho and Jeff Ullman is available for free download online. This book provided a clear explanation of solving real world problems by applying Computer Science knowledge.
It filled a beginner’s gap in my knowledge. We have worked with graph in high school, we think of plotting a graph using the x and y axis in a graph paper. But in Computer Science graph means something different. It represents nodes and edges. Here is my notes from the book that resulted in my Aha moment.
Useful Notes from the Book
Science of Abstraction
Computer science is a science of abstraction - creating the right model for thinking about a problem and devising the appropriate mechanizable techniques to solve it.
Computer scientists create abstractions of real-world problems that can be understood by computer users and, at the same time, that can be represented and manipulated inside a computer.
Scheduling Exam Problem
For example, consider the problem of scheduling final examinations for courses. We must assign course exams to time slots so that two courses may have their exams scheduled at the same time slot only if there is no student taking both. How do we model this problem?
One approach is to draw a circle called a node for each course and draw a line called an edge connecting two nodes if the corresponding courses have a student in common. The figure suggests a possible picture of five courses. The picture is called a course-conflict graph.
Given the course-conflict graph, we can solve the exam-scheduling problem by repeatedly finding and removing “maximal independent sets” from the graph. You can read the first chapter of Foundations of Computer Science by Al Aho and Jeff Ullman on how this problem can be solved with graph.
Abstraction
The term abstraction is used to imply simplification, the replacement of a complex and detailed real-world situation by an understandable model within which we can solve a problem. That is, we abstract away the details whose effect on the solution to a problem is minimal or nonexistent, thereby creating a model that lets us deal with the essence of the problem.
Problem Solving Tools
There are three important problem solving tools:
Data models, the abstractions used to describe problems. We have seen a graph to model the course conflict problem.
Data structures, the programming language constructs used to represent data models. For example, C provides built-in abstractions, such as structures and pointers, that allow us to construct data structures to represent complex abstractions such as graphs.
Algorithms, the techniques used to obtain solutions by manipulating data as represented by the abstractions of a data model, by data structures or by other means.
Data Models
We meet data models in two contexts. In the context of the problem domain, data models such as the graphs are abstractions used to formulate solutions to problems. In the context of programming languages and computers, for example, C has a data model that includes abstractions such as characters, integers and floating-point numbers. The C data model also includes types such as structures, pointers and functions.
Data Structures
When the data model of the language in which we are writing a program lacks a built-in representation for the data model of the problem at hand, we must represent the needed data model using the abstractions supported by the language. For this purpose, we study data structures, which are methods for representing in the data model of a programming language abstractions that are not explicit part of that language.
Different programming languages may have strikingly different data models. For example, unlike C, the language Lisp supports trees directly, and the language Prolog has logic built into its data model.
Algorithms
An algorithm is a precise specification of a sequence of steps that can be carried out mechanically.
There are sorting and searching algorithms that efficiently solves sorting and searching problems. There are many other tricks for solving common problems. These are the tools a computer scientist uses when designing programs.
We need to know the best ways to perform common tasks and we need to learn the principal techniques for designing good algorithms.
Conclusion
The book Foundations of Computer Science by Al Aho and Jeff Ullman is a good read. The algorithms textbooks use mathematical notation to describe the algorithms. This approach is not accessible to some developers. Once you realize you can create a model of the problem, you are better equipped with solving it and coming up with a solution that can be implemented by using computers.
Richard Feynman Explanation
Let’s think about a car assembly line. Each car that comes out of this assembly line is a product of a well-structured process where humans and machines work together to assemble thousands of parts. Each car that rolls off the line is a complex machine, but we don’t have to understand the intricate details of every single component to drive one. That’s an abstraction. We only need to know about the steering, brakes, gas pedal, and a few other controls to operate it.
Now, in the world of Computer Science, we do something similar. Instead of physical cars, we’re creating programs and software, but the idea of an assembly line still applies. At the heart of it, we’re turning human ideas into a form that a machine, a computer, can work with. That’s the “mechanization” part.
The “abstraction” part comes in when we design these programs. We create layers upon layers of abstraction to manage the complexity. For example, when you’re writing a program, you don’t need to worry about how the computer is storing your variables in its memory or how it’s performing each mathematical operation. Those details are abstracted away. You just tell the computer what you want it to do in a high-level language, and it takes care of the details.
So, when we say “the mechanization of abstraction” in Computer Science, what we’re talking about is this idea of turning high-level ideas into something a machine can understand and process, all while keeping the nitty-gritty details hidden away. Just like you don’t need to be a mechanic to drive a car, you don’t need to understand every tiny detail of a computer’s operation to write a program. And that’s the real beauty of it!
Key Takeaways
One of the key concepts highlighted in the book is the science of abstraction. Computer science is characterized as a science of abstraction, meaning it involves creating suitable models to understand a problem and devise mechanizable techniques to solve it. The models built by computer scientists are meant to represent real-world problems in a way that is comprehensible to computer users, while also being manipulatable within a computer.
A practical example given in the book is the scheduling exam problem. The issue is to schedule final exams for courses in a way that no two courses with a common student are assigned the same time slot. This problem is represented as a course-conflict graph where each node (or circle) represents a course and an edge (or line) connects two nodes if the corresponding courses share a student. The problem can then be solved by repetitively identifying and eliminating “maximal independent sets” from the graph.
The term abstraction refers to the simplification process, wherein a complex real-world situation is replaced by an understandable model to solve a problem. This involves abstracting away insignificant details to focus on the essence of the problem.
The book also introduces three important problem-solving tools:
Data models: These are abstractions used to describe problems. The course conflict graph mentioned earlier is an example of a data model.
Data structures: These are constructs used in programming languages to represent data models. C, for instance, provides built-in abstractions like structures and pointers to construct data structures that represent complex abstractions such as graphs.
Algorithms: These are techniques used to solve problems by manipulating data represented by data models, data structures, or other means.
The author further discusses data models in the context of problem domains and programming languages. For instance, C includes abstractions such as characters, integers, and floating-point numbers in its data model.
Data structures are required when the data model of a language doesn’t have a built-in representation for the data model of the problem at hand. We need to represent the needed data model using the abstractions supported by the language.
Finally, an algorithm is a precise sequence of steps that can be executed mechanically. Knowing the best ways to perform common tasks and the main techniques for designing good algorithms is crucial for a computer scientist.
Foundations of Computer Science is approachable and practical way of presenting computer science concepts and problem-solving techniques. They argue that once you realize you can create a model of the problem, you are better equipped to solve it and devise a computer-implementable solution.