您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
Slopes and Lines - Buffalo State College.doc12页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
文档加载中...广告还剩秒
需要金币：150 &&
Slopes and Lines - Buffalo State College
你可能关注的文档：
··········
··········
Slopes and Lines
Algebra/Accelerated 7th & 8th Grade
1-Day Lesson Plan
TI-83 Calculator
Overhead projector and the TI-83 adapter
By: Mary Hojnacki
Objectives
The students will be able to:
Find the slope of a line given two points on that line.
NCTM Standard # 2 ,NYS Standard #2,7 Write an equation for a line in slope-intercept form when given the slope and y-intercept.
NCTM Standard # 2 ,NYS Standard #, 7 Determine the slope and the y-intercept of a line when given the equation of a line.
NCTM Standard # 2 ,NYS Standard #,7 Develop an understanding of the slope of a line.
NCTM Standard # 1,2 ,NYS Standard #1,2, Understand what the y-intercept is algebraically and graphically.
NCTM Standard # 2,3 ,NYS Standard #1,4,7 Use equations for lines to describe real situations.
NCTM Standard # 2 ,NYS Standard #,7 Graph a straight line given its equation, or given a point on the line and the slope of the line.
NCTM Standard # 2 ,3,10,NYS Standard #2,3,4 Find an equation for a line given its slope and one point on it.
NCTM Standard # 2 ,NYS Standard #,7 Note: Some of the objectives are for the lessons that preceded the lesson on the videotape.
Resources:
Scott Foresman, UCSMP Algebra, second edition, Chapter 7, copyright 1996.
http://math.buffalostate.edu/%7Eit/standards/index. NYS Standards with A level examples
Materials and Equipment
Class set of TI-83 graphing calculators.
Overhead projector and attachment for TI-83 graphing calculator.
Class set of rulers.
Graph paper.
Lesson Plan
Objectives:
The students will be able to:
Find the slope of a line given two points on that line.
Write an equation for a line in slope-intercept form when given the slope and y-intercept.
Determine the slope and the y-intercept of a line when given the equation of a line.
Develop an understanding of the slope of a line.
Understand what the y-intercept is algebraically and graphically.
Use equations for lines to describe real situations.
Outline of Activit
正在加载中，请稍后...The Composition Lines of the Visible Band of Synthetic Diamond_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
The Composition Lines of the Visible Band of Synthetic Diamond
上传于|0|0|文档简介
&&The visible band (band A) of Photoluminescence spectra of high-purity synthesized diamond is analyzed by deconvolution technique. A set of eight lines with distinct peak energy are found. The peak energy and the width of these lines were either constant or
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩3页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢【图文】新编大学英语(第二版)外研社Book2Unit2Part 1_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
新编大学英语(第二版)外研社Book2Unit2Part 1
上传于|0|0|暂无简介
大小：1.32MB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢ON THE NON-UNIQUENESS OF q-CONES OF MATROIDS_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
ON THE NON-UNIQUENESS OF q-CONES OF MATROIDS
上传于|0|0|文档简介
&&Abstract. Let M be a rank-r simple matroid that is representable over GF (q). A q-cone of M is a matroid M
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩1页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢From PEGWiki
The convex hull trick is a technique (perhaps best classified as a data structure) used to determine efficiently, after preprocessing, which member of a set of linear functions in one variable attains an extremal value for a given value of the independent variable. It has little to do with
algorithms.
The convex hull trick is perhaps best known in algorithm competitions from being required to obtain full marks in several USACO problems, such as , which began to be featured in national olympiads after its debut in the IOI '02 task , which itself credits the technique to a 1995 paper (see references). Very few online sources mention it, and almost none describe it. It has been suggested (van den Hooff, 2010) that this is because the technique is "obvious" to anybody who has learned the
Suppose that a large set of linear functions in the form
is given along with a large number of queries. Each query consists of a value of
and asks for the minimum value of
that can be obtained if we select one of the linear functions and evaluate it at . For example, suppose our functions are , , , and
and we receive the query . We have to identify which of these functions assumes the lowest -value for , or what that value is. (It is the function , assuming a value of 2.)
The variation in which we seek the maximal line, not the minimal one, is a trivial modification and we will focus our attention on finding the minimal line.
Graphical representation of the lines in this example
When the lines are graphed, this is easy to see: we want to determine, at the -coordinate 1 (shown by the red vertical line), which line is "lowest" ( has the lowest -coordinate). Here it is the heavy dashed line, .
For each of the
queries, of course, we may simply evaluate every one of the linear functions, and determine which one has the least value for the given -value. If
lines are given along with
queries, the complexity of this solution is . The "trick" enables us to speed up the time for this computation to , a significant improvement.
Consider the diagram above. Notice that the line
will never be the lowest one, regardless of the -value. Of the remaining three lines, each one is the minimum in a single contiguous interval (possibly having plus or minus infinity as one bound). That is, the heavy dotted line is the best line at all -values left of its intersection with
the heavy solid line is the best line between that intersection and its intersection with
and the light solid line is the best line at all -values greater than that. Notice also that, as
increases, the slope of the minimal line decreases: 2/3, -1/2, -3. Indeed, it is not difficult to see that this is always true.
Thus, if we remove "irrelevant" lines such as
in this example (the lines which will never give the minimum -coordinate, regardless of the query value) and sort the remaining lines by slope, we obtain a collection of
intervals (where
is the number of lines remaining), in each of which one of the lines is the minimal one. If we can determine the endpoints of these intervals, it becomes a simple matter to use
to answer each query.
The term convex hull is sometimes misused to mean upper/lower envelope. If we consider the "optimal" segment of each of the three lines (ignoring ), what we see is the lower envelope of the lines: nothing more or less than the set of points obtained by choosing the lowest point for every possible -coordinate. (The lower envelope is highlighted in green in the diagram above.) Notice that the set bounded above by the lower envelope is convex. We could imagine the lower envelope being the upper convex hull of some set of points, and thus the name convex hull trick arises. (Notice that the problem we are trying to solve can again be reformulated as finding the intersection of a given vertical line with the lower envelope.)
As we have seen, if the set of relevant lines has already been determined and sorted, it becomes trivial to answer any query in
time via binary search. Thus, if we can add lines one at a time to our data structure, recalculating this information quickly with each addition, we have a workable algorithm: start with no lines at all (or one, or two, depending on implementation details) and add lines one by one until all lines have been added and our data structure is complete.
Suppose that we are able to process all of the lines before needing to answer any of the queries. Then, we can sort them in descending order by slope beforehand, and merely add them one by one. When adding a new line, some lines may have to be removed because they are no longer relevant. If we imagine the lines to lie on a , in which the most recently added line is at the top, as we add each new line, we consider if the line on the top of the stack if it still is, we push our new line and proceed. If it is not, we pop it off and repeat this procedure until either the top line is not worthy of being discarded or there is only one line left (the one on the bottom, which can never be removed).
How, then, can we determine if the line should be popped from the stack? Suppose , , and
are the second line from the top, the line at the top, and the line to be added, respectively. Then,
becomes irrelevant if and only if the intersection point of
is to the left of the intersection of
and . (This makes sense because it means that the interval in which
is minimal subsumes that in which
was previously.) We have assumed for the sake of simplicity that no three lines are concurrent.
Clearly, the space required is : we need only store the sorted list of lines, each of which is defined by two real numbers.
The time required to sort all of the lines by slope is . When iterating through them, adding them to the envelope one by one, we notice that every line is pushed onto our "stack" exactly once and that each line can be popped at most once. For this reason, the time required overall is
although each individual line, when being added, can theoretically take up to linear time if almost all of the already-added lines must now be removed, the total time is limited by the total number of times a line can be removed. The cost of sorting dominates, and the construction time is
Up to 50000 rectangles of possibly differing dimensions are given and it is desired to acquire all of them. To acquire a subset of these rectangles incurs a cost that is proportional to neither the size of the subset nor to its total area but rather the product of the width of the widest rectangle in the subset times the height of the tallest rectangle in the subset. We wish to cleverly partition the rectangles into groups so that the tot what is the total cost if we do so? Rectangle that is, we may not interchange the length and width of a rectangle.
Suppose that both of rectangle A's dimensions equal or exceed the corresponding dimensions of rectangle B. Then, we may remove rectangle B from the input because its presence cannot affect the answer, because we can merely compute an optimal solution without it and then insert it into whichever subset contains rectangle A without changing the cost. Rectangle B, then, is irrelevant. We first sort the rectangles in ascending order of height and then sweep through them in linear time to remove irrelevant rectangles. What remains is a list of rectangles in which height is monotonically increasing and width is monotonically decreasing. (Otherwise, a contradiction would exist to our assumption that all irrelevant rectangles have been removed.)
In the sorted list of remaining rectangles, each subset to be acquired is contiguous. Thus, for example, if there are four rectangles, numbered 1, 2, 3, 4 according to their order in the sorted list, it is possible for the optimal partition to be
but not ; in the latter,
is contiguous but
is not. This is true because, in any subset, if rectangle A is the tallest and rectangle B is the widest, then all rectangles between them in the sorted list may be added to this subset without any additional cost, and therefore we will always assume that this occurs, making each subset contiguous.
The remaining problem then is how to divide up the list of rectangles into contiguous subsets while minimizing the total cost. This problem admits a
solution by , the pseudocode for which is shown below: Note that it is assumed that the list of rectangles comes "cooked"; that is, irrelevant rectangles have been removed and the remaining rectangles sorted.
for i ∈ [1..N]
input rect[i].h
input rect[i].w
let cost[0] = 0
for i ∈ [1..N]
let cost[i] = ∞
for j ∈ [0..i-1]
cost[i] = min(cost[i],cost[j]+rect[i].h*rect[j+1].w)
print cost[N]
In the above solution, cost[k] stores the minimum possible total cost for acquiring the first k rectangles. Obviously, cost[0]=0. To compute cost[i] when i is not zero, we notice that it is equal to the total cost of acquiring all previous subsets plus the total cost of acquiring the subset containing rectangle number i; the latter may be readily calculated if the size of the latter subset is known, because it is merely the width of the first times the height of the last (rectangle number i). We wish to minimize this, hence cost[i] = min(cost[i],cost[j]+rect[i].h*rect[j+1].w). (Notice that j is the last rectangle of the previous subset, looping over all possible choices.)
Unfortunately,
is too slow when , so a better solution is needed.
Let , , and . Then, it is clear that the inner loop in the above DP solution is actually trying to minimize the function
by choosing
appropriately. That is, it is trying to solve exactly the problem discussed in this article. Thus, assuming we have implemented the lower envelope data structure discussed in this article, the improved code looks as follows:
for i ∈ [1..N]
input rect[i].h
input rect[i].w
let E = empty lower envelope structure
let cost[0] = 0
add the line y=mx+b to E, where m=rect[1].w and b=cost[0] //b is zero
for i ∈ [1..N]
cost[i] = E.query(rect[i].h)
E.add(m=rect[i+1].w,b=cost[i])
print cost[N]
Notice that the lines are already being given in descending order of slope, so that each line is added "at the right"; this is because we already sorted them by width. The query step can be performed in logarithmic time, as discussed, and the addition step in amortized constant time, giving a
solution. We can modify our data structure slightly to take advantage of the fact that query values are non-decreasing (that is, no query occurs further left than its predecessor, so that no line chosen has a greater slope than the previous one chosen), and replace the binary search with a , reducing query time to amortized constant as well and giving a
solution for the DP step. The overall complexity, however, is still , due to the sorting step.
You are given:
A sequence of
positive integers ().
The integer coefficients of a quadratic function , where .
The objective is to partition the sequence into contiguous subsequences such that the sum of
taken over all subsequences is maximized, where the value of a subsequence is the sum of its elements.
dynamic programming approach is not hard to see.
We define:
sum(i,j) = x[i] + x[i+1] + ... + x[j]
adjust(i,j) = a*sum(i,j)^2 + b*sum(i,j) + c
Pseudocode:
dp[0] ← 0
for n ∈ [1..N]
for k ∈ [0..n-1]
dp[n] ← max(dp[n], dp[k] + adjust(k + 1 , n))
Now let's play around with the function "adjust".
by . Then, for some value of , we can write
Then, we see that
is the quantity we aim to maximize by our choice of . Adding
(which is independent of ) to the maximum gives the correct value of . Also,
is independent of , whereas
are independent of , as required.
Unlike in task "acquire", we are interested in building the "upper envelope". We notice that the slope of the "maximal" line increases as
increases. Since the problem statement indicates , the slope of each line is positive.
Suppose . For
we have slope . For
we have slope . But ,
and since the given sequence is positive, so . We conclude that lines are added to our data structure in increasing order of slope.
Since , query values are given in increasing order and a
suffices (it is not necessary to use binary search.)
The convex hull trick is easy to implement when all insertions are given before all queries (offline version) or when each new line inserted has a lower slope than any line currently in the envelope. Indeed, by using a deque, we can easily allow insertion of lines with higher slope than any other line as well. However, in some applications, we might have no guarantee of either condition holding. That is, each new line to be added may have any slope whatsoever, and the insertions may be interspersed with queries, so that sorting the lines by slope ahead of time is impossible, and scanning through an array to find the lines to be removed could take linear time per insertion
It turns out, however, that it is possible to support arbitrary insertions in amortized logarithmic time. To do this, we store the lines in an ordered dynamic set (such as C++'s std::set). Each line possesses the attributes of slope and y-intercept, the former being the key, as well as an extra
field, the minimum -coordinate at which this line is the lowest in the set. To insert a new line, we merely insert it into its correct position in the set, and then all the lines to be removed, if any, are contiguous with it. The procedure is then largely the same as for the case in which we always inserted lines of minimal slope: if the line to be added is , the line to the left is , and the line to the left of that is , then we check if the - intersection is to the left of the - if so,
is dis similarly, if lines
are on the right, then
can be removed if the - intersection is to the left of the - intersection, and this too is performed repeatedly until no more lines are to be discarded. We compute the new
values (for , it is the - intersection, and for , it is the - intersection).
To handle queries, we keep another set, storing the same data but this time ordered by the
value. When we insert or remove lines from that set (or update, in the case of
above), we use the
value from the element in that set to associate it with an element in this one. Whenever a query is made, therefore, all we have to do is to find the greatest
value in this set that is less
the corresponding line is the optimal one .
Brucker, P. (1995). Efficient algorithms for some path partitioning problems. Discrete Applied Mathematics, 62(1-3), 77-85.
Christiano, Paul. (2007). Land acquisition. Retrieved from an archived copy of the competition problem set at
Peng, Richard. (2008). USACO MAR08 problem 'acquire' analysis. Retrieved from
van den Hooff, Jelle. (2010). Personal communication.
Wang, Hanson. (2010). Personal communication.