DATA STRUCTURES 8

Question 1

Ο( g(n) )

Answer 1

a ≤ b; f(n) ≤ cg(n)

Question 2

Ω( g(n) )

Answer 2

a ≥ b; f(n) ≥ cg(n)

Question 3

Θ( g(n) )

Answer 3

a = b; c₁g(n) ≤ f(n) ≤ c₂g(n)

Question 4

ω( g(n) )

Answer 4

a > b; f(n) > cg(n)

Question 5

ο( g(n) )

Answer 5

a < b; f(n) < cg(n)

Question 6

O( n² )

Answer 6

bubble sort; Shell sort; quicksort; selection sort; insertion sort

Question 7

O( log n )

Answer 7

binary search

Question 8

When parameters are passed ______, the formal parameters of a function refer to _______ of the actual parameters which are discarded as soon as the function call returns.

Answer 8

by-value; copies

Question 9

void addOne( long x )

Answer 9

passed by-value

Question 10

void addOneByRef( long& x )

Answer 10

passed by-reference

Question 11

Function overloading

Answer 11

Has to have different parameters. Can return different value types. Can have one version with 2 parameters and one with 3 parameters.

Question 12

*p = ?

Answer 12

value of variable pointed to

Question 13

p = ?

Answer 13

address of variable pointed to

Question 14

&x = ?

Answer 14

address of variable

Question 15

N + (N - 1) + … + 2 + 1 =

Answer 15

N(N+1)/2

Question 16

Time for searching?

Answer 16

O( log n )

Question 17

Time for Traveling Salesman?

Answer 17

O( n! )

Question 18

Time for one loop?

Answer 18

O( n )

Question 19

Time for a loop with in a loop?

Answer 19

O( n² )

Question 20

Static memory is created on the _____?

Answer 20

Stack

Question 21

Dynamic memory is created on the ____?

Answer 21

Heap

Question 22

Dynamic memory must be ____ via _____?

Answer 22

released; delete

Question 23

Static is freed when they go out of ____?

Answer 23

Scope

Question 24

______ is a data structure that uses a ____ function to map identifying values, known as keys (e.g., a person’s name), to their associated values (e.g., their telephone number).

Answer 24

Hash Table; Hash

Question 25

What are hash tables good for?

Answer 25

The main advantage of hash tables over other table data structures is speed. This advantage is more apparent when the number of entries is large (thousands or more). Hash tables are particularly efficient when the maximum number of entries can be predicted in advance, so that the bucket array can be allocated once with the optimum size and never resized.

Question 26

In what situations are hash tables not likely to be useful?

Answer 26

The main issue is the flexibility of the table in terms of size. Once you have chosen a particular size m for the array, you will also commit to a particular hash function h whose range is exactly {0,…,m-1}. If you do not have a reasonably tight estimate for the size of the set S that you’d like to store in your hash table ahead of time, hash tables may not be the best answer. Hash tables become quite inefficient when there are many collisions.

Question 27

What are the worst-case running times of the hash table algorithms for insertion, removal and search?

Answer 27

For the worst choice of hash function, every insertion causes a collision, and hash tables degenerate to linear search, with Ω(k) amortized comparisons per insertion and up to k comparisons for a successful lookup.

Question 28

“What are the average-case running times for hash tables, and what are the caveats regarding the ““average-case?”””

Answer 28

The average case time for searching (as well as insertion and removal) is still Θ(1) under various assumptions about h.

Question 29

What is a universal hashing family?

Answer 29

“A family of functions is a universal hash family if for any two keys of the universe that collide, there is a probability at most (1 / m) when the hash function h is drawn randomly from H. “

Question 30

In the context of hash tables, what problem does universal hashing families solve?

Answer 30

Guarantees a low number of collisions in expectation, even if the data is chosen by an adversary.

Question 31

What is recursion?

Answer 31

See: What is recursion?In mathematics and computer science, a class of objects or methods exhibit recursive behavior when they can be defined by two properties: (1) A simple base case (or cases), and (2) A set of rules which reduce all other cases toward the base case.

Question 32

Recursive solution to the Towers of Hanoi?

Answer 32

To move n discs from peg A to peg C:(1) Move n−1 discs from A to B. This leaves disc n alone on peg A.(2) Move disc n from A to C.(3) Move n−1 discs from B to C so they sit on disc n.

Question 33

What is a Binary Search Tree (BST)?

Answer 33

A binary search tree (BST), which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties: (1) The left subtree of a node contains only nodes with keys less than the node’s key. (2) The right subtree of a node contains only nodes with keys greater than the node’s key. (3) Both the left and right subtrees must also be binary search trees.

Question 34

What are the traversals for a BST?

Answer 34

Pre-Order; In-Order; Post-Order; Breadth First; Depth First;

Question 35

Worst case running time for pre/in/post order traversal?

Answer 35

It takes O(n) time to walk (in-order, pre-order and post-order) a tree of n nodes.

Question 36

Worst case running time for deletion for a BST?

Answer 36

The procedure runs in O(h) time on a tree of height h.

Question 37

Worst case running time for insertion for a BST?

Answer 37

It runs in O(h) time on a tree of height h.

Question 38

Worst case running time for Breadth First Traversal of a BST?

Answer 38

The total running time for breadth-first search traversal is O(V + E) where V is the verts and E is the edges.

Question 39

Worst case running time for Depth First Traversal of a BST?

Answer 39

The running time of DFS is Θ(V + E).

Question 40

For graphs, in an ______ ____ representation, we keep, for each vertex in the graph, a list of all other vertices which it has an edge to.

Answer 40

Adjacency List

Question 41

For graphs, an ______ ____ is a means of representing which vertices (or nodes) of a graph are adjacent to which other vertices.

Answer 41

“Adjacency Matrix “

Question 42

When might an adjacency list be better than an adjacency matrix?

Answer 42

It is easy to find all vertices adjacent to a given vertex in an adjacency list representation; you simply read its adjacency list. With an adjacency matrix you must instead scan over an entire row, taking O(n) time. If you, instead, want to perform a neighbor test on two vertices (i.e., determine if they have an edge between them), an adjacency matrix provides this at once.For a graph with a sparse adjacency matrix an adjacency list representation of the graph occupies less space, because it does not use any space to represent edges that are not present. A graph must be sparse for an adjacency list representation to be more memory efficient than an adjacency matrix.

Question 43

How does BFS work?

Answer 43

Breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.BFS uses a QUEUE.http://www.youtube.com/watch?v=or9xlA3YYzo&feature=player_detailpage#t=271s

Question 44

How does DFS work?

Answer 44

Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.DFS uses a STACK.https://www.youtube.com/watch?v=or9xlA3YYzo

Question 45

What is BFS good for?

Answer 45

BFS can be used to test bipartiteness, by starting the search at any vertex and giving alternating labels to the vertices visited during the search. That is, give label 0 to the starting vertex, 1 to all its neighbours, 0 to those neighbours’ neighbours, and so on. If at any step a vertex has (visited) neighbours with the same label as itself, then the graph is not bipartite. If the search ends without such a situation occurring, then the graph is bipartite.Finding the shortest path between two nodes u and v.The set of nodes reached by a BFS (breadth-first search) form the connected component containing the starting node.

Question 46

When is a graph useful?

Answer 46

Using graphs can involve representing relationships between objects, places, or concepts. Because graphs can be either directed or undirected, they are a flexible method of showing connections. For instance, you can describe who knows whom in a room as a collection of nodes, each representing a person, and directed edges, each representing that one person knows another.

Question 47

What is abstraction in C++?

Answer 47

In object-oriented programming languages such as C++, the concept of abstraction has itself become a declarative statement - using the keywords virtual (in C++). After such a declaration, it is the responsibility of the programmer to implement a class to instantiate the object of the declaration.An abstract class is a class that is designed to be specifically used as a base class. An abstract class contains at least one pure virtual function. You declare a pure virtual function by using a pure specifier (= 0) in the declaration of a virtual member function in the class declaration.class AB {public: virtual void f() = 0;};

Question 48

Example of Polymorphism in C++?

Answer 48

class CPolygon { protected: int width, height; public: void set_values (int a, int b) { width=a; height=b; } };class CRectangle: public CPolygon { public: int area () { return (width * height); } };

Question 49

How does one declare one class as a derived class of another?

Answer 49

“Use of the ““public”” keyword.class Derived: public Base”

Question 50

Can you think of an instance where a virtual destructor would be a good idea?

Answer 50

It is a good idea to use a virtual destructor in any class that will be used as an interface (i.e., that has any other virtual method). If your class has no virtual methods, you may not want to declare the destructor virtual because doing so will require the addition of a virtual table pointer.

Question 51

How does insertion sort work?

Answer 51

Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain. The choice of which element to remove from the input is arbitrary, and can be made using almost any choice algorithm.

Question 52

How does selection sort work?

Answer 52

(1) Find the minimum value in the list.(2) Swap it with the value in the first position.(3) Repeat the steps above for the remainder of the list (starting at the second position and advancing each time).

Question 53

How does merge sort work?

Answer 53

(1) If the list is of length 0 or 1, then it is already sorted. Otherwise:(2) Divide the unsorted list into two sublists of about half the size.(3) Sort each sublist recursively by re-applying the merge sort.(4) Merge the two sublists back into one sorted list.

Question 54

How does quick sort work?

Answer 54

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.The steps are:(1) Pick an element, called a pivot, from the list.(2) Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.(3)Recursively sort the sub-list of lesser elements and the sub-list of greater elements.The base case of the recursion are lists of size zero or one, which never need to be sorted.

Question 55

What is a heap?

Answer 55

“In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap.) “

Question 56

How does heap sort work?

Answer 56

https://www.youtube.com/watch?v=WYII2Oau_VY

Question 57

How does bucket sort work?

Answer 57

https://www.youtube.com/watch?v=Iiuqrns0Gwk

Question 58

Insertion sort has ___ worst case and ___ average case run time.

Answer 58

О(n²); О(n²)

Question 59

Selection sort has ___ worst case and ___ average case run time.

Answer 59

О(n²); О(n²)

Question 60

Merge sort has ___ worst case and ___ average case run time.

Answer 60

O(n log n); O(n log n)

Question 61

Quick sort has ___ worst case and ___ average case run time.

Answer 61

О(n²); O(n log n)

Question 62

Heap sort has ___ worst case and ___ average case run time.

Answer 62

O(n log n); O(n log n)

Question 63

Bucket sort has ___ worst case and ___ average case run time.

Answer 63

О(n²); O(n)

Question 64

Why might one prefer quick sort to merge sort in spite of the О(n²) worst case running time?

Answer 64

For Merge sort worst case is O(nlog(n)), for Quick sort: O(n²). For other cases (avg, best) both have O(nlog(n)). However Quick sort is space constant where Merge sort depends on the structure you’re sorting.

Question 65

Be able to prove Ω(n log n) bounds on the running time for comparison sorts.

Answer 65

Proof: Recall that the sorting algorithm must output a permutation of the input [a1, a2, . . . , an]. The key to the argument is that (a) there are n! different possible permutations the algorithm might output, and (b) for each of these permutations, there exists an input for which that permutation is the only correct answer. For instance, the permutation [a3, a1, a4, a2] is the only correct answer for sorting the input [2, 4, 1, 3]. In fact, if you fix a set of n distinct elements, then there will be a 1-1 correspondence between the different orderings the elements might be in and the permutations needed to sort them.Given (a) and (b) above, this means we can fix some set of n! inputs (e.g., all orderings of {1, 2, . . . , n}), one for each of the n! output permutations. Let S be the set of these inputs that are consistent with the answers to all comparisons made sofar (so, initially, |S| = n!). We can think of a new comparison as splitting S into two groups: those inputs for which the answer would be YES and those for which the answer would be NO.Now, suppose an adversary always gives the answer to each comparison corresponding to the larger group. Then, each comparison will cut down the size of S by at most a factor of 2. Since S initially has size n!, and by construction, the algorithm at the end must have reduced |S| down to 1 in order to know which output to produce, the algorithm must make at least log2(n!) comparisons before it can halt. We can then solve:log2(n!) = log2(n) + log2(n − 1) + . . . + log2(2)= Ω(n log n).Notice that our proof is like a game of 20 Questions in which the responder (the adversary) doesn’t actually decide what he is thinking of until there is only one option left. This is legitimate because we just need to show that there is some input that would cause the algorithm to take a long time.In other words, since the sorting algorithm is deterministic, we can take that final remaining option and then re-run the algorithm on that specific input, and the algorithm will make the same exact sequence of operations.http://www.cs.cmu.edu/~avrim/451/lectures/lect0908.pdf