Skip to main content

About this book

The current text provides a clear introduction to Computer Science concepts in a programming environment. It is designed as suitable use in freshman- or introductory level coursework in CS and provides the fundamental concepts as well as abstract theorems for solving computational problems. The Python language serves as a medium for illustrating and demonstrating the concepts.

Table of Contents

Chapter 1. The World of Programming

Chapter 1 briefly introduces what should be known before starting to learn programming. The chapter first mentions the building blocks of a computer that are relevant to a programmer—i.e., the CPU, the memory and the Von Neumann architecture. The chapter continues by introducing how big the “zoo” of programming languages is, thereby presenting the different paradigms that the “zoo” of programming languages falls into. A discussion of the advantages and disadvantages of each paradigm follows where hints are provided to the programmer about how he may choose a programming language based on the nature of the problem. The chapter also talks about the way programs are written and put into action by a computer, after which Python is introduced with a brief historical background and a small interaction.
Göktürk Üçoluk, Sinan Kalkan

Chapter 2. Data: The First Ingredient of a Program

Chapter 2, on top of the basic knowledge provided in Chap. 1, gets the reader familiar with how “information” is represented by a computer in the form of “data”. The chapter starts by introducing why data is essential and how it relates to the representation of a real-world problem on a computer. Afterwards data is classified into two types based on their representational complexity and internals: “basic data” and “structured data”. After presenting the basic data types in details, the string, list, and tuple containers are introduced as structured data. While doing so, the chapter discusses how the different basic data types are represented internally by the computer and how the structured data is organized in the memory. As case studies, the corresponding data types in Python are introduced. Lastly, the chapter covers the concept of “variables”, i.e., names that can be used to store and access data in memory.
Göktürk Üçoluk, Sinan Kalkan

Chapter 3. Actions: The Second Ingredient of a Program

In this chapter the second ingredient of a program namely “actions” that programmers use to manipulate data for solving real-world problems are introduced. Actions are transformed into machine instructions, which are then decoded and executed by the CPU. After a brief discussion on the purpose and the scope of actions, different action types are introduced. An important part of Chap. 3 is devoted to expressions and their evaluation: regarding this, Church–Rosser property, side-effects and Dikstra’s “Shunting Yard Algorithm”, which is the most common expression evaluation method, are presented. The chapter also talks about the different operators that a programmer can use in expressions, the actions that can be used for controlling the flow of the program (i.e., conditionals) and the actions that can be reused again (i.e., functions). Like other chapters, the discussions and the presentations are supported by the case studies and examples in Python.
Göktürk Üçoluk, Sinan Kalkan

Chapter 4. Managing the Size of a Problem

This chapter pertains to how a programmer can deal with problems that involve actions on ‘bulky’ data. For such problems, a programmer has two choices: “recursion” or “iteration”. The chapter presents a meta-algorithm, a novel set of rules for the construction of a recursive solution to a world problem, and illustrates it with clear examples. As for iteration, the chapter covers all the basic types of iterative constructs (e.g., Premod-Posttest, etc.) that are widely used in the world of programming. Tips for the construction of an efficient iterative solution are also given. Finally, the advantages and disadvantages of recursion and iteration are discussed in depth. While covering recursion and iteration, examples and case studies are provided in Python.
Göktürk Üçoluk, Sinan Kalkan

Chapter 5. A Measure for ‘Solution Hardness’: Complexity

Often, for a single problem, no matter how simple or difficult it is, a programmer ends up with more than one plausible solution, and based on different constraints on development time, running resources such as memory and CPU power, the programmer needs to choose “the best” solution. In this chapter, the most widely used criteria, complexity, for choosing among alternative solutions is covered. The chapter focuses on running-time complexity of algorithms with which a programmer can estimate comparative performance of available algorithms without necessarily implementing them. The chapter talks about the different notations that are used for analyzing the complexity of algorithms and how they can be computed from any given algorithm.
Göktürk Üçoluk, Sinan Kalkan

Chapter 6. Organizing Data

Often, a programmer will need to organize data together based on the nature of the problem. In this chapter, these data types that are called “abstract data types” are covered. Abstract data types (ADTs) that are covered include stacks, queues, priority queues, bags, sets, lists, maps and trees. By means of a suitable notation These ADTs are formally depicted in terms of operations that define the ADTs. A big part of the chapter is devoted to trees, since they have more varieties both in terms of representation and type, and since they are often encountered in problems that require computationally efficient structured representations. Regarding trees, various application examples of the tree ADT (like Huffman coding, decision trees etc.) are discussed. The chapter is concluded with how ADTs can be represented in Python.
Göktürk Üçoluk, Sinan Kalkan

Chapter 7. Objects: Reunion of Data and Action

In the first chapters of the book, while implementing a solution to a world problem, data was separated from action. In this chapter, based on the analogy to objects in the real-world, data and action are combined in single representational entities that are called objects. This brings into the scene a new programming paradigm known as “object-oriented programming”. This chapter talks about the ideas and principles that govern object-oriented programming; namely, encapsulation, inheritance and polymorphism. Encapsulation means grouping actions and data together as objects for hiding the internal details of the objects from the outside world, i.e., other objects. Inheritance is the ability to define new objects based on already defined objects. Through inheritance, objects can share actions and data that help the programmer in organizing the solution in a modular and structured manner. Polymorphism, on the other hand, pertains to objects’ behaving differently (either as itself or as the object that it has inherited from) based on context and usage. Finally, how objects are defined in Python is presented and the properties of object-oriented programming are analyzed in Python with illustrative examples.
Göktürk Üçoluk, Sinan Kalkan
Additional information