Flashcards
DSA: Lecture 2
Cards in this deck (35)
- 1Which type of running time is usually focused on and why?Worst-case;
it's easier to analyse,
crucial to applications such as games, robots and finance. - 2What determines the length of the running time?Input size of the algorithm
- 3What is required in order to compare two algorithms?Same software environments and same hardware
- 4Three features of theoretical analysis1. Uses high level description of algorithm rather than implementation
2. Characterizes running time as a function of the input size
3. Takes into account all possible inputs - 5What does theoretical analysis allow us to evaluateSpeed of an algorithm independent of the hardware/software environment
- 69 types of growth ratesConstant = O(1)
Logarithmic = O(log n)
Linear = O(n)
Log-linear = O(n logn)
Quadratic = O(n^2)
Cubic = O(n^3)
Polynomial = O(n^3) and above
Exponential = O(a^n)
Tetration = 0(a^^n) n times - 7What is growth rate not affected by?Constant factors or,
lower-order terms - 8How would you simplify running time of 3n+5?O(n)
- 9What determines the running time in BigOh notation?The asymptotic analysis of an algorithm
- 10How do we perform this analysis?Find worst-case number of primitive operations executed as a function of the input size,
express this function with BigOh notation. - 11Practice running times in book and lecturesk
- 124 relatives of BigOhBig-Omega
Big-Theta
little-oh
little-omega - 13Describe the Vector ADT1. Extends notion of array by storing sequence of arbitrary objects
2. Element can be accessed, inserted and removed by specifying its rank
3. Exception is thrown if incorrect rank is specified - 14Main operations of a vectorelemAtRank()
replaceAtRank()
insertAtRank()
removeAtRank() - 15Applications of vectorsSorted collections of objects
(elementary database) - 16Describe the implementation of an array-based vectorUse an array V of size N
Have a variable n to keep track of size of vector
Implement elemAtRank - 17What's the worst case running time for insertAtRank and removeAtRank?O(n)
- 18What is the worst case running time for replaceAtRank and size?O(1)
- 19What will be the running time of insertAtRank and removeAtRank in a circular array?O(1)
- 20What is a singly-linked list?Concrete data structure consisting of a sequence of nodes
- 21What does each node store in a singly-linked list?Element and link to the next node
- 22What does the Position ADT do?It models the notion of place within a data structure where a single object is stored
- 23What are the query methods of the List ADT?isFirst
isLast - 24What are the accessor methods of the List ADT?first()
last()
before()
after() - 25What are the update methods of a List ADT?replaceElement()
swapElements()
insertBefore()
insertAfter()
insertFirst()
insertLast()
remove() - 26How does a singly-linked list differ from a doubly-linked list?Doubly-linked list links to previous AND next node, while singly just to next.
- 27What kind of nodes does a singly-linked list have?Header and trailer node to link to previous and next nodes
- 28Running time of doubly-linked list?O(1)
- 29What is Sequence ADT the union of?List ADT and Vector ADT
- 30Vector-based methods of Vector ADTelemAtRank()
replaceAtRank()
removeAtRank()
insertAtRank() - 31List-based methods of Vector ADTfirst(), last()
before(), after(),
replaceElement(), swapElements()
insertBefore(), insertAfter(),
insertFirst(), insertLast(),
remove() - 32Applications for Sequence ADTGeneric replacements for vector, list, stack, queue, etc.
Small database - 33What does an iterator do?Abstracts the process of scanning through a collection of elements
- 34What are the 4 methods of the ElementIterator ADT?E element();
boolean hasNext();
E nextElement();
reset(); - 35What are the 2 notions of an iterator?Snapshot: freezes contents of data structure at a given time.
Dynamic: follows changes of data structure
Information
- Description
- Flashcards on DSA: Lecture 2, created by krisbraz on 19/03/2015.
- Created by
- krisbraz
- Views
- 0
- Rating