Computer Science

Introduction to Algorithms

Which Algorithm Works Warmup

         

A Nasa robot (bottom right) is trying to rendezvous back with the spaceship (top left). However, it cannot enter the marked yellow squares, which represent unstable areas due to tectonic activity.

Which of these algorithms would guide the robot safely back to the spaceship?

Algorithm 1: Walk 1 square up and 1 square left. Repeat.
Algorithm 2: Walk 2 squares up and 2 squares left. Repeat.
Algorithm 3: Walk 1 square left and 1 square up. Repeat.
Algorithm 4: Walk 2 squares left and 2 squares up. Repeat.

Show explanation
by Brilliant Staff

Peter wants to create an algorithm to ensure that he buys exactly N items.

Which of these algorithms could he use?

Algorithm 1: Start with n=1 n =1 .
Buy one item. Increase nn by 1.
Repeat. Stop when n=N n = N .

Algorithm 2: Start with n=1 n =1 .
Buy one item. Multiply nn by 2.
Repeat. Stop when n=N n = N .

Algorithm 3: Start with n=0 n =0 .
Buy one item. Increase nn by 1.
Repeat. Stop when n=N n = N .

Show explanation
by Brilliant Staff

Helen wants to create an algorithm that would help her find the largest number in a set. Assume that the set is denoted by a[0], a[1], ..., a[N-1].

Which of these algorithms could she use?

Algorithm 1:

  • Start with i = 0.
  • While i < N - 1:
    • Set large = a[i].
    • Increase i by 1.

Algorithm 2:

  • Start with i = 0 and large = a[0].
  • While i < N:
    • If a[i] > large, replace large with a[i].
    • Increase i by 1.

Algorithm 3:

  • Start with i = 0. Set large = a[0].
  • While i < N - 1:
    • If a[i] > large, replace large with a[i].
    • Increase i by 1.
Show explanation
by Brilliant Staff

Jordan wants to create an algorithm to count the number of positive numbers out of an array of real numbers. Assume that the array is denoted by {a[0], a[1], ... , a[N - 1]}. Clearly, N is the number of elements in the array a

Which of these algorithms could he use? (They only differ by the first line.)

Algorithm 1:

  • Start with i = 0 and total = 0.
  • While i < N:
    • If a[i] > 0, increase total by 1.
    • Increase i by 1.

Algorithm 2:

  • Start with i = 0 and total = 1.
  • While i < N:
    • If a[i] > 0, increase total by 1.
    • Increase i by 1.

Algorithm 3:

  • Start with i = 1 and total = 0.
  • While i < N:
    • If a[i] > 0, increase total by 1.
    • Increase i by 1.
Show explanation
by Brilliant Staff

Susan wants to create an algorithm that finds the Nth Fibonacci number, which follows the rules that

F1=1,F2=1,Fn=Fn−1+Fn−2. F_1 = 1, F_2 = 1, F_{n} = F_{n-1} + F_{n-2}.

Which of the following algorithms could she use to find FN F_N?

Algorithm 1: Set n=1;first=1;second=1 n=1; \color{#D61F06}{\text{first}} = 1; \color{#3D99F6}{\text{second}} = 1 .
1. If n=N n = N , print first\color{#D61F06}{\text{first}} and end the program.
2. Set first=second;second=second+first \color{#D61F06}{\text{first}} = \color{#3D99F6}{\text{second}}; \color{#3D99F6}{\text{second}} = \color{#3D99F6}{\text{second}} + \color{#D61F06}{\text{first}} and increase nn by 1.
3. Go back to step one.

Algorithm 2: Set n=1;first=1;second=1 n=1; \color{#D61F06}{\text{first}} = 1; \color{#3D99F6}{\text{second}} = 1 .
1. If n=N n = N , print first\color{#D61F06}{\text{first}} and end the program.
2. Set second=second+first;first=second \color{#3D99F6}{\text{second}} = \color{#3D99F6}{\text{second}} + \color{#D61F06}{\text{first}}; \color{#D61F06}{\text{first}} = \color{#3D99F6}{\text{second}} and increase nn by 1.
3. Go back to step one.

Algorithm 3: Set n=1;first=1;second=1 n=1; \color{#D61F06}{\text{first}} = 1; \color{#3D99F6}{\text{second}} = 1 .
1. If n=N n = N , print first\color{#D61F06}{\text{first}} and end the program.
2. Set second=second+first,first=second−first \color{#3D99F6}{\text{second}} = \color{#3D99F6}{\text{second}} + \color{#D61F06}{\text{first}}, \color{#D61F06}{\text{first}} = \color{#3D99F6}{\text{second}} - \color{#D61F06}{\text{first}} and increase nn by 1.
3. Go back to step one.

Show explanation
by Brilliant Staff
×

Problem Loading...

Note Loading...

Set Loading...