Scribd
Upload
21 views8 pages

Intro Ds

This document provides an overview of an introductory discrete mathematics course. The course will cover fundamental mathematical concepts like logic, proofs, graph theory, and counting which provide the foundation for solving problems in computer science, such as designing algorithms and security systems. Discrete mathematics deals with discrete, finite objects like integers rather than continuous concepts like real numbers. It focuses on techniques like induction, recursion, and graph modeling that are important for computer science applications. The course will help students learn rigorous proof methods and apply discrete math concepts to domains including algorithms, artificial intelligence, and computer networks.

Uploaded by

YapYoongSeng
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
21 views8 pages

Intro Ds

This document provides an overview of an introductory discrete mathematics course. The course will cover fundamental mathematical concepts like logic, proofs, graph theory, and counting which provide the foundation for solving problems in computer science, such as designing algorithms and security systems. Discrete mathematics deals with discrete, finite objects like integers rather than continuous concepts like real numbers. It focuses on techniques like induction, recursion, and graph modeling that are important for computer science applications. The course will help students learn rigorous proof methods and apply discrete math concepts to domains including algorithms, artificial intelligence, and computer networks.

Uploaded by

YapYoongSeng
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

About the Course

Lecture 0: Sep 2

Mathematics
Computer Science: use computer technology to solve problems.
Many courses in our curriculum will talk about computer technology.
This course will provide the mathematical foundation to solve problems,
e.g. to design a security system, to design a fast searching algorithm,
to analyze algorithms rigorously (e.g. pagerank and linear algebra), etc.

(pictures from wiki)

Discrete Mathematics
What is discrete mathematics?
discrete mathematics

continuous mathematics

integers

real numbers

graphs

geometric space

induction

calculus

logic

These two areas are not disjoint, e.g. calculus can be


used to solve discrete problems (generating functions).

Discrete Mathematics
Why discrete mathematics?
In computer science we usually deal with finite, discrete objects. For example,
- we cannot store a real number (infinite precision) in a computer but can only
store bits (finite precisions).
- we often model a computer network as a graph, and use the knowledge and
techniques in dealing with graphs to solve problems in networks.
The problems and the techniques are often different (e.g. induction, recursion).

Logic and Proofs


How do computers (and humans) think?
Logic: propositional logic, first order logic
Proof: induction, contradiction

Applications: artificial intelligence, database, circuit, algorithms


Objective: to reason rigorously and learn basic proof techniques (e.g. induction)

Graph Theory
Graphs
Degree sequence, Eulerian graphs, isomorphism
Trees
Matching
Coloring

Applications: Computer networks, circuit design, data structures

Graph Theory

How to color a map?


How to schedule exams?

How to send data efficiently?

Objective: to model problems and learn basic concepts and knowledge

Counting
Sets and Functions
Combinations, Permutations, inclusion-exclusion
Counting by mapping, pigeonhole principle
Recursions, generating functions

C
Applications: probability, data structures, algorithms
Objective: to learn basic concepts (set, functions) and fundamental techniques.

You might also like