[CSE 215]  Midterm Exam Guide  Everything you need to know! (21 pages long)
For unlimited access to Study Guides, a Grade+ subscription is required.
SBU
CSE 215
MIDTERM EXAM
STUDY GUIDE
Homeworks are on his website, but the answers are on Blackboard.
•
Homeworks are harder than the actual exams.
•
Classes are usually recorded and can be viewed on Blackboard.
•
Important Stuff
Office: CS 335 New Building
•
Open ended hours.
○
Hours: Mondays 4pm and Wednesdays 5pm, or by appointment.
•
Office Hours
Assignments: 40% (Tough; groups of 2)
•
Finals: 30%
•
Midterms and finals are easier than the homeworks.
○
Two Midterms: 15% each
•
Extra credit (for answering in

class questions).
•
It's a trap.
•
Grading
Never on slides, only writing down in class.
•
Solutions
Work in groups of two, submit one paper.
•
1 homework per chapter or topic. (About 6

7)
•
10

15 exercises for each assignment.
•
Homeworks
Formal concepts that we study in CSE 215, are essential to program effectively (among other
things).
•
What is the smallest rote that goes through all the 50 capital cities of USA?
○
How would you write a program to solve the above?
○
Travelling Salesman Problem:
•
There are 49! Possibilities assuming that there is 1 route to each capital city. This would be a
tour
,
visiting all cities once.
•
Enumerate all routes, and pick the best.
1.
Start from a city, and pick the next based on some "condition". Pick any city and move to
each city based on a condition. However, this could
easily be proven incorrect
with a route
in a straight line going the wrong way.
2.
Solve the problem for all possible subsets of cities. Done "recursively"; also solving the
problem for the full set (sets of 2 cities, 3 cities, etc). This is an expansion on the first
method. You pretty much solve for the shortest route between n number of cities and then
use the subset of the shortest paths and combine them into the most efficient route.
(Smaller solution to larger solution.) Much faster than number 1.
3.
Possible TSP Algorithms:
•
Concepts needed: counting, enumeration, conditions, sets, subsets, functions, variables, etc.
•
Which of the above is optimal? Requires proof techniques.
•
Motivation for CSE 215
Logical conditions, statements.
•
Proof Techniques
•
CSE 215 Topics
Lecture 1

Intro
Monday, January 23, 2017 2:28 PM
New Section 1 Page 1
Proof Techniques
•
Induction, Recursion
•
Set Theory, Functions
•
Counting, Probability
•
A variable is a name given to an entity whose value is unclear/unknown/not

fixed.
•
Eg. How much it costs to drive 100 miles.
•
Answer = 100 (gallon per mile) (price per gallon)
•
= 100xy where x and y are variables for (gallons per mile) and (price per gallon).
○
Since the (price/gallon) may change over time, and (gallon/mile) depends on the car, its best to
express the answer as:
•
Variables
All men are crazy. (Doesn't state that if you are crazy, you are a man)
•
Crazy people like each other.
•
John is a man.
•
Alex is crazy, but doesn't like John.
•
Is Alex a man?
•
To solve for these types of problems, we must convert these statements to formerly represent
these statements.
•
Logical Statements
For all numbers r, there exists a number y such that y > r. This is a logical statement which does
not need to give us exact values for r and y.
•
X is prime if for all 1 < y < x, ceiling(x/y) =/= (x/y)

> Either true or false depending on x and
y.
○
Prime Test: A positive natural number is prime, if
it is not divisible by any number less than it
(except for 1).
•
More Logical Statements
We'll learn techniques to prove/disprove claims.
•
Any number greater than 1 is divisible by a prime number.
○
For all numbers n, if n is even, then n or n+2 is divisible by 4.
○
There exists a number n, such that n^2

3 is divisible by 7.
○
Examples of claims:
•
To start proving these claims, we must formally define what things are such as even numbers,
primes, etc.
•
Proofs
A set is a collection of elements.
•
Sets
Subset
•
Proper Subset
•
Superset
•
Union, intersection, minus.
•
Cartesian product.
•
Ordered pairs.
•
Set Relationships and Operators
Relations define an "association/relationship" between elements of two sets.
•
Aka relations that are 1 to 1, onto, or neither.
Eg, Consider two sets "Drinkers" and "Beers". Each drinkers "likes" a certain set of beers.
•
Relations
New Section 1 Page 2