Programming & Computer Science Answers

A Transport Company is requested for a software and asked for the following functionalities.

o Client name, contact, email and transection (only one) are important to keep.

o Client can buy or sell car through pinwheels. The transection details which are important

to keep are date (day), transection type (Buy or Sell) and amount.

Implement the above demand in such a way what if the client is deleted, none of its transection

record will remain. (Use Composition)

The String_collection.txt file contains 4000 random English names (keys), write a C++ program that generates hash codes for each key using polynomial accumulation.In addition your program should perform the following tasks. consider a=37 [constant]

Write separate function for each task and call it in proper order

1. Create a hash table to store the keys based on the hash values generated

➢ Hash value: h(key)=|hash code| mod N , use appropriate value for N

➢ For collision handling use separate chaining

1.1. Write a function insert(key), and find(key) to insert and find the key in the hash table.

1.2. Write a display function that display all the keys in ascending order of hash values (line-wise) such that each line display the keys (names) having the same hash value.

1.3 Find the hash value with maximum number of collisions and display all the string associated with this hash value

2. Compare the total number of collisions for a=33, 37, 39, 41

2.1. Display the total number of collisions occurred for each case

You are given a graph G = (V, E) where the weights of the edges can have

only three possible values - 2, 5 and 7. Design a linear time , that is O(E + V) time algorithm to find the minimum spanning tree of G. Hint: Modify a known algorithm.

There are n galaxies connected by m intergalactic teleport-ways. Each

teleport-way joins two galaxies and can be traversed in both directions.

However, the company that runs the teleport-ways has established an

extremely lucrative cost structure: Anyone can teleport further from their

home galaxy at no cost whatsoever, but teleporting toward their home galaxy

is prohibitively expensive.

Judy has decided to take a sabbatical tour of the universe by visiting as

many galaxies as possible, starting at her home galaxy. To save on travel

expenses, she wants to teleport away from her home galaxy at every step,

except for the very last teleport home.

(a) Describe and analyze an algorithm to compute the maximum number of

galaxies that Judy can visit. Your input consists of an undirected graph G

with n vertices and m edges describing the teleport-way network, an

integer 1 <= s <= n identifying Judy’s home galaxy, and an array D[1 .. n]

containing the distances of each galaxy from s

(Greedy Algorithms) Suppose you are given n tasks J = {j1, j2, · · · jn}.

Each task J has two parts - a preprocessing phase which takes pi units and a main phase which takes fi units of time. There are n machines that can execute the main phases of the jobs in parallel. However, the preprocessing phases need to be executed sequentially on a special machine. The completion time of any schedule is the earliest time when all tasks have finished execution. Design a greedy algorithm which produces a schedule that minimizes the completion time.

When would best-first search be worse than simple breadth-first search?