Deck 1 Flashcards
(51 cards)
What is data structure?
A systematic way of organizing and accessing data
What is an algorithm?
A step-by-step procedure for performing some task in finite time
How do you perform a linear search?
Given a value x, compare it to each element of L until an element L[i] of value x is found
or
x is compared against all elements in L and all of them are different from x
What is the pseudo-code for a linear search?
Algorithm LinearSearch(L, n, x) Input: array L of size n and value x Output: • position i, 0 ≤ i < n, such that L[i] = x, if x ∈ L, or • −1, if x !∈ L i ← 0 while (i < n) and (L[i] != x) do i ← i + 1 if i = n then return −1 else return i
How do you perform a binary search?
Compare x with any name y located near the middle of the phone book. If x = y search ends.
If x precedes y in lexicographic order, continue search for x on the first half of the phone book
Otherwise, continue the search for x on the second half of phone book
What is the pseudo-code for binary search?
Binary Search
Algorithm BinarySearch(L, x, first, last)
Input: array L of size n and value x
Output:
• position i, 0 ≤ i < n, such that L[i] = x,
if x ∈ L, or • −1, if x 6∈ L
if first > last then return −1
else {
mid ← ⌊(first + last)/2⌋
if x = L[mid] then return mid
else if x < L[mid] then
return BinarySearch(L, x, first,mid−1)
else
return BinarySearch(L, x,mid+1, last)
}What is the complexity of an algorithm?
The complexity of an algorithm is the amount of computer resources it uses.
What type of computer resources are we interested in, in terms of the complexity of an algorithm?
Time and Memory
What is space complexity?
amount of memory the algorithm needs
What is time complexity?
amount of time needed by the algorithm to complete?
What is the best case?
Least amount of time needed by algorithm to solve an instance of the problem of size n
What is the worst case?
Largest amount of time needed by the algorithm to solve an instance of the problem of size n.
What is the average case?
time to solve instance 1 of size n + time to solve instance 2 of size n + ... time to solve last instance of size n number of instances of size n
What mathematical notation is used to express time complexities?
Asymptotic notations
How is f(n) is O(g(n)) read as?
f(n) is the big-Oh of g(n) if there is a real constant c > 0 and an integer constant n0 >= 1 such that f(n) = n0
What are the basic operations that an algorithm performs?
Assignment, comparison, return, boolean, and arithmetic operations
Why do we focus on the worst case running time?
Easier to analyze, average case difficult to determine, crucial to applications such as games, finance and robotics
What method can you use to get an accurate measure of running time?
System.currentTimeMillis()
What is Pseudo-code?
High-level description of an algorithm
More structured than English prose
less detailed than a program
Hides program design issues
What are the two parts of a recursive algorithm
A base case
A recurisve part
What are abstract data types? How parts do they have?
They are user defined data types. There are 2 parts:
- A name or type, specifying a set of data
- Descriptions of all the operations that do things with that type (e.g. find, insert, remove)
Why are ADTs the preferred way of designing and implementing data structures?
Because of it’s ability to hide information and re-usability
Explain Information hiding in ADTs
User data structure should not need to know details of its implementation.
We should be able to change implementation without affecting applications that use it
Explain why re-usability in ADTs is important
If data structure is useful for one application, it is probably useful for another.
