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.