Logic, Sets, and Functions (313K) (a.k.a. Mathematics for Computer Science)
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 GAR 0.102
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.
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.
I missed a quiz, and I have a legitimate reason for missing it. What should I do?
Answer: Email the instructor and give your reason. We will take your final exam grade and substitute it for the missed quiz grade. So, do not worry about missing a quiz if you have a reasonable excuse for being absent (e.g., you are sick). There are no make-up quizzes.
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
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.
Links to Additional Reading Material
Additional Notes
Course material may vary depending on
student interest.