Algorithms

• Topic: Algorithms.
• Video

Concepts

• Algorithm (input, output, interface, function, implementation)
• Abstraction, level of abstraction
• Task decomposition (how to solve complex problems)
• Lists, arrays, index

Practical skills

• How should you approach solving complex problems?

  Guiding question

  For example, if you are given the task “prepare a full meal,” how would you begin?

  Hint 1

  “Prepare a full meal” is a complex task consisting of high-level subtasks: preparing the first course and preparing the second course.

  Hint 2

  Analyze the task: determine what is needed for the first course and the second course. Decide exactly what you will cook. Identify the required ingredients and utensils.

  Hint 3

  Prepare the ingredients and utensils. Cook the dishes by following the steps described in the recipe.

  Answer

  Analyze the complex task. Break it down into large, high-level subtasks. Analyze the subtasks. Break them down into smaller subtasks. Continue until you reach elementary tasks that cannot be broken down further, or tasks for which a solution already exists (for example, finding a recipe with all the steps online).

• How can a list of numbers be represented in linear memory?

• What needs to be done to iterate over every element in a list? To calculate the sum of the list elements?

  Answer

  In each case, you need a variable (a memory cell) to keep track of the “current” value. This variable might hold an index, the current sum, or a set of visited graph vertices.

• Give an example of an algorithm that uses another algorithm during its execution.

Practice

• Write an algorithm (on paper, with words) to solve the following problem: “Given 2 lists containing the same number of values, calculate the sum of each corresponding pair of elements (the first element of the first list and the first element of the second list; the second element of the first list and the second element of the second list; …)”