Coursework University of Surrey

[fundamental skills and numeracy] The purpose of this task is to strengthen your familiarity with growth rates of running times.

Suppose you have algorithms with the ﬁve running times listed below. (Assume these are the exact number of operations performed as a function of the input size n). Suppose your computer runs with 10 GHz, ie can perform 1010 operations per second, and you need to compute a result in at most one hour of computation. For each of the algorithms, what is the largest input n for which you would be able to get the result within an hour?

- f(n) = n
^{2} - f(n) = n
^{3} - f(n) = 100n
^{3} - f(n) = nlog(n)
- f(n) = 2
^{n} - Finally, what is the ratio between the largest and smallest number of inputs that can be processed within an hour for algorithms with the above running times?

For each of the following recurrence relations determine values a,b,c and possibly k to insert into the master theorem as presented in the lecture. Determine which case of the master theorem applies and give the solution for T(n) if the relation can be solved using one of the cases of the Master Theorem. Otherwise, explain why the Master Theorem is not applicable.

- T(n) = 9T(n/9) + n
^{2} - T(n) = 9/4 T(2/3 n) + n
- T(n) = 8T(n/4) + n
^{3/2} - T(n) = (4/3)
^{n}T (n/4) + n^{2} - T(n) = √2T (n/2) + log n

This exercise is about applying one of the algorithms from the lecture on a small scale by hand to experience how a divide-and-conquer algorithm works. In your solution, refer to the points given by their label pi rather than just be their coordinates.

It is essential that you follow the algorithm.Any graphs or graphical argumentation you might ﬁnd helpful for your own understanding of the algorithm will be ignored for marking as they are not part of the algorithm.

Let the set S = {pi|i = 1,2,··· ,8} contain the following points:

p1 = (10,9) p2 = (12,−11) p3 = (−11,8) p4 = (−6,−7) p5 = (15,8) p6 = (14,−10) p7 = (−5,−4) p8 = (−9,−6)

Find the minimal distance of points within the set using the algorithm from the lecture. Calculate distances using the Euclidean metric

Consider the following basic problem: You are given an array A consisting of n integers A[0],A[2],··· ,A[n]. You would like to output a 2D n × n array B in which B[i,j] (for i < j) contains the sum of array entries from A[i] through A[j] – that is the sum A[i] + A[i + 1] +···A[j]. The entry B[i,i] shall have the value A[i] (ie the sum running from A[i] to A[i]). (The value of entries B[i,j] is left unspeciﬁed whenever i > j, so it does not matter what is output for these values, or whether there is a value at all.)

Here is a simple brute force algorithm to solve this problem:

- for i = 1,2,···n do
- for j = i + 1,i + 2,···n do
- Add up entries A[i] to A[j].
- Store the result in B[i,j].
- end for
- end for
- Return B.

1. Give a big-O bound on the running time of this algorithms in terms of n and the reasoning which leads up to your result for the big-O.

2. Although the algorithm is the most straight forward way to solve the problem, it contains some unnecessary sources of ineﬃciency. Find a diﬀerent algorithm with a lower order of running time, and write it down in pseudo-code with a lower order of running time.

Assignment Writing Help

- Science Assignment Help
- Math Assignment Help
- Chemistry Assignment Help
- Physics Assignment Help
- Biology Assignment Help
- Psychology Assignment Help
- History Assignment Help
- Geography Assignment Help
- English Assignment Help
- Humanities Assignment Help
- Nursing Assignment Help
- Social Science Assignment Help
- Arts and Architecture Help
- Statistics Assignment Help
- Law Assignment Help
- Computational Mathematics Assignment Help

Engineering Assignment Services

- Programming Assignment Help
- Database Help
- Data Structure Assignment Help
- Operating Systems Assignment Help
- Computer Network Assignment Help
- UML Diagram Assignment Help
- IT Assignment Help
- Game Programming Help
- Computer Science Assignment Help
- Information Systems Assignment Help
- Chemical Engineering Assignment Help
- Civil Engineering Assignment Help
- Electrical, Electronics Help
- Mechanical Engineering Assignment Help
- Petroleum Engineering Assignment Help
- Biochemical and Biotechnology Help

Do My Assignment Help

- Accounting Assignment Help
- Finance Assignment Help
- Economics Assignment Help
- Marketing Assignment Help
- Human Resources Assignment Help
- Operations Management Assignment Help
- Strategy and Planning Help
- Project Management Help
- Case Studies Writing Help
- Political science
- Referencing Help
- Assignment Help Websites
- Online Assignment Help
- Do My Assignment
- Do My Homework

Write My Essay Services

- Essay Writing Help
- Business Essay Writing Help
- Assignment Writing Services
- Plagiarism Free Essay Writing
- Essay Editing Service
- Dissertation Writing Services
- Thesis Writing Help
- Custom Writing Help
- Write My Essay
- Write My Paper
- Paper Writing Service
- Academic Writing Help
- College Essay Writing
- Cheap Essay Writing