4 - Sequences and iteration

Question 1

What are some of the operations used to create sequences in M269?

Answer 1

Slicing, concatenating, and sorting are operations used to create new sequences from existing ones in M269.

Question 2

How do you access a cell within a tuple table, and what are the alternative methods?

Answer 2

To access a cell in a tuple table, you first access the row and then the column. Alternatively, you can directly access the cell using indices, such as games_by_row[1][2] to access the cell in the 2nd row and 3rd column.

note that:
Indexing is left-associative, and the first index selects the row, while the second index selects the column.

Question 3

When problem-solving, what type of problem involves finding one or more items that satisfy specific criteria?

Answer 3

A search problem involves finding one or more items that satisfy certain criteria.

Question 4

What are the inputs and preconditions for the slicing operation?

Answer 4

Inputs: values (a sequence), start (an integer), and end (an integer). Preconditions: 0 ≤ start ≤ end ≤ │values│.

Question 5

What is a subsequence in a sequence?

Answer 5

A subsequence is a sequence that can be obtained from another sequence by deleting zero or more, not necessarily consecutive, items.

for example, in the sequence s = [1, 2, 3, 4, 5, 6, 7], the subsequence s1 = [1, 3, 5, 7] is obtained by deleting certain items from s.

Question 6

What does the indexing operation allow you to do with a sequence, how is it written, and what is its time complexity in M269?

Answer 6

The indexing operation allows you to retrieve an element from a sequence using its index.

In mathematics, it’s written as “𝑠𝑖” for a sequence s and index i, while in computing, it’s more commonly denoted as “s[i].”

In M269, the indexing operation is assumed to have a constant time complexity because all data is stored in RAM, Any RAM position can be accessed in the same time, so we assume that indexing takes constant time..

Question 7

In problem-solving, what type of problem involves checking a property of the input and making a decision?

Answer 7

A decision problem involves checking a property of the input.

Question 8

What is the worst-case complexity of lexicographic comparison operations on sequences?

Answer 8

The worst-case complexity is Θ(min(│left│, │right│)) because it may take until the end of the shorter sequence to make a decision in a worst-case scenario.

Question 9

What is the output of the slicing operation, and what are the postconditions?

Answer 9

Output: substring (a sequence). Postconditions: If start = end, then substring is (), otherwise substring includes items from values[start] to values[end - 1].

Question 10

What is a key feature of the list data type in Python, and how does it compare to other sequence types like tuples, strings, and ranges?

Answer 10

Lists in Python are mutable, meaning they can be modified, and they may contain heterogeneous elements. All operations that work on tuples also work on lists.

Question 11

What are some common aspects to consider when testing sequences, and what are the elements to test for?

Answer 11

When testing sequences, it’s important to consider edge cases, including testing with an empty sequence (if allowed by precondition) and a single element in the sequence.

Additionally, test for both odd and even length sequences, as operations might behave differently in these cases.

If preconditions allow, test with duplicate items, unique items, heterogeneous sequences (different data types), and homogeneous sequences (same data types).

Question 12

What is a substring in sequences?

Answer 12

If sequences s1, s2, s3, and s satisfy s1 + s2 + s3 = s, then s2 is a substring of s.

Question 13

What is lexicographic comparison in the context of sequences?

Answer 13

Lexicographic comparison of two sequences involves pairwise comparison of items, one by one, until a decision can be made.

It continues until items differ or one sequence ends before the other. If two sequences are equal until one ends, the shorter sequence is considered ‘less than’ the longer one.

Question 14

What does the concatenation operation do in M269?

Answer 14

The concatenation operation in M269 forms a new sequence by joining both input sequences, written as left + right.

Question 15

What’s important to remember about operations on strings in M269?

Answer 15

Operations on strings are carried out on a character by character basis, not the entire string sequence. This is crucial when considering algorithms that use the string data type.

Question 16

What defines a sorted sequence?

Answer 16

A sequence is sorted if it is ordered by ascending or descending value and requires all items to be pairwise comparable.

Question 17

How can sequences be categorized in terms of data types?

Answer 17

Sequences can be categorized as:

• homogeneous - with all items of the same data type
• heterogeneous - with items varying in data types.

Question 18

How is the size of a sequence typically stored and updated in memory and what is the complexity of looking up the size of a sequence?

Answer 18

The size of a sequence is typically stored in memory along with the sequence, and it is computed and updated when the sequence is created and modified.

with these asumptions the size/length operation can look up the size in constant time, which means it has a constant time complexity.

Question 19

What is the runtime complexity of the concatenation operation in terms of the lengths of the input sequences?

Answer 19

The runtime of concatenation is proportional to the number of items copied, which is │left│ + │right│.

It has a linear runtime in the total length of the inputs: Θ(│left│ + │right│).

Question 20

How does Python perform lexicographic comparison on strings?

Answer 20

Python’s lexicographic comparison of strings uses the character ordering of the Unicode standard.

Question 21

What is a linear search, and what does it involve?

Answer 21

A linear search is an algorithm used to systematically go through a sequence and check each element to find one or more elements that match a given condition. It’s commonly used to solve search problems involving sequences.

Question 22

What is the output of the concatenation operation, and what are the postconditions?

Answer 22

Output: joined (a sequence).

Postconditions: joined is formed by copying all items of left and all items of right in order.

Question 23

What is the complexity of the slicing operation, and why does it have this complexity?

Answer 23

The complexity of the slicing operation is Θ(end - start).

This complexity arises because the operation copies all items in the slice to a new sequence. The time it takes to copy the items is directly proportional to the size of the slice, which is determined by the difference between the end and start indices. Therefore, the complexity is linear in the size of the slice, and it’s denoted as Θ(end - start).

Question 24

What is a search problem, and how is a linear search performed?

Answer 24

A search problem involves finding items in a sequence that satisfy specific conditions.

A linear search checks every item of the sequence one by one to find the desired items.

Question 25

What are the inputs and preconditions for the concatenation operation?

Answer 25

Inputs: left (a sequence) and right (a sequence). Preconditions: True.

Question 26

What are the inputs and outputs of the indexing operation

Answer 26

The indexing function takes a sequence and an index as inputs

The indexing operation returns the value from that sequence, as the abstract data type (ADT) “object” is used to represent the data type being returned.

Question 27

How does the “in” operator work with tuples, and what does it check for?

Answer 27

The “in” operator checks for membership in tuples, not for substrings as in strings. If an element is a member of the tuple, it returns true.

Question 28

What is a sequence?

Answer 28

A sequence is an ordered collection of zero or more items.

Question 29

What is the significance of including a comma when concatenating tuples in Python, and why is it important?

Answer 29

When concatenating tuples in Python, including a comma is essential to indicate that you’re working with a tuple with a single element.

Omitting the comma can lead to unintended results, such as the sum of the elements rather than tuple concatenation.

For example, (3) + (4) results in 7, while (3,) + (4,) gives the correct result of (3, 4).

Question 30

What is the difference in performance between an algorithm with linear complexity and one with quadratic complexity as the input size increases?

Answer 30

When the input size doubles, a linear algorithm takes double the time, while a quadratic algorithm takes 2² = 4 times as long.

If the input is a thousand times as long, a linear algorithm takes a thousand times as long, but a quadratic algorithm takes 1000² = 1,000,000 times as long.

This demonstrates that a quadratic algorithm becomes significantly slower than a linear one as the input size increases.

Question 31

How do you define a prefix and suffix in sequences?

Answer 31

If sequences s1 and s2 satisfy s1 + s2 = s, then s1 is a prefix of s, and s2 is a suffix of s.

Question 32

What are the characteristics of tuples in Python?

Answer 32

Tuples in Python are immutable, possibly heterogeneous, and may contain other tuples, allowing them to represent tabular data.

Question 33

What are some functions that allow us to obtain information about a sequence?

Answer 33

Functions related to sequences include:

• size
• indexing
• membership
• comparison.

Question 34

What kind of problem in problem-solving requires assigning a category to each input?

Answer 34

A classification problem involves assigning a category to each input.

Question 35

What does the “Membership” operation in inspecting sequences check, how is it written, and what are its best-case and worst-case complexities?

Answer 35

The “Membership” operation checks if a value “v” is an element of a sequence “s.”

It can be written as “v in s” or “v ∈ s.”

The best-case complexity is Θ(1) when the value is the first element, requiring one comparison.

The worst-case complexity is Θ(│values│), which occurs when the value is the last element or not in the sequence, resulting in a linear time operation.

Question 36

What is the best-case complexity of lexicographic comparison operations on sequences?

Answer 36

The best-case complexity is Θ(1) because a decision can be made after one comparison in the best-case scenario.

Question 37

What does the slicing operation do with a sequence?

Answer 37

The slicing operation extracts a consecutive sequence of items from the input sequence.

Question 38

What does the size of a sequence represent and how is it written in english/maths?

Answer 38

The size of a sequence s, denoted as │s│, represents the number of elements in the sequence.

Question 39

What is an in-place algorithm?

Answer 39

An in-place algorithm works directly on the input/output sequence, without using an additional sequence.

Question 40

What can lead to unexpected behavior when comparing strings in Python?

Answer 40

Unexpected behavior can occur in string comparisons when, for example, ‘A-Z’ comes before ‘a-z’ in Unicode, resulting in cases like ‘aardvark’ < ‘Zeus’ returning False.

Question 41

When can the minimum and maximum operations be applied to determine the smallest and largest values in a sequence?

Answer 41

The minimum and maximum operations can be applied to determine the smallest and largest values in a sequence when the items of the sequence are pairwise comparable, meaning each item can be compared to every other item.

Question 42

What are the input and output of the “Membership” operation in inspecting sequences?

Answer 42

The input for the “Membership” operation is a sequence “values” and a value “v” to check for membership.

The output is a Boolean, “is member,” which is true if and only if there’s an integer index such that “values[index] = value.”

Question 43

How is the complexity of a loop determined

Answer 43

the complexity of a loop is determined by the number of iterations multiplied by the complexity of the instructions within the loop. The general rule is that the complexity of a loop is Θ(I x e), where I is the number of iterations, and e is the complexity of the loop’s body.

Question 44

What are the characteristics of Python’s
* str,
* range,
* tuple,
* and list types,
*
* and how can tuples and lists be used to represent tables?

Answer 44

• str is immutable and represents immutable strings.
• range represents immutable sequences of integers.
• tuple represents immutable sequences,
• while list represents mutable sequences.

Tuples and lists can contain items of any type, including other tuples or lists, making them suitable for representing tables in Python.

Immutable types like str and range cannot be modified, so operations like replacing and removing elements are not possible.