Unit 2 computing Flashcards
What is caching?
Predicting the data that will be needed later on in the program and storing it in cache (faster to access)
What is prefetching?
Where data is requested from main memory before it’s actually required
What are the benefits of caching?
Improves speed and efficiency of processing
What are the drawbacks of caching?
Complexity, wrong data can be cached and has to be flushed
Can reusing code be a positive?
Saves time and resources
What is recursion?
When a subroutine calls itself within its own subroutine
What are the 3 characteristics of a recursive subroutine?
Stopping condition, routine calls itself for any value except stopping condition, stopping condition reachable within finite number of times
What does IDE stand for?
Integrated development environment
What is the purpose of an IDE?
To provide a range of tools and features that help speed up and enhance program development
What are examples of features in an IDE?
Code editors, error diagnostics, run-time environments, translators and auto-documentation
What is an example of an IDE?
Python IDLE (Integrated Development and Learning Environment)
What is a run-time environment?
Software that supports the running of programs allowing programmers to easily run code during development
What is done in auto-documentation?
Variables and modules are tracked with a view to produce documentation that aids in program maintenance, debugging and support
What are the two rules of Big O notation?
Remove all terms except one with largest exponent, remove any constant from this
What does O(1) mean in Big O notation?
Constant - always executes in same amount of time regardless of data set
What does O(log n) mean in Big O notation?
Logarithmic - complexity grows slowly in proportion to number of items in list
What does O(n) mean in Big O notation?
Linear - direct correlation between input size and time taken
What does O(n²) mean in Big O notation?
Polynomial - impact of algorithm is directly proportional to the square of the input size
What does O(2ⁿ) mean in Big O notation?
Exponential - time taken to execute algorithm doubles with each item added
What characteristics will an O(1) algorithm have?
No loops or iterations
What characteristics will an O(log n) algorithm have?
Halving data set
What characteristics will an O(n) algorithm have?
A singular for or while loop
What characteristics will an O(n²) algorithm have?
Nested loops
What characteristics will an O(2ⁿ) algorithm have?
Recursion (if it calls itself twice)
How do you execute a pre-order tree traversal?
(node-left-right) Output root, mark count on left of each node when drawing traversal
How do you execute an in order tree traversal?
(left-node-right) mark count on bottom of each node when drawing traversal
How do you execute a post order tree traversal?
(left-right-node) mark count on right of each node when drawing traversal
What is a linked list?
A list which provides a foundation for other structures to be built
How does a linked list work?
Each node has a pointer indicating to other nodes in the linked list
What does the pointer point to when there are no more items in a linked list?
Null
When would you pass values in a function by value rather than by reference?
When the original values don’t need to be changed