Introduction To Algorithms

COURSE – CODING INTERVIEW PREPARATION QUIZ ANSWERS

Week 3: Introduction to Algorithms

Meta Front-End/Android Developer Professional Certificate

Complete Coursera Answers & Study Guide

Click to Enroll in Coursera Meta Front-End Professional Certificate

Introduction to Algorithms INTRODUCTION

As part of the Introduction to Algorithms module in the Meta Front-End Developer Professional Certificate from Coursera, you will gain the skills needed to approach data structure and algorithm problems.

This module covers the fundamentals of sorting and searching algorithms, including time and space complexity considerations. You will then learn how to utilize algorithmic approaches such as divide and conquer greedy algorithms, and dynamic programming when problem-solving. With this knowledge, you will be able to write efficient code for a variety of applications.

Upon completing this module, you will have acquired a solid foundation in understanding algorithms applicable in many technology fields. Start your journey today!

Learning Objectives

  • Introduce the concept and usage of algorithms
  • Demonstrate how to visualize an algorithm
  • Combine new and previously learned coding patterns to solve problems

KNOWLEDGE CHECK: SORTING AND SEARCHING

1. Given an array of 6 numbers -> 6, 8, 19, 48, 9, 90 and applying a selection sort.  How many swaps must occur before the array is sorted?

  • 2 (CORRECT)
  • 4

Correct: That’s correct. The array is mostly ordered so only have to swap 19 and 9; and then 48 and 19.

2. Given an array of numbers and a target value, using a loop, what is the worst-case time complexity to check if the number is present in the array?

  • O(n) (CORRECT)
  • O(1)
  • O(log n) 

Correct: That’s correct. To determine if a value was there, using a loop would mean checking every element in the array.

3. A binary search can only be performed on a sorted dataset.

  • True (CORRECT)
  • False 

Correct: That’s correct. The nature of binary search is that it checks if the value is higher or lower and removes everything beyond the point of that conditional statement. 

4. Given the following snippet of pseudocode:

array = []
n = 4 
FOR i = 0 TO n:
   FOR j = 0 TO n:
      array.add(i*j) 
What is the space complexity of this problem?
  • O(log n)
  • O(n)
  • O(n^2) (CORRECT)

Correct: That’s correct. As n is looped through twice, the number of computations will reflect n*n or n^2. 

5. What advantage is there to changing element location using an in-place swap? 

  • It reduces the amount of space taken by removing the need to create another variable in memory. (CORRECT)
  • It reduces the time taken to complete an algorithm through lowering the time complexity. 
  • It is a memory feature that allows many variables to reference the same memory location. 

Correct: That’s correct. In-place swapping is done to arrays in place of creating new ones and storing the sorted data there. It is a good process for reducing the space complexity of a solution.

KNOWLEDGE CHECK: WORKING WITH ALGORITHMS

1. What is  memoization?

  • It is an example of divide and conquer.
  • It is a process of retaining the results from a computation so that they can be reused rather than recalculating a result. (CORRECT)
  • It is a practice of only computing what is in the cache in place of expensive memory calls.

Correct: That’s correct! It is the practice of retaining results to speed up subsequent computations. 

2. The practice of breaking a problem into a set of overlapping subproblems is referred to as: 

  • Dynamic programming (CORRECT)
  • Divide and conquer
  • Memoization

Correct: That’s correct. This is a practice that employs a divide and conquer approach to breaking problems down. When an overlapping pattern has been identified, this approach further utilizes memoization to compute solutions more quickly.

3. Quicksort is an example of divide and conquer?

  • True (CORRECT)
  • False

Correct: That’s correct. The array is repeatedly broken into smaller components until the data is sorted. 

4. Examine the following problem:

A bank robber has entered a bank vault and sees 3 stacks of precious bars:  Gold, silver and platinum. The gold weighs 6kg and is valued at 60 dollars. The silver weighs 1 kg and is valued at 5 dollars. And the platinum weighs 10kg and is valued at 110 dollars. The robber can only carry 38kg.  What is the optimal combination of items to take? Your solution is to fill the bag with as many platinum bars as possible before moving to the gold and then the silver. What type of approach best describes this solution?

  • Graph approach
  • Dynamic programming 
  • Greedy approach (CORRECT)

Correct: That’s correct. This approach involves taking the immediate item with the highest value regardless of any other factors.

5. Why is a base case crucial when designing recursive solutions? 

  • Without it the function would go on forever. (CORRECT)
  • The algorithm needs to know the shape of the minimum case so it can model the solution from it. 
  • It is used to ensure that the input diminishes at each call. 

Correct: That’s correct. The base case is the termination condition that ends the iterative nature of the function.

Coursera Meta Front-End Developer Professional Certificate Answers and Study Guide

Liking our content? Then don’t forget to ad us to your bookmarks so you can find us easily!

Weekly Breakdown | Meta Study Guides | Back to Top

MODULE QUIZ: INTRODUCTION TO ALGORITHMS

1. Insertion sort is an example of divide and conquer?

  • True 
  • False (CORRECT)

Correct: That’s correct. Insertion sort processes each element in relation to its surrounding elements until the data is eventually sorted.

2. Given an array of 6 numbers [6,8,19,48,9,90] and applying insertion sort, how many swaps must occur before the array is sorted?

  • 4
  • 2 (CORRECT)

Correct: That’s correct. The array is mostly ordered so only have to swap 9 twice, first with 48, then with 19.

3. What time complexity is required to do a linear search?

  • O(1)
  • O(n) (CORRECT)
  • ((log (n)) 

Correct: That’s correct. A linear search requires that you do a search of every item. So it will take n (the number of items) time to search.

4. Why do we need Big-O notation to evaluate our programs?

  • Because sorting requires that things are moved around to save space. 
  • Because sorting is complicated, and we need a complicated metric. 
  •  Because measuring time is relative to a person’s computer, so a relative metric is required. (CORRECT)

Correct: That’s correct. A relative metric is required to measure time.

5. What is parallelization?

  • It is about writing your code in one go. 
  • It is about calling functions repetitively until they have achieved a base case. 
  • It is about running code at the same time in threads or on separate computers. (CORRECT)

Correct: That’s correct. You have successfully identified a brief definition of parallelization.

6. Why would you decide to use recursion?

  • Recursion reduces the pressure on the compiler by making less stack calls. 
  • It looks cool and makes your code seem more intelligent.
  • It lends itself well to a divide and conquer approach. (CORRECT)

Correct: That’s correct. Recursion works well with the divide and conquer approach.

7. Why does Memoization work well with dynamic programming? 

  • It takes up less space in the hard drive. 
  • It requires less compiling because it stores previous results, reducing the load on the CPU. (CORRECT)
  • Because it takes a lot of memory to run some programs and memoization allows you to store data in smaller sizes.  

Correct: That’s correct. Dynamic programming utilizes memoization because it stores the results of computations, meaning the computations don’t have to be repeated.

8. How are the principles of dynamic programming and greedy algorithms at odds with one another? 

  • The principle of dynamic programming is to exhaustively compute the best solution, while a greedy approach will favor take the immediate best option. (CORRECT)
  • The greedy algorithm will use up CPU by monopolizing resources. 
  • Because dynamic programming will react with more agility to a program, while the greedy approach will be slower and more self-centered. 

Correct: That’s correct. With dynamic programming, you can find the most best solution, whereas greedy algorithms have a specific process.

9. Why is a binary search conducted in O(log n) time?

  • Regardless of the size of the input, at every step the number of calculations is halved. (CORRECT)
  • Because as it searches it sorts the elements.
  • It is not, it is conducted in O(n).

Correct: That’s correct. Log n means that it is not instantaneous access but it rapidly reduces the lookup space.

10.

Untitled 8
def fibonacci (number)
   if number < 2
     number 
    else
      fibonacci (number - 1) + fibonacci(number - 2)
    end
   end

In the Fibonacci pseudocode above how many recursive instances can be seen? 

  • 0
  • 1
  • 2 (CORRECT)

Correct: That’s correct. The algorithm is being called on the last, and second to last number on the series.

11. If provided with the following array of numbers and you applied the selection sort approach. How many swaps must occur before the array is sorted? 
[9, 2, 4, 8, 7, 90]   

  • 3 (CORRECT)
  • 2
  • 4

Correct: That’s correct. In this case 3 swaps occur to sort the array.       

12. If you have a data set and decide to use the linear search approach to locate an element, which of the below is accurate?    

  • Within the array of elements, the linear search will search from the start of the index until an appropriate element is found. (CORRECT)
  • The linear search first checks the halfway point of the array of elements. Determining if the element is greater or smaller than the target element.      

Correct: That’s correct! The linear search will search from the start of the index until an appropriate element is found, or there are no more elements to check.      

13. Which of the following options are benefits of the divide and conquer paradigm? Select all that apply:      

  •  Combine    
  • Memory management      
  •  Parallelization  (CORRECT)

Correct: Well done. Parallelism is when you have different threads or computers working on the same problem at the same time to complete it in a quicker time.     

14. In the following code, what is the base case?  

def fibonacci(number)
	if number < 2
		number
	else
		fibonacci(number – 1) + fibonacci(number – 2)
	end
end
  • When the number >2      
  • When the number < 2 (CORRECT)
  • Fibonacci (number – 1)      

Correct: Well done. That will cause the termination of the loop.      

15. Which of the steps are included in the dynamic programming process?  Select all that apply:      

  • Alter the code to get to an outcome.      
  • Describe the optimum outcome. (CORRECT)
  • Break the problem into smaller steps. (CORRECT)

Correct: Well done. When computing dynamic programming solutions, one must first determine the objective function.  That is the description of what the optimum outcome is to be.       

Correct: Well done.  Breaking the problem into smaller steps can allow recursions to take place. That is when functions call themselves repeatedly until a solution is reached.       

16. Using the greedy algorithm, which route will be taken to move from node B – D ?  Select the correct option.

Untitled 9
  • B – S –  C – E – D  (CORRECT)
  • B – E – D      
  • B – E – H – G – F –D     

Correct: Well done. That will be the route with the current most rewarding solution at each juncture.  This approach only considers the next best choice.       

Introduction to Algorithms CONCLUSION

Algorithms form an important part of computer science, and in this module you learned about some common sorting and searching algorithms as well as time and space complexity. You also explored how to work with algorithms, visualizing and problem solving with algorithmic approaches. Now that you’ve completed this module, you have a strong foundation on which to build more complex skills.

Coursera offers many courses on computer science if you’re interested in learning more. Join Coursera now!

Subscribe to our site

Get new content delivered directly to your inbox.

Liking our content? Then, don’t forget to ad us to your BOOKMARKS so you can find us easily!