4 - Sequences and iteration Flashcards
What are some of the operations used to create sequences in M269?
Slicing, concatenating, and sorting are operations used to create new sequences from existing ones in M269.
How do you access a cell within a tuple table, and what are the alternative methods?
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.
When problem-solving, what type of problem involves finding one or more items that satisfy specific criteria?
A search problem involves finding one or more items that satisfy certain criteria.
What are the inputs and preconditions for the slicing operation?
Inputs: values (a sequence), start (an integer), and end (an integer). Preconditions: 0 ≤ start ≤ end ≤ │values│.
What is a subsequence in a sequence?
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.
What does the indexing operation allow you to do with a sequence, how is it written, and what is its time complexity in M269?
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..
In problem-solving, what type of problem involves checking a property of the input and making a decision?
A decision problem involves checking a property of the input.
What is the worst-case complexity of lexicographic comparison operations on sequences?
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.
What is the output of the slicing operation, and what are the postconditions?
Output: substring (a sequence). Postconditions: If start = end, then substring is (), otherwise substring includes items from values[start] to values[end - 1].
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?
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.
What are some common aspects to consider when testing sequences, and what are the elements to test for?
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).
What is a substring in sequences?
If sequences s1, s2, s3, and s satisfy s1 + s2 + s3 = s, then s2 is a substring of s.
What is lexicographic comparison in the context of sequences?
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.
What does the concatenation operation do in M269?
The concatenation operation in M269 forms a new sequence by joining both input sequences, written as left + right.
What’s important to remember about operations on strings in M269?
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.
What defines a sorted sequence?
A sequence is sorted if it is ordered by ascending or descending value and requires all items to be pairwise comparable.
How can sequences be categorized in terms of data types?
Sequences can be categorized as:
- homogeneous - with all items of the same data type
- heterogeneous - with items varying in data types.
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?
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.
What is the runtime complexity of the concatenation operation in terms of the lengths of the input sequences?
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│).
How does Python perform lexicographic comparison on strings?
Python’s lexicographic comparison of strings uses the character ordering of the Unicode standard.
What is a linear search, and what does it involve?
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.
What is the output of the concatenation operation, and what are the postconditions?
Output: joined (a sequence).
Postconditions: joined is formed by copying all items of left and all items of right in order.
What is the complexity of the slicing operation, and why does it have this complexity?
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).
What is a search problem, and how is a linear search performed?
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.
