Data References, Advanced Arrays and Searching

Data References, Advanced Arrays and searching

Today we will cover the following topics:

Review

Review – Warmup Task

• Create a concept map – Try to link the topics and tools covered.
• On a piece of paper try to draw a map, then check with the students on your table if it is correct.
• Feel Free to use some of the words below or add your own (Python related) Concepts – (Repetition, Functional Decomposition) Artefacts (Byproduct) – (Program, functions, diagrams, files) Actions – (Assignment, function call, condition evaluation) Terminology – (Local/global variable, parameter vs argument) You can clean this up and submit it for task 7.1

Concept Map Example

P. Conrad (2006) -

https://www1.udel.edu/CIS/474/pconrad/06S/topics /pbl/ConceptMapping/intoToConceptMapping.htm

Problem Scenario

Think about... You have:

• players = ["Tom", "Sara", "Leo", "Mina"] scores = [150, 200, 120, 180]
• Tasks:
• Find the highest score
• Print the name of the winner
• Find the rank of a given player

Advanced Arrays & Lists

• We will covered some Array Theory and then look at Lists in Python

Arrays in Concept

• What happens when we store an array of 5 strings in memory?
• We can store each of these items sequentially in the memory. Image Source – Ed

• What are the limitations with this? Can anyone figure it out?
• Keep in mind traditionally arrays have a fixed size. (Python Lists are dynamic, we will explain this later)
• We have a fixed size taken up in the memory.

Arrays in Concept

Static vs Dynamic

• A static array takes up a fixed amount of memory space, it's allocated continuous space for multiple variables of a given type. Image Source -

https://www.geeksforgeeks.org/dsa/how-do-dynamic- arrays-work/

Arrays in Concept

Static vs Dynamic

• A dynamic array will automatically copy the array to a new larger one and update as needed. Image Source -

https://www.geeksforge eks.org/dsa/how-do- dynamic-arrays-work/

Arrays in Concept

Dangers

• When we access an array it's possible to go out of bounds. When we do this, it can cause our program to crash, or even worse access data from memory elsewhere and cause unexpected behaviour.

Arrays in Concept

Dangers

• Accessing this memory address in C could return an unrelated value! Image Source -

https://www.geeksforgeeks.org/dsa/how-do-dynamic- arrays-work/

Arrays in Concept

2D Arrays

• What do you imagine when you think of 2D arrays?
• We can have an array of arrays to create a 2D array.
• What might this be useful for?

Arrays in Concept

2D Arrays Image Source – Ed

Arrays in Concept

2D Arrays Image Source – Neves, António & Barbosa, Bruno & Soares, Sandra & Dimas, Isabel. (2018). Analysis of Emotions From Body Postures Based on Digital Imaging.

Python Lists

• Lets look at some of the features in Python Lists
• Lists in Python are dynamic and automatically handled by the Python Memory Manager
• Keep in mind in other programming languages arrays you might need to manage the memory allocation of arrays yourself.

Lists are ordered

Lists are Mutable (Changeable)

Lists allow duplicates

List Comprehensions

List Methods

• https://www.w3schools.com/python/python_lists_methods.asp

Searching Arrays – Theory

• When an array has lots of data in it, we need to think about how we might find an item in it?
• What if we want to find a specific user from a list of users?
• Search for a score in a list of scores?
• We need to implement a function to search the list.

Linear Search – Pseudocode

Linear Search – Implementation

What are some problems with this implementation?

Binary Search

• I am thinking of a number between 1 and 100. Everytime you guess I will tell you if the number is higher or lower
• Try to guess what I am thinking of?
• How many guesses does it take?

Binary Search – Theory

Source: https://www.geeksfor geeks.org/dsa/binary-search/

Binary Search – Bonus

Try to implement your own Binary Search algorithm using this pseudocode Keep in mind the list must be pre-sorted. We will cover sorting in Week 9 so just use a pre-sorted list for now.

Searching Arrays – Python

Also see: Lecture for W6 and the

accompanying code.

Pointers, stack & heap

Theory

• We're going to look at what happens under the hood of the memory in the computer when a program runs.
• This is very important to know when working with low level languages like C or Rust.
• We will study it anyway because it is useful to know, but the Python Memory Manager will handle it behind the scenes when writing python programs.

Parameter Passing

Pass By Value

• Pass by value takes a copy of the variable and passes it to the called function or procedure:
• The original value is unchanged, a copy is made in the memory.
• Can be slower, have overhead for large copies.

Pass by Reference

• Instead of making a copy, the memory address of the original is passed to the function.
• Changes made to the data change the original. There is no backup.
• Faster for large objects but is less safe.

Python uses Pass by Object Reference

• In Python we pass not by reference or by value.
• In python everything is an object. Objects can be Mutable (changing) or Immutable (unchanging)
• Int, str, float etc are examples of Immutable data.
• Lists, objects are examples of mutable data.

Python Immutable Example

Python Mutable Example

Stack & Heap

Memory Diagram

Memory Diagram

Code Area

Memory Diagram

Stack

Memory Diagram

Heap

Garbage Collection

Theory

Garbage Collection Python

You don't need to manually delete a reference to an object unless you want to free up the space. Please note del doesn't delete it from memory, it deletes the reference so the GC will clean it up later. Python used a Garbage Collector to free up memory when no references to the data exist. It's automatic and behind the scenes.

Custom Project Design

It's time to start thinking about the design of your Custom Program. If you are unsure about what you want to do please reach out.

• Music player submission
• This is a major task, you will have to demonstrate and explain your code in order to pass.
• You MUST use While loops only for this task and will not pass if you use any other kind.

Problem Scenario – Can you solve it?

You have:

• players = ["Tom", "Sara", "Leo", "Mina"] scores = [150, 200, 120, 180]
• Tasks:
• Find the highest score
• Print the name of the winner
• Find the rank of a given player