Download ProblemSolvingwithAlgorithmsandDataStructures.pdf PDF

File Size4.2 MB
Total Pages240
Table of Contents
	Getting Started
	What Is Computer Science?
	Review of Basic Python
	Key Terms
	Programming Exercises
Algorithm Analysis
	What Is Algorithm Analysis?
	Performance of Python Data Structures
	Key Terms
	Discussion Questions
	Programming Exercises
Basic Data Structures
	What Are Linear Structures?
	The Stack Abstract Data Type
	The Unordered List Abstract Data Type
	Implementing an Unordered List: Linked Lists
	The Ordered List Abstract Data Type
	Key Terms
	Discussion Questions
	Programming Exercises
	What is Recursion?
	Stack Frames: Implementing Recursion
	Visualising Recursion
	Complex Recursive Problems
	Exploring a Maze
	Key Terms
	Discussion Questions
	Programming Exercises
Sorting and Searching
	Key Terms
	Discussion Questions
	Programming Exercises
Trees and Tree Algorithms
	Examples Of Trees
	Vocabulary and Definitions
	Priority Queues with Binary Heaps
	Binary Tree Applications
	Tree Traversals
	Binary Search Trees
	Key Terms
	Discussion Questions
	Programming Exercises
	What is JSON?
	The JSON Syntax
Document Text Contents
Page 1

Problem Solving with Algorithms and
Data Structures

Release 3.0

Brad Miller, David Ranum

September 22, 2013

Page 120

Problem Solving with Algorithms and Data Structures, Release 3.0

116 Chapter 3. Basic Data Structures

Page 121




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


Page 239




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

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"


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",

"Compsci 101", "Compsci 105", "Phil 101", "Maths 108"
"address": {

"street_address": "1 Horse Lane",
"city": "Auckland",
"post_code": 0632


236 Chapter 7. JSON

Similer Documents