Problem Set: 1 2 3 4 5 6
Problem Set: 1
1. Classify the following into generalization, association,
aggregation, or composition:
a. A country has a capital city
b. A dining philosopher uses a fork
c. A file is an ordinary file or a directory file
d. Files contain records
e. A polygon is composed of an ordered set of points
f. A person uses a computer language on a project
g. A class can have several attributes
h. A relationship can be an association or a generalization
i. A student takes a course from a Professor
j. A course has registrants
2. With concrete examples, discuss the implications of the following
tradeoffs:
a. Association versus generalization
b. Aggregation versus association
c. Single inheritance versus multiple inheritance
d. Class inheritance versus object composition
3. Find an appropriate many-to-one matching from the left items to right
items:
| 1. Abstraction |
|
A. Structural relationship |
| 2. Encapsulation |
|
B. Hierarchy |
| 3. Inheritance |
|
C. Implementation |
| 4. Interface |
|
D. Business objects |
| 5. Persistence |
|
E. Observable behavior of objects |
| 6. Aggregation |
|
|
7. Information hiding
|
|
|
| 8. Association |
|
|
4. For each following task, state whether it is relevant for analysis
(A) or for design (D) or for both (AD)
4.1. Decide a software architecture for
the given application
4.2. Choose the window classes for the GUI
4.3. Develop Use Case Diagrams
4.4. Write down sequence diagrams for use cases
4.5. Write down a state diagram describing the steps of an algorithm
4.6. Remove a use case from the use case diagram
4.7. Use a stereotype
4.8. Select a data structure
5. Prepare a class diagram showing appropriate relationships
(association, aggregation, generalization, etc. ) in UML notation
between the classes given.
IISc,
director, employee, faculty, instructor, student, library, hostel,
department, research-advisor, research student, course student
6. Identify classes and create a class diagram for the following.
A B2B
Call Market (B2BCM) allows trading between buyers and sellers. Buyers describe products they wish to buy
and place bids. Sellers describe
products they wish to sell and place offers. The system, i.e. B2BCM looks at the bids and offers and
determines a matching between buyers
and sellers. A trader may also be both a buyer and seller (that is, buys some products and sells other
products).
7. All of you know about amazon.com. Suppose you are required to design
the software for amazon.com (i.e. users creating a shopping-cart of
books, placing an order, making a payment, etc.). Identify 10 important
classes for this system and create a class diagram depicting
interesting relationships among these abstractions.
8. Create an XML Document that describes the content of the
Ecommerce course.
- where it is offered
- who is handling
- Time frame
- Objectives
- Topics
9. Can you create a generalized template for the above question which
can be used for any course?
10. What does it take to take this data (many such documents) to
present it on a web browser?
11. Write a Java program to take 5 such documents, and print a
report (a simple table) that works?
Table example:
COURSE WHO NO:OF TOPICS
DURATION
Top
Problem Set: 2
1. How do you detach responsibilities in Decorator?
2. How do you dynamically switch between algorithms in the strategy
pattern. What additional infrastructure do you need for this.
3. Clearly understand the reason why a "bridge" pattern is used for
implementing portability across windowing standards rather than an
"abstract factory" pattern.
4. A combinatorial auction is one where a seller announces the
availability of a package of products for selling and prospective
buyers bid for bundles (or subsets of these products). An auction
object can be either a simple auction object (where only one product
type is involved) or a combinatorial auction type. Once the type of the
auction object type is fixed, the structure of bids and offers should
conform to that auction type. Show a class diagram which can capture
the main classes in such an application using design patterns.
5. In the above problem, the winner determination (algorithm to decide
who the winners are) depends on the type of auction. Also, for a given
auction type, there could be several different ways in which winners
could be determined. Furthermore, once the winners are determined, the
prices they pay could be determined in a variety of ways. Use design
pattern(s) to show these details could be captured in an extensible
way.
6. Let us say you are using the composite pattern to represent
assets of an individual. An asset could be a one or more bank accounts,
one or more stocks, one or more properties, or any bundling of these.
Write down a class diagram depicting this.
7. An electronic document is to be tranferred from one machine to
another using the web. Depending on the nature of the document, it is
automatically decided (a) whether the document should be sent in
compressed form or in original (uncompressed) form; (b) whether the
document should be sent in secure mode or insecure mode. The
decision about compression or security is made dynamically only after
looking at the header of the document. Decide whether you want to use
strategy or decorator here and set up a class diagram representing all
essential abstractions.
8. A bank allows its account holders to open deposits through a secure
online system. There are three different types of deposits that
customers may open: fixed deposits, recurring deposits, mixed deposits.
(a) What would be a good creational
pattern to use to generate the relevant form on-line. Explain your
answer.
(b) If innovative new types of deposits have to be introduced by the
bank in future, which design pattern will help you to maximize reuse of
client code. Explain your answer.
9. A trading application is used in three modes:
(a) "forward auction" mode where there
is one seller and multiple buyers
(b) "reverse auction" mode in which there is one buyer and multiple
sellers
(c) a "double auction" mode where there are multiple sellers and
multiple buyers.
Several trading applications may have to be deployed concurrently by
the trading server. Write down three "compelling" design patterns which
may be used in designing this trading application, so as to maximize
reuse. Justify your answer in each case.
10. In the auction house case study, explain how the following patterns
will be useful: (a) COR (b) Mediator (c) Command (d)
Proxy (e) Iterator
Top
Problem Set: 3
1. Suppose the Vickrey auction pricing mechanism is used for English
auctions. Will it generate more revenue, less revenue, or the same
revenue as the classical English auction. Why?
2. Dutch auction and first price sealed bid auction produce the same
average revenue even if all the assumptions of the benchmark model
(independent private values, symmetry, risk-neutal bidders, prices
depend on bids alone) are violated. Is this statement true or false.
Justify.
3. Consider first price sealed bid auction under the benchmark model.
Let vi be the valuation of bidder i. Let bidder i conjecture
that
all other bidders are using a bidding function B to deicide their bids.
That is, if vj is the valuation of bidder j, then bidder j
will bid
B(vj). Note that the individual valuations vj are
not known to bidder i. Assume that B is a monotonically increasing
function (which guarantees that the inverse of B exists). Compute the
probability that bidder i will win with a bid bi in the
above setting.
4. For the benchmark model, it is found that variance of revenue is
lower in English or Vickrey auction than in first price sealed bid or
Dutch auction. How would a seller and a buyer use this information?
5. Assume that there is perfect competition (infinitely many bidders)
and assume the benchmark model. Is this good for the seller or the
buyers. What would be the price the winning bidder will pay?
6. Proof of correctness of Sandholm's Algorithm: Given a set of items
and a set of bids for some subsets of these, Sandholm's algorithm
constructs an allocation tree where children of a node are those bids
that
(a) include the item with the smallest
index among the items that are not yet on the path, and
(b) do not include items that are already on the path
Show that this algorithm constructs "every" feasible allocation
"exactly once."
7. Assume that there are two items {A,B} and three bidders {X,Y,Z}. X
has only one bid (AB, 400). Y has only one bid (AB, 500). Z also has
only one bid (B, 600). What is the revenue maximizing allocation for
this? What problem will this produce when Sandholm's algorithm is used.
How do you modify Sandholm's algorithm to "fix" this problem.
8. Sandholm's algorithm assumes that there is exactly one unit of each
item. If there are multiple units of each item, Sandholm's algorithm
can still be applied by viewing multiple units as multiple items.
Without taking this view, how do you generalize Sandholm's algorithm
for multiple units of different items.
9. Let there be two items {A,B} and three bidders {X,Y,Z}. Let the
values of each bidder for the bundles A, B, and AB be 10,15,25,
respectively. Let the bids be as follows:
| Bidder |
A
|
B
|
AB
|
X
|
5
|
10
|
12
|
Y
|
8
|
5
|
12
|
Z
|
5
|
5
|
10
|
For the above bids, find the allocation, payments, revenue to the
market, and revenue to the bidders. Assume XOR bids. Now do the
following.
(a) Change the bids of X to his true
values and repeat the computations.
(b) Now change the bids of Y to her true values and repeat.
(c) Finally, change the bids of Z to his true values and repeat.
10. Let there be 3 items {A,B,C} and three bidders {X,Y,Z}. Let the XOR
bids be as follows:
Bidder
|
A
|
B
|
C
|
AB
|
BC
|
AC
|
ABC
|
X
|
10
|
20
|
30
|
25
|
40
|
35
|
45
|
Y
|
15
|
25
|
25
|
30
|
35
|
40
|
55
|
Z
|
5
|
15
|
35
|
20
|
50
|
45
|
55
|
If GVA is the mechanism used, who will be the winners and what prices
will they pay? What valuations do you think the winners have for the
allocated subsets?
11. Rework the GVA truth revelation proof that we discussed in the
class for the case of the classical Vickrey auction (second price
sealed bid auction).
12. There are two items {A,B} and three bidders {X,Y,Z}. The valuations
of the bidders are provided in the matrix below.
| Bidder |
A
|
B
|
AB
|
X
|
0
|
0
|
3
|
Y
|
2
|
0
|
2
|
Z
|
0
|
2
|
2
|
Assuming a minimal bid increment of 1, write down the details of
successive rounds in the iBundle auction algorithm (on the lines that
we did in the class). Assume the initial prices as (0,0,0).
13. Do you think iBundle is truth revealing. If so, provide an
intuitive justification. If not, what can we do to make it truth
revealing?
14. In the e-procurement system PROMISE that was discussed in the
class, examine how a reverse Dutch auction will be relevant for
procuring a bundle of items. Do you think a forward Dutch auction can
also be used.
Top
Problem Set: 4
[1] Choose the correct answer(s):
(i) In a reverse auction:
[a] bid price decreases
[b] auctioneer is buyer
[c] auctioneer increases the price
[d] none of the above
(ii) Consider a combinatorial
auction with goods A, B, and C. Bidder X has following values for the
subsets: {A}=20, {B}=30, {C}=10, {A,B}=40, {A,C}=40, and {B,C}=30.
[a] A and C are complimentary
[b] B and C are substitutable
[c] A and B are complimentary
[d] A and C are substitutable
Note: (For problems 2-4)
Value
= Price at which the buyer is indifferent between the good and the money
Profit = Value - Price Paid (if
buyer gets the good) = 0 (Otherwise)
Every buyer maximizes his expected profit Incentive Compatible Auction:
Every bidder bids his true value (i.e. bidding true value
maximizes expected profit). To show the incentive compatibility of
auctions: The bidder has 3 possible strategies:
(1) overbidding (bidding above his
value),
(2) bidding his true value, and
(3) underbidding. His aim is to maximize his expected profit. With
logically consistent arguements, find out the best strategy for the
buyer.
[2] Show that Vickrey auction is incentive compatible.
[3] Consider the following auction. There is a single item for sale and
buyers submit sealed bids. The buyer who quoted the highest price
receives the item and he pays (b'+b")/2, where b' is the highest bid
and b" is the second highest bid. Is this auction incentive compatible?
[4] Show that Dutch auction and First price sealed bid auction are
strategically equivalent for a bidder.
[5] Consider the auction of M units of an item. The bidding language is
as follows: (xi, yi). The buyer i wants "upto" xi
units at unit price yi. The buyers submit sealed bids. Write
an algorithm to find the winning bidders and the number of goods each
receives, such that the seller's revenue is maximized. (# of bidders:
N).
[6] In the first price sealed bid auction, the strategy of a bidder is
to bid epsilon amount more than the 'expected' second highest
valuation. Let
there be N bidders and bidder 1 has value v_1. He does not know the
values of other bidders. He assumes that they are uniformly distributed
between 0 and v_1. What is price he will quote in his bid?
[7] Sniping (last minute bidding) in online auctions can be avoided by
the use of proxy bidding. Identify atleast two other techniques that
can prevent sniping. (Refer to online auction sites such as eBay and
Amazon).
Top
Problem Set: 5
Note 1: Notation: Zn* = Multiplicative group
modulo n of all positive integers less than n and relatively prime to n.
Note 2: Read up the following sections in the Handbook by Menezes et
al. Susection 1.1, 1.2, 1.3, 1.4, 1.5.1, 1.6, 1.7, 1.8, 1.9, 1.10,
1.11,1.12,
1.13, 8.1,8.2, 8.4, 11.1, 11.2, 11.3.1, 11.3.2, 11.5.2.
1. Study the Extended Euclidean algorithm (Algorithm 2.107 in the
Handbook). What is the worst-case computational complexity of this
algorithm.
2. Study the repeated square and multiply algorithm for modular
exponentiation (Algorithm 2.143 in the Handbook). What is the
worst-case computational complexity of this algorithm.
3. What is the worst-case compuatational complexity of:
(a) Key generation in RSA
(b) Encryption in RSA
(c) decryption in RSA
(d) Key generation in Elgamal
(e) Encryption in Elgamal
(f) decryption in ElGamal
(g) Digital Signature generation in RSA-based DS scheme with appendix
(h) Digital Signature Verification in RSA-based DS scheme with appendix
4. Given Zn* with n = 8, say whether it is
cyclic. If cyclic, find out all its generators.
5. Given Zn* with n = 12, say whether it is
cyclic. Justify your answer. If cyclic, determine all its generators.
6. Justify Step 3 of RSA Key Generation algorithm: Select a random
integer e, 1 < e < phi such that gcd (e, phi) = 1.
7. RSA: Choose p = 3; q = 5. Choose a public key and private key of
this scheme. Let the message be 2. What will be the encrypted message.
Show the decryption process also.
8. ElGamal: Choose p = 11. Choose alpha = 2 and a = 2. Compute the
public key and private key. Let the message be 5 and choose a random
integer k = 2. Show the encryption process, cipher text, and the
decryption process.
9. What is the need for a hash function in the context of digital
signatures ?
10. What is the difference between providing an authenticated message
and providing a digital signature?
11. RSA-based Digital Signature with Appendix: For the above choice of
public key, private key, and message, find the digital signature if the
hash function used is: h(m) = m^5 mod n. Show the verification of this
digital signature.
12. ElGamal-based Digital Signature with Appendix: For the above choice
of public key, private key, k, and message, find the digital signature
if the hash function used is: h(m) = m5 mod p. Show the
verification of this digital signature.
13. In an RSA system, you intercept the ciphertext c = 10 sent to a
user whose public key is e = 5, n = 35. What do you think is the
plaintext m?
14. In an RSA system, the public key of a given user is e = 31, n =
3599. What is the private key of this user.
15. In the ElGamal scheme, instead of sending (gamma, delta), why not
send (k, delta)?
16. In the RSA scheme, the private key of an entity A is broken, so A
has to regenerate a new pair of public key and priavte key. Is it safe
to use the same "n" for generating the new keys or should he use a
different n altogether?
17. With respect to the analogy between iBundle and primal-dual
algorithm for solving LPs, describe what the primal solution represents
and what the dual solution represents.
18. Suppose there is only one item that is to be auctioned and two
buying agents A and B are interested. If the valuation of A is 3 and
the valuation of B is 4, how does iBundle guarantee that B will be
allocated the object and not A. What price will B pay for the object.
Top
Problem Set: 6 (Security
and Electronic Payment)
1. Given a generator g for
the cyclic group Zp*,
p prime, d the private key of C, e=gd the public key,
the undeniable signature on the message m given by s = md
mod p , is initiated as :
C <-- V: z = sx ey
mod p .
Complete the response and verification steps. Why is this protocol
called undeniable ?
2. Give a simple authentication mechanism between a Merchant and a
Customer.
3.In a digital signature application which of 'e' and 'd' (servers
keys) should be smaller and why? (Hint: Clients are low power devices)
4.In the RSA scheme, what limits the number of different messages that
could be sent?
5. Explain the mathematical ideas behind the strength of the RSA and
ElGamal signature schemes.
6. What are the considerations in choosing the primes in the above
algorithms.
7. Compare the security of the following two methods of a customer
sending a message to a merchant: (a) encrypt message with the public
key of the merchant. (b) Use a digital envelope (that is, encrypt
message with a symmetric key and encrypt symmetric key with public key
of merchant).
8. Study the digital signature scheme based on El Gamal method.
9. Explain the use of a dual signature in the context of Kasbah.
10. In the three part form of representing electronic cash, how do you
prevent double spending of e-cash?
Top
|
