Algorithms + Programming Languages (Week 5) Flashcards
What do many problems in computer science involve?
Searching for data, e.g. text search in Word document, Google search, etc.
How does Binary Search work? Assume the list is already sorted.
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
Definition : Runtime Complexity
A function that describes the amount of time it takes to run an algorithm.
What is the Runtime Complexity of Binary Search?
Log2 N
How common of a task is sorting data items?
A) Very common
B) Not common
C) Never done
A) Very common
What are some methods of sorting?
Quicksort, Bubble sort, Selection sort
What is the Runtime Complexity of Quicksort?
N x Log2 N
What is the Runtime Complexity of Bubble sort?
N^2
What is the Runtime Complexity of Selection sort?
N^2
Definition : “Easy” Problem
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.
Definition : “Hard” Problem
“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.
What situations would need a fast solution?
e.g., brake or swerve
What situation would need a slow solution?
e.g. cryptography (decrypting data without knowing the key is “hard”)
What are some possible runtime complexities?
From fastest to slowest :
Log N
N
N x Log2 N
N^2
2^N
What are computers? (In terms of what they are able to process)
Computers are general purpose computing machines – without software, they don’t know what to do
Definition : Software
The term “software” refers to instructions that make a computer do something useful => the “program”
Data is also considered to be software
Differences between hardware and software?
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.
Definition : Algorithm
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
What is an Algorithm composed of?
- Sequence of ordered and precisely described steps to achieve a result (solve a problem)
- Each step is expressed in terms of basic operations whose meaning is completely specified (There should be no ambiguity about what anything means)
- Guaranteed to produce the desired result: all possible situations (input configurations) are covered
- Must stop eventually (finite number of steps)
What is an example of a High-Level Description of an Algorithm?
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.
What are 2 good methods of describing Algorithms unambiguously
1) Flow charts
2) Pseudo code
Definition : Pseudo Code
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
How are flowcharts used to define algorithms?
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.
Flow Chart Symbol : Arrow
Flow line
Indicates the next operation (the “flow” of operations = sequence) by connecting symbols.
Flow Chart Symbol : Oval
Stop/Start
Used to represent start and end of a flow chart.
Flow Chart Symbol : Parallelogram
Input/Output
Used for input and output operations.
Flow Chart Symbol : Rectangle
Operation
Used for any kind of operation and/or data-manipulation.
Flow Chart Symbol : Diamond
Decision
Represents a conditional operation that determines which one of two paths the program will take.
What does a “good” algorithm look like?
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.
What is a Linear Algorithm?
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
What did Alan Turning do?
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.
What is the Turing Award? (Who knows, this might be on a test!)
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”
What is the Turing Test?
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?
Real CPUs vs. Toy Computer
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
What are some methods of speeding up CPU perfomance?
CPUs use several mechanisms to speed up computations e.g. Caching, Pipelining, Parallel Computing
Definition : Caching
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
Sort from Fastest to slowest : RAM, CPU, Storage
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
Definition : Pipelining
Improve CPU speed with Pipelining: let fetch, decode and execute for subsequent instructions overlap; each clock cycle performs all 3 steps!
How does Parallel Computing work?
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
What is a Supercomputer?
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
What is an Embedded System?
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.
Representation of programs in RAM (This isn’t a question so just flip it)
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
Can all tasks be done with parallel computing?
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
