Fall 2021 Intro to Computer Science Flashcards
Algorithm
A well-ordered collection of unambiguous & effectively computable operations that, when executed produces a result & halts in a finite amount of time.
Programming Language
A notation for specifying instructions that a computer can execute.
Each(programming) language has a syntax and a semantics:
- Syntax specifies how something is said (grammar)
- Semantics specifies what it means
Pseudocode
An informal programming language with English-like constructs modeled to look like statements in a Java-like language.
Anyone able to program in any computer language should understand how to read pseudocode instructions.
When in doubt write it out in English.
What are three components to an algorithm?
1) A set of inputs, where each input is a finite sequence of items.
2) A set of outputs, where each output is a finite sequence of items.
3) A method consisting of a finite sequence of instructions, each one of which can be mechanically executed in a fixed length of time with a fixed amount of resources. The method must produce an output for each input in the set of of possible inputs in a finite amount of time.
Input size
is associated with each input is a measure of its size.
How we measure the size can vary from problem to problem.
Examples:
- Number of digits as in the number of digits in a number (Often we use binary digits).
- Number of characters in a string.
- Number of items as in the number of items to be searched or sorted.
Binary Search
- Searching a sorted list
- How can we exploit the structure that a sorted list provides?
- Start in the middle and determine in which half of the list our target lives
- Repeat this procedure eliminating half of the remaining list elements on each iteration
- What is the maximum number of comparisons required here?
Input: A list of n ≥1 numbers A[1], A[2], … , A[n],
and a target number x.
Output: The message “Sorry, x is not on the list” if x is not
on the list.
Otherwise, the message: “x occurs at position i on the list.”
Pseudocode for Binary Search:
found = "no";
begin = 1;
end = n;
while (found == "no" and begin < end)
{
m = begin + floor((end-begin)/2)
if(A[m] == x)
{
found = "yes";
location = m;
}
if(A[m]>x)
end = m-1;
if(A[m]
Selection Sort
Algorithm to sort the items on a list into nondecreasing
order
Input: A list of n ≥1 elements A[1], A[2], … , A[n].
Output: The list sorted in nondecreasing order.
for (i = 1; i < length(A); i++)
{
locmin=i;
for (j=i+1; j <= length(A); j++)
{
if (A[locmin] > A[j])
locmin=j;
}
exchange(A[locmin], A[i]);
}
Insertion Sort
Input: A list of n ≥1 elements A[1], A[2], … , A[n].
Output: The list sorted in nondecreasing order.
Method:
for (j=2; j <= n; j ++)
{
temp = A[j]
i=j-1
while (i > 0 and A[i] > temp)
{
A[i+1]=A[i]
i=i-1
}
A[i+1]=temp
}
Analyzing Algorithms
We would like to measure the quality or efficiency of an algorithm so that we may compare algorithms that perform similar tasks.
We want this measure to be machine (and implementation) independent.
We will consider the number of instructions that need to be executed.
This will be a function of the input size, n.
This may vary depending on “chance”.
We will consider worst-case running time and also average-case running times.
Instead of all instructions being counted equal we will count mathematical and/or logical operations involving variables that are unknown ahead of time.
At the end of the day our “measure” will be a function of n. Therefore, we need a way of comparing these functions.
Big-O Notation
Given a function of n, we will consider only the most dominant term. What we really care about is the order of magnitude of growth.
Example: T(n)=25n3+log(n)+2n = O(2n)
Example: T(n)=3n2+100n = O(n2)
We’ll save the technical definition for COMS W3203 Discrete Math. The point is we care about growth because we care about really really big n!
