Chapter 1 Introduction

Number Systems and the Foundation of Computing

Initially, computers and computing devices were developed to deal with numbers. They later made their way into the realm of text handling and information processing. This is done through encoding. When properly coded, all text can be represented as numbers—codes—and all ways of manipulating text can be accomplished through operations on those codes. Number systems and operations on numbers are really a basic foundation of computing and modern computers.

We all know numbers, and the number system we have known since childhood is base-10, which is represented using 10 digits from 0 to 9. A base-10 number such as 2539867 can be written as

In general, an n-digit number d_n−1d_n−2…d₁d₀ (where n is any positive integer and each d ∈ [0, 1, 2, …, 9], where 0 < i < n ) in a base-10 number system can be rewritten as

In fact, a number system can be based on any whole number other than 0 and 1. There is a base-7 system for weeks, a base-12 system for the Chinese zodiac and imperial foot and inch, and a base-24 number system for the 24-hour clock. A long list of different numbering systems that have appeared since prehistory can be found at https://en.wikipedia.org/wiki/List_of_numeral_systems.

In general, a base-Q number system will require Q unique symbols representing 0, 1, … Q−1, respectively. The base-10 equivalence of an n-digit base-Q number d_n−1d_n−2…d₁d₀ can be represented as

The evaluation of the expression above will result in its base-10 equivalence. This is how we convert a number from base-Q to base-10.

For Q = 2, the numbers 0 and 1 are used to represent digits; for Q = 3, the numbers 0, 1, and 2 are used; for Q = 8, the numbers 0, 1, 2, 3, 4, 5, 6, and 7 are used; for Q = 16, the numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a/A, b/B, c/C, d/D, e/E, and f/F are used.

The expression above also shows how to convert a number from base-10 to base-Q: divide the number by Q repeatedly, and the remainders will be the digits. The details of these conversions can be found on the internet.

For a number d_n−1d_n−2…d₁ d₀ in a base-Q number system, it is often necessary to add Q as a subscription of the sequence, as shown below:

This explicitly indicates that the number is in a base-Q number system. For example, number 657 in a base-8 number system will be written as 657₈ or (657)₈, especially if the context does not indicate which number system the number is in.

All number systems have the same operations that we are already familiar with in a base-10 system, such as addition, subtraction, multiplication, and division. The only difference is that in a base-Q number system, a 1 carried to or borrowed from a higher digit is equal to Q instead of 10.

For example, in a base-2 number system, 101 can be written as 1 * 22 + 0 * 21 + 1 * 20, and its 10-base equivalence is 1 * 4 + 0 + 1 = 5, and for 101 + 110, the operation is

Given the four basic mathematical operations—addition, subtraction, multiplication, and division—it is very simple to prove that multiplication can be done by repeated addition, whereas division can be done by repeated subtraction. Therefore, if you know how to do addition and subtraction and are able to count, you will be able to do multiplication and division as well.

More importantly, because a − b can be rewritten as a + (−b), you may be able to eliminate subtraction if you can represent −b without the minus sign. In a base-Q number system, (a − b) can be conveniently handled through a + b′, in which b′ is the Q-complement of b representing (−b).

Given a negative number, −N, in which N is called the magnitude of −N, how do you get N′, the Q’s complement to N? It turns out to be very easy.

For a number N written as d_nd_n−1…d₀ in a base-Q number system, its Q-complement N′ is a number, also in a base-Q number system, such that N + N′ = Qⁿ, and N′ can be easily calculated in the following two steps:

1. 1. For each d_i in d_n−1d_n−2…d₀, find t_i such that d_i + t_i = Q−1, to get t_n−1t_n−2…t₀
2. 2. Add 1 to t_n−1t_n−2…t₀ to get N’s complement c_n−1c_n−2…c₀

For b in a − b, if b has fewer digits than a, add 0s to the left of b to make up the missing digits before working on the above steps. For example, for 768 − 31, do 768 + (−31) or 768 + the 10’s complement of 31.

To get 10’s complement of 31, first add one 0 to the front of 3 to get 031, then find out the 10’s complement of 031, which is 968 + 1 = 969. Then do 768 + 969 to get 1737, and ignore the last carried digit, 1, to get 737, which is the result of 768 − 31.

It is easy to see that if C is N’s complement, then N is C’s complement as well. Using the notation given above, this can be written as (N′)′ = N.

What about floating-point numbers—that is, numbers with fractions, such as 3.1415926?

In a base-Q number system, a floating-point number can be represented much like integers, as shown below:

This may give us a hint that a floating-point number can be represented by two sequences of digits: one for the integer portion and the other for the fraction portion. If floating-point numbers are represented this way in computers, addition and subtraction could be performed on the two portions separately, but with a mechanism to deal with carrying from the fraction to the integer in the case of addition, and a mechanism to deal with borrowing from the integer to the fraction in the case of subtraction. This would be rather clumsy, and it would be even more clumsy when doing multiplication and division.

In reality, floating-point numbers are represented in scientific notation, such as 1.3 * 10² in a base-10 or decimal system, where 1.3 is called the fraction, 2 is called the exponent, and 10 is the radix. In a base-2 system, the radix would be 2.

In scientific notation, arithmetic operations on floating-point numbers can be easily done, especially if the fractions of all floating-point numbers are normalized—that is, if the number of digits before the radix point is fixed for all floating-point numbers. For example, to perform the addition or subtraction of two floating-point numbers, all you need to do is shift the digits of one floating-point number based on the difference of the two exponents, then perform addition or subtraction in the same way as on integers. More surprisingly, multiplying and dividing floating-point numbers in scientific notation is much easier than adding and subtracting. There is no need to shift the digits because

and

All you need to build a computer capable of adding, subtracting, multiplying, and dividing in a base-Q number system is the ability to add and count, which is needed for multiplication and division. Moreover, counting itself can be done by addition when counting up or subtraction when counting down. This is very encouraging.

The following discoveries are even more encouraging:

• • Many mathematical and scientific problems can be represented and reformulated based on the basic mathematical operations discussed above.
• • If we can build a computing device capable of doing basic mathematical operations, the machine can solve many computing and information processing problems.

The remaining question is how to make such a machine work faster. On a computing machine with only an addition and counting unit, if each step of an operation has to be enabled by a human, the computation would be very slow because it would have to wait for the human to input instructions and data. To speed things up, the entire problem solving process needs to be automated. This requirement has led to the introduction of memory to computing machines to store both the operating instructions (the program) and data needed during the computation. For the central processing unit (CPU) and memory (RAM) to communicate and work together, a communication channel and control unit need to be added. For human users to communicate with the computing machine, input and output units are also needed. Together these include everything described in Von Neumann’s architecture for modern computers.

Computability and Computational Complexity

Now comes the question of how powerful the computing machine described above can be. In particular, we should ask,

• • What problems can or cannot be computed with a computing machine?
• • How difficult is it to solve a given problem with a computing machine, assuming that the machine can take as many steps and use as much memory as needed to solve the problem?

Answering the first problem is the study of computability. Answering the second question is the study of computational complexity.

A well-known computability problem was raised by David Hilbert, a very famous German mathematician in the 19th century. The 10th problem in his list of 23 important mathematical problems he published in 1900 is the decidability problem, which is about finding an algorithm that can determine whether a Diophantine equation such as xⁿ + yⁿ = zⁿ, where n is an integer and greater than 2, has integer solutions. It was proved in 1970 that such an algorithm doesn’t exist, meaning that the problem of deciding whether a Diophantine equation has integer solutions is unsolvable, or incomputable.

Between the 1930s and 1940s, before the existence of modern computers, Alan Turing invented a simple yet powerful abstract machine called the Turing machine. He proved that the abstract machine could simulate the logic of any given algorithm and further determine whether an algorithm is computable. The operation of the machine will halt if the algorithm is incomputable. During the same time, computability was also well studied by Alonzo Church based on lambda calculus. The two works later intertwined in a formal theory of computation known as the Church-Turing thesis.

In computer science, the computational complexity of an algorithm devised to solve a problem is about the number of resources—CPU time and memory, in particular—needed to run the algorithm on a computer. A problem may be solved in different ways using different algorithms with different computational complexities. Sometimes it is necessary to find a better algorithm that runs faster and/or uses less memory.

The time required to run an algorithm is also related to the size of the problem to be solved. For example, finding someone in a classroom would be much easier than finding someone in a city. If you denote the size of a problem with n, then in computer science, O(f(n))—called the big O of f(n)—is used to describe asymptotically the upper bound of running time: the time complexity of an algorithm for solving the problem.

For example, assume you want to sort the numbers in a list. The size of the problem will be the number of numbers in the list. One algorithm is called selection sort, which begins with selecting the smallest number from the list, then selecting the smallest number from the remaining of the list, and so on. Assume the size of the list is n. The first time it will need to do n − 1 comparisons. The second time it will need n − 2 comparisons. When these are only two numbers left in the list, only one comparison is needed to finish. So the complexity of the algorithm in terms of the total number of comparisons needed will be

You may have noted in the big-O notation that we have kept only the highest-order term and have removed the constant ½ as well. This is because, with the big-O asymptotic notation, only the scale of complexity increased when the size of the problem increases is of interest.

In computer science, problems can be classified as P (for polynomial), NP (for nondeterministic polynomial), NP-complete, or NP-hard problems. A problem is said to be in P if it can be solved using a deterministic algorithm in polynomial time—that is, if the complexity is a big O of a polynomial. A problem is said to be in NP if it can be solved with a nondeterministic algorithm in polynomial time. A problem is NP-complete if a possible solution can be quickly verified but there is no known algorithm to find a solution in polynomial time. A problem is NP-hard if every NP problem can be transformed or reduced to it within polynomial time.

In the above, a deterministic algorithm refers to the one in which, given the same input, the output would always be the same, whereas a nondeterministic algorithm may give different outputs even for the very same input.

The complexity of algorithms, which is closely related to the response and processing speed of programs and computer systems, is the concern of good programmers, especially when dealing with resource-intensive applications. It is also an important topic to be studied in senior or graduate courses in computing and computer science. When writing a program or just a function for assignments or an application, always think about the time and space complexity and ask yourself, Is there a better way to get the job done?

The Construction of Modern Computers

In general, computers can be categorized into two types: analog computers and digital computers. The computers in use today are almost all digital computers. But analog computers do have their advantages.

The Development and Implementation of Python

Python was originally conceived and developed in the Netherlands by Guido van Rossum in the late 1980s. Its first release was Python 0.9.0 in 1991. Python 2.0 was released in 2000, nine years after the release of Python 0.9.0.

Most of the development of Python was accomplished between 2005 and 2013, when Guido van Rossum was working at Google, where he spent half of his time on the development of the programming language. The latest Python 2 release is Python 2.7.16, whereas the latest release of Python 3 is Python 3.9.0, at the time of writing.

Python is an interpreted programming language rather than a compiled programming language. Programs written in Python don’t need to be compiled into target machine code. Instead, they only need to be translated into bytecodes, then executed by a Python Virtual Machine (PVM), which is built into the Python interpreter.

Python language has different implementations with different names. CPython, written in C and known simply as Python, is what we will be using, and it is the implementation you will get from Python standard distribution at python.org by default. In addition to CPython, the following are some alternative implementations of Python:

1. 1. JPython or Jython, and implementation for running on Java Virtual Machine (JVM)
2. 2. IronPython, an implementation for running on .NET
3. 3. PyPy, an implementation for working with a just-in-time (JIT) compiler
4. 4. Stackless Python, an implementation of a branch of CPython supporting microthreads
5. 5. MicroPython, an implementation for running on microcontrollers

These implementations may be of interest only for some special applications.

Advantages of Python

Python was designed with the principle of “programming for everyone.” Programs written in Python are clean and easy to read. Yet Python is a general-purpose programming language and very powerful to code in. Programming in Python has the least overhead, especially when compared to Java. Let’s take the famous “Hello World!” application as an example. In Java, to create this application, you need to write a class with a main method like the following:

Then save it to a file and compile the file into Java bytecode by running the following command, provided you have a JDK correctly installed:

This command will generate a file named first.class. You can then run command java first to have “Hello World!” spoken out.

In Python, however, you only need to write the following code and save to a file, say, myhelloworld.py:

Then run the following command:

More importantly, Python supports different programming paradigms, including structured programming, imperative programming, object-oriented programming, functional programming, and procedural programming. Logic programming is probably the only exception; it is not supported by Python.

Python is very powerful for two reasons. The first reason, as you will see later, is that Python has many powerful language constructs and statements to represent data and operations on various data. The second reason is that there are thousands of third-party packages/libraries/modules available for all kinds of programming needs in addition to the large standard libraries included with every release of Python. For example, Python is widely used for data analytics and machine learning with the support of the NumPy, SciPy, Pandas, Matplotlib, and TensorFlow libraries.

Resources for Python and Python Education

The ultimate resource for Python and API libraries is the official website of the Python software foundation at https://www.python.org/. From that website, you will be able to access all the releases of Python and other packages and libraries that you may be interested in, in addition to the standard libraries that come with the official release of Python.

At the time of writing, the latest release of Python is 3.11.1, but you can always check and locate the latest release for your platform at https://www.python.org/downloads/. However, for your convenience and for your future study and use of Python, we will use a package management system called Anaconda to install and manage Python and all tools and libraries that you will need for this textbook, as detailed later.

There are plenty of resources on the internet for eager learners to learn almost anything, including programming in Python. To learn effectively on the internet, however, a learner must be able to choose the right materials from thousands—even millions—of choices, and that has proved to be a very difficult task. That’s probably one of the reasons why universities and professors are still needed: to set the right learning paths and to select the right resources for learners.

On the internet, the most authoritative learning source about the Python language is the documentation (https://docs.python.org/3/), including language references (https://docs.python.org/3/reference/index.html) and library references (https://docs.python.org/3/library/index.html), although they may not be articulated for beginners.

For learners who prefer to learn by reading, the following are some of the best resources on the web:

• • https://docs.python.org/3/: This resource is from the official Python website, so the terms and jargons used should be deemed official at least within the Python community. It is a comprehensive section as well.
• • https://www.w3schools.com/python/: This is a very popular site that offers resources covering many different languages.
• • https://www.learnpython.org/: This is another good site for learning Python. it has many resources on specific topics.

For learners who love to watch videos and lectures, the following are recommended:

• • Python Crash Course for Beginners, at https://www.youtube.com/watch?v=JJmcL1N2KQs, by Traversy Media. This video uses VS Code IDE to illustrate the program examples so that you can follow along once you have the required programming environment set up.
• • Learn Python—Full Course for Beginners, at https://www.youtube.com/watch?v=rfscVS0vtbw, by freeCodeCamp.org and narrated by Mike Dane. This video is one of the best. Please note that the video lecture recommends the installation and use of PyCharm IDE. However, the installation and use of VS Code IDE is required in this book.

Installing and Setting Up the Python Programming Environment

There are different ways of setting up your Python programming environment. The method we present below is believed to be more reliable and less subject to future changes.

Additional Tools Supporting Software Development in Python

To make software development more efficient, the Python community has made the following frameworks or systems available for Python developers.

Program Interactively with Python Interactive Shell

Programming for computers is writing instructions for computers to execute. Interactive programming is programming in an environment in which you can interact with a computer, the interpreter of the programming language, more precisely, instruction by instruction. The opposite of interactive programming is batch programming, in which you will need to write a complete program and then feed the entire program to a language engine such as an interpreter, language runtime, or virtual machine in order to execute it. In interactive programming, a piece can be a single statement or a group of statements, but not a complete program. One of the advantages of interactive programming is immediate feedback on the code pieces from the interpreter.

The simplest interactive programming environment for Python is the Python interactive shell. It can be quickly started by running command Python at a command prompt such as within a Windows PowerShell, as shown here:

The started interactive Python programming environment should look like this:

Here, >>> is the prompt of the Python interactive shell, waiting for your input, which will then be evaluated by the interpreter. This is how you program interactively within this environment.

As the de facto standard, our first program in the interactive Python programming environment is to say “Hello World!” as shown here:

As can be seen above, this program in Python needs only one statement made of one line of code, whereas in C/C++ or Java, it would need a dozen lines of code.

Please note that in the previous example, the characters behind the Python prompt >>> are Python statements you need to type, and the rest are output from Python interpreter or Python Virtual Machine (PVM).

Our next sample program within the Python interactive shell is to assign 8 to variable x and assign 9 to variable y, then print out the sum of x and y, as shown here:

Within this interactive programming environment, you can type any Python expression directly behind >>>, and it will then be evaluated. An example is shown here:

You may have realized that the interactive Python programming environment can be used as a powerful scientific or financial calculator, with all the functions you need, as long as you know where to find the functions and how to import and use them to write formulas.

Throughout the textbook, we will occasionally give examples in Python interactive shell when it is more convenient and proper in context. However, our preferred interactive programming environment is Jupyter Notebook within VS Code IDE, as you will see later in this section.

Program with VS Code IDE

Interactive programming environments like Python Shell and Jupyter Notebook are good for testing Python statements, code blocks, and some real programming tasks such as data analytics, where interactive programming is more suitable. However, writing programs that contain thousands of lines of code in a Python interactive shell or Jupyter Notebook is inconvenient.

As previously mentioned, we will be using VS Code as our IDE. Our first small project is to write a program that takes an integer from the user input and tells whether it is a prime number or not. The first step to do this is to start VS Code from the Windows Start menu or desktop. In Windows or iOS, you may type “VS Code” in the search bar to launch the application.

To create a Python program file within VS Code, choose “New File” from File, and then save the file as xyz.py, where xyz is your preferred name for the small project. Here, we use “primetest.py.” VS Code will ask you to choose a folder for the program, and you may create one and then select it to open after the file is created. The program in VS Code will look like the one in Figure 1-4.

At this time, you are not required to fully understand the program, but if you are interested, you may type the code line by line into your VS Code and run it by clicking the play button at the top-right corner of the VS Code window, just to get a taste of programming in VS Code with Python.

Please note that if you have multiple Python program files open in VS Code and want to run a particular one within the IDE, you will need to click the file to make it active; then, within the editing area, click the right button of the mouse to pop up a menu and select run for your particular program. This is even more important if you have multiple editing tabs open for different programs.

Use Jupyter Notebook Within VS Code to Program Interactively

You may recall that Jupyter Notebook can be launched and run in a web browser, but for the purposes of this text, Jupyter Notebook will be run and used within VS Code to program interactively to allow you to benefit from many of the features that VS Code has.

Because Jupyter Notebook is natively supported within Visual Studio Code (as long as Jupyter Notebook is installed in your Python environment), all you need to do to get Jupyter Notebook running within VS Code is to open or create a notebook file, with extension ipynb in VS Code.

There are two ways to create a Jupyter Notebook file. One is to press Ctrl+Shift+P to search for the command “create new blank Jupyter Notebook,” then click the command. A new blank Jupyter Notebook will be created within VS Code.

Alternatively, we can also simply create a new text file, and then save the file as xyz.ipynb, where xyz is a name you prefer and ipynb is the file’s extension. Please note that to ensure the file type is ipynb, you have to select Jupyter (.ipynb) or all files (*.*) from the “Save as Type” list.

In either case, you may be asked to install an extension for Jupyter Notebook support. Click yes when you are asked to. You may also be asked to install Python if you have not done so yet or if the installation path has not been added to the environment variable. Click yes too to make sure you have Python properly installed on your computer.

Once a new Jupyter Notebook is created, you can then use it to program interactively within VS Code and enjoy many of the smart features of VS Code, such as those offered by IntelliCode.

Another advantage of using Jupyter Notebook within VS Code is that you can export a notebook as an HTML, PDF, or Python Script file. If you use Markdown cells to document your coding in code cells, you can produce a very nice document as a PDF or in HTML.

Later on, you will be required to create a Jupyter Notebook for each chapter or section, if there are many coding examples to work on in a section. You will use the Jupyter Notebook to interactively program all sample codes in that chapter or section or to test your own code to reinforce your learning. For chapter x, the Jupyter Notebook should be named chapter-x.ipynb, and for section x.y, the notebook should be named section-x.y.ipynb.

In the next section, we will provide a brief introduction to Markdown language that you can use to document your work either within Markdown cells of Jupyter Notebook or within a Markdown file, a file with md as the file extension.

Write Documentation in Markdown

Markdown is a simple and straightforward markup language with a plaintext-formatting syntax. It was created by John Gruber and Aaron Swartz in 2004. With Markdown, you can write a document in an easy-to-write and easy-to-read format, then convert it to HTML. Within VS Code IDE, a Markdown file, with md as the extension, can be converted to PDF as well as HTML. Moreover, documentation written in Markdown cells of a Jupyter Notebook can be automatically converted into docstrings when the Jupyter Notebook is exported into a Python script file, and when the notebook is exported into PDF, scripts in code cells will be nicely embedded into documentation written in Markdown cells. Together with markup syntax for program code, Markdown cells within Jupyter Notebook running in VS Code provide a much more user-friendly way to include program code in rich and formatted documents.

The Markdown language has been extended since its initial release by John Gruber. You will be introduced to both the basic syntax and some extended syntax (but only those supported by Jupyter Notebook within VS Code) to serve our purposes in this book.

Programming Interactively with Jupyter Notebook Within VS Code

Earlier in this section, we learned how to program interactively within a Python Shell launched within a CMD or PowerShell window, and how to start Jupyter Notebook within VS Code. In this section, we will find out how to use Jupyter Notebook within VS Code to program interactively as well as how to document your work and learning journey in both code cells and Markdown cells of Jupyter Notebook within VS Code.

Compared to the Python interactive shell, Jupyter Notebook is a much better and more powerful environment for interactive programming and has the following advantages:

1. 1. Everything you typed and the output from the Python interpreter are kept in a notebook file so that you can go back and review your work whenever needed. In the Python interactive shell, however, everything within the shell will be lost as soon as you exit from it.
2. 2. Within a programming cell of Jupyter Notebook, you can write and edit as many Python statements as you want, and the interpreter will wait until you hit Shift+Enter to run all the statements within the active cell, whereas the simplest interactive programming environments run only one statement at a time.
3. 3. You can go back to a previous programming cell and edit the code in it, and then rerun the code as you wish, which you cannot do in a Python Shell.

Again, our first example to program interactively in Jupyter Notebook is to say Hello World! But before we begin, we need to create a new Jupyter Notebook named section-1.6.ipynb for this section. If you are using this book for a course, we recommend that on your desktop, you create a folder using the course name or number, and then create this and all the Jupyter Notebook files within this folder or subfolders to better organize all the files for the course. For the purposes of this textbook, we will give this folder the name “comp218.” In the example shown here, the notebook file section-1.6.ipynb is under a subfolder named “VS Code.”

With Jupyter Notebook in VS Code, you can use Markdown cells to present your ideas and thoughts about the program you are to write, and use code cells to write program code and Python documentation on your code. In this first example, we first write the following in a Markdown cell:

We then write the following in a code cell:

This results in the notebook printing, outside of the code cell, the following:

In Jupyter Notebook, there are two types of cells for input. One is the code cell for you to write actual program code in. The other is the Markdown cell for you to write more detailed notes or reports about your work within the notebook using the Markdown language we have introduced in the previous section.

When a new cell is created in a Jupyter Notebook within VS Code, by clicking the plus sign + on the left side of the notebook window, you will get a code cell by default. To change a code cell to a Markdown cell, click the M↓ button at the top of the cell; to change a Markdown cell back to code cell, click the {} button at the top of the cell.

Please note that when using Jupyter Notebook within a web browser, to switch a code cell to Markdown cell you will need to click “Code” at the top of the cell, and then choose “Markdown” from the pop-up menu.

In the Jupyter Notebook example above, two cells are used. The first is a Markdown cell, in which we explain in more detail what we are going to do for our first Python program and how we will do it, whereas the second cell is a code cell, in which actual Python code is written, together with docstring and inline comments, for the program.

In the simple program above, a pair of triple quotation marks is used to enclose some string literals, called docstrings, as the formal documentation for the program or module. In addition to each program file or each module file, a docstring is also recommended, and even required, for each function, class, and method. Docstrings should be placed at the very beginning of a program file, module file, or right after the header of the definition of a class, function, or method. The docstrings will be retrieved and stored as the __doc__ attribute of that respective object and can be displayed when help is called on that object. Python also has a utility program called pydoc that can be used to generate documentation from Python modules by retrieving all the docstrings.

Right after the docstring is a print statement that will print out Hello World! when the program is executed by pressing Shift+Enter while the cell is still active. A cell is active if there is a vertical blue bar on the left side of the cell. To execute statements inside an active cell, we can also click the play button (the thick right-facing arrow) at the top of the cell.

Our next sample program is to assign integers to two variables and then print the sum, difference, product, quotient, integer quotient, remainder, power, and root. The Python statements to accomplish these operations are as follows:

• + operator for addition
• - operator for subtraction
• * operator for multiplication
• / operator for division
• % operator for modulus
• ** operator for exponentiation
• // operator for floor division

We then write the following in a code cell:

This prints the following:

• 5 + 3 = 8
• 5 − 3 = 2
• 5 x 3 = 15
• 5 / 3 = 1.6666666666666667
• 5 // 3 = 1
• 5 % 3 = 2
• 5 ** 3 = 125
• root 3 of 5 = 1.7099759466766968

As you can see, in this interactive programming environment, you can write and edit many Python statements within a single cell. You may simply write some statements to accomplish certain calculation or data analysis tasks that cannot be done even on an advanced scientific finance calculator.

This next example in Jupyter Notebook within VS Code calculates the sum and the product of 1, 2, 3, … 100:

This prints the following:

• Sum of 1,2,…,100 is 5050
• The product of 1,2,…,100 is 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Our next sample program in Jupyter Notebook within VS Code creates a simple data visualization to showcase how Python can be used for that purpose.

The data for x-axis are a list of letter grade in a grading system; the data for y-axis contain a list of numbers representing how many students received each corresponding grade in a class. The purpose of visualization is to see how the grades are distributed within the class.

Here we use a module called Matplotlib to visualize the data by plotting graphs. The result of the program as shown in Figure 1-6.

As you can see, with only 11 lines of code, you can produce a nice graph to visualize the data in Python.

Run Python Programs Outside IDE

The VS Code IDE we used in previous sections is good for developing programs or applications, but it is impractical to start an IDE each time you need to run a Python program.

So how can we run a Python program or scripts stored in a file? In a previous section, we wrote a program called primetest.py. To run the program without invoking VS Code, we need to take the following steps:

1. 1. Start Windows PowerShell or Windows Command Prompt by typing “terminal” in the search field on the Windows taskbar if you are on other platforms such as Linux. A shell terminal will come up; type the following:

   PS S:\Dev\Learn_Python>

2. 2. Within the terminal, go to the directory where the Python program file is located.
3. 3. Change the working directory to that folder by typing the following PowerShell command:

   cd  S:\Dev\Learn_Python\samples\

4. 4. Run the Python program file by typing the following command at the PowerShell prompt:

   python .\primetest.py

   the result is shown below:

   PS S:\Dev\Learn_Python> cd .\samples\

   PS S:\Dev\Learn_Python\samples> python .\primetest.py

   give me an integer that is greater then 1, and I will tell you if it is a prime: 23

   23 is a prime

   PS S:\Dev\Learn_Python\samples>

Note that to run a Python program from a terminal, two conditions must be met: (1) The location of the Python interpreter (python.exe) must be in the PATH system variable, so that Windows is able to find it. (2) The Python program file should be in the current working directory of the terminal. If that is not the case, you must either change your current working directory to where the Python program file is located or specify the path to the program file. Assume we change the current working directory from the one shown at the end of the list above to the one shown here using the command cd:

Because now the primetest.py program is one-level down from the current working directory at .\samples, where the leading dot (.) refers to the current directory, to run the program, you will have to specify the path to the program, as shown here:

Make the Python Program File Executable

Sometimes, we may still consider it inconvenient to run a Python program file from a terminal by feeding the file to the Python interpreter and rather prefer to make the program executable on its own so that it can be run by clicking the file within Windows File Explorer. Luckily, a tool called pyinstaller can be installed and used to do that. To install it, you need to run PowerShell or another shell terminal as an administrator. Within the terminal, run the command shown here to install pyinstaller using the pip tool:

Before you can use the pyinstaller tool to make the conversion, you will need to copy the Python library into Windows’ system32 directory, as shown below:

Now you can simply run the command pyinstaller <Python program file name> to make the conversion, as shown here.

The created executable is under .\build\primetest, named primetest.exe.

Please note, however, that the executable file requires the Python DLL library in order to run, so that you can either (1) make the DLL library searchable and accessible by Windows OS or whatever OS you are using, if you have many executables generated from Python program files, or (2) copy the Python DLL to where the executable file is located. In this case, since we are using Python3.11, the library is named python311.dll—which is located within the installation directory of Python3.11, which is s:\python\python311—we can simply copy the DLL file to .\build\primetest for a test, as shown below:

Once you have done all the steps above, you can run the program like all other apps on your computer, as shown here:

Errors in Programs

Errors in programs are hardly avoidable, and you should be prepared to see a lot of errors in your programs, especially at the beginning. The nice thing about programming within an IDE such as Visual Studio Code is that the IDE can point out many syntax errors and coach you to code along the way by showing you a list of allowable words or statements that you may want to use in that context, although you will have to decide which one to use for your program by highlighting the words that are problematic.

Syntax errors often include the following:

1. 1. Missing, misspelled, or misplaced keywords such as for, while, if, elif, else, with, class, def, and so on. Remember that Python language is case-sensitive so for and For are totally different words to Python Virtual Machine (PVM).
2. 2. Missing or misspelled operators such as >=, <=, +=, -=, *=, /=, and so on.
3. 3. Missing symbols, such as a colon, comma, square or curly bracket, or parenthesis.
4. 4. Mismatched parentheses, double quotation marks, single quotation marks, curly brackets, and square brackets.
5. 5. Incorrect indentation because Python uses indentation to form code blocks.
6. 6. Empty code blocks. If you do not know what to write in a code block, you can simply use a pass statement as a placeholder, as shown in the following examples.

   """

   This function will find the best student in a class based on their over performance, but at this time we don't know how.

   """

   def findBest():

    pass   # the pass statement is used to hold the place for a code block

The second type of errors you may encounter are runtime errors. While syntax errors may be easily avoided when programming within VS Code IDE, runtime errors can only be found during runtime. Examples of runtime errors include dividing a number with 0 and using a variable that has not been defined or that has no value before it is used. The discussion of error and exception handling, covered in Chapter 4, is mostly about runtime errors.

The following are some common runtime errors in Python programs:

1. 1. ZeroDivisionError, when dividing something by 0.
2. 2. TypeError, when an operation is performed on incompatible data types.
3. 3. ValueError, when an incorrect value is used in a function call or expression.
4. 4. NameError, when an identifier is used that has not been defined. In Python, define means that it has been assigned a value, even if the value is None.
5. 5. IndexError, when the index used to access a sequence is out of boundary.
6. 6. KeyError, when an incorrect key is used to access a dictionary value.
7. 7. AttributeError, when an object attribute is sued that does not exist.
8. 8. FileNotFoundError, when a file that one is trying to open to read does not exist. It is OK to open a file to write that does not exist. The operation will create a new file in that case.

In addition to syntax and runtime errors, you can also have logical errors in your programs. These errors can be found only by you or users of the program. An example of logical errors is when you are supposed to add two numbers, but you subtract one from the other instead.

Throughout the text, you will learn and gradually gain the ability to make your programs logically correct and to identify logical errors in your programs.

Design Algorithms to Solve Problems

An algorithm is a sequence of instructions showing steps to solve a problem or get something done. The recipe for cooking a dish is an example of an algorithm from our everyday lives. Unlike algorithms for people to follow, algorithms for computers must show definitive steps of explicit operation.

Consider a very simple task for a computer to complete: give a computer two numbers and ask the computer to find the sum and print out the result. The algorithm can be described as follows:

• [algorithm 1] Get two numbers from user, calculate, and print out the sum.
• Step 1. Get the first number to n1.
• Step 2. Get the second number to n2.
• Step 3. Calculate the sum of n1 and n2, and store the result to s.
• Step 4. Print out s.
• [end of algorithm 1]

Describing the steps of operations as shown above is just one way to present algorithms. In computing and software development, algorithms can also be, and more often are, presented using pseudocode or a flowchart.

Pseudocode is a language that is easier for humans to understand but that is written like a computer program. There is no widely standard vocabulary and grammar for pseudocode. However, within an organization or even a class, the same pseudocode language should be used for collaboration and communication.

The above algorithm can be described in pseudocode as follows:

• Start
• Input from user → n1 # get an input from user and assign it to n1
• Input from user → n2 # get another input from user and assign it to n2
• n1 + n2 → s # n1 + n2 and assign the sum to s
• print(s)
• End

This simple algorithm can also be described using a flowchart, as in Figure 1-7.

In problem solving and computing, conditional operations and repetitive operations are often needed. An example is to calculate the sum of number 1, 2,…10000. One might think that the sum could be calculated by writing 1 + 2 + 3 + … + 10000, but that is wrong because that mathematical expression cannot be precisely understood by computers. The correct algorithm should be:

• [algorithm 2] Calculate the sum of all positive integers that are no greater than 10000.
• Step 1. 1 → i, 0 → s
• Step 2. s + i → s, i +1 → i
• Step 3. If i <= 10000 go to step 2 # loop back and make repetition under condition

• Step 4. Print s
• [end of algorithm 2]

In pseudocode, the algorithm can be described as follows:

• Start
• Initialization: i = 1, s = 0
• Repeat
•    s = s + i
•    i = i + 1
• Until i > 10000
• End

The algorithm can be depicted using a flowchart, as in Figure 1-8.

When programming to solve a problem, first develop an algorithm describing the steps of how the problem can be solved using computers, even if it is not explicitly and formally formulated as above.

Phases of Software System Development

Algorithm design and representation are essential when programming for computers to solve a problem or complete a task, but it is only part of software system development. Developing a software system to satisfy the requirements of a client requires several phases.

Set Up Git on Your Computer and Version-Control Locally

Git can be freely downloaded from https://git-scm.com/downloads and installed on your computer. After installing Git, you can create a local Git repository on your computer by running the git init command within a shell window such as CMD or PowerShell on Windows. A preferred one is Git-Bash shell, which comes with Git. It can be started within Windows File Explorer.

For example, if you want to start a project called Learn_Python, you can create a folder called Learn_Python on your desktop within Windows File Explorer, then right-click the folder icon, and choose from the pop-up menu. A Git-Bash window will open with Learn_Python as the current working directory, as shown here:

Within this Git-Bash shell window, you can run the following command to initialize:

You have to run this Git command once to create a local repository for a project. It will create an empty Git repository on your local computer, which is a directory named .git with specific subdirectories and files that Git will use to version-control your project files. It will also create a master/main branch for the project. Other branches can be created if the project is divided into smaller ones to be worked on in parallel and then later merged.

Before running the command, you can set up an environment variable called $GIT_DIR to determine where the local repository will be placed on your computer. If $GIT_DIR is not set, the local Git repository—that is, the .git subdirectory—will be created right under the current working directory; if $GIT_DIR is set in a different location of your choosing, .git will be created right under $GIT_DIR. The common location of .git for a project is right under the project directory.

For the system to know who has made changes to the files and how to communicate with them, the following two commands need to run to config the Git that you installed on your computer:

These commands will configure the user’s name and email address. Please keep in mind that this username is different from the username that you will use to sign up for your account with GitHub later in this section.

When changes have been made to a file and you want Git to manage the changes to the file, the first step is to stage the file by running the following command:

This is called “staging changes to the file,” which is the first step Git takes to version-control files.

For example, if you want to stage changes to all Python program files under the current project directory, run the following command:

To stage changes to all files and even subdirectories under the current working directory, run the following command:

The next step Git will take to version-control your project files is called commit. It is done by running the following command:

Now changes to the files have been committed to the local repository. Please note that the stuff inside the quotation marks behind option -m are the comments or notes about the changes. If you run Git commit without option -m, a text editor will pop up to let you enter comments.

You can check the status of your Git system by running the following command:

This shows that the file start.py has been staged but not committed yet. You can still use the git rm command to unstage the file (remove it from the staged list).

In the above, we basically described a process of making changes to a file, staging the files for the changes, and committing the changes to the repository. You may, and most likely want to, reverse the process to undo some changes.

To a file that has been staged but not committed, use the following command to unstage it:

or

To a file that has not been staged, use the following command to discard the changes to the file:

To revert a commit that has been made, run the following command:

To restore a file to one that is n versions back in the master branch of the repository, run the following command:

There are some other Git commands available for various needs of version control, and each has many options providing powerful functionalities. A list of these commands can be found at https://git-scm.com/docs/git#_git_commands. You can also get the GitHub-Git cheat sheet at https://training.github.com/downloads/github-git-cheat-sheet/.

For Git, files that have been staged or committed for changes are called tracked, and those that have not been staged or committed are called untracked. In software development, some files, such as those objects and executable files derived from code files, do not need to be tracked for changes, so they should be ignored by Git. To tell Git what files under a project directory can be ignored, especially when running the command to stage all, you can add the file names or ignore patterns to a special file called .gitignore right under the project directory. You need to manage the list in the .gitignore file by editing the file using a text editor. Details of ignored file patterns can be found from Git documentation at https://git-scm.com/docs/gitignore. For our purposes, it may be sufficient to just describe the files based on what you already know, such as a file name or file names with a wildcard such as *.log.

Note that unlike other version-control systems, Git does not work with files for different versions, but works only with the changes that led to the current version of the file. For each file, Git will only keep one copy of the file for its current version in its repository and keep only the changes that led to the current version for all older versions.

Set Up an Account on GitHub and Version-Control with Remote Repositories

With Git, you can also use remote repositories on GitHub, which is a web-based system that you can use to create, access, and manage your remote repositories on a GitHub server. The benefits of working on a remote repository like GitHub for a software development project are twofold: the first is that you do not need to worry about the possible loss of your computer or the corruption of the file system; the second is that a team of programmers can work on a project at the same time efficiently and globally.

To use the remote repository on GitHub, first create an account with GitHub.com. GitHub offers students use of their repositories free of charge but also provides a pack of paid professional tools for software development.

Once you have signed into GitHub.com, you can create a repository for each of your projects under your account. Once created, each repository will have a unique URL where project files can be synchronized between the local repository and the remote repository, which can be cloned/downloaded. A repository on GitHub can be either public or private. A private repository can be accessed only by the owner, whereas a public repository can be accessed by everyone on the internet. Because you will be using the remote repository for your assignment projects, you should choose private so that your assignment work will not be shared with any others. You can create public repositories for projects that are substantially different from projects in the assignments and interesting enough for others to collaborate with you on the projects.

Now you know how to create both a local repository and a remote repository, and you’ve learned how to use Git commands to move project files to and from the local repository.

To continue work on a remote repository for the version-control of project files, you need to tell the computer where the remote repository is by using the following Git command:

Git supports several network protocols to communicate between your local computer and remote repository servers such as GitHub, including SSH and HTTPS. Because using SSH requires additional setup on your computer, we recommend HTTPS. The following is an example of adding the remote repository previously created for Jupyter Notebooks to our local notebook repository for Jupyter Notebooks:

You can also use the following to delete a remote repository:

And you can use

to rename a remote repository.

You can also make changes to the URL of an existing repository, as shown in the following example:

To view which remote repository is configured for the current project, use the following Git command:

The command below initializes a git repository and adds remote notebooks:

The text below shows a git command to display the remote connections configured after running the commands above:

Between the local repository and the remote repository, project files can go in two directions. Moving files from the local to the remote repository is referred to as a push; moving files from the remote to the local repository is a pull or fetch. Between pull and fetch, pull is the default mode of moving files from remote to local, and fetch provides additional power, such as is needed when moving files from several repositories at the same time.

Please note that pull or push operations are not just transferring files. Key points of the operation are merging the changes to files in the target repository and versioning. Git has special commands for those key operations, but those operations often run behind the scenes without anyone noticing.

After you have added a remote repository to your project, you can push the already committed changes to the local repository by running the git push command in a shell terminal within the project directory, as shown here:

Sometimes you might be interested in a project in a repository and would like to make a local copy of the entire project. The operation of copying an entire project in a remote repository onto a local computer is called cloning. For example, say there is a repository called learn-python3 in GitHub containing sample code, and you want to download all the code to play with it. You can do that by doing the following:

1. 1. Open a terminal on a file folder in which the project is to be placed—say, the desktop.
2. 2. From GitHub.com, copy the HTTPS URL from the “Code” dropdown menu of the learn-python3 repository and run the following Git command:

   $ git clone https://github.com/michaelliao/learn-python3.git

   You will then have all the code samples on your computer.

To work with Git and GitHub, you can use Git GUI, a GUI-based system, by invoking Git GUI on the project folder within Windows File Explorer.

Another way, our preferred way to use Git and GitHub for versioning on both local and remote repositories, is to operate within VS Code, which has native support for Git and GitHub, as long as Git is properly installed on the local computer, as shown earlier in this section.

1. 1. Create a new folder on your local drive for a project.
2. 2. Open the folder from VS Code. The new folder can also be created when you open the file folder in VS Code.
3. 3. Initialize the local repository for the project by running git initialize in VS Code command palette by pressing Ctrl+Shift+P. Type “git” and click “git initialize.” You will be asked to do the following:
   1. a. Choose a local workspace folder to initialize.
   2. b. Set the email address of the programmer/developer/author.
   3. c. Set the name of the programmer/developer/author.

   Now the local repository is ready for versioning your project files locally.

4. 4. Create or copy project files under the project folder.
5. 5. Click the source control icon on the left navigation bar, type a brief message about the changes to the files or project, and press Ctrl+Enter or click the commit icon above.
6. 6. To push the changes to the project files and the project to the remote repository in GitHub, click the Git Sync icon at the bottom-left of the VS Code window.
   1. a. If this is the first time you are pushing the project to your GitHub account, the command palette dialogue will pop up and ask you to choose whether to publish the project into a public repository or private repository under your account. The project folder name will be used as the repository name by default, but you can use a different name.
   2. b. You may be asked to sign into your GitHub account if you have not accessed GitHub from VS Code before.
   3. c. You may also be asked to either use the existing username and email associated with your GitHub account or provide a different email and/or username to identify yourself as the author of the project being pushed.

If you have already created a repository for the project on GitHub, you can copy the URL of the repository and add the remote repository to the project in VS Code by running git add remote in the command palette. You will also be asked to provide a name for the remote repository after entering the URL.