# Logic, Sets, and Functions (313K) (a.k.a. Mathematics for Computer Science)

### We are using Quest!

Quest is a website developed by the College of Natural Sciences that hosts all of the videos we will be using for this "flipped" course. Before each lecture, you will watch typically 2-3 videos and take a quiz. In class, we will work as many practice problems as possible. Frequently, we will break up into groups to solve these problems with hints from me (the instructor) and the TAs. The idea is for you to absorb background material on your own, so we can do more fun things (like problem solving) during class.

### Course Calendar

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

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

## ****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]

--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)

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

### Textbook

It is helpful but not necessary for you to purchase the 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.