# Logic, Sets, and Functions (313K)

### 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.

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.

### Additional Notes

Course material may vary depending on student interest.