Course Overview

We will briefly discuss some things related to how one can do well in CSE 331.

Proofs

CSE 331 will involve a lot of proofs. In this recitation, we will first do an overview and then talk about proof by induction.

Proofs in English

In this course, we will do (and you will submit in your homeworks) proofs in English. As an example to illustrate why this is a good idea, we will go over the Asleep in class problem in this video by Alan Cline :

Searching a Sorted List

Imagine we have a list of sorted values. These could be anything from user IDs, processes, song names, etc., as long as they are sorted. What would we do if we wanted to find a specific entry is this list? We could look at every entry and determine if it is the one we are looking for, but this could take a very long time, and is not at all efficient. What we need is some way to look through this sorted list as quickly as possible, while also remaining perfectly accurate.

More formally, we want to solve the following problem:

The Algorithm

Here is an iterative implementation of Binary Search:

                                        //Input: A[0],...,A[n-1];v (A is sorted)

					left=0;
					right=n-1;

					while(left <= right)
					{
						mid=ceil( (right+left)/2);
						if(A[mid]==v)
							return mid; // v is present 
						else if(A[mid]< v)
							left=mid+1; // Search for v in right half
						else
							right = mid-1; // Search for v in left half
					}

					return -1; // v is not present
				

When it successfully finds the given value $v$, it returns the index of the value. Otherwise, it returns $-1$, indicating that $v$ is not present in $A$.

This is a powerful algorithm, but how do we know for sure that it always works correctly?

Proof of Correctness

To prove this algorithm, we will consider two approaches – induction and contradiction. In the case of binary search, induction is for more natural and intuitive, but we will also cover a proof by contradiction to show alternate strategies, as there is no one, specific way to prove correctness of a given algorithm. Using induction, we would want to show that as $n$ (the size of the input array) increases by an arbitrary amount, it can always be reduced to a single base case.

Contradiction is slightly more complicated. For that, we would need to show that there is some property of the algorithm that must always be true, and then dismiss any arguments against it by following the example logically until it contradicts the original statement.

Proof by Induction

Proof by Contradiction

Reduction

In the context of proofs, a reduction is essentially taking a problem and trying to prove that after some logical steps, it’s proof or answer is the same as a known problem. This is useful when you have a family of similar problems, because in some cases they have some shared property or limitation that is solved the same way across each one.

Imagine we have an array $A$ with $v$ where $v = a_0$. Binary search would actually be worse in this scenario, taking the full $O(\log n)$ time whereas a linear search will be $O(1)$. So this brings to light that as the array increases in size, if the index $v$ is at is significantly smaller than the size $n$ of the array, we are essentially searching a large portion of the array we don’t need to. How can we restrict binary search so it only searches as small a portion of the array as possible?

Let's define the problem like this:

Algorithm Details

                                        //Input: A[0],...,A[n-1];v (A is sorted)

					m = 1

					while(A[m] < v)
					{
						m = min(m*2,n-1)
					}
                    
                                        B = A[0:m]

					return binarySearch(B, v);
				

The important thing to notice here is that after determining $m$, we just run binary search kind of like calling a library function. This is the goal of a reduction $-$ taking an unsolved problem and reducing it to a form that is the same as a solved problem.

Runtime Analysis

The last thing we need to do is show that the algorithm is efficient enough. To do this, we show that the maximum value of $m$ is $2(i^*+1)$, which bounds how many iterations the algorithm will run for. If $i^*=0$, then the algorithm terminates at $m=1\le 2(i^*+1)=2$. Otherwise when $i^*>0$, we double $m$ each time we see that $a_m$ is less than $v$, meaning $m$’s maximum index must be some index whose value is less than $v$, then multiplied by $2$. We can thus simply say that this value must be less than $2i^*\le 2(i^*+1)$.

How many iterations of doubling is this? Well at iteration $j$, $m=2^j$, and if the final iteration is $j^*$, we know $2^{j^*}\leq2(i^*+1)$. Now when taking $\log$ $2^{j^*}$, that reduces to just $j^*$, which then is at most $\log(2(i^*+1))=1+\log(i^*+1)$. Since each of the $j^*$ iterations take $O(1)$ time, the overall time before we call binarySearch is $O(j^*)\le O(1+\log(i^*+1))$. Then the call to binarySearch is $O(\log(m+1))$, (since B is an array of size $m+1$), which is bounded from above by $ O(1+\log(i^*+1))$, so we simply state our overall runtime as $O((\log i^*+1) + 1)$, as desired.

Q3 on HW 0

Next, we will be reviewing the support page on matrix-vector multiplication with the goal of setting up some background for Q3 on HW 0. In particular, we will try and cover as much as the topic below as time permits:

• Definition of matrices and vectors.
• Example of a matrix-vector multiplication (time $O(n^2)$).
• Inner product
• Structured matrices

What is a Matrix?

In mathematics, a vector is simply an ordered list of values. A matrix represents a vector of vectors, or a 2-d vector. From the support page:

The Inner Product

It turns out that to visualize the matrix-vector multiplication, it is helpful to define a simpler operation between two vectors:

Armed with the definition of the inner product, here is an equivalent definition of the matrix-vector multiplication problem:

Below is one example of a matrix vector multiplication: \[ \begin{pmatrix} 1 & 2 & -3\\ 2 & 9 &0\\ 6 & -1 & -2 \end{pmatrix} \times \begin{pmatrix} 2\\ 3\\ -1 \end{pmatrix} = \begin{pmatrix} 1\times 2 + 2\times 3 + (-3)\times(-1)\\ 2\times 2+ 9\times 3+0\times (-1)\\ 6\times 2+(-1)\times 3+ (-2)\times(-1) \end{pmatrix} = \begin{pmatrix} 11\\ 31\\ 11 \end{pmatrix}. \]

Time Complexity

The time complexity of a regular multiplication is $O(n\cdot m)$, or $O(n^2)$ for square matrices. You can think of it as being two nested for loops. One for each row, and the inner one for each column. Here is a pseudocode example of multiplying matrix $\mathbf{A}$ with vector $\mathbf{x}$:

                                    Allocate an array of length n and call it y

                                    #Initialize the array
                                    for i= 0 .. n-1
                                        y[i]=0

                                    #Do the actual matrix-vector multiplication
                                    for i = 0 .. n-1
                                        for j= 0 .. n-1
                                            y[i] += A[i][j] * x[j]

                                    return y
                                

Structured Matrices

If we know what the structure of a matrix is, we can often cut down on our algorithm time. We will consider one such example below and Question 3 on HW 0 is also based on this theme.

Outer Product

Next, we present an algorithm to multiply the outer product of two arbitrary vectors $\mathbf{s}$ and $\mathbf{t}$ with a vector $\mathbf{x}$ in time $O(n)$. (Note that this is a significant improvement over the runtime from the trivial algorithm above.) In other words, we want to solve the following problem

Further Reading

• Make sure you carefully read the policy documents: Syllabus and Homework policies.
• Support page on proofs.
• Proof by induction support page.