Algorithms + Programming Languages (Week 5)

Question 1

What do many problems in computer science involve?

Answer 1

Searching for data, e.g. text search in Word document, Google search, etc.

Question 2

How does Binary Search work? Assume the list is already sorted.

Answer 2

Step 1: Identify the middle of the list and split it into two halves

Step 2: If the element we look for is earlier/later in the alphabet than the middle, reduce the list to the lower/upper half

Step 3: Continue with step 1 unless the list contains only 1 element

Step 4: element found

Question 3

Definition : Runtime Complexity

Answer 3

A function that describes the amount of time it takes to run an algorithm.

Question 4

What is the Runtime Complexity of Binary Search?

Answer 4

Log2 N

Question 5

How common of a task is sorting data items?

A) Very common
B) Not common
C) Never done

Answer 5

A) Very common

Question 6

What are some methods of sorting?

Answer 6

Quicksort, Bubble sort, Selection sort

Question 7

What is the Runtime Complexity of Quicksort?

Answer 7

N x Log2 N

Question 8

What is the Runtime Complexity of Bubble sort?

Answer 8

N^2

Question 9

What is the Runtime Complexity of Selection sort?

Answer 9

N^2

Question 10

Definition : “Easy” Problem

Answer 10

Algorithms with runtime complexities like Log N, N, N × Log N or N2 - these complexities are called polynomial.

Problems that can be solved by algorithms with a complexity that looks like Nx are considered to be “easy” – N is a factor in this formula.

Question 11

Definition : “Hard” Problem

Answer 11

“Hard” problems can only be solved by algorithms with exponential runtime complexity like this: x^N (N is an exponent here, e.g. 2^N)

Nature of exponential problems: if problem size increases by 1, runtime multiplies, e.g., doubles, triples, quadruples etc.

Question 12

What situations would need a fast solution?

Answer 12

e.g., brake or swerve

Question 13

What situation would need a slow solution?

Answer 13

e.g. cryptography (decrypting data without knowing the key is “hard”)

Question 14

What are some possible runtime complexities?

Answer 14

From fastest to slowest :

Log N
N
N x Log2 N
N^2
2^N

Question 15

What are computers? (In terms of what they are able to process)

Answer 15

Computers are general purpose computing machines – without software, they don’t know what to do

Question 16

Definition : Software

Answer 16

The term “software” refers to instructions that make a computer do something useful => the “program”

Data is also considered to be software

Question 17

Differences between hardware and software?

Answer 17

Software is intangible – it is not easy to see or put your hands on a sequence of bits (e.g. represented by electrical signals)

Software is more flexible, easier and often cheaper to change (update) than hardware.

Question 18

Definition : Algorithm

Answer 18

The purpose of software is to perform a task

If we focus on a task and how to complete it in general, ignoring the details of its implementation as software (e.g. the type of hardware, etc.), we talk about algorithms

An algorithm is a detailed description of a sequence of steps a software (or also a person) needs to perform and in order to solve a problem

Question 19

What is an Algorithm composed of?

Answer 19

1. Sequence of ordered and precisely described steps to achieve a result (solve a problem)
2. Each step is expressed in terms of basic operations whose meaning is completely specified (There should be no ambiguity about what anything means)
3. Guaranteed to produce the desired result: all possible situations (input configurations) are covered
4. Must stop eventually (finite number of steps)

Question 20

What is an example of a High-Level Description of an Algorithm?

Answer 20

Example task:
* Find out who is the tallest person of all in the class?
* Computer scientists call this a problem

A high-level description of an algorithm to solve this problem could be:
Ask every person in the room for their body height and report back who is tallest.

Question 21

What are 2 good methods of describing Algorithms unambiguously

Answer 21

1) Flow charts
2) Pseudo code

Question 22

Definition : Pseudo Code

Answer 22

It is a methodology that allows the programmer to represent the implementation of an algorithm. Simply, we can say that it’s the cooked up representation of an algorithm. Often at times, algorithms are represented with the help of pseudo codes as they can be interpreted by programmers no matter what their programming background or knowledge is. Pseudo code, as the name suggests, is a false code or a representation of code which can be understood by even a layman with some school level programming knowledge.

Eg :

1 set variable tallest to zero (a.k.a. as initialize it)
2 set variable selected to “blank”
3 for every person in the room, repeat steps 4-8
4 ask next person for name and height in cm
5 if height is greater than tallest: perform steps 6 & 7
6 set tallest to height
7 set selected to name
8 thank the current person for their cooperation and go to 3
9 report selected as result

Question 23

How are flowcharts used to define algorithms?

Answer 23

Flow charts are used to visualize the “flow of operations” of an algorithm.

Have standardized symbols for different
types of operations.

We will use only 5 of them.

Biggest advantage: easy to read.

Major disadvantage: might be confusing if a chart gets too large.

Question 24

Flow Chart Symbol : Arrow

Answer 24

Flow line

Indicates the next operation (the “flow” of operations = sequence) by connecting symbols.

Question 25

Flow Chart Symbol : Oval

Answer 25

Stop/Start

Used to represent start and end of a flow chart.

Question 26

Flow Chart Symbol : Parallelogram

Answer 26

Input/Output

Used for input and output operations.

Question 27

Flow Chart Symbol : Rectangle

Answer 27

Operation

Used for any kind of operation and/or data-manipulation.

Question 28

Flow Chart Symbol : Diamond

Answer 28

Decision

Represents a conditional operation that determines which one of two paths the program will take.

Question 29

What does a “good” algorithm look like?

Answer 29

For each problem we can probably think of more than one algorithm to solve it

Computer scientists want to find good (= efficient) algorithms that use minimal resources:
* Runtime: how long does it take to compute the result? How much work is it? How many steps/operations are carried out?
* Memory: how much memory is needed to do the calculations? E.g. to store intermediate and final results

Not all problems are equally difficult. Some are computationally harder to solve than others.

Question 30

What is a Linear Algorithm?

Answer 30

An algorithm with a computational complexity of N

The number of steps (#) increases linearly with problem size N

If problem size N doubles, the # steps (= runtime) doubles as well

For example:
if N=80 => runtime of 80 ms,
then N=160 => runtime of 160 ms

Question 31

What did Alan Turning do?

Answer 31

Proved in 1930’s that all computers (even the Toy) are theoretically equivalent in what they can compute.

Some may be too slow or may not have enough memory for certain tasks, but in theory all have equal capabilities

Turing used the “Turing Machine”, a very simple theoretical computer (even simpler as the Toy Computer) to show this.

Question 32

What is the Turing Award? (Who knows, this might be on a test!)

Answer 32

The Turing award, considered to be the Nobel prize of computing, is awarded annually to an individual selected for contributions “of lasting and major technical importance to the computer field”

Question 33

What is the Turing Test?

Answer 33

Turing also proposed a test (the Turing test) to assess if a computer was demonstrating human intelligence:

Can a human interrogator only by having a discussion (via keyboard and display) with a computer and a human determine which one the computer is?

Question 34

Real CPUs vs. Toy Computer

Answer 34

Real CPUs understand more instructions
* A few dozen to a few hundred instructions
* More ways to move data around (e.g. in bulk)
* More ways to do arithmetic calculations
* Ability to handle different sizes and kinds of numbers

Multiple accumulators (also known as registers)
* Perhaps 16 to 32
* Enables more elaborate instructions, e.g. add 3 numbers at once

Programs typically have millions of instructions or more

Question 35

What are some methods of speeding up CPU perfomance?

Answer 35

CPUs use several mechanisms to speed up computations e.g. Caching, Pipelining, Parallel Computing

Question 36

Definition : Caching

Answer 36

One way to improve execution speed of a program is Caching – a general strategy that is quite common

Caches store copies of data items to serve future requests faster and to avoid waiting times

Is frequently used, e.g. for buffering for video streaming

Caching is a very useful strategy for CPUs as they have to deal with much slower devices

Question 37

Sort from Fastest to slowest : RAM, CPU, Storage

Answer 37

CPU speed:
* With 1 GHz clock speed => one operation per nanosecond Accumulators inside the CPU also work with this speed

RAM speed:
* A data fetch operation (copy data from RAM into the accumulator) could take 25 to 50 nanoseconds
* That is 25 to 50 CPU cycles => CPU must wait!

Storage (HD, flash memory, optical disc) speed:
* Access times (fetching) typically are in the range of milliseconds
* 1 millisecond = 1000 microseconds = 1 million nanoseconds

Question 38

Definition : Pipelining

Answer 38

Improve CPU speed with Pipelining: let fetch, decode and execute for subsequent instructions overlap; each clock cycle performs all 3 steps!

Question 39

How does Parallel Computing work?

Answer 39

Nowadays, CPUs have multiple cores

Similar to multiple CPUs, but sharing RAM and I/O devices

Multiple cores may perform several independent tasks concurrently, e.g. playing music from a streaming provider, editing a Word document and downloading a file

To make use of multiple cores, an app has to be programmed for it. Otherwise, apps typically use only one core at a time.

Parallel computing: divide a single task into smaller subtasks and perform those subtasks in parallel to get the final result faster

Question 40

What is a Supercomputer?

Answer 40

High performance supercomputers feature a large number of processors and lots of memory, e.g. 7,299,072 cores (Fugaku)

Are used for computation- intensive scientific calculations and simulations E.g. weather and climate simulations

Question 41

What is an Embedded System?

Answer 41

Embedded systems are computer systems with a dedicated function within a larger mechanical or electrical system.

Embedded means they are part of an integrated device often including hardware and mechanical parts, e.g. washing machine

They often operate under real-time computing constraints and guarantee defined response times, e.g. anti-lock braking system of a car

98 percent of all microprocessors are manufactured as components of embedded systems.

Question 42

Representation of programs in RAM (This isn’t a question so just flip it)

Answer 42

The Toy Computer uses simplified RAM
* Every memory location can store a label and one instruction or one data item

A more realistic system would be
* Each memory location stores 1 byte (e.g., a number)
* Memory locations have a serial number (address)
* A label in fact is the address of a memory location
* Instructions are encoded as numbers
* If an instruction refers to a memory location, the location ́s address is stored in the next memory location

Question 43

Can all tasks be done with parallel computing?

Answer 43

Some tasks cannot be divided into independent subtasks

• Task 1: Add up a list of 8 numbers
  => can easily be divided into two separate subtasks (need to add one extra addition to get the final result)
• Task 2: Add up a list of 8 numbers with sub-totals
  => each addition depends on the previous result
  => subtasks are not independent and cannot run in parallel