Basics

Question 1

Why do we use Big O?

Answer 1

It’s growth rate what matters, not execution time

Question 2

Recursion

Answer 2

Some task from topcoder?

Question 3

Insertion Sort. Write pseudocode for sorting elements in non ascending order.

Answer 3

for i = 2:n, for (k = i; k > 1 and a[k] > a[k-1]; k–) swap a[k,k-1] → invariant: a[1..i] is sorted end https://www.toptal.com/developers/sorting-algorithms/insertion-sort

Question 4

bit shifting int x = 0x0011; int y = x << 1; y = ?

Answer 4

For example, if you “decimal shifted” the number 14 left, you’d have 140 and if you did it to the right, you’d wind up with 1 (rounding down from 1.4). Decimal shifting is really just a question of multiplying and dividing by powers of 10. Bit-shifting is the same thing, but with powers of two. y = 6

Question 5

Translate into binary 28 = ?

Answer 5

Suppose we’re working with 8 bit quantities answer is 00011100 https://www.wikihow.com/Convert-from-Decimal-to-Binary

Question 6

Divide&Conquer. Main idea, steps. Example of applying

Answer 6

1.Find the base case (the easiest one) 2.Divide until getting to the base case. 1.DIvide problem into non-overlapping subproblems 2.Solve them recursively 3. Combine results. Examples: quick sort, merge sort

Question 7

Quick sort Write the code, estimations

Answer 7

https://www.toptal.com/developers/sorting-algorithms/quick-sort

Question 8

Greedy

Answer 8

Read after dynamic programming

Question 9

When insertion sort is effective?

Answer 9

When sorting a small number of entities

Question 10

Does insertion sort use extra space?

Answer 10

It’s in place

Question 11

What is loop invariant?

Answer 11

A loop invariant is a property of a program loop that is true before (and after) each iteration. It is a logical assertion, sometimes checked within the code by an assertion call. Knowing its invariant(s) is essential in understanding the effect of a loop.

Question 12

What is the essence of algorithm analysis?

Answer 12

Analyzing an algorithm has come to mean predicting the resources that the algorithm requires.

Question 13

What technology is assumed when analyzing an algorithm?

Answer 13

We shall assume a generic oneprocessor, random-access machine (RAM) model of computation

Question 14

What is a word?

Answer 14

A word is the natural unit of data used by a particular processor design. A word is a fixed-sized piece of data handled as a unit by the instruction set or the hardware of the processor. The number of bits in a word (the word size, word width, or word length) is an important characteristic of any specific processor design or computer architecture.

Question 15

What parameters does insertion sort performance depend on?

Answer 15

Input size and how nearly sorted sequence already is

Question 16

What is the best/worst timing for Insertion Sort? Why?

Answer 16

O(n^2) the worst and O(n) the best

Question 17

Write code for MergeSort

Answer 17