Flashcards
Data structures and Algorithms
Cards in this deck (28)
- 1Little o(N) and growthT(N) is o(N) if T(N) is O(F(N)) and not θ(F(N)). Growth of T(N) is < the rate of growth of F(N).
- 2Big O(N) and growthT(N) is O(F(N)) if there are positive constants C and N0 such that T(N) <= C*F(N) when N >= N0. Growth of T(N) is <= the rate of growth of F(N)
- 3How many edges will a minimal spanning tree have|N|-1
- 4Best and worse case scenario of Bubble SortBest: O(N) Worse: O(N^2)
- 5Best and worse case of Quick sortBest O(n Log n) Worse O(n^2)
- 6Best and worse case of HeapsortBest: O(n log n) Worse: O(n log n)
- 7Efficiency of sum++O(n^4)
- 8Big Ω(N) and growthT(N) is Ω(F(N)) if there are positive constants C and N0 such that T(N) >= C*F(N) when N >= N0. Growth of T(N) is >= the rate of growth of F(N)
- 9Big Θ(N) and growthT(N) is Θ(N) if T(N) is O(F(N)) and Ω(F(N)). Growth of T(N) is = to the rate of growth of F(N)
- 10Explain Kruskal's AlgorithmStart with an empty forest, consider the edges in sorted order. From the lowest cost to greatest cost. For each edge, if it links two nodes not already connected then add that edge to the forest. Repeat this until all nodes are connected, i.e. until you have added |N|-1 edges.
- 11Explain Pimm's AlgorithmStart from an arbitrary node, let that be the node 'connected so far'. Repeatedly: find the shortest edge from the nodes connected so far. Add to the tree, add the linked node to those connected so far. Repeat until all nodes are connected.
- 12Best and worse case of Radix sortBest: O(N log N) Worse: O(kN)
- 13Describe Radix sortWe separate elements based
on their first character into
their own sets, then by second
digit and so on until all
elements are sorted. - 14Best and worse case of Insertion sortBest case: Ω(n)
comparisons, O(1) swaps Worse case: O(N^2) - 15Describe Dijkstra's AlgorithmDijkstra's algorithm finds the
shortest path from the start
point to connect all nodes
within a graph.
On each cycle of the algorithm, work out
the next node to add - that's he node you
can reach from one of the known nodes
with the shortest path back to the start
point. Repeat until all nodes are
connected. - 16What is a MST?A Minimal Spanning Tree
(MST) is a tree which
connects all Nodes in a
graph through shortest
possible path - 17What is a Tree?A Tree is a graph of connected nodes
with no cycles - 18What is a cycle?A cycle is a path that
starts and ends with the
same node (a loop.) - 19Describe a Binary TreeBinary trees exist of nodes, each node
holds data about it's self and two links
to other nodes. Usually which link goes
to which node has a rule to follow, for
example all nodes with a lesser value go
through the left link, and all nodes with
a greater value or equal go through the
right link. - 20What is the efficiency of Add, Find and Remove in a Binary Tree?Add: O(log N)
Find: O(log N)
Remove: O(log N) - 21What is a Heap?A heap is a specialised
tree-based structure that
satisfies a heap property (If a
node A is a parent of B then
the value of node A is
ordered with respect to the
value of B, with the same
being applied across the
heap.) - 22What is a min-heap?Min-heap: The value of parent
nodes are less than or equal to the
children and the lowest value is in
the root node. - 23What is a max-heap?Max-Heap: The values of parent
nodes are always greater than or
equal to those of the children and
the highest value is the root node. - 24What is the efficiency of Add and Remove/Pop and Push for Stacks and Queues?Add: O(1)
Remove: O(1) - 25Describe a Linked ListA linked list is a more flexible data
structure for inserting and
removing elements. It consists of
node, a node holds one element of
a list and a link to the next list in
the node. - 26How do you insert a new Node in a Linked List?If we have a reference to a
node in the list, we can insert
immediately after that item. If there is
already an item there change the
predecessor link to the element we
are inserting, and make the link of the
inserted element point to the
element we are moving along. - 27How do you add a new element to a Heap structure and what is the efficiency of this?Create an empty node for our new element at the bottom of the Heap, then compare it with it's parent; if it needs to be swapped do so. Repeat this until the new node settles in a spot.
The efficiency of this function is O(log N). - 28How do you remove an element from a Heap? And hat is the efficiency of this?Empty the node we are removing and replace it with a child of it (if there is no child then do nothing). Then call the compare function recursively so that node is swapped until it settles in a location.
The efficiency of this is O(log N).
Information
- Description
- Flashcards on Data structures and Algorithms, created by Jaabiri Slim on 29/08/2015.
- Created by
- Jaabiri Slim
- Views
- 0
- History
-
- Created by Charlie Tizzard Ó Kevlahan · Aug 29, 2015
- Copied by Jaabiri Slim · Aug 29, 2015
- Rating