Ask Question, Ask an Expert


Ask Computer Engineering Expert

problem 1: This problem involves the problem of computing change for a given coin system. A coin system is defined to be a sequence of coin values v1 < v2 < . . . < vn, such that v1 = 1. For ex, in the U.S. coin system we have six coins with values h1, 5, 10, 25, 50, 100i. The problem is what is the best way to make change for a given integer amount A.

a) Let c ≥ 2 be an integer constant. Suppose that you have a coin system where there are n types of coins of integer values v1 < v2 < . . . < vn, such that v1 = 1 and, for 1 < i ≤ n, vi = c · vi−1. (For ex, for c = 3 and n = 4, an ex would be h1, 3, 9, 27i.) Describe an algorithm which given n, c, and an initial amount A, outputs an n-element vector that indicates the minimum number of coins in this system that sums up to this amount. (Hint: Use a greedy approach.)

b) Given an initial amount A ≥ 0, let hm1, . . . ,mni be the number of coins output by your algorithm.

Prove that the algorithm is correct. In particular, prove the following:

i) For 1 ≤ i ≤ n, mi ≥ 0
ii) Pni=1mi · vi = A
iii) The number of coins used is as small as possible.

Prove that your algorithm is optimal (in the sense that of generating the minimum number of coins) for any such currency system.

c) Give an ex of a coin system (either occurring in history, or one of your own invention) for which the greedy algorithm may fail to produce the minimum number of coins for some amount. Your coin system must have a 1-cent coin.

problem 2: You are given an undirected graph G = (V,E) in which the edge weights are highly restricted.

In particular, each edge has a positive integer weight of either {1, 2, . . . ,W}, where W is a constant (independent of the number of edges or vertices). Show that it is possible to compute the single-source shortest paths in such a graph in O(n + m) time, where n = |V | and m = |E|. (Hint: Because W is a constant, a running time of O(W(n + m)) is as good as O(n + m).)
Requirement: Algorithm running time needs to be in DJIKstra’s running time or better.

problem 3: You are the mayor of a beautiful city by the ocean, and your city is connected to the mainland by a set of k bridges. Your city manager tells you that it is necessary to come up with an evacuation plan in the event of a hurricane. Your idea is to add a sign at each intersection pointing the direction of the route to the closest of the k bridges. You realize that this can be modeled as a graph problem, where the street intersections are nodes, the roads are edges, and the edge weights give the driving time between two adjacent intersections. Note that some of the roads in your city are one-way roads.

a) describe how to solve the evacuation-route problem in O(mlog n) time, where n is the number of intersections and m is the number of streets connecting two adjacent intersections. Note that the number of bridges k is not a constant, that is, it may depend on n and m. Therefore, a running time of O(k · mlog n) is not an acceptable solution. The output of your algorithm will be a labeling of the intersections, with an arrow pointing to the road to take to the closest bridge.

b) Some of the bridges can hold more capacity than others. For 1 ≤ i ≤ k, we associate a positive numeric weight ci with each bridge. To encourage people to use bridges with higher capacity, we treat distances to different bridges differently. In particular, if δ is the actual distance from some intersection to bridge i, we assign it a capacity-weighted distance of δ/ci. Therefore, the higher the bridge capacity is, the lower the weighted distance. Present an O(mlog n) time algorithm to solve the evacuation-route problem using capacity-weighted distances.
Additional info: Some of the bridges will be higher capacity. Their weights will be function of (distance/number of lanes) → this will give us shorter weight and we can treat it as a better route to take even though the distance is farther away.

Computer Engineering, Engineering

  • Category:- Computer Engineering
  • Reference No.:- M91939

Have any Question? 

Related Questions in Computer Engineering

For the following exercises you do not use the tal

For the following exercises, you do not use the TAL Distributors database. Use computer magazines, books, or the Internet to investigate the role the cloud computing plays in disaster recovery planning. Then prepare a re ...

Te volume of a parallelepiped can be computed from a

The volume of a parallelepiped can be computed from |A · (B×C)|, where A, B, and C define three sides of the parallelepiped (see Figure P34). Compute the volume of a parallelepiped defined by A = 6i, B = 2i + 4j, and C = ...

One night a sheriffs department helicopter lands a swat

One night, a sheriff's department helicopter lands a SWAT team in the yard of a rural residence suspected of containing a methamphetamine lab. After the raiding party disembarked, and as the pilot was turning the aircraf ...

Explain what is establishing security controls and why it

Explain what is Establishing Security Controls and why it is necessary for record keeping(e.g. what characteristics of records, recordkeeping systems or processes does it support?)

What is the largest number of k-shingles a document of n

What is the largest number of k-shingles a document of n bytes can have? You may assume that the size of the alphabet is large enough that the number of possible strings of length k is at least as n.

Another placement algorithm for dynamic partitioning is

Another placement algorithm for dynamic partitioning is referred to as worst-fit. In this case, the largest free block of memory is used for bringing in a process. Discuss the pros and cons of this method compared to fir ...

We observed in our study of lock-based schedulers that

We observed in our study of lock-based schedulers that there are several reasons why transactions that obtain locks could deadlock. Can a timestamp scheduler using the commit bit C(X) have a deadlock?

What are the common activities conducted during

What are the common activities conducted during construction phase in the software development life cycle? What quality control measures are taken during construction phase? What is done to construct a software applicati ...

Write an arduino program to turn 3 leds on repeatedly in a

Write an Arduino program to turn 3 LEDs on repeatedly in a traffic light pattern of - Green light is on for 8 sec, and it is connected to pin 5. - Yellow light is on for 4 sec, and it is connected to pin 6. - Red light i ...

In 300 to 500 words answer these questionsno plagiarismin

In 300 to 500 words. Answer these questions. No Plagiarism In Clear English Cash Flow and Taxes 1. How does net cash flow differ from net income and why is that difference relevant to financial decision making? 2. With r ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

A cola-dispensing machine is set to dispense 9 ounces of

A cola-dispensing machine is set to dispense 9 ounces of cola per cup, with a standard deviation of 1.0 ounce. The manuf

What is marketingbullwhat is marketing think back to your

What is Marketing? • "What is marketing"? Think back to your impressions before you started this class versus how you

Question -your client david smith runs a small it

QUESTION - Your client, David Smith runs a small IT consulting business specialising in computer software and techno

Inspection of a random sample of 22 aircraft showed that 15

Inspection of a random sample of 22 aircraft showed that 15 needed repairs to fix a wiring problem that might compromise

Effective hrmquestionhow can an effective hrm system help

Effective HRM Question How can an effective HRM system help facilitate the achievement of an organization's strate