CSE 20 Lecture Notes - Lecture 1: Discrete Mathematics, Pseudocode
11 May 2018
School
Department
Course
Professor
Cues (Reduce) Notes (Record)
What are the two of the most important problems
in computer science?
What are some general classes of problems that
arise in discrete mathematics?
What is done when presented with these
problems?
What is an algorithm?
What are the properties of algorithms?
What is pseudocode?
What is the goal of an optimization problem?
searching for an element in a list
sorting a list so its elements are in some
prescribed order
such as increasing, decreasing, or alphabetic
given a sequence of integers, find the largest one
given a set, list all its subsets
given a set of integers, put them in increasing
order
given a network, find the shortest path between
two vertices
When presented with such a problem, the first
thing to do is to construct a model that translates
the problem into a mathematical context.
Discrete structures used in such models include
sets, sequences, and functions
As well as such other structures include
permutations, relations, graphs, trees, networks,
and finite state machines
a finite sequence of precise instructions for
performing a computation or for solving a
problem
Input and Output (set)
Definiteness (steps must be defined precisely)
Correctness (produce correct output from input
values)
Finiteness, Effectiveness, and Generality
an intermediate step between an English language
description of steps of a procedure and a
specification of the procedure in a programming
language
Find a solution that either minimizes or maximizes
the value of some parameter
Examples:
finding a route between two cities with
smallest total mileage
Document Summary
What are the two of the most important problems in computer science? searching for an element in a list sorting a list so its elements are in some prescribed order such as increasing, decreasing, or alphabetic. When presented with such a problem, the first thing to do is to construct a model that translates the problem into a mathematical context. Discrete structures used in such models include sets, sequences, and functions. As well as such other structures include permutations, relations, graphs, trees, networks, and finite state machines a finite sequence of precise instructions for performing a computation or for solving a problem. Finiteness, effectiveness, and generality an intermediate step between an english language description of steps of a procedure and a specification of the procedure in a programming language. Find a solution that either minimizes or maximizes the value of some parameter. Examples: finding a route between two cities with smallest total mileage.
