Applied Computational Thinking with Python

By Sofía De Jesús , Dayrene Martinez
    Advance your knowledge in tech with a Packt subscription

  • Instant online access to over 7,500+ books and videos
  • Constantly updated with 100+ new titles each month
  • Breadth and depth in over 1,000+ technologies
  1. Chapter 1: Fundamentals of Computer Science

About this book

Computational thinking helps you to develop logical processing and algorithmic thinking while solving real-world problems across a wide range of domains. It's an essential skill that you should possess to keep ahead of the curve in this modern era of information technology. Developers can apply their knowledge of computational thinking to solve problems in multiple areas, including economics, mathematics, and artificial intelligence.

This book begins by helping you get to grips with decomposition, pattern recognition, pattern generalization and abstraction, and algorithm design, along with teaching you how to apply these elements practically while designing solutions for challenging problems. You’ll then learn about various techniques involved in problem analysis, logical reasoning, algorithm design, clusters and classification, data analysis, and modeling, and understand how computational thinking elements can be used together with these aspects to design solutions. Toward the end, you will discover how to identify pitfalls in the solution design process and how to choose the right functionalities to create the best possible algorithmic solutions.

By the end of this algorithm book, you will have gained the confidence to successfully apply computational thinking techniques to software development.

Publication date:
November 2020
Publisher
Packt
Pages
420
ISBN
9781839219436

 

Chapter 1: Fundamentals of Computer Science

The world of computer science is a broad and complex one. Not only is it constantly changing and evolving, but the components we consider part of computer science are also adapting and adjusting. The computational thinking process allows us to tackle any problem presented with purpose and focus. No matter what the problem is, we can break it down, find patterns that will help us find solutions, generalize our solutions, and design algorithms that can help us provide solutions to the problems.

Throughout this book, we will be looking at the computational thinking process carefully, tackling problems in multiple areas and using the Python programming language and associated libraries and packages to create algorithms that help us solve these problems. Before moving into the problems, however, we will explore some of the important computer science concepts that will help us navigate the rest of the book.

In this chapter, we will explore the following topics:

  • Introduction to computer science
  • Theoretical computer science
  • Systems software
  • Computing
  • Data types and structures
 

Technical requirements

You will need the latest version of Python to run the codes in this chapter. You will find the full source code used in this chapter here: https://github.com/PacktPublishing/Applied-Computational-Thinking-with-Python/tree/master/Chapter01

 

Introduction to computer science

When looking for a definition of computer science, you will encounter multiple variations, but all state that computer science encompasses all aspects of computers and computing concepts, including hardware and software. In computer science, hardware design is learned in courses offered in engineering or computer engineering, for the most part. The software side of computer science includes operating systems and applications, among other programming areas. For the purposes of this book, we will be concentrating on the software side of computer science.

In this chapter, we'll look at some of the basic definitions, theories, and systems that are important as we delve deeper into the computational thinking world. Once we have identified key areas and defined the concepts, we will be ready to move on to the applications and real-world challenges we face in an ever-changing tech world while also exploring the elements of computational thinking and the Python programming capabilities that can help us tackle these challenges.

The wide range of topics available in computer science can be both daunting and exciting and it is ever evolving. Some of these topics include game design, operating systems, applications for mobile or desktop devices, the programming of robots, and much more. Constant and consistent breakthroughs in computers and computing provide new and exciting opportunities, much of which are unknown to us. Having a basic understanding of the systems behind computer science can help us interact with technology and tackle problems more efficiently.

Learning about computers and the binary system

All computers store information as binary data. The binary system reads all information as a switch, which can be on or off, 0 or 1. The binary system is a base-2 system. You'll need a basic understanding of binary numbers and the binary system to progress in computer science.

The binary system translates all data so that it can be stored as strings using only two numbers: 0 and 1. Data is stored in computers using bits. A bit (which stands for binary digit) is the smallest unit of data you can find in a computer, that is, a 0 or a 1.

When counting in the binary system, the first two numbers are 0 (or 00) and 1 (or 01), much like in the base-10 number system we use in everyday life. If we were to continue counting in binary, our next number would be 10. Let's compare the first three numbers in the base-10 system and the binary system before we learn how to convert from one to the other:

Figure 1.1 – Base-10 and binary comparison

Figure 1.1 – Base-10 and binary comparison

The next number in the base-10 system would be 3. In the binary system, the next number would be 11, which is read as one one. The first 10 numbers in the base-10 and binary systems are shown as follows:

Figure 1.2 – Base-10 and binary comparison (cont'd)

Figure 1.2 – Base-10 and binary comparison (cont'd)

As mentioned, the binary system is a base-2 system. This means that each digit of the base-10 system is paired with a power of 2, so we use those powers to convert between numbers. Understanding how to convert from base-2 to base-10 and vice versa can help us have a better understanding of the relationship between numbers in the different systems.

Converting from binary to base-10

We will start with an example to convert from a binary number to a base-10 number. Take the number 101101. To convert the number, each digit is multiplied by the corresponding base-2 power. The binary number given has 6 digits, so the powers of 2 we will use are 5, 4, 3, 2, 1, and 0. This means the number is converted as follows:

The binary number 101101 is equivalent to 45 in the base-10 system. In everyday life, we write numbers in base-10, so we understand the number 45 as written. However, our computers convert this information into binary to be able to process it, so the number becomes the binary number 101101 so that it can be easily read by the computer.

Converting from base-10 to binary

Again, let's start with an example to demonstrate the process of converting from a base-10 number to a binary number. Take the number 591. To convert the base-10 number to binary, we have to divide the number by 2 iteratively. If the result has no remainder, we insert a 0 (if it is the first number) or insert a 0 to the left of the existing numbers.

If the result has a remainder of 1, we insert a 1 (if it is the first number) or insert a 1 to the left of the existing numbers.

When we divide 591 by 2, the result is 295 with a remainder of 1. That means our right-most number, which is our first number, is 1.

Now divide 295 by 2. The result is 147 with a remainder of 1. So, we insert a 1 to the left of the 1. Our number is now 11.

Now divide 147 by 2. The result is 73 with a remainder of 1. Our result is now 111. Now we'll carry out further divisions:

  • with a remainder of 1. Our number is now 1111.
  • with no remainder. Our number is now 01111.
  • with no remainder. Our number is now 001111.
  • with a remainder of 1. Our number is now 1001111.
  • with no remainder. Our number is now 01001111.
  • with no remainder. Our number is now 001001111.
  • with a remainder of 1. Our number is now 1001001111.

The number 591 in base-10 is equivalent to the number 1001001111 in the binary system.

Another way to convert the number is to use a table for the divisions:

Table 1.1 – Conversion of the base-10 number 591 to binary

Table 1.1 – Conversion of the base-10 number 591 to binary

Using the table, take the numbers from the right-most column and write them starting with the last row from bottom to top. The result is 1001001111.

Learning how to convert numbers is only a small piece of converting data to binary, but it is an important piece. All information, including letters and symbols, must be converted to binary in order to be read by a computer. ASCII (which stands for American Standard Code for Information Exchange) is a protocol that has been adopted universally to convert information. That said, some of the protocol is obsolete, so other protocols use ASCII as a base to expand on its capabilities. Unicode is a widely used 16-bit character set that is based on ASCII.

As discussed, in this section, we learned that information must be encoded or converted in order for a computer to read it. Multiple systems and protocols exist, but for now, we will move on to computer science theory. However, revisiting binary, ASCII, and Unicode as you work through problems can be helpful.

 

Understanding theoretical computer science

While you don't need to be a master mathematician to love computer science, these two subjects are intrinsically tied. Computer science, particularly programming, uses algorithms, which are algebraic in nature. We will explore algorithms in depth later on, but again, the important point here is that they are mathematical. The logical processes stem from the philosophical nature and history of mathematics. Now, if mathematical topics are not to your liking, don't despair. The logical processes needed to become a programmer and developer can be used without having to learn higher mathematics. Knowing higher mathematics just simplifies some concepts for those who have that background.

Theoretical computer science includes multiple theories and topics. Some of the topics and theories are listed as follows, but keep in mind that other topics are also included in theoretical computer science that may not be discussed in this book. A short description and explanation for each of the theories or terms listed as follows are included for your review:

  • Algorithms
  • Coding theory
  • Computational biology
  • Data structures
  • Cryptography
  • Information theory
  • Machine learning
  • Automata theory
  • Formal language theory
  • Symbolic computation
  • Computational geometry
  • Computational number theory

We will look at the aforementioned theories in the following sections.

Algorithms

An algorithm is a set of instructions that a computer can read. Algorithms provide the rules or instructions in a way that means a computer can logically process the information provided as input and create an output. In most books, you are introduced to the algorithm and programming by creating the Hello World! program. I won't make this book the exception.

In Python, the code would require that we print the message to the screen. Because the Python language is easy to learn and to read, many, if not most, of the code strives to be logical. So, in order to print a message to the screen, we use the print() command. Here is the code we'd use:

print("Hello world!")

Similarly, we could use the code given as follows:

print('Hello world!')

Python reads both " and ' as the same thing when it comes to strings.

The result of the preceding code looks like the following screenshot when we run the algorithm:

Figure 1.3 – The 'Hello World!' Python program

Figure 1.3 – The 'Hello World!' Python program

Don't worry, we'll discuss the Python programming language later on in Chapter 2, Elements of Computational Thinking, and more in depth in Part 2, Applying Python and Computational Thinking, starting in Chapter 8, Introduction to Python, as well.

While lengthy, the discussion on algorithms is critically important to this book and to your progression with Python. Consequently, we will be covering this in-depth exploration of algorithms in Chapter 2, Elements of Computational Thinking, and Chapter 3, Understanding Algorithms and Algorithmic Thinking, of this book, as algorithms are a key element of the computational thinking process.

Important Note:

Chapter 2, Elements of Computational Thinking, will focus on the computational thinking process itself, which has four elements: decomposition, pattern recognition, pattern generalization and abstraction, and algorithm design. As you can see, that last element is algorithm design, so we will need to get more acquainted with what an algorithm is and how we can create them so that you can then implement and design algorithms when solving problems with Python. Chapter 3, Understanding Algorithms and Algorithmic Thinking, will focus on a deeper understanding of algorithm definition as well as an introduction to the design process.

We'll look at coding theory next.

Coding theory

Coding theory is also sometimes known as algebraic coding theory. When working with code and coding theory, there are three areas that are studied: data compression, error correction, and cryptography. We will cover these in more detail in the following sections.

Data compression

The importance of data compression cannot be understated. Data compression allows us to store the maximum amount of information while taking up the least amount of space. In other words, data compression uses the fewest number of bits to store the data.

Important Note:

Remember that a bit is the smallest unit of data you can find in a computer, that is, a 0 or a 1, while a group of bits is called a byte. One byte usually has 8 bits. We use bytes as a unit of measurement for the size of the memory of a computer, storage device, such as a memory card or external drive, and more.

As our technology and storage capacities have grown and improved, our ability to store additional data has as well. Historically, computers had kilobytes or megabytes of storage when first introduced into households, but they currently have gigabytes and terabytes worth of storage. The conversions for each of the storage units are shown as follows:

Figure 1.4 – Byte conversions

Figure 1.4 – Byte conversions

If you look for information online, you may find that some sources state that there are 1,024 gigabytes in a terabyte. That is a binary conversion. In the decimal system, or base-10 system, there are 1,000 gigabytes per terabyte. To understand conversion better, it is important to understand the prefixes that apply to the base-10 system and the prefixes that apply to the binary system:

Table 1.2 – Base-10 and binary prefixes with values

Table 1.2 – Base-10 and binary prefixes with values

As mentioned, the goal is always to use the least amount of bits for the largest amount of data possible. Therefore, we compress, or reduce, the size of data in order to use less storage.

So, why is data compression so important? Let's go back in time to 2000. Back then, a laptop computer on sale for about $1,000 had about 64 MB of RAM (Random Access Memory) and 6 GB of hard drive memory. A photograph on our digital phones takes anywhere from 2 to 5 megabytes of memory when we use its actual size. That means our computers couldn't store many (and in some cases any) of the modern pictures we take now. Data compression advances allow us to store more memory, create better games and applications, and much more, as we can have better graphics and additional information or code without having to worry as much about the amount of memory they use.

Error correction

In computer science, errors are a fact of life. We make mistakes in our processes, our algorithms, our designs, and everything in between. Error correction, also known as error handling, is the process a computer goes through to automatically correct an error or multiple errors, which happens when digital data is incorrectly transmitted.

An Error Correction Code (ECC) can help us analyze data transmissions. ECC locates and corrects transmission errors. In computers, ECC is built into a storage space that can identify common internal data corruption problems. For example, ECC can help read broken codes, such as a missing piece of a QR (Quick Response) code. A type of ECC is a hamming code. A hamming code is a binary linear code that can detect up to two-bit errors.

Important Note:

Hamming codes are named after Richard Wesley Hamming, who discovered them in 1950. Hamming was a mathematician who worked with coding as related to telecommunications and computer engineering.

Another type of ECC is a parity bit. A parity bit checks the status of data and determines whether any data has been lost or overwritten. Error correction is important for all software developed, as any updates, changes, or upgrades can lead to corruption of the entire program or parts of the program or software.

Cryptography

Cryptography is used in computer science to hide code. In cryptography, information or data is written so that it is unreadable by anyone other than the intended recipient of the message. In simple terms, cryptography takes readable text or information and converts it into unreadable text or information.

When we think about cryptography now, we tend to think of encryption of data. Coders encrypt data by converting it into code that cannot be seen by unauthorized users. However, cryptography has been around for centuries, that is, it pre-dates computers. Historically, the first uses of cryptography were found around 1900 BC in a tomb in Egypt. Atypical or unusual hieroglyphs were mixed with common hieroglyphs at various parts of the tomb.

The reason for the unusual hieroglyphs is unknown, but the messages were hidden from others with their use. Later on, cryptography would be used to communicate in secret by governments and spies, in times of war and peace. Nowadays, cryptography is used to encrypt data, as our information exists in digital format, so protecting sensitive information, such as banking, demographic, or personal data is important.

We will be further exploring the topics of coding theory through some of the problems presented throughout this book.

Computational biology

Computational biology is the area of theoretical computer science that focuses on the study of biological data and bioinformatics. Bioinformatics is a science that allows us to collect biological data and analyze it. An example of bioinformatics is the collection and analysis of genetic codes. In the study of biology, large quantities of data are explored and recorded.

Studies can be wide-ranging in topics and interdisciplinary. For example, a genetic study may include data from an entire state, an entire race, or an entire country. Some areas within computational biology include molecules, cells, tissues, and organisms. Computational biology allows us to study the composition of these things, from the most basic level to the larger organism. Bioinformatics and computational biology provide a structure for experimental studies in these areas, create predictions and comparisons, and provide a way to develop and test theories.

Computational thinking and coding allow us to process that data and analyze it. In this book, problems presented will allow us to explore ways in which we can use Python in conjunction with computational thinking to find solutions to complex problems, including those in computational biology.

Data structures

In coding theory, we use data structures to collect and organize data. The goal is to prepare the data so that we can perform operations efficiently and effectively. Data structures can be primitive or abstract. Software has built-in data structures, which are the primitive data structures, or we can define them using our programming language. A primitive data structure is pre-defined. Some primitive data structures include integers, characters (char), and Boolean structures. Examples of abstract or user-defined data structures include arrays and two-dimensional arrays, stacks, trees and binary trees, linked lists, queues, and more.

User-defined data structures have different characteristics. For example, they can be linear or non-linear, homogeneous or non-homogeneous, and static or dynamic. If we need to arrange data in a linear sequence, we can use an array, which is a linear data structure. If our data is not linear, we can use non-linear data structures, such as graphs. When we have data that is of a similar type, we use homogeneous data structures.

Keep in mind that an array, for example, is both a linear and homogeneous data structure. Non-homogeneous or heterogeneous data structures have dissimilar data. An example of a non-homogeneous data structure a user can create is a class. The difference between a static and a dynamic data structure is that the size of a static structure is fixed, while a dynamic structure is flexible in size. To build a better understanding of data structures, we will explore them through problem solving using the computational thinking elements throughout this book. We will revisit data structures again very briefly at the end of this chapter, as they relate to data types, which are discussed then.

Information theory

Information theory is defined as a mathematical study that allows for the coding of information so that it can be transmitted through computer circuits or telecommunications channels. The information is transmitted through sequences that may contain symbols, impulses, and even radio signals.

In information theory, computer scientists study the quantification of information, data storage, and information communication. Information can be either analog or digital in information theory. Analog data refers to information represented by an analog signal. In turn, an analog signal is a continuous wave that changes over a given time period. A digital signal displays data as binary, that is, as a discrete wave. We represent analog waves as sine waves and digital waves as square waves. The following graph shows the sine curve as a function of value over time:

Figure 1.5 – Analog signal

Figure 1.5 – Analog signal

An analog signal is described by the key elements of a sine wave: amplitude, period, frequency, and phase shift:

  • The amplitude is the height of the curve from its center. A sine curve repeats infinitely.
  • The period refers to the length of one cycle of the sine curve, that is, the length of the curve before it starts to repeat.
  • The frequency and the period of the sine curve have an inverse relationship:

In relation to the inverse relationship, we can also say:

  • The phase shift of a sine curve is how much the curve shifts from 0. This is shown in the following graph:
Figure 1.6 – Phase shift examples

Figure 1.6 – Phase shift examples

In contrast, digital signal graphs look like bar graphs or histograms. They only have two data points, 0 or 1, so they look like boxy hills and valleys:

Figure 1.7 – Digital signal

Figure 1.7 – Digital signal

Digital signals have finite sets of discrete data. A dataset is discrete in that it contains individual and distinct data points. For analog signals, the data is continuous and infinite. When working with computer science, both types of signals are important and useful. We will explore digital signals in some of the applications in later problems throughout the book, and specifically in the problems presented in Chapter 16, Advanced Applied Computational Thinking Problems.

Automata theory

Automata theory is one of the most fascinating topics in theoretical computer science. It refers to the study of machines and how calculations can be completed in the most reliable and efficient way. Automata theory involves the physical aspects of simple machines as well as logical processing. So, what exactly is automata used for and how does it work?

Automata are devices that use predetermined conditions to respond to outside input. When you look at your thermostat, you're working with an automata. You set the temperature you want and the thermostat reacts to an outside source to gather information and adjust the temperatures accordingly.

Another example of automata are surgical robots. These robots can improve the outcomes of surgeries for patients and are being improved upon constantly. Since the goal of automata theory is to make machines that are reliable and efficient, it is a critical piece in the development of artificial intelligence and smart robotic machines such as surgical robots.

Formal language theory

Formal language theory is often tied to automata theory in computer science. Formal language is the study of the syntax, grammar, vocabulary, and everything involving a formal language. In computer science, formal language refers to the logical processing and syntax of computer programming languages. With regard to automata, the machines process the formal language to perform the tasks or code provided for it.

Symbolic computation

Symbolic computation is a branch of computational mathematics that deals with computer algebra. The terms symbolic computation and computer algebra are sometimes used interchangeably. Some programming software and languages are focused on the symbolic computations of mathematics formulas. Programs using symbolic computation perform operations such as polynomial factorization, simplifying algebraic functions or expressions, finding the greatest common divisor of polynomials, and more.

In this book, we will use computer algebra and symbolic computation when solving some real-world problems presented. Python allows us to not only perform the mathematical computations that may be required for problems, but also explore graphical representations or models that result from those computations. As we explore solutions to real-world problems, we will need to use various libraries or extensions to the Python programming language. More on that throughout Part 2, Applying Python and Computational Thinking, of this book, where we will explore the Python programming language in greater detail.

Computational geometry

Like symbolic computation, computational geometry lives in the branch of computer science that deals with computational mathematics. The algorithms we study in computational geometry are those that can be expressed with geometry. The analysis of the data is done with geometric figures, geometric analysis, data structures that follow geometric patterns, and more. The input and output of problems that require computational geometry are geometric.

When thinking of geometry, we often revert to the figures we mostly associate with that branch of mathematics, such as polygons, triangles, and circles. That said, when we look at computational geometry, some of the algorithms are those that can be expressed by points, lines, other geometric figures, or those that follow a geometric pattern. Triangulation falls under this branch of computer science.

Triangulation of data is important for applications such as optical 3D measuring systems. We triangulate GPS signals to locate a phone, for example, which is used in law enforcement.

There are many uses of triangulation in modern times, some of which we'll explore through real and relevant problems presented in this book.

Computational number theory

Number theory is the branch of mathematics that studies integers and their properties. Computational number theory then is the study of algorithms used to solve problems in number theory. Part of the study of number theory is primality testing.

Algorithms created to determine whether input or output is prime have been used for many purposes. One of the most critically important uses and applications of primality testing and number theory is for encryption purposes. As our lives have moved to saving everything electronically, our most personal information, such as banking information, family information, and even social security numbers, live in some code or algorithm. It is important to encrypt such information so others cannot use or access it. Computational number theory and cryptography are intrinsically tied, as you will be able to explore later.

Some of the theories presented are meant to help you understand how intertwined computer science theories are, their applications, and their relevance to what we do each day.

In this section, we learned about theoretical computer science. We also learned about its various theories.

Throughout this book, we will be using computational thinking (discussed further in Chapter 2, Elements of Computational Thinking) to help us tackle problems, from the most basic applications to some complex analyses, by defining and designing adequate algorithms that use these theories. Theoretical computer science is used to study a system's software, which we will explore next.

 

Learning about a system's software

System's software is used to perform multiple functions and communicate between the operating system (OS) of a computer, peripherals such as a keyboard and mouse, and firmware, which is permanently saved to a device and is needed for its operation, among other functions. These are part of the two main types of software: system software and application software.

System software allows a computer to communicate between the hardware and the applications. Think of a smartphone. The phone is composed in its most basic form of the hardware, which includes the battery, cameras, memory, screen, and all the physical components and peripherals. The OS allows those components to be used by applications.

Take the camera application of a phone. The system's software lets the application communicate with the phone to use the camera to take a picture, edit it, save it, and share it. A computer's OS also allows the hardware to communicate with programs. A design program will use the mouse or other peripheral that can be used to draw, create, use a touchscreen if available, and more.

If we do not know our system's software, we cannot create applications that can communicate effectively with our hardware, creating errors that can range from critical, or rendering a peripheral useless, to minor, where some components may work, say taking a picture, but others may not, such as saving or sharing the picture. The system's software is created in a way that provides us with the easiest, most efficient way to communicate between the hardware and applications.

Operating systems

The OS performs multiple tasks. If you recall, error handling is part of an OS that checks for the most common possible errors in order to fix them without creating a larger problem or rendering an application worthless. Error handling is one of the operating system's most important tasks. In addition, the OS is responsible for the security of your computer or device. If you have a smartphone, you know that many updates to the OS are done in order to fix a security problem or to prevent a security breach. The OS is responsible for only allowing an authorized user to interact with the content that is stored in the device.

In addition to security and error handling, an OS is responsible for allocating memory for files and organizing them. When we save and delete a file or program, the memory that had been used is now free. However, there may be something saved immediately before and immediately after. The OS allocates and reallocates memory in order to maintain the best performance possible by the device. Memory management not only refers to user-saved files, but also to the RAM.

The file management of a device is also run by the OS. The OS will allocate the information as a filesystem, breaking the information into directories that are easily accessed by the user and by the device. The filesystem is responsible for keeping track of where files are, both from the OS and from the user, the settings for access to the device, which are evolving constantly, and how to access the files and understand the status of the files. Access to devices has changed in recent years.

While computers typically use a username and password, many devices can now be accessed through a fingerprint, a numerical or alpha-numerical passcode, facial recognition, images, paths, and more. As any of these topics evolve, the OS evolves as well and needs to be updated or recreated. The operating system is also responsible for allowing communication between the applications and the device.

Application software

Application software refers to software applications that perform a particular task. Think of the applications, or apps, that you can access from a mobile device. There are hundreds of types of applications, such as static games that live on the device, games that allow you to play with others remotely, news applications, e-book readers, fitness training apps, alarms, clocks, music, and so much more! Applications always perform some form of task, be it for personal use, business use, or educational use.

Application software has multiple functions. You may find suites for productivity, such as Microsoft (Office) and Google products. When we need to do research on the internet, we use applications called browsers, which allow us to access the information and index the information so that we can access it. These browsers include Google Chrome, Safari, Firefox, Edge, Opera, and others. Browsers are used by both mobile devices and computers. Keep in mind that the purpose of an app is to perform a specific task for the end user.

Important Note:

As an aside, applications have grown exponentially since computers became household tools and phones started being used for other things rather than just for calling others. Early computers were used for just that: computing, or calculating mathematical analyses and tasks. That's one of the reasons it is so important to have an understanding of the development and history of computer science. Since we cannot completely predict future uses of computer science and system software, the more we know about them, the more we will be able to create and adapt when technological advances happen.

In this section, we learned about the system's software. We also learned about OS software and application software. For the purposes of this book, some applications will be more important as we sort through some of the problems presented, such as databases, productivity software, enterprise resource planning, and educational software.

In the next section, we'll learn about computing.

 

Understanding computing

In computer science, computing refers to the activities that computers perform in order to communicate, manage, and process information. Computing is usually divided into four main areas: algorithms, architecture, programming languages, and theory.

Since, we've discussed theory and algorithms in previous sections, we will now focus on defining architecture and programming languages.

Architecture

Computer architecture refers to the set of instructions that interact with computer systems. In more basic terms, the architecture includes the instructions that allow software and hardware to interact. Computer architecture has three main subcategories: Instruction Set Architecture (ISA), Microarchitecture, and System Design.

Instruction Set Architecture (ISA)

The ISA is the boundary that exists between the hardware and the software. It is classified in multiple ways, but two common ones are complex instruction set computer (CISC) and reduced instruction set computer (RISC). These are defined as follows:

  • CISC: This is a computer that has explicit instructions for many tasks, such as simple mathematical operations, and loading something from memory. CISC includes everything that is not included in RISC.
  • RISC: This is a computer with an architecture that has reduced cycles per instruction (CPI).

CISC tries to complete instructions with fewer steps, while RISC only uses simple instructions. CISC is multi-step, while RISC is single-step, performing one task at a time. The CISC process includes the instructions, the microcode conversion, microinstructions, and execution. By contrast, RISC includes instructions and execution.

In CISC, microcode conversion refers to the interpretation of the language at a lower level. It takes into consideration the hardware resources to create microinstructions. Microinstructions are single instructions in microcode. After microcode creates the microinstructions, the microinstructions can be executed. The following diagram shows the process for both RISC and CISC:

Figure 1.8 – Difference between RISC and CISC

Figure 1.8 – Difference between RISC and CISC

Both RISC and CISC are necessary for computer programmers. There are advantages and disadvantages to having a single-step process (RISC) versus a multi-step process (CISC). RISC reduces the cycles per instruction, doing one thing at a time. CISC reduces the instructions in a program, but at the cost of cycles per instruction. Depending on what our needs are, we can choose the best path to take.

Programming languages

Programming languages are the way we write instructions for computers and other devices. Different languages are used depending on what is needed, ease of use, and much more. Examples of programming languages include the following:

  • Ruby and Python: Ruby is a programming language mostly used for web applications. Ruby is stable and easy to use; however, many developers choose to use Python over Ruby because Python is faster. Although Ruby has not been as popular and had some performance issues, the language is very much alive in 2019 and continues to grow. Python, on the other hand, is widely used for multiple purposes, such as web applications, user interface applications, and websites, among others. We will explore Python in greater depth later on in this book.
  • C: The C languages are a critically important part of computer science, as C was the first language used and is still the most widely used language. C has been around since 1972, when Dennis Ritchie invented it, but it has been used by others since 1978, when it was first published. While other languages have grown in popularity since, C is still used in 2019. Some of its uses include operating systems, hardware drivers, and applications, among others. C is a base-level language, which means it requires almost no abstraction.
  • C++: C++ was developed by Bjarne Stroustrup as an extension of C in 1985. The goal of the language was to add object-oriented capabilities. The language is still widely used both in conjunction with the C language in operating systems and for other software. C++ is an intermediate-level programming language.
  • C#: C# (C sharp) is a high-level programming language. Much like C++, it has object-oriented capabilities and is an extension of the C programming language. One of the main differences between C++ and C# is that C++ uses machine code while C# uses bytecode. Machine code can be executed directly by a computer. Bytecode has to be compiled, so it is considered a low-level code that needs to be interpreted.
  • Swift: The Swift programming language was developed by Apple Inc. in 2014. As programming languages go, Swift is one of the newest. Apple released it as an open source programming language with version 2.2, which was released in 2015. The language is considered to be a general-purpose and compiled programming language.
  • Scratch: Scratch was developed as a visual programming, block-coding language in 2002 by MIT Media Lab. As a block programming language, it is used extensively in schools to teach students of all ages how to code. Scratch is now adapted for multiple uses, including some robotic applications, such as Vex Code, incorporating machine learning and artificial intelligence, and much more. It is compatible with popular classroom peripherals such as the Makey Makey, which is a circuit that interacts with the computer and can be fully controlled with a Scratch program. While it is popular for educational purposes, the power of the programming language cannot be understated and the language itself and its functionalities continue to grow.
  • Java and JavaScript: JavaScript is a scripting language that is used only within browsers. It is used in the making of websites and web applications. Java, on the other hand, is a general-purpose programming language. JavaScript helps us make websites animated or add interactive functionalities to them. Contrastingly, Java is compiled into bytecode and is widely used in the development of Android devices and applications.
  • PHP: PHP is otherwise known as Hypertext Preprocessor. Much like Java, it is a general-purpose programming language. It is widely available, as it is open source. PHP is used in website design and applications and is considered to be easy to learn, yet has many advanced features. PHP can also be used to write desktop applications.
  • SQL: SQL, or structured query language, is a programming language used to interact with data. SQL is domain-specific. It has been around for almost as long as C, making its first appearance in 1974. The main importance of SQL is that it can interact with databases, where other languages are not able to do so.

In computational thinking, we use many different programming languages, depending on what our goals are, what information we have or need, and what our application or software requirements are. Choosing a language is dependent on not just our knowledge of the language, but the possible functionalities of the language.

We will get to work more extensively with Python in this book because of its open source nature, ease of use, and the large number of applications it can be used for. However, Python is not the only option. Knowing about other languages is important, especially for developers.

In this section, we learned about computing and a few of its areas, namely, architecture and programming languages. We also learned about the ISA and its types, along with an introduction to various programming languages. In the next section, we'll look at data types and structures.

 

Learning about data types and structures

In computer science, data types and structures are two distinct things:

  • A data type is a basic classification. Some data types include integers, float, and strings.
  • Data structures use multiple types of data types. They can organize the information into the memory and determine how we access the information.

Let's look at these in more detail in the following sections.

Data types

As mentioned, data types are basic classifications. They are variables that are used throughout a program and can only exist with one classification. There are different classes of data type. We will focus on primitive and abstract data types for now, but we will revisit this topic as we move through problems and design solutions.

Primitive data types include byte, short, int, long, float, double, Boolean, and char:

  • A byte can store numbers from -128 to 127. While these numbers can be stored as integers, or int, a byte uses less storage, so if we know the number is between those values, we can use a byte data type instead.
  • A short is a number between -32,768 and 32,767.
  • An integer, int, is used to store numbers between -2,147,483,648 and 2,147,483,647.
  • Long is used to store numbers from -9,223,372,036,854,775,808 and 9,223,372,036,854,775,807.
  • A float allows us to save a decimal number.
  • Decimal numbers can also be saved as double, which has more precision than a float.
  • Boolean values are data types that are either True or False. So, a variable can be saved such that when its value is printed, the result will be saved as true or false.
  • Char is used to save a variable as a single character.

We'll look at data structures in the next section.

Data structures

As mentioned under the Coding theory section earlier in this chapter, data structures are used to collect and organize data in the most efficient and effective way possible. Data structures can be primitive, such as the built-in data structures in software, or abstract. Primitive data structures can also be defined using programming languages, but they are pre-defined. Some of the primitive data structures include the data types listed in the previous section, such as chars and Boolean structures.

Abstract data types (ADTs) include the information for the structure and design of data types. Abstract data structures include arrays and two-dimensional arrays, stacks, trees and binary trees, linked lists, queues, and more, as mentioned in the Coding theory section earlier in this chapter. Lists can contain multiple instances of the same data values. These lists are countable, so we can find how many elements are in the list, reorder them, remove items, add items, and so on. Lists are widely used as linked lists, arrays, or dynamic arrays:

  • A linked list means that each data element in the list is connected, or points, to the next one, regardless of where they are stored within the memory.
  • An array is ordered. The elements are read in order to be able to make sense. Think of an array as reading this sentence. You don't read the sentence as "array an think reading as this of sentence." We read the sentence in order, from left to right, not in a jumbled order.
  • Dynamic arrays can be resized, which is important when choosing a data type.

A stack ADT is a collection of elements and has two operations – push and pop. A push is used to add an element to the collection while a pop removes the most recent element.

A queue ADT is a linear data structure. As with a stack, we can add or remove elements. However, in a queue ADT, the point of deletion and the point of insertion are done at two different ends.

As mentioned before, the data structures are concrete implementations of data types. How we add or remove elements from a collection, for example, is the data structure.

This can all be slightly confusing, but we will be learning more about them through examples in later chapters. For now, understanding the definitions and simple examples is enough.

 

Summary

We have learned some fundamentals of computer science in this chapter. We looked at how to convert from binary to base-10. We also explored topics and theories in theoretical computer science. We learned about computing and data types and structures. These sections will allow us to understand the computational thinking process and how to tackle all types of problems presented, starting in Chapter 2, Elements of Computational Thinking, of this book.

As we delve deeper into the computational thinking world and process, we will need to revisit some of the content of this chapter as we look at problems, search for the best way to solve them, and make decisions about how to write the algorithms.

Problems may have an infinite number of ways to be solved using algorithms. Understanding how processes work and which data structures are most suitable for our problems is imperative in creating the best solutions. Identifying the data types needed for the algorithms and how computers read data will only help us in writing the most effective and efficient algorithms.

In the next chapter, we will learn about the computational thinking process and how to break down problems in order to design our algorithmic solutions.

About the Authors

  • Sofía De Jesús

    Sofía De Jesús is a computational thinking teacher with a degree from the University of Puerto Rico with a focus on math. She has a master’s degree from the University of Dayton. Her experience in education and development spans two decades. She has worked with clients to develop solutions in multiple programming languages. As a teacher, Sofía helps students incorporate the philosophy of computational thinking in courses like game design, circuits, Python, web design, and robotics. She likes to play video games and spend time with her 11 year old Yorkie, King Kong. Sofía also enjoys creating materials, small furniture, and jewelry using CNC machines and laser cutters. She enjoys spending as much time in Puerto Rico as work and life permits.

    Browse publications by this author
  • Dayrene Martinez

    Dayrene Martinez is a Systems Engineer in the Defense Industry where she develops neural networks embedded in real-time software to aid in decision making for aerospace vehicles. She received a B.S. in Electrical Engineering from the New Jersey Institute of Technology (NJIT). Dayrene is passionate about STEM education and volunteers her free time to inspire the next generation of engineers. She is an active supporter and keynote speaker for the non-profit organization Latinas in STEM. She teaches middle and high school students circuitry, robotics design and software engineering.

    Browse publications by this author
Book Title
Access this book and the full library for FREE
Access now