+1-415-315-9853

info@mywordsolution.com

## Engineering

 Civil Engineering Chemical Engineering Electrical & Electronics Mechanical Engineering Computer Engineering Engineering Mathematics MATLAB Other Engineering Digital Electronics Biochemical & Biotechnology

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

### Define inflation assume that you live in a simple economy

Define inflation. Assume that you live in a simple economy in which only three goods are produced and traded: fish, fruit, and meat. Suppose that on January 1, 2010, fish sold for \$2.50 per pound, meat was \$3.00 per poun ...

### 1 the ieee 80211 task group i tgi is developing new wlan

1. The IEEE 802.11 Task Group i (TGi) is developing new WLAN security protocols named TKIP and CCMP. CCMP is envisioned to supersede WEP and TKIP. Research and study these efforts and comment on the progress. 2. It has b ...

### A program is to perform two products one is a vector

A program is to perform two products: one is a vector product of two 100-element vectors and the other is the product produced by multiplying the corresponding elements of a 1000 by 1000 element matrix by a scalar consta ...

### 1 what do we mean when we say that a link-layer switch can

1. What do we mean when we say that a link-layer switch can filter traffic? Why is filtering important? 2. Which one has more overhead, a switch or a router? Explain your answer. 3. Which one has more overhead, a hub or ...

### 1 if the drain and gate supply voltages are dropped to 06v

1. If the drain and gate supply voltages are dropped to 0.6V and the oxide reduced to 40A as indicated by a recent (1989-1990)IBM 0.1-micron Si nMOST at 77K, compute the device parameters required in Table 662.1. Discuss ...

Austin's Commonplaces of Law Based on your reading of the Introduction, describe the three commonplaces of law and create examples to illustrate the meaning of each commonplace.

### 1 what mac protocol is used in the baseband layer of

1. What MAC protocol is used in the baseband layer of Bluetooth? 2. What is the role of the L2CAP layer in Bluetooth? 3. In an 802.11, give the value of the address 1 field in each of the following situations (left bit d ...

### Search the web for security education and training programs

Search the Web for security education and training programs in your area. Keep a list and see which category has the most examples. See if you can determine the costs associated with each example. Which do you think woul ...

### 1 if you were setting up an encryption-based network what

1. If you were setting up an encryption-based network, what size key would you choose and why? 2. What is the average key size of a strong encryption system in use today?

### Mr beautiful an organization that sells weight

Mr. Beautiful, an organization that sells weight training sets, has an ordering cost of \$35 for theBB-1 set (BB-1 stands for Body Beautiful Number1). The carrying cost for BB-1 is \$20per set per year. To meet demand, Mr. ...

• 13,132 Experts

## 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.

### Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

### Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

### Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

### Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro

### Describe what you learned about the impact of economic

Describe what you learned about the impact of economic, social, and demographic trends affecting the US labor environmen