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.