Intro and Basics

Question 1

What is a computational problem?

Answer 1

A general description, from inputs to outputs.

Question 2

What s a problem instance of a computational problem?

Answer 2

A concrete input.

Question 3

What is an algorithm?

Answer 3

A well-defined computational procedure that from inputs computes outputs. In other words, it solves a problem instance.

Question 4

Does algorithm have to work on all inputs/problem instances?

Answer 4

Yes

Question 5

What is a program?

Answer 5

A particular implementation of some algorithm.

Question 6

Give a simple description of an Insertion Sort.

Answer 6

Take the next element, insert it into the already sorted part.

Question 7

What data structure are we using for Insertion Sort

Answer 7

Array

Question 8

In terms of the resources that the algorithm requires, what are we typically interested in?

Answer 8

• Runtime
• Memory
• Number of basic operations

Question 9

What is the main parameter when analysing the running time of an algorithm?

Answer 9

Input size

Question 10

What are the 4 types of analysis?

Answer 10

• Exact analysis
• Best-case
• Worst-case
• Average-case