### All Weeks Algorithmic Toolbox Coursera Quiz Answers

### Algorithmic Toolbox Coursera Quiz Answers

#### Week 1: Solving Programming Challenges

Q1. What will you typically need to implement yourself in the programming assignments if you program in C++, Java or Python?

- Just reading the input.
**Just the solution of the problem.**- Just writing the output.
- Reading input, writing output and the solution to the problem.

Q2. Your program in C, C++ or Java thinks that the product of numbers 5000050000 and 5000050000 is equal to -1794967296−1794967296. What is the most probable reason?

**Integer overflow.**- Compiler error.
- The input data is incorrect.
- The problem statement is wrong.

Q3. Which tests should you perform before submitting a solution to the programming assignment?

- Just submit the program and see if it passes the assignment.
**Test on the examples from the problem statement. Then make a few other small tests, solve them manually and check that your program outputs the correct answer. Generate a big input and launch your program to check that it works fast enough and doesn’t consume too much memory. Test for corner cases: smallest allowed values and largest allowed values of all input parameters, equal numbers in the input, very long strings, etc. Then make a stress test. After all these tests passed, submit the solution.**- Test on the examples from the problem statement. Then make a few other small tests, solve them manually and check that your program outputs the correct answer. After all these tests passed, submit the solution.
- Just check that the answers for the examples from the problem statement are correct.

Q4. Where does the input data come from when you implement a stress test?

**You generate valid input data as a part of the stress test implementation.**- You download and use the tests we’ve prepared to check your solution to the problem.
- You enter the input data manually.

Q5. If you submit a solution of a programming assignment, but it does not pass some of the tests, what feedback will you get from the system?

- You will see the input data, the answer of your program, the correct answer, how long did your program work and how much memory did it use for each of the tests.
**If it is one of the first few tests, you will see the input data, the answer of your program and the correct answer. Otherwise, you will only see either that the answer of your program is wrong or that your program is too slow or that your program uses too much memory.**- You will only get the feedback that your program either passed or did not pass.

#### Week 2: Algorithmic Toolbox

#### QUIZ 1: Logarithms

Q1. The goal of this assignment is to practice with logarithms that appear frequently in the analysis of algorithms.

Recall that \log_anlog*a**n* is the power to which you need to raise a*a* in order to obtain n*n*.

The main rules for working with logarithms are the following:

- log
*a*(*nk*)=*k*log*an* - log
*a*(*nm*)=log*an*+log*am* *n*log*ab*=*b*log*an*- log
*an*⋅log*ba*=log*bn*

Is it true that (log5*n*)2=2log5*n*?

- Yes
**No**

Q2. log2*n*⋅log32=log3*n*

**Yes**- No

Q3. *n*log2*n*=*n*

- Yes
**No**

Q4. log3(2*n*)=log32⋅log3*n*

- Yes
**No**

Q5. log10(*n*2)=2log10*n*

**Yes**- No

Q6. *n*log73=7log3*n*

- Yes
**No**

#### Quiz 2: Big-O

Q1. Introduction and Learning Outcomes

The goal of this assignment is to practice with big-O notation.

Recall that we write f(n)=O(g(n))f(n)=O(g(n)) to express the fact that f(n)f(n) grows no faster than g(n)g(n): there exist constants NN and c>0c>0 so that for all n \ge Nn≥N, f(n) \le c \cdot g(n)f(n)≤c⋅g(n).

Is it true that log2*n*=*O*(*n*2)?

**Yes**- No

Q2. *n*log2*n*=*O*(*n*)

- Yes
**No**

Q3. *n*2=*O*(*n*3)

**Yes**- No

Q4. *n*=*O*(*n*)

- Yes
**No**

Q5. 5log2*n*=*O*(*n*2)

- Yes
**No**

Q6. *n*5=*O*(23log2*n*)

- Yes
**No**

Q7. 2*n*=*O*(2*n*+1)

**Yes**- No

#### Quiz 3: Growth rate

Q1. Order the given functions by increasing growth rate.

f_1(n)=n^3*f*1(*n*)=*n*3

f_2(n)=n^{0.3}*f*2(*n*)=*n*0.3

f_3(n)=n*f*3(*n*)=*n*

f_4(n)=\sqrt{n}*f*4(*n*)=*n*

f_5(n)=\frac{n^2}{\sqrt{n}}*f*5(*n*)=*n**n*2

f_6(n)=n^2*f*6(*n*)=*n*2

As an answer, provide a string of length exactly six (with no spaces or quotes) containing the numbers of six functions (the first number indicates the function with the smallest growth rate, while the last number indicates the function with the largest growth rate). For example, for a similar, but simpler problem f_1(n)=n^2*f*1(*n*)=*n*2, f_2(n)=n*f*2(*n*)=*n*, f_3(n)=n^3*f*3(*n*)=*n*3 the answer would be 213.

Enter answer here

Q2. Order the given functions by increasing growth rate.

f_1(n)=3^n*f*1(*n*)=3*n*

f_2(n)=n\log_2n*f*2(*n*)=*n*log2*n*

f_3(n)=\log_4n*f*3(*n*)=log4*n*

f_4(n)=n*f*4(*n*)=*n*

f_5(n)=5^{\log_2n}*f*5(*n*)=5log2*n*

f_6(n)=n^2*f*6(*n*)=*n*2

f_7(n)=\sqrt{n}*f*7(*n*)=*n*

f_8(n)=2^{2n}*f*8(*n*)=22*n*

As an answer, provide a string of length exactly eight (with no spaces or quotes) containing the indices of eight functions (so, the first number indicates the function with the slowest growth rate, while the last number indicates the function with the highest growth rate). For example, for a similar, but simpler problem f_1(n)=2^n*f*1(*n*)=2*n*, f_2(n)=\log_2n*f*2(*n*)=log2*n*, f_3(n)=n^2*f*3(*n*)=*n*2 the answer would be 231.

Enter answer here

#### Week 3: Introduction

#### Quiz 1: Puzzle: Largest Number

Q1. Compile the largest number by concatenating the given numbers.

Q2. Compile the largest number by concatenating the given numbers.

Q3. Compile the largest number by concatenating the given numbers.

Q4. Compile the largest number by concatenating the given numbers.

#### Quiz 2: Puzzle: Car Fueling

Q1. A car can travel at most 3 miles on a full tank. You want to make as few

refills as possible while getting from A to B. Select gas stations

where you would like to refill and press “Start journey” button.

Q2. A car can travel at most 3 miles on a full tank. You want to make as few

refills as possible while getting from A to B. Select gas stations

where you would like to refill and press “Start journey” button.

Q3. A car can travel at most 3 miles on a full tank. You want to make as few

refills as possible while getting from A to B. Select gas stations

where you would like to refill and press “Start journey” button.

Q4. A car can travel at most 3 miles on a full tank. You want to make as few

refills as possible while getting from A to B. Select gas stations

where you would like to refill and press “Start journey” button.

Q5. A car can travel at most 3 miles on a full tank. You want to make as few

refills as possible while getting from A to B. Select gas stations

where you would like to refill and press “Start journey” button.

#### Quiz 3: Greedy Algorithms

Q1. You work as a freelancer and have a pool of 10 projects to work on. For each project you know how much money you will get for completing the project. You can complete any 3 projects this month. You want to select such projects that you will get the most money by completing them. What are the safe moves in this problem? (Mark all that apply.)

**If there are more than 3 projects in the pool, remove the project with the lowest payment for completion, don’t work on this project. In the other case, remove the first project from the pool and work on this project.**- Take the project with the highest payment for completion, complete it and remove it from the pool of projects.
- Take the project which you like the most.
- Take the project for which you can apply the cool new technology that you’ve recently learned about.

Q2. In the previous problem, what is the subproblem you need to solve after you’ve made a safe move?

**Choose projects with highest payment to work on from the pool of projects which now contains only 9 projects.**- Determine the order in which to work on the selected projects.
- Compute the sum of payoffs you will get when you complete the selected projects.

Q3. You need to find an integer 23 \le x \le 7323≤x≤73 with the largest product of digits. You use a greedy strategy: first, determine the largest possible first digit (tens) of xx, then determine the largest possible second digit (ones) of xx (among all the numbers in the range from 23 to 73 whose first digit is equal to the digit selected at the first step). Will this greedy strategy work correctly?

- Yes.
**No.**

#### Weel 4: Algorithmic Toolbox

#### Quiz 1: Linear Search and Binary Search

Q1. You have an array with 1023 numbers. You use linear search to determine whether number 239 is in this array or not. How many elements of the array will you look at if number 239 is not present in the array?

**1023**- 10
- 11
- 1
- 0

Q2. Can you use binary search to find number 8 in the array [1, 24, 25, 23, 17, 8, 9]?

- Yes, you can.
**No, you cannot.**

Q3. You have a sorted array with 1023 elements. You use binary search to determine whether number 239 is present in this array or not. How many elements of the array will you compare it with if number 239 is not present in this array?

**10**- 1023
- 1
- 0

Q4. What is the maximum number of iterations a binary search will make to find some number in the array [1, 2, 3, 5, 8, 13, 21, 34]?

**4**- 3
- 8

#### Quiz 2: Puzzle: 21 questions game

Q1. Find an unknown integer 1 ≤ x ≤ 3 by asking 2 questions “Is x = y?” (for

any 1 ≤ y ≤ 3 ). When you ask such a question, simply enter “y” instead

of “Is x=y?” Your opponent will reply either “Yes”, or “x < y”, or “x > y.”

Q2. Find an unknown integer 1 ≤ x ≤ 15 by asking 4 questions “Is x = y?” (for

any 1 ≤ y ≤ 15 ). When you ask such a question, simply enter “y” instead

of “Is x=y?” Your opponent will reply either “Yes”, or “x < y”, or “x > y.”

Q3. Find an unknown integer 1 ≤ x ≤ 127 by asking 7 questions “Is x = y?” (for

any 1 ≤ y ≤ N ). When you ask such a question, simply enter “y” instead

of “Is x=y?” Your opponent will reply either “Yes”, or “x < y”, or “x > y.”

Q4. Find an unknown integer 1 ≤ x ≤ 2097151 by asking 21 questions “Is x = y?” (for

any 1 ≤ y ≤ 2097151 ). When you ask such a question, simply enter “y” instead

of “Is x=y?” Your opponent will reply either “Yes”, or “x < y”, or “x > y.”

#### Quiz 3: Puzzle: Two Adjacent Cells of Opposite Colors

Q1. You are given 20 black and white cells. The leftmost one is white, the

rightmost one is black, the colors of all other cells are hidden. You

can reveal the color of a cell by clicking on it. Your goal is to find

two adjacent cells of different colors by using at most 5 clicks.

#### Week 5: Change Problem

#### Quiz 1: Change Money

Q1. What is the smallest amount of money for which greedy strategy fails with coin denominations of 11, 88 and 2020?

Enter answer here

Q2. What is the minimum number of coins needed to change 32 into coins with denominations 1, 8, 20?

- 3
- 5
- 6
**4**

Q3. What is the running time of the dynamic programming algorithm to change mm using nn different coin denominations?

**O(nm)**- O(n + m)O(n+m)
- O(m \log n)O(mlogn)

Q4. Is it possible to change 997997 using coins with denominations 22, 44 and 88?

**No**- Yes

#### Quiz 2: Puzzle: Number of Paths

Q1.There are several points connected by arrows as on the picture. There is

a starting point s and a final point t. How many different ways are

there to get from s to t following arrows? Fill numbers of paths to each

point into circles below.

Q2. There are several points connected by arrows as on the picture. There is

a starting point s and a final point t. How many different ways are

there to get from s to t following arrows? Fill numbers of paths to each

point into circles below.

Q3. There are several points connected by arrows as on the picture. There is

a starting point s and a final point t. How many different ways are

there to get from s to t following arrows? Fill numbers of paths to each

point into circles below.

Q4. There are several points connected by arrows as on the picture. There is

a starting point s and a final point t. How many different ways are

there to get from s to t following arrows? Fill numbers of paths to each

point into circles below.

#### Quiz 3: Puzzle: Two Rocks Game

Q1. There are two piles of ten rocks. In each turn, you may either take one rock from a single pile, or one rock from both piles. The player that takes the last rock wins the game. Your opponent moves first.

#### Quiz 4: Puzzle: Three Rocks Game

Q1. There are two piles of ten rocks. In each turn, you may take up to three rocks. The player that takes the last rock wins the game. Your opponent moves first.

#### Week 6: Knapsack

#### Quiz 1: Practice quiz

Q1. In the TV commercial placement problem, your goal is to select a set of TV commercials (each

commercial has duration and revenue) so that

the total revenue is maximum while the total duration does not exceed the length of the

available time slot.

To state this problem as a knapsack problem, you set

**item value to be equal to TV commercial revenue and item weight to be equal to TV commercial duration.**- item value to be equal to TV commercial duration and item weight to be equal to TV commercial revenue.

Q2. In optimizing data center performance problem your goal is to purchase computers for a data center to achieve the maximal performance under limited budget.

To state this problem as a knapsack problem, you set

- item value to be equal to computer cost and item weight to be equal to computer performance.
**item value to be equal to computer performance and item weight to be equal to computer cost.**

#### Quiz 2: Maximum Value of an Arithmetic Expression

Q1. What is the maximum value of an expression 5-8+7\times 4-8+95−8+7×4−8+9 that can be obtained by placing pairs of parentheses into it? For example, ((5-8)+7) \times 4-8+9=17\, ,((5−8)+7)×4−8+9=17, (5-(8+7)) \times (4-(8+9)) = 130\, .(5−(8+7))×(4−(8+9))=130.

But the maximum value is even larger! Try a few ways of placing parentheses into this expression and then check your intuition by submitting the maximum value that you’ve found to the field below. As you see, the questions is non-trivial already for such a small input size. But don’t spend too much time on this quiz: we will find the answer to this question together by the end of this lesson; you will then be able to get back to this quiz to submit the right value. Moreover, you will be able to implement an algorithm solving this problem quickly.

Enter answer here

#### Get All Course Quiz Answers of **Entrepreneurship Specialization**

Entrepreneurship 1: Developing the Opportunity Quiz Answers

Entrepreneurship 2: Launching your Start-Up Quiz Answers

Entrepreneurship 3: Growth Strategies Coursera Quiz Answers

Entrepreneurship 4: Financing and Profitability Quiz Answers