Discrete Math Final

Increasing function

if ∀x1∀x2(x1 < x2 → f (x1) ≤ f (x2))

Strictly Increasing Function

∀x1∀x2(x1 < x2 → f (x1) < f (x2))

Increasing vs. Strictly Increasing functions

Increasing functions can have flat points, so previous points could have the same output as future points. But this is not the case for strictly increasing functions.

Decreasing Function

∀x1∀x2 (x1 < x2 → f (x1) ≥ f (x2))

Strictly Decreasing Function

∀x1∀x2 (x1 < x2 → f (x1) > f (x2))

Decreasing vs Strictly Decreasing Functions

Same as Increasing vs Strictly increasing, no flat points allowed

Injective functions

Every image has a unique pre-image. Ex: f(x) = x+1 (R to R), f(x) = x^2 (Z+ to Z+)

Injective Functions are also known as...

one-to-one functions

Surjective functions

For every element of the co-domain, there is a corresponding pre-image in the domain. (codomain = range). Ex: f(x) = x + 1, from Z to Z

Surjective functions are also called..

Onto Functions

Bijective Functions

When a function is both injective and surjective, it is a bijective functions. (Both one-to-one and onto). Ex: f: {a, b, c, d} → {1, 2, 3, 4} with f (a) = 4, f (b) = 2, f (c) = 1, and f (d) = 3

Different Functions Example

How to show that a function is one-to-one?

Show that if f(x) = f(y) for some x and y of the domain, then x = y.

How to show that function is not one-to-one?

Find x and y such that f(x) = f(y) and x ≠ y

How to show that function is onto?

Take an arbitrary element y from the co-domain, show that there is an element x from the domain such that f(x) = y

How to show that f is not onto?

Find an arbitrary y belonging to the co-domain such that f (x) ≠ y for all x ∈ A.

How to show that a function is bijective?

Show that function is both injective and surjective

Inverse functions

The function that maps B to A (given original function mapped from A to B). In other words, g(y) = x iff f(x) = y

What kind of functions are invertible?

Only bijective functions

Composition

if f maps B to C and g maps A to B, composition function h = f o g(x) = f(g(x)) will map from A to C

Function Graphs

The points such that one coordinate belongs to the domain and other to the range and f(a) = b. (not lines, dots, we're dealing with integers here)

Floor Function

f(x) = ⌊x⌋. The largest integer less than or equal to x.

Ceiling Function

f(x) = ⌈x⌉. The smallest integer greater than or equal to x.

Floor and Ceiling Function Properties

Factorial Functions

f(n) = 1*2*3*....*(n-1)*n. The product of the first n positive integers when n is a nonnegative integer.

Stirling's Formula

Partial Functions

An assignment of each element of the domain to a unique element in the co-domain. This means there can be holes (in graphs)

Sequences

Ordered lists of elements. Indices are important with sequences. Used in mathematics, computer science and other disciplines like botany and music.

Sequences (2)

A function from the subset of integers to a set S.

Geometric Progression

A sequence of the form a, ar, ar^2....ar^n. a is the initial term and r is the common ratio

Arithmetic Progression

A sequence of the form a, a+d, a+2d...a+nd. Here a is the initial term and d is the common difference.

Summations

The sum of the terms am, am+1, ...an. Here j is the index of summation. m is the lower limit and n is the upper limit.

Geometric Series

Sums of terms of geometric progression

Useful summation formulae

The first step in solving computational problems..

precisely state the problem, using
the appropriate structures to specify the input
and the desired output

Algorithm

An algorithm is a finite set of precise instructions for performing a computation or for solving a problem

Algorithms can be specified in different ways

Human Language, Flowchart, Pseudocode

Pseudocode

an intermediate step between an English language description of the steps and coding of these steps using a programming language

Flowchart

Graphical representation of an algorithm. Different types of instructions are represented by boxes of different shapes. The flow of control is represented by directional lines. Con is it gets complicated pretty quickly.

Properties of Algorithms

Input: An algorithm typically has input values from a specified set.

Output: The algorithm performs an action or produces the output values from a specified set (the solution).

Correctness: An algorithm should produce the correct output values for each set of input values.

Finiteness: An algorithm should produce the output after a finite number of steps for any input.

Effectiveness: It must be possible to perform each step of the algorithm correctly and in a finite amount of time.

Generality: The algorithm should work for all problems of the desired form.

Algorithm Problem Types

Searching Problems, Sorting problems, Optimizations Problems

Searching Problems

Finding the position of a particular element in a list

Sorting Problems

Putting the elements of a list into increasing order

Optimization Problems

Determining the optimal value of a particular quantity over all possible inputs.

Heuristic Algorithms

An algorithm that quickly produces good, but not necessarily optimal solutions

Linear search algorithm

Locates an item in a list by examining elements in the sequence one at a time, starting at the beginning

Binary Search

Cuts the list in half each time when searching. Sorted list, checks mid value, if smaller searches up else searches down.

Sorting

To sort elements of a list is to put them in increasing order.

Why is sorting an important problem?

Sorting takes a lot of resources. There's a lot algorithms that have been developed for efficient sorting that are studied extensively. Illustrate the basic notions of computer science.

How many sorting algorithms have been developed till date?

More than 100

Examples of common sort algorithms

Binary, Insertion, Bubble, Selection, Merge, Quick and Tournament

Bubble Sort

Multiple passes, swaps when out of order. With each iteration the highest remaining number "sinks" to its correct position.

Selection Sort

Finds the smallest element and brings it to the front of the list.

Insertion sort

Like sorting cards. Goes to element, checks against sorted portion, puts it in the correct spot.

Greedy Algorithms

An optimization algorithm. Makes the best choice at each step. This could mean making a unsustainable solution at the end as a total.

Greedy Change Making Algorithm

Greedy Scheduling Algorithm

Talk that ends the soonest

Halting Problem

A program that tells if a program can stop or will run forever is impossible to create. Alan Turing. Proof by contradiction, feeding the program itself

Growth of Functions

Algorithm efficiency is evaluated and compared by seeing how fast the problem can be solved given a growing size of input

Factors that affect the runtime of a program

1. The size of the input to the program *

2. The time complexity of the algorithm underlying the program *

3. The quality of code generated by the compiler used to create the object program

4. The nature and speed of the instructions on the machine used to execute the program

Big O Notation

f(x) is O(g(x)) if f(x) grows slower than g(x). |f(x)|

Parts of Big O

C - constant of multiplication
k - the point where g(x) goes over f(x)
these two combined are called witnesses

A property of a pair of witnesses

you can pick any C greater, say C' and this C'g(x) would still continue to satisfy the the big O inequality.

Big O of any polynomial function is...

The highest power

Big O estimates for some functions

1+2+3+...+n -> O(n^2)
n! -> O(n^n)

log(n!)

O(nlog(n))

Growth of functions visual

Combinations of functions

f1+f2 -> O(max of the two)
f1*f2 -> O(both big o product)

Big Omega Notation

gives the lower bound on the growth of a function. It tells us that a function grows at least as fast as another.

Big-Omega Inequality

|f(x)| >= C|g(x)| when x > k

Big Theta Notation

f(x) is big theta of g(x) if big o of g(x) and big omega of g(x)

Big Theta Inequality

C1g(x) < f(x) < C2g(x)

Big Theta polynomial estimate

highest order exponent is big theta

What questions do we ask when checking how efficient an algorithm is?

How much time does this algorithm take? How much memory does this algorithm use?

Time-Complexity

When we analyze the time the algorithm uses to solve the problem given input of a particular size

When we analyze the computer memory the algorithm uses to solve the problem given input of a particular size

Space-Complexity analyzes..

the extra memory needed to solve the problem. So storing the input itself doesn't matter.

Time-complexity analyzes..

the number of operations it takes to arrive at the solution

Focus of time-complexity analysis

lies in the worst-case complexity (big O), the upper bound. It is harder to determine the average-case complexity (big Theta).

Time-Complexity of some algorithms

Linear search: Θ(n)
Binary search: Θ(log n)
Bubble Sort: Θ(n^2)
Selection Sort: Θ(n^2)
Insertion Sort: Θ(n^2)
Matrix Multiplication (n x n): Θ(n^3)

Complexity chart

Tractable Problem

There exists a polynomial time algorithm to solve this problem. Belongs to Class P.

Intractable Problem

There does not exist a polynomial time algorithm to solve this problem

Unsolvable Problem

No algorithm exists to solve this problem (halting problem)

Class NP

Solution can be checked in polynomial time. But no polynomial time solution has been found for problems in this class.

NP complete class

if we find a polynomial time time solution for one member of the class, it can be used to solve all the problems in the class

P vs NP

are there problems that can be checked in polynomial time but cannot be solved in polynomial time? not discovering does not mean that it doesn't exist

Number theory

part of mathematics devoted to the study of integers and their properties

Application of number theory

cryptography, pseudorandom number generation, error detection and error correction codes

Division

If a and b are integers with a ≠ 0, then a divides b if there exists an integer c such that b = ac

a|b

this means a "divides" b. another way to think about this b/a is an integer.

a|b is a..

boolean function. true when remainder is equal to 0

Properties of divisibility

if a|b and a|c then a|(b+c)
if a|b then a|bc for all integers c
if a|b and b|c, then a|c

Division terms

positive and negative remainders

+1 the multiplication, take the difference. normally, 18/5 is q: 3 and remainder 3. but negative remainder would work like q: 4 and 4: -2

Congruence

Two integers a and b are said to be congruent modulo m if a mod m = b mod m

a is congruent to b modulo m

if m divides a-b

a is congruent to b modulo m (2)

if there is an integer such that a = b + km

Congruence Class

The set of all integers congruent to a mod m is called the congruence class of a modulo m

if a is congruent to b mod m, and c is congruent to d mod m then...

a+c is congruent to b+d mod m and ac is congruent to bd mod m