Computer Programming Questions. Please Answer ALL questions and number them. leg

Question

Computer Programming Questions. Please Answer ALL questions and number them. legible hand writing preferred :)

1. Many amusement parks have “Fast Passes” to enable customers to bypass waiting in line. How would you use a combination queues and priority queues to simulate how this work?

2. Compare/contrast Trees, Binary Search Trees, Balanced Trees, and Heaps.

3. Use the letters “G R E Y H O U N D S” to build the following trees (letters earlier in the alphabet are less than letters later in the alphabet)

-Binary Search Tree

-MinHeap

-Remove the “D” from each tree

4. What are all the different methods for implementing dictionaries, their average case time complexities for retrieval, and their pros/cons?

5. Describe hashing. List 2 hash functions. Which is most common? Why?

6. Describe 2 methods for handling collisions

7. What are the similarities and differences between Graphs and Trees?

8. Name and describe the two ways of traversing a Graph (include the basic algorithm and include which data structures support the algorithm).

9. Do you think LinkedIn would use a DFS or BFS in their connections-recommendation algorithm? Why?

Explanation / Answer

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

Answer 2

HEAP :-
heaps required the nodes to have a priority over their childern . in a max heap , each nodes childern must be less than itelf .
BINARY SEARCH TREE :-
Binary search tree follows a specific order (per-order , in-order , post-order ) among sibling nodes . The tree must be sorted in ascendinng order .
BALANCED BINARY TREE :-
A tree is balanced binary tree if for each node it hold that the number of inner nodes in the left subtree and the number od inner nodes in the right sub tree difer by at most 1.

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

Answer 7

Difference Between Tree and Graph :-
1. In tree there is exactly one root node and every child have only one parent , In graph there is no such concept of root node.
2. Tree always has N-1 edges , In graph no. of edges depend on the graph.
3.Tree is a Hierarchical model , Graph is a network model .
4.Trees come in the category of DAG(Directed Acyclic Graph) and has no cycles , Graph can be Cyclic or acyclic.
5. Trees are less complex than graph , Graph are more complex ass it have cycles , loops etc.

Smilarities between trees and graphs :

1. Trees and Graph both are non-linear data structure that are used to resolve complex computer problems .
2. Trees and Graph both are data structure having parent nodes and multiple subnodes.
----------------------------------------------------------------------------------------------------------------------------------------------------------------------

Answer - 8

Traversing a graph refers to a process of visiting each vertex in a graph . Such traversals are classified by the order in which the vertices are visited .
there are mainly two types of graph traversing :
1. DFS (depth first search )
2. BFS( Breadth first search )

In DFS , the graph traverses the depth of any particular path before exploring its breadth .A stack is generally used in this algorithm .

procedure DFS(G, v):
label v as explored
for all edges e in G.incidentEdges(v) do
if edge e is unexplored then
w G.adjacentVertex(v, e)
if vertex w is unexplored then
label e as a discovered edge
recursively call DFS(G, w)
else
label e as a back edge

In BFS , traversing a graph . BFS visits the neighbor vertices before visiting the child vertices , and a queue is used in search process .

procedure BFS(G, v):
create a queue Q
enqueue v onto Q
mark v
while Q is not empty:
t Q.dequeue()
if t is what we are looking for:
return t
for all edges e in G.adjacentEdges(t) do
o G.adjacentVertex(t, e)
if o is not marked:
mark o
enqueue o onto Q
return null

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

Answer 5

A hash function is any function that can be used to map datat of arbitary size of data or fixed size . the values return by hash function are call Hash values , Hash codes , or Hashes .
Two types of hash function :
1. collosion solution
2. Double Hashing

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.