|
|
programing 2
|
Deadline: 1386/4/8
|
|
|
The Circus Problem
A circus is designing an act consisting of a tower of people standing on each others’
Shoulders. For practical and aesthetic reasons, each person on top of another must be
both shorter and lighter. Given the heights and weights of each person in the circus, what
is the largest number of people in such a tower?
Example: Input: 6 65 100 70 150 56 90 75 190 60 95 68 110
Output: The longest tower is length 6 and includes from top to bottom:
56,90 60,95 65,100 68,110 70,150 75,190
You muse also give a complete document for your programming code. (40% of your grade)
Put your files in a folder that its name contains “DAP2”+ "your student number" and send them to kafi@ce.sharif.edu |
|
|
|
|
exercise9
|
Deadline: 1386/3/19
|
|
|
Consider the below grammar:
initial(vp)
vp --> v,np
vp --> v,np,pp
np --> det,n
np --> det,n,pp
pp --> [with],np
v --> [saw]
n --> [man]
n --> [binoculars]
det --> [the]
How I can parse this statement:
“saw the man with the binoculars”? |
|
|
|
|
greedy
|
Deadline: 1386/2/30
|
|
|
Interval Cover
Define a unit interval as a subset of the real line of the form [a, b] = {z : a <= z <= b}, where b − a = 1. For example, [ 5/4 , 9/4 ] is a unit interval.
Consider the problem Interval-Cover where the input is a set {x1, x2, . . . , xn} of n points
in arbitrary order on the real line, and the output is a set consisting of the smallest number of unit intervals that cover all the input points (in the sense that every point is in at least one of the intervals).
As an example, suppose the input is {7/4 , 7/2 , 1/2 , 2 , 3/2, 0}. Then {[0,1], [5/4,9/4], [ 5/2 , 7/2]} is a valid output: we can easily check that these three intervals cover all of the six input points, and also that no two unit intervals can cover all of the input points. |
|
|
|
|
Dynamic Programming
|
Deadline: 1386/2/16
|
|
|
1.
Given: A sequence of matrices A1...An to be multiplied where each Ai has dimension pi-1 x pi.
To do: A parenthesization of the sequence that minimizes the number of scalar multiplications needed.
2.
Input: a set of S = { s1, …, sn } of n items where each si has value vi and weight wi, and a knapsack capacity W.
Required solution: choose a subset O of S such that the total weight of the items chosen does not exceed W and the sum of items vi in O is maximal with respect to any other subset that meets the constraint.
send them to sharifian@ce.sharif.edu, you should deliver them before exercise class, i mean 12:30, 16th ofb ORDIBEHESHT |
|
|
|
|
Transform and conquer
|
Deadline: 1386/2/10
|
|
|
1.A company makes two products (X and Y) using two machines (A and B). Each unit of X that is produced requires 50 minutes processing time on machine A and 30 minutes processing time on machine B. Each unit of Y that is produced requires 24 minutes processing time on machine A and 33 minutes processing time on machine B.
At the start of the current week there are 30 units of X and 90 units of Y in stock. Available processing time on machine A is forecast to be 40 hours and on machine B is forecast to be 35 hours.
The demand for X in the current week is forecast to be 75 units and for Y is forecast to be 95 units. Company policy is to maximise the combined sum of the units of X and the units of Y in stock at the end of the week.
Formulate the problem of deciding how much of each product to make in the current week as a linear program.
Solve this linear program graphically.
please sendit to sharifian@ce.sharif.edu |
|
|
|
|
programming1
|
Deadline: 1386/2/8
|
|
|
» Assignment File:
|
» Comments:
The attached file contains the definition of your programming exercise.
Each code will be test by 4 input examples.
You muse also give a complete document for your programming code. (40% of your grade)
Put your files in a folder that its name contains your student number and “DAP1” and send them to sharifian@ce.sharif.edu |
|
|
|
|
decrease and conquer
|
Deadline: 1386/2/1
|
|
|
برای تشخیص همبند بودن گراف الگوریتمی ارائه دهید.
please send it to sharifian@ce.sharif.edu |
|
|
|
|
divide and conquer
|
Deadline: 1386/2/1
|
|
|
Closest Pair
Input:
P = {p(1), p(2) ,..., p(n) }
where p(i) = ( x(i), y(i) ).
A set of n points in the plane.
Output
The distance between the two points that are closest.
Note: The distance DELTA( i, j ) between p(i) and p(j) is defined by the expression:
Square root of { (x(i)-x(j))^2 + (y(i)-y(j))^2 }
describe a divide-and-conquer algorithm for this problem.
please send them to sharfian@ce.sharif.edu |
|
|
|
|
Recurrence Equations
|
Deadline: 1385/12/25
|
|
|
|
From CLRS: 4.3-1, 4.3-4, 4-1, 4-5 |
|
|
|
|
Amortized Analysis
|
Deadline: 1385/12/21
|
|
|
|
From CLRS: 17-1, 17-2, 17-3 |
|
|
|
|
