Flashcards
DSA - Lecture 2
Cards in this deck (20)
- 1Why do we focus on worst case time in algorithm analysis?Because average case time is difficult to determine and worst case is very import in order to know how long the user has to wait in the worst case scenario.
- 2What is a method taht allows us to measure the actual running time of our Algorithm?System.curentTimeMillis()
- 3Give 4 reasons why Theoretical Analysis is better than Experimental.1) Uses a high level description of the algorithm instead of an implementation
2) Characterizes running time as a function of the imput size: n
3) Takes into account all possible inputs
4) Allows to evaluate the speed of an algorithm independant of hardware or software. - 4Learn how to Pseudocode!k
- 5How can we know the maximum number of primitive operations that are executed by an algorithm?By counting the primitive operations
- 6What is Big-Oh notation?a notation O(something) that we use to describe running time of the most toned down version of a function.
- 7Write down the theory of O(), in terms of f(n), g(n) and big OhGiven functions f(n) and g(n), we say that f(n) is O(g(n)) if there are positive constants
c and n0 such that
f(n) <= cg(n) for n >= n0 - 8What do you need to do in order to write a polynomial in O()?1) Drop lower order terms(x^2 +x = O(x^2))
2) Drop constant factors(3n = O(n)) - 9What is the Vector ADT?It extends the notion of an array by storing a sequence of arbitrary objects. Element can be accesed or removed by specifying its rank(#elements before)
- 10What is a Singly Linked List?A concrete data structure consisting of a sequence of Nodes, every Node stores an element and a link to next node.
- 11What is the Posittion ADT?A a place within a data structure where a single object is stored. E element()
- 12What is the List ADT?A sequence of Positions, establishes a before and after relationship between positions
- 13What is a Doubly Linked List?A sequence of Nodes containing an element and a link to the next and previous Node, It also has trailer and header Nodes that signify the beginning and end of the List.
- 14What is the Sequence ADT and what two other ADTs does it combine?It is the union between Vector and List, its elements are accesed by Postition and rank
- 15What is a Sequence good for?Storing a ordered collection of elements
- 16Explain the array based implementation.You have a circular array of Nodes which stores an element and index at every position. Indices f and l keep track of first and last in order to make it circular
- 17What is an Iterator ADT used for?It is used for scanning through a collection of elements.
- 18What is Rank of an element?The amount of elements that precede said element
- 19What is rank useful for?Its useful so we can point at an element even if the sequence is not implemented as an array.
- 20Read about and Draw all ADTs mentionedk
Information
- Description
- Flashcards on DSA - Lecture 2, created by Lucas Vanparijs on 17/03/2015.
- Created by
- Lucas Vanparijs
- Views
- 0
- Rating