طراحي الگوريتم

---

شرح پروژه

1) با استفاده از روش تقسيم و حل الگو ريتم کارآمدي با زمان اجراي كمتر از خطي بنويسيد که در يک جدول(آرايه) n*n يک مقدار مفروض را جستجو کند. اين جدول در راستاي سطرها و ستون ها مرتب شده اند. ورودي فايل in.txt است كه در سطر اول آن عدد n مشخص شده و درn سطر بعدي فايل : در هر سطر n عدد مربوط به آن سطر آمده است. مثال: 5 1 4 7 12 20 2 6 15 17 33 5 8 19 21 34 9 10 22 23 35 2) يك الگوريتم كارا براي پيدا كردن بزرگترين زير رشته¬اي كه هم به صورت پيشرو و هم به صورت عقبرو در رشته ورودي مشاهده مي¬شود، ارائه دهيد. دو زير رشته پيشرو و عقبرو نبايد با هم اشتراك داشته باشد. الگوريتم شما بايد در زمان O(n2) انجام شود. در زير چند مثال آمده است: • For T = ALGORITHM, your algorithm should return 0. • For T = CPEGCOMP, your algorithm should return 1, for the substring C or P. • For T = MANYDYNAMICPROGRAMMING, your algorithm should return 4, for the substring MANY. Note that neither MANYD or MANYDYNAM count, since each overlaps its backwards occurrence in T. 3) Suppose we are given an array A[1..n] of distinct numbers with the special property that A[1] > A[2] and A[n − 1] < A[n]. We say that an element A[x] is a local minimum if it is less than both its neighbors, or more formally, if A[x − 1] > A[x] and A[x] < A[x + 1]. For example, there are two local minima (3 and 1) in the following array: 9 3 7 2 1 4 5 We can obviously find a local minimum in O(n) time by scanning through the array. Describe and analyze an algorithm that finds a local minimum in O(log n) time. If there is more than one local minimum, finding any of them is fine. [Hint: With the given boundary conditions, the array must have at least one local minimum. ]


قابل تحویل:

مهارت ها و تخصص های مورد نیاز

---

---