Week 3 Flashcards
What is Data?
Independent fact, observation or value.
What is a record?
The data pertaining to a unique object. .
Sometimes called an element. Consists of one or more fields. Can be thought of as rows in tables.
What is a field?
A field is a constituent part of a record, usually consisting of a single data element.
It has a specified type and size.
What is a file?
A collection of records
What is a key?
The data field used to select or order records.
May or may not be unique.
What is a primary key?
The field used first for selecting or sorting records.
eg. Last names in a telephone book
What is a Secondary Key?
The field used if 2 or more records have equal primary keys.
eg. first names in a telephone book
What is searching? What is sorting?
Searching: An operation that returns a pointer to a record that matches a key value.
Sorting: arranges items of a list into ascending or descending order.
What are the two classification of search algorithms.
Sequential and interval
How does a linear search work? What is the complexity of a linear search.
A linear search algorithm starts at the beginning of a list, then compares each successive item to a query key until we find a match or reach the end of the list.
The complexity is O(n) or better for small sets of data in some cases.
What is the best case complexity of a linear search?
The best case is O(1). Or constant
We know that the average case complexity for a linear search is O(n). We also know that the worst case complexity is O(n). Does this mean that they take the same time?
No this doesn’t mean that they take the same time. What this tells us is that they are both linear.
This analysis is not based on time.
What are the three design techniques for divide and conquer?
Divide the problem into a number of subproblems that are smaller instances of the same problem.
Conquer the subproblems by solving them recursively.
Combine the solutions to the subproblems into the solution for the original.
What is recursion?
Recursion is a programming construct where a function calls itself during execution.
