## Description

I. Overview

You have practiced empirical evaluations in your previous assignment. The current one thus

complements your practice by focusing on theoretical evaluations. It also gives you an incentive to

take the time to reflect on what worked for you and how you may improve.

II. Reflection

You’ve now had several weeks of the course, so you have gotten feedback on your performance and

you are familiar with the expectations as well as the format. This is a good time to reflect on what

worked for you and what may need some improvement going forward. To help you contextualize the

quantitative feedback (=grades), the grade for each activity in the class is provided on the next page.

1) What has worked. What are you currently doing that is helping you to prepare for this course?

Please detail at least two activities, over at least one paragraph.

2) What needs to be addressed. What do you see as the main challenges in this course? Please detail

at least two challenges, over at least one paragraph. In case you don’t see any challenge, think of

what may be most challenging for others.

3) How you may address your challenges. For each of the challenges listed in #2, explain how you plan

to address it. You may identify resources that could be helpful but that you haven’t used yet.

4) Class design. Although this is the 4th semester in a row that the class is taught, there are always a

chance to learn from your feedback and adjust for next semester or, when it is feasible, changes to

the current term. Think of the ways in which the class is taught and then identify what you find

most helpful and/or what could change. Note that questions 1-3 are about yourself but this

question is about the class design, so it affects everyone.

III. Tricky little loopses

A common assumption when doing a Θ analysis is

that you can just look at loops. One may assume

that a single loop would be Θ(n), a nested loop

Θ(n2

) and so for. However, there is much more to it

than that: we need to precisely understand what

the loops do! This function will serve as example→

1) Copy mystery into Eclipse. Edit its code so that

it returns both the answer and the number of times

that the loop runs. (Hint: use a Pair)

In your main function, call mystery on arrays of

different sizes and show how many times the loop

runs for each array size.

In comments below your main function, interpret

the results and conclude about the Θ of mystery

0.5 pt

each

public static boolean mystery(int[] array){

int index=1;

boolean answer = true;

for(int i=0;i<array.length-1;) {

if(index==array.length) {

i = i + 1;

index=i+1;

}

else {

if(array[i]>=array[index])

answer=false;

index = index + 1;

}

}

return answer;

}

1 pt

each

2) The function mystery had a single loop, yet it did not have the complexity that you may have

expected from a single loop. Explain which tricks were used in the function such that its complexity

was not as it may have seemed from a cursory look.

3) Use the same tricks as you learned from mystery to write a function trickyhobbitses that has a

single for loop but runs in Θ(n3

).

Include your entire Eclipse project (not just the src files) into your zip file for submission.

IV. Various levels of analyses

1) Detail the Θ complexity of addStuff.

2) Detail the ~ complexity of addStuff.

3) Imagine that you had to choose between addStuff

and another solution with a complexity of Θ(n3

).

Explain how you would arrive at a decision.

4) Imagine that you had to choose between addStuff

and another solution with a complexity of Θ(n2

).

Explain how you would arrive at a decision.

Provide your answers in a PDF and include it into your zip file for submission.

V. Unusual times

The two questions in this section can be challenging at first, because they will get you to think.

Although you have all it takes to answer them, you may not immediately think of the solution. And

that’s ok. Many algorithms will take time to come up with, and sometimes a bit of inspiration. Look at

these questions early enough so you give yourself time. A hint is provided to help you.

1) The most common categories of time complexity are listed on the next page, which you can print

as a cheat sheet for your midterm (when the time comes). However, there are other categories. They

may be rare, but they still exist. One such category is Θ(log log n). In other words, the time complexity

grows as a function of the log of the log of n.

Consider a function that takes as argument an array list representing consecutive numbers from 1 to

n (e.g., 1, 2, 3, 4, …). Explain which algorithm you may create such that the function runs in Θ(log log

n). Your algorithm does not need to do something useful, but it has to do it in Θ(log log n).

Hint: Θ(log log n) arises when one function over the data results in data of size log n, which is further

processed through another function in log n.

2) Consider a function that takes as arguments two arrays of the same length, which represent

consecutive numbers from 1 to n. Explain which algorithm you may create such that the function runs

in Θ(log2

n). Your algorithm does not need to do something useful, but it has to do it in Θ(log2

n).

Hint: Θ(log2

n) is the product of two log functions, that is, log n * log n.

Provide your answers in a PDF and include it into your zip file for submission.

public static int addStuff(int[] array){

int res = 0;

for(int i=0; i<array.length; i++)

for(int j=i; j<array.length; j++)

res += 2;

return res;

}

0.5 pt

each

1 pt

each

Algorithms Cheat Sheet

Core concepts, in short:

– The ‘efficiency’ of your solution is always a trade-off, at least between time and space. Prioritizing

one over the other depends on the context (e.g., embedded systems, real-time systems).

– Knowing the time complexity by reading the code is very limited (i.e. theoretical), because the

code may intricate, and because it requires a top-notch knowledge of what a language does.

– Knowing the time complexity by running the code (i.e. empirical) will tell us exactly how long it

takes on one specific hardware, given one specific use of this hardware, and given the versions

of the libraries used to run the code. It’s specific but also ‘polluted’ by all these factors.

– The (theoretical) time complexity is often expressed as a function of the size of the input. The

first input is denoted n, the next one m.

– The size of the input cannot always be assumed to be arbitrarily large. In many applications, it is

known and fixed. What may vary could be the amount of missing data or its properties.

– Counting the theoretical time complexity is done through two assumptions: uniform cost model

(we assumed that each operation takes a constant amount of time although we do know that

adding two big numbers is longer than two small ones) and random access machine model (we

lump all operations together by assuming they all take the same time although we do know that

a division is longer than a multiplication).

– We have four notations for the theoretical time complexity:

o Exact one. Count everything, sort it by decreasing term at the end.

E.g.: ⅙ N 3 + 20 N

+ 16

o ~ (“tilde”). Drop all terms but the leading one.

E.g.: ⅙ N 3 + 20 N

+ 16 ~ ⅙ N 3

o Θ (“theta”). Drop all terms and constants but the leading one.

E.g.: ⅙ N

3 + 20 N

+ 16 is in Θ(N

3

)

o O (“big O”). Take any function either of the same class or above. There are multiple

answers to this one whereas there is a single answer to ~ or Θ.

E.g.: ⅙ N

3 + 20 N

+ 16 is in O(N

3

) but also O(N

4

), O(N

5

), O(N!) or O(2

N

) since all of

these functions are eventually bigger than ⅙ N

3 + 20 N

+ 16 from some N onward.