# Logic, Sets, and Functions (313K)

### Instructor: Adam Klivans

### PLEASE USE THE EMAIL ADDRESS "313questions at gmail.com" FOR ALL
NON-URGENT EMAILS!

### Course meets Tuesday and Thursday at 3:30 PM in WCH 1.120

### We are using Quest! Please go to quest.cns.utexas.edu to sign up.

### Office Hours, Locations (including Tutoring): PLEASE SEE THE GOOGLE CALENDAR

### Course Calendar

### FREQUENTLY ASKED QUESTIONS:

#### When is Homework so-and-so due? Was there Homework handed out?

Answer: Please see the Google Calendar. The Calendar shows when homeworks were
handed out, when they are due, etc.

#### When is Exam so-and-so?

Answer: Please see the Google calendar. If it's not there, it means I haven't scheduled it yet. I will be sure to give everyone plenty of notice before exams.

#### When are office hours? When is the tutoring session?

Answer: Please see the Google calendar.

#### Where do I turn in my homework?

Answer: In class.
#### Where can I pick up my homework?

Answer: In discussion section or someone's office hours only. Not during lecture!
#### I wasn't in class when you handed out homework, where can I get a copy?

Answer: You will have to go a TA's office hours (or Prof. Klivans' office hours), or pick one up during a discussion section.
#### Is there a quiz or a video I need to watch?

Answer: Go to quest.cns.utexas.edu. The website will tell you about upcoming modules/quizzes that are due. Typically, there is a set of videos and quiz due at 2pm before every lecture.
#### Where is the syllabus?

Answer: Below.
#### What section of Rosen are you following?

Answer: See Syllabus Below.
## ****Syllabus**** (updated as the course progresses)

#### Predicates, Quantifiers, and Satisfiability (1 week) [Rosen: 1.3--1.5]

--Encode statements into predicates with quantifiers.
--Boolean formulas; the notion of Satisfiability.

#### Basic Proof Techniques (1 week) [Rosen 1.6--1.8]

--Direct Proof; Proof by Contradiction;
--Simple Examples; Refresher on summation notation.

#### Induction and Invariants (1.5-2 weeks) [Rosen 5.1--5.3]

--Basic proofs by induction
--Proving simple invariants

#### Graph Theory (3 weeks) [Rosen 10.1,10.2,10.5,10.7,10.8,11.1]

-- Graph Coloring and applications
-- Trees

-- Planarity

-- Proving simple graph properties using induction

#### Sets and Functions (2-2.5 weeks) [Rosen 2.1--2.3, 2.5]

-- Definitions, Relations
-- Injections, Surjections, and Bijections

-- Infinite sets; uncountability

#### Recurrences (2 weeks) [Rosen 8.1--8.3]

--Recurrences; applications to counting
--Solving Linear recurrences

#### Big-O and Intro to Algorithms (2 weeks) [Rosen 3.1--3.3]]

--Growth of common functions; Big-O and Big-Omega
--Master Theorem and Intro to algorithms (simple divide and conquer)

### Grading

Module questions: 10%, homework 20%, pop quizzes 10%, tests 30%, final exam 30%.

### Textbook

We will roughly follow chapters from Rosen's "Discrete
Mathematics and Its Applications" (Seventh Edition). Several lectures,
however, will be based on other sources (for example my own
experience).

### Homework Policy

You may work in groups of three, but
you must write up the solutions to the homeworks yourself.
### Links to Additional Reading Material

### Additional Notes

Course material may vary depending on
student interest.