Logic, Sets, and Functions (313K)

Instructor: Adam Klivans


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


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)


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


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

Mathematics: A Very Short Introduction.

Additional Notes

Course material may vary depending on student interest.