Chapter 1 Algorithms Flashcards
(14 cards)
What is an algorithm?
A finite sequence of steps that a computer can carry out to transform some input into some output.
Why is Ada Lovelace significant in computing history?
She is considered to have written the first computer program for Babbage’s Analytical Engine.
What does STAT0041 focus on?
Understanding algorithms at an abstract level, including complexity and data structures.
How does STAT0041 differ from programming courses like STAT0004?
STAT0041 focuses on algorithmic logic and complexity rather than actual coding.
What is Euclid’s GCD algorithm used for?
Finding the greatest common divisor of two positive integers.
What is computational complexity?
A measure of the number of steps an algorithm takes as a function of the input size.
What is meant by worst-case analysis?
Analyzing an algorithm based on the maximum number of steps it might take for any input of a given size.
What is big-O notation?
A mathematical notation used to describe the upper bound of an algorithm’s running time.
What does O(n) mean?
That the algorithm’s running time grows linearly with the input size n.
What is the complexity of a sequential search in an array?
O(n) in the worst case.
How does number representation affect computation?
Different representations (like using 7 vs 64 bits) affect the precision and possibly the step cost.
What is a data structure?
A representation of data with defined operations.
What is the significance of Euler’s Konigsberg bridges problem?
It led to the development of graph theory.
What is the complexity of searching a number q in an array of arrays?
Depends on m (number of arrays) and n (max length of arrays); worst-case is O(mn).
