Title ProblemSolvingwithAlgorithmsandDataStructures.pdf 4.2 MB 240
```                            Introduction
Objectives
Getting Started
What Is Computer Science?
Review of Basic Python
Summary
Key Terms
Programming Exercises
Algorithm Analysis
Objectives
What Is Algorithm Analysis?
Performance of Python Data Structures
Summary
Key Terms
Discussion Questions
Programming Exercises
Basic Data Structures
Objectives
What Are Linear Structures?
Stacks
The Stack Abstract Data Type
Queues
Deques
Lists
The Unordered List Abstract Data Type
Implementing an Unordered List: Linked Lists
The Ordered List Abstract Data Type
Summary
Key Terms
Discussion Questions
Programming Exercises
Recursion
Objectives
What is Recursion?
Stack Frames: Implementing Recursion
Visualising Recursion
Complex Recursive Problems
Exploring a Maze
Summary
Key Terms
Discussion Questions
Programming Exercises
Sorting and Searching
Objectives
Searching
Sorting
Summary
Key Terms
Discussion Questions
Programming Exercises
Trees and Tree Algorithms
Objectives
Examples Of Trees
Vocabulary and Definitions
Implementation
Priority Queues with Binary Heaps
Binary Tree Applications
Tree Traversals
Binary Search Trees
Summary
Key Terms
Discussion Questions
Programming Exercises
JSON
Objectives
What is JSON?
The JSON Syntax
```
##### Document Text Contents
Page 1

Problem Solving with Algorithms and
Data Structures

Release 3.0

September 22, 2013

Page 120

Problem Solving with Algorithms and Data Structures, Release 3.0

116 Chapter 3. Basic Data Structures

Page 121

CHAPTER

FOUR

RECURSION

4.1 Objectives

The goals for this chapter are as follows:

• To understand that complex problems that may otherwise be difficult to solve may have
a simple recursive solution.

• To learn how to formulate programs recursively.

• To understand and apply the three laws of recursion.

• To understand recursion as a form of iteration.

• To implement the recursive formulation of a problem.

• To understand how recursion is implemented by a computer system.

4.2 What is Recursion?

Recursion is a method of solving problems that involves breaking a problem down into smaller
and smaller subproblems until you get to a small enough problem that it can be solved trivially.
Usually recursion involves a function calling itself. While it may not seem like much on the
surface, recursion allows us to write elegant solutions to problems that may otherwise be very
difficult to program.

4.2.1 Calculating the Sum of a List of Numbers

We will begin our investigation with a simple problem that you already know how to solve
without using recursion. Suppose that you want to calculate the sum of a list of numbers such
as: [1, 3, 5, 7, 9]. An iterative function that computes the sum is shown below. The function
uses an accumulator variable (the_sum) to compute a running total of all the numbers in the
list by starting with 0 and adding each number in the list.

def list_sum(num_list):
the_sum = 0

117

Page 239

CHAPTER

SEVEN

JSON

7.1 Objectives

• To establish an overview of why we use JSON

• To understand the syntax of JSON

• Demonstrate how Python objects can be serialized into JSON using the native library

7.2 What is JSON?

JSON stands for Javascript Object Notation and is a lightweight format used for data inter-
change. What do we mean by this? Well, in the age of the world wide web it is fairly common
for different programs distributed across a network to wish to communicate and share data
with one another. This can cause problems however as there are a large number of different
programming languages in the wild. Its not hard to imagine a situation in which a program
written in Python might want to send an object to another program that is written in Java, but
the internal representations are going to be quite different. This can be a problem even when
developing an offline project, sometimes it is more convenient to actually write different parts
of a project in separate languages because they have different requirements that might be better
suited to separate languages.

Well, the obvious solution is to translate the format into an intermediate data type that can be
understood by both languages. JSON is one such format. Others include XML, SOAP and
YAML.

7.3 The JSON Syntax

JSON syntax is based around three simple data types. The first is a Name-Value pair which in
a programming language could be realised as an object, record, struct, dictionary, hash table,
keyed list, or associative array. A name-value pair looks as follows:

"first_name" : "Jacob"

235

Page 240

Problem Solving with Algorithms and Data Structures, Release 3.0

The name here can be any String, and is typically used to refer to the name of a property of a
particular object. The value can be one of the following:

• A number

• A String

• A Boolean

• A JSON Array

• An object

• null

The second type is the JSON Object. A JSON Object is a collection of name-value pairs or
Arrays encased in curly brackets.

{ "first_name":"Jacob" , "last_name":"Bellamy" }

Lastly, we have the JSON Array. A JSON Array roughly corresponds to a list in python. A
JSON array is a list of values encased in square brackets. For example:

{"courses": ["Compsci 101", "Compsci 105", "Compsci 107"]}

Putting it all together, suppose we have a fairly complex Object such as a student that we
wished to represent in JSON. This student has a name, id number, GPA, a list of courses they
are enrolled in, and a boolean representing whether their fees are paid, and an address. a JSON
representation of this object might look as follows:

{
"name":"Jacob Bellamy",
"id_number":3352976,
"gpa":8.2,
"courses":[

"Compsci 101", "Compsci 105", "Phil 101", "Maths 108"
],
"fees_paid":true