chapter5_python.md

theme	_class	paginate	backgroundColor	footer	marp
gaia	lead	true		Computational Thinking and Social Science | :copyright: Matti Nelimarkka | 2023 | Sage Publishing	true

<style> footer { font-size: small; } </style>

Chapter 5

Data structures in Python

---

Learning goals

• Identify the differences among variables, lists, and dictionaries
• Be able to add items to lists and dictionaries, and remove them
• Use for statements with lists and dictionaries
• Simplify problem solving using listsand dictionaries as abstractions
• Examine the computational complexity of an algorithm
• Evaluate whether solving a given problem computationally is feasible through back-of-envelope calculations.

---

List

Lists allow storing several values in one variable.

Each value is stored in a pre-defined index.

---

List

Lists can

• add new values to it
• remove old values from it
• recall or change values on it
• go through all values stored on it

Lists are indexed.

---

List

names_list = [ 'Cat', 'Dog', 3.1415, 'Pie' ]

for name in names_list:
  print( "Say hello to", name )
  print( name, "says: Hi." )

---

List

List help with

1. conducting the same operation to various variables
2. cleaning and making the code more readable
3. storing unknown number of variables
4. working on data which is indexed

---

Conducting same operations

---

Cleaning code

---

Storing unknown number of items

---

Dictionary

Dictionaries store key, value pairs. It is easy to access the value by a given key.

---

Dictionary

Dictionaries can

• add new values to it
• remove old values from it
• recall or change values on it
• go through all values stored on it

Dictionaries have keys and corresponding values.

---

Dictionary

---

Dictionary

Remember to manage cases where a key does not have a corresponding value.

---

Dictionary

1. maintaining a static mapping between two related ideas
2. serving as a meta variable, such as gatherer when there are several different cases

---

Dictionary

---

Dictionary

---

Dictionary

---

The limits of computing

---

The limits of computing

• Computing resources are limited: there are time and memory constrains that impact how we solve a problem.
• As the number of items in the list grows, it takes more and more time to go through the entire list through.
• $\mathcal{O}$ measures the order of growth, algorithm’s resource requirements in relation to input size (often $n$).
• Analysis is simplified to the highest polynomial only, as it is the only significant factor when $n$ is high.

---

Addressing the limits of computing

• Code optimisations: choosing better data structures, examining if approaches can be improved
• Profiling code: examining where code bottlenecks are and improving them specially

---

Review questions

1. What operations does a list involve?
2. What operations does a dictionary perform and allow?
3. What are the similarities and differences between lists and dictionaries?
4. In what circumstances do you need dynamic data structures?
5. In what kinds of cases would you use these data structures for working with networks?
6. In which types of cases would you use them for analysing data algorithmically?

---

Review questions

7. In what cases should you pay attention to the algorithmic complexity of code?
8. List the following levels of algorithmic complexity in order from lowest to highest: $\mathcal{O}(n2)$, $\mathcal{O}(n)$, $\mathcal{O}(2n)$, $$\mathcal{O}(1)$.
9. Go through five pieces of example code and estimate their algorithmic complexity.
10. Write pseudocode that has $\mathcal{O}(n)$ complexity and a piece of pseudocode that has $\mathcal{O}(n3)$.