الگوریتم امروز

وبلاگ تخصصی الگوریتم

الگوریتم امروز

وبلاگ تخصصی الگوریتم

وبلاگ علمی و مخصوص مباحث الگوریتمی است.
نظر خصوصی نگذارید چون جواب نمی‌دهم نظر عمومی بگذارید بدون نام هم که باشد همانجا جواب می‌دهم.

بایگانی

دو سوال جا افتاده از نمونه سوالات قبلی

چهارشنبه, ۱۰ ارديبهشت ۱۳۹۳، ۰۴:۱۱ ب.ظ

Next two questions are on PRAM. (Linearly ordered means any two elements are comparable and they can be oredered from smaller to bigger)


Problem 6:  Let A=(a_1,a_2,...,a_n) be an array of elements drawn from a linearly ordered set. The suffix-minima problem is to compute for each i, where 1 <= i  <= n, the minimum element among {a_i,a_{i+1},...,a_n}. Develop an O(log n) time algorithm to compute suffix minima of A using a total of O(n) operations.


Problem 7: Given an array A=(a_1,a_2,...,a_n) where the elements come from a linearly ordered set S, and given two elements x,y in S, show how to store all the elements a_i from A that are between x and y in consecutive memory locations. 

Your algorithm should run in O(log n) time using O(n) operations. 

موافقین ۰ مخالفین ۰ ۹۳/۰۲/۱۰
سپیده آقاملائی

نظرات  (۰)

هیچ نظری هنوز ثبت نشده است

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی