A2 Theory W5 Flashcards
Define the concept of an iterator and explain how it works. Then, describe a scenario where and how iterators are helpful. Finally, explain what needs to be done to make an iterator class in Python.
An iterator is a programming concept used to traverse and process elements sequentially in a collection or container, such as lists, arrays, or custom data structures without exposing the underlying details of the containers instructions.
Iterators work by providing two essential methods:
1, __iter__: this method initializes the iterator and returns the iterator object itself. It is called when you create an iterator for collection.
2, __next__: This method is used to retrieve the next element in the collection. It should raise a ‘StopIteration’ to signal the end of the iteration.
Consider a scenario where you have a large dataset, like a database query result, and you want to process the records one by one without loading the entire dataset into memory. Using an iterator, you can fetch and process records efficiently, one at a time, without consuming excessive memory. This is particularly useful when working with streaming data or handling large files.
To create an iterator class in python, you need to define a class with the following methods:
__iter__: returns the iterator object itself which is typically ‘self’, this indicates that the class is iterable
__next__: This method should implement the logic to retrieve the next element in the sequence. When there are no elements, it should raise a ‘StopIteration’ exception.
Define the concept of an iterable in Python and explain how it works. Then, provide examples of intrinsic Python iterable classes and describe how they are used. Finally, explain the difference between an iterable and an iterator in Python, and provide an example to illustrate the difference.
An iterable in python is an object that can be looped over or iterated through, allowing access to its elements one at a time. Iterables are an essential concept in Python and are commonly used in loops, such as ‘for’ loops, list comprehensions, and generator expressions. To be considered iterable, an element must implement the __iter__ method, which returns an iter.
An iterable object works by:
1, Iterable object: An iterable object is an instance of a class that implements the _iter__ method. This method returns an iterator object
2, Iterator object: An iterator is an object that implements the __iter__ () and __next__() methods, the __next__() method returns the next element form the iterable when there are no more elements to return and raises a Stopiteration.
Some intrinsic Python iterable classes and how they are used:
1, lists:
2, Tuples:
3, Strings:
4, Dictionaries:
5, Sets:
- An iterable is an object that can be iterated over and typically implements the __iter__() method to return an iterator. It defines how to get an iterator from itself.
- An iterator is an object that keeps track of the current state of the iteration and implements both the __iter__() and __next__() methods. It defines how to get the next element in the sequence and when to stop iterating.
What are the key points one has to keep in mind when making a class iterable (classes and methods to use)?
When designing a class to be iterable you need to keep the following key points in mind:
1, Implement the __iter__() method:
- To make a class iterable, it must implement the __iter__() method, this method returns an iterator object.
- Inside the __iter__() method, you typically initilaize any necessary state for iteration and return ‘self’ as the iterator.
2, Implement the __next__() method for the iterator:
- If your iterable class is also the iterator itself(which is common), you should implement the __next__() method within the same class
- The __next__() method should return the next element of the iteration or raise the StopIteration exception when there are no more elements
3, Initialization and State management:
- Initilaize any necessary state variables in the constructor of your class. This state might include information about the current position of the iteration
- Ensure that the state is properly updated in the __next__() method as you iterate through the elements
4, Handle iteration termination:
- In the __next__ method, check for the condition when there are no more elements to iterate over. when this condition is met, raise the StopIteration exception to signal the end of iteration
- You can use other exceptions to indicate specific error conditions if needed
5, Support multiple iterations:
- Ensure that your iterable class can be iterated over multiples times. To achieve this, you might need to reset the internal state when the __iter__ method is called again
6, Testing and validation:
- Thoroughly test your iterable class to ensure that it behaves as expected in various iteration scenarios
- Make sure it handles corner cases gracefully, such as an empty collections or stopping iteration manually
7, Use cases and doumnetation:
- clearly state how your iterable class should be used, including any requirements for the object it contains.
- Consider the typical use cases for your iterable and design it to meet those use cases effectively.
In Python, what do you need to do in order to augment your collection of elements with an iterator?
To augment a collection of elements with an iterator:
1, Create a collection class: Define a class that represents your collection of elements. This class should implement the __iter__() method
2, Implement the __iter__() method: Inside the __iter() method of the collection class, reutrn an iterator object. This iterator object can be either the collection class itself or a seperate iterator class.
3, Implement the __next__() method: This is only if using a seperate iterator class, this method is repsonsible for returning the next element of the collection during iteration and raising the StopIteration exception when there are no more elements.
4, Initialize state: If your collection class and iterator class are seperate, ensure you initialize any neccessary state variables, such as current position in the collection, in the constructor of the iterator class
5, make the collection iterable: Instantiate your collection class and use it in a loop or any context where iteration is needed. Pythons ‘for’ loop will automatically call the __iter__() method to obtain an iterator and use it to loop through the elements
You can also make the collection class itself an iterator by having it implement both the __iter__ and __next__ methods within the same class, eleiminating the need for a seperate iterator class if it’s not neccessary for your case.
If implemented properly in Python, how should your iterator inform Python that there are no more elements in the collection to iterate through?
In python, when an iterator has no more elements to iterate through, it should inform Python by raising the “stopIteration’ exception in the __next__() method. This is the standard and expected way to signal the end of iteration.
The __next__() method checks wether there are more elements to iterate through by comparing the current index to the length of the data. If there are no more elements, it returns the next element. When there are no more exceptions to iterate through, it raises the StopIteration exception to signal the end of iteration.
What is a generator in Python, and how is it different from an iterator?
In python, a generator is a special type of iterable that allows you to iterate over potentially large or infinite sequence of values without precomputing and storing all of them in memory. Generators are defined using functions with the yield keyword. When you call a generator function, it returns an iterator that you can use to generate values one at a time as needed. This is in contrast to iterators, which typically have their elements precomputed and stored.
Main differences between generator and iterator:
1, Definition:
- A generator is defined using a special function called a generator function, which contains one or more yield statements. When a generator function is called, it returns a generator iterator.
- An iterator is an object that implements the __uter__() and __next__() methods. IT can be created from any iterable object likes lists or tuples.
2, Memory efficiency:
- Generators are memory-efficient because they generate values on the fly as you iterate over them. The don’t store the entire sequence of values in memory at once.
- Iterators on the other hand often require the entire sequence of values to be precomputed and store in memory
3, Lazy evaluation:
- Generators use lazy evaluation, which means they only compute and yield values when requested. This is useful when dealing with large data sets and infinite sequences.
- Iterators are usually eager, meaning they computer and store all values in memory before iteration begins.
4, State preservation:
- Generators automatically preserve their natural state between iterations, when you resume iteration, it continues from where it left off.
- Iterators may or may not preserve state, depending on their implementation. Many iterators are stateless and start form the beginning upon each iteration.
When you call __next__() on the generator, it computes and yields the next value. In contrast, the iterator created from a list precomputes all values and calling next() retrieves the next precomputed value.
How can you use the yield keyword to create a generator function in Python?
The yield keyword in python is used to create a generator function. When a function contains one or more ‘yield’ statements, it becomes a generator function. Generator functions allow you to generate values on the fly and are particularly useful when dealing with large data sets or infinite sequences.
Here how to create a generator function from yield keyword:
- define a regular function
- use yield keyword inside the function to yield a value, yield statement temporarily suspends the functions execution and returns the yielded value to the caller.
- the function can continue execution from where it was suspended when called again, preseving local state
- continue using the yield keyword to yield more values if needed
- generator function automatically raises a stopIteration when there are no more values to yield
Using the yield keyword in a generator allows you to create iterators that are memory efficient and can handle potentially larger or infinite sequences of values.
What are the advantages of using generators over lists or other iterable objects in Python?
Generators offer several adavantages over lists or other iterable objects, especially when memory efficiency, lazy evaluation and the ability to with large numbers are important. Here are some advantages of using generators:
1, Memory efficient: Generators are memory efficient because they generate values on the fly as you iterate over then, they don’t store the entire sequence of values in memory at once. Makes them suitable for large data sets that won’t fit into memeory
2, Lazy evaluation: Generators use lazy evaluation, meaning they wait to be told which values to iterate over rather than going ahead and precomputing those values and storing them. Again, this is helpful when dealing with large data sets that won’t fit into memeory.
3, Performance: Generators can provide better performance in scenarios where you only need to process a subset of data, as they avoid unnecessary computation and memory allocation. They are often faster than creating and manipulating lists or other data structures.
4, Avoid upfront computation: With generators, you can avoid the overhead of computing and storing all values upfront, especially when some values may never be used.
5, State preservation: Generators automatically preserve their internal state between iterations. When you resume iteration, it continues where it left off. Making generators useful for implementing stateful iterators.
6, Infinite sequences: Generators are ideal for representing and working with infinite sequences or streams of data. You can keep generating values as long as needed.
7, Ease of use: Generators are easy to implement using the yield keyword. They provide a clean and concise way to define iterators without the need for explicit iterator classes.
8, Reduced memory footprint: When working with large data, generators allow you to process data in chunks or batches, reducing memory usage compared to loading the entire data set into memory.
9, Composition: Generators can be compose and chained together to create complex data processing pipelines, this promotes modular and reuseable code.
10, Stream processing: Generators are well suited for stream processing, where data is continoussly processed as it becomes available.
While generators offer these advantages, it’s important to note that thy may not be suitable for all scenarios. If you need random access to elements, need to modify the data, or want to perform multiple iterations over the same data, using lists or other iterable objects may be more appropriate.
How can you use the for loop to iterate over an iterator or generator in Python?
In python, you can use a for loop to iterate over an iterator or generator in a straightforward and intuitive way. The for loop automatically calls the __iter__() method to obtain an iterator from the iterable and the uses the __next__() method to retrieve each element in the sequence. The loop continues until the iterator raises a SopIteration exception, signalling the end of the iteration.
Wether working with generators or iterators, using a for loop simplifies the process of iterating through elements, making your code more readable and pythonic.
Consider the following Python generator function called mystery . What does this function do? Analyze the time complexity of its single run in terms of the input size n. How does the use of the yield keyword and the conditional statement affect the output of the function? Provide some examples of input values and their corresponding output values. Finally, explain some potential use cases for this generator function.
This function generates a sequence of numbers starting from 0 up to the input value of ‘n’ where n is the size of the input. Specifically when the value ‘i’ becomes a mutiple of 5 during iteration, it is incremented by 2 instead of 1.
Time complexity of this finction:
- the generator function runs O(n) time because it iterates from 0 to n-1 and yields each value once. Therefore, it has a linear time complexity
The yield keyword and condition statement affects the output in the following way:
- When ‘i’ is not a multiple of 5, the function yields ‘i’ as is, this means it yields consecutive numbers from 0 up to n-1 without any midification.
- When ‘i’ becomes a multiple of 5, it is incremented by 2 before being yielded. This means that multiples of 5 in the output sequence will have a gap of 2 between them.
Examples of input and corresponding outputs:
- n = 10 will yield an output of [0, 1, 2, 3, 4, 7, 8, 9]
- n =15 will yield an output of [0, 1, 2, 3, 4, 7, 8, 9, 12, 13, 14]
Potential uses for this fucntion:
- when you need t iterate over a range of numbers and perform some operation on them, skipping certain values based on a condition
- when you want to create custom sequence of indices for accessing elements in a data structure, and you want to introduce specific patterns or gaps in the indexes
- when you need to simulate or model a sequence of events where certain events occur regularly but with gaps in their timing.
What is the complexity of a given operation on a given Linked ADT? Examples: push/pop operation on a linked stack, append/serve operation on a linked queue, etc.
The time complexity of operations on a linked data structure depends on the specific operation and the underlying data structure, example below:
1, push/pop on linked stacks:
- push: O(1) time complexity, it involves creating a new node and updating the references, both of which takes constant time.
- pop: O(1) time complexity, involves simply removing the top node and updating references
2, append/serve operation on linked queue:
- append: O(1) time complexity, it involves creating a new node, updating the rear reference and adjusting the next poiner of the current rear node, which all take constant time
- serve: O(1) time complexity, it involves updating the front of the reference to point to the next node in the queue
3, insertion/deletion at a specific position in a linked list:
- inseetion: O(n) time complexity in the worst case, where ‘n’ is the number of nodes in the list. This is necasue you may need to traverse the list to find the position where you want to insert.
- deletion: O(n) time complexity in worst case, as you may need to traverse the list to find the node to be deleted.
Give a summary of what Abstract Data Types are, and explain what their main advantages and disadvantages are. Exemplify your explanation.
ADT’s are high level data structures that are defined by a set of operations and their behaviour rather than their implementation details. ADT’s provide a blueprint or a specification for how data should be organised or manipulated without specifying the underlying data structures or algorithms used to implement them. They are a fundamental concept in computer science and SE, serving as a way to abstract and encapsulate data and operations.
Summary of ADT’s:
- definition by behaviour: ADT’s are defined by the set of operations they support and the behaviour of those operations. These operations can include creation, insertion, deletion, traversal, searching and more depending on the specific ADT.
- Encapsulation: ADT’s can encapsulate data and operations in to a single unit, allowing users to interact with the data in a well-defined manner without needing to understand the internal details.
- Implementation independence: ADT’s separate the interface form the implementation. This allows for flexibility in choosing different implementations based on the specific needs of an application.
Advantages of ADT’s:
- modularity and abstraction: ADT’s promote modularoty and abstraction in software design. They allow you to encapsulate data and operations into reuseable components, making code more organized and maintainable.
- Ease of use: ADT’s provide clear and well-defined interface for working with data, making it easier for programmers to understand and use the data structures correctly.
- Implementation flexibility: the separation of interface and implementation allows for flexibility in choosing the most appropriate data structure for a particular problem. You can switch implementations without affecting the code that uses the ADT.
- encapsulation: ADT’s hide the internal details of data structures, reducing the risk of unintentional modification or misuse of data.
Disadvantages:
- performance overhead: ADT’s may introduce a performance overhead compared to low-level data structures directly, as they add an additional layer of abstraction and indirection.
- Lack of customaization: some ADT’s may not provide the level of customaization or fine-tuning the low-level data structures offer, in certain situations, custom data structures might be needed for optimal performance.
- learning curve: Understanding and using ADT’s effectively may require a learning curve, especially for novice programmers who are not familiar with the concept.
- limited availaibility: ADT’s are predefined, and their usefulness depends on the available ADT’s. If specific ADT doesn’t exist for a particular problem, you may need to create a custom solution.
Given a simple arithmetic expression provided to you by your instructor, show how a stack-based calculator computes its result. Show all the states of the stack until it computes the final result. The expression should be given in the postfix notation stored as a list.
Example expression: [1, 2, +, 3, 4, +, -].
To compute this in reverse polish notation you can do so by the following steps:
- initilise an empty stack to store the intermediate results
- iterate through each element in the expression from left to right
- for each element: if it is a number, push it onto the stack, if it is an operator, pop the required number of operands form the stack, apply the operator to those operands and then push the result back onto the stack
Calculate example expression:
- start with an empty stack []
- process first number: push onto stack: [1]
- process second number: push onto stack [2]
- process first operator: pop the last two elements from the stack (1 and 2), add them together, and push result back onto stack: [3]
- process third number: push onto stack: [3,3]
- process 4th number: push onto stack: [3,3,4]
- process second operator: pop the last two values from the stack (4 and 3), add them, and push result back onto stack: [3,7]
- process third operator: pop the last two values from the stack(7 and 3), subtract them, and push the result back onto stack: [-4]
So the final result of the expression [1,2,+,3,4,+,-] in postfix notation is -4.
Summarise the main advantages and disadvantages of linked ADTs vs their array-based counterparts.
Linked ADT’s:
Advantages:
1, dynamic size: linked ADT’s can easily grow or shirnk in size during run time, as memeory allocation is typically handled dynamically. Makes them suitable for situations where the size of the data structure is not known in advance.
2, Insertion/deletion efficiency: linked structures excel at insertion and deletion operations, especially in the middle of the structure. Inserting or deleting elements usually requires updating a few pointers, making these operations efficient.
3, memory efficiency: linked structures can be more memory efficient when elements are added and removed frequently. They allocate memory only for the elements present, avoiding wasted space due to unused capacity
4, Ease of expansion: Linked structures can be easily expanded by adding new nodes as needed.
Disadvantages:
1, random access: linked structures do not support random access to elements. Accessing an element at a specific index typically requires traversing the structure from the beginning, resulting in O(n) time complexity.
2, Space overhead: linked structures incur space overhead due to the additional memory required for maintaining the pointers/references between nodes. The overhead can be significant when dealing with small elements.
3, Complexity: Working with linked structures can be more complex and error prone than working with arrays, especially when it comes to managing memory and dealing with pointers
Array-based ADT’s
Advantages:
1, random access: array-based structures provide efficient random access to elements in O(1) time complexity, as elements are stored in contiguous memory locations.
2, simplicity: working with arrays is often simpler and more intuitive than managing linked structures, especially for small to moderate size collections of elements.
3, predictable memory usage: arrays have predictable memory usage as their size is fixed upon creation. This can be an advantage in resource constrained environments.
Disadvantages:
1, fixed size: array-based structures have a fixed size, which may lead to wasted memory if the allocated size is not fully utilised or insufficient if more space is needed.
2, inefficient insertion/deletion: insertion and deletion operations in array-based structures can be inefficient, especially when elements are added or removed form the middle of the structure. This often requires shifting elements, resulting in O(n) time complexity.
3, Dynamic resizing overhead: To overcome the fixed size limitation, dynamic arrays are used, which can dynamically resize themselves. However, this resizing operation incurs additional time and memory overhead.
4, fragmentation: over time, dynamic arrays may suffer form memory fragmentation as they allocate new blocks of memory when resizing, this can lead to inefficient memory storage.
The choice between array based and linked ADT’s depends on the specific requirements of the application.
What is the difference between a stack and a queue? Can you provide an example of a scenario where a stack would be more appropriate than a queue and vice versa?
A stack and queue are both ADT’s that are used for organising and maintaining a specific order of elements. But they both operate differently.
Stack:
- follows the LIFO, last in, first out principle, meaning that the last added item is the first one out
- supports two primary operations: push and pop. push adds the items on to the top of the stack and pop retrieve the top element from the stack.
- stacks are mainly used in tracking function calls and managing excecution context (call stack). They are also used in undo/redo functions and browser history.
Queue:
- follows the FIFO principle, meaning the first element added is the first one out
- supports two primary operations: append and serve. append adds an item to the back of the queue and serve removes the first element in the queue.
- queues are mainly used in print job management, handling requests, call centres.
Scenario for using a stack:
If you were implementing a web browser with a back button functionality. You would use a stack to add the the page last visited onto the stack when the user has moved onto the next link. If the user would like to go back, the stack pops the last visited page from stack. In this case a stack is more appropriate as it follows the LIFO principle and makes it easy to retrieve the most recent page.
Scenario for queue:
print queues in office environments can get multiple print jobs submitted to a printer and the need to be processed in the order they were received. New print jobs are added to the back of the queue and the first print jobs in are processed first. In this case, a queue is more appropriate as it follows the FIFO principle and allows things to be processed in the order they were recived.
How can you use a stack to check if a string of parentheses is balanced? Can you provide an example of a balanced and an unbalanced string?
You can use a stack data structure to check if a string of parentheses is balanced in the following way:
- initialize an empty stack
- iterate through each character in the strong from left to right
- for each character:
- if it’s an opening parantheses, push it onto the satck
- if its a closed parenthesis, check if the stack is empty, if the stack is not empty pop the top element from the stack and compare it to the current closing parenthesis. if they match, continue to the next character.
- if the do not match, the string is unbalanced because the parenthesis are in the wrong order
- after processing all characters, if the stack is empty, the string is balanced. If the stack is not empty, the string is unbalanced because there are unmatched opening parenthesis
What is the time complexity of the push(), pop(), peek(), and __len__() operations in a linked stack? How do they compare to the time complexity of the same operations in an array-based stack?
