| Timing |
Monday |
Tuesday |
Wednesday |
Thursday |
Friday |
3rd period
(9:35 am to 10:25 am) |
Office hours,
Jyungryun (CSE 309) |
|
Office hours,
Hale (CSE 309) |
|
|
4th period
(10:40 am to 11:30 pm) |
Office hours,
Jyungryun (CSE 309) |
|
Office hours,
Hale (CSE 309) |
|
|
5th period
(11:45am to 12:35 pm) |
|
Office hours,
Venkat (CSE 309) |
|
|
|
6th period
(12:50 pm to 1:40 pm) |
|
Office hours,
Venkat (CSE 309) |
Office hours,
Venkat (CSE 309) |
|
|
7th period
(1:55 pm to 2:45 pm) |
|
|
|
Office Hours,
Ajit (CSE 506) |
Office Hours,
Amit (CSE 309) |
8th period
(3:00 pm to 3:50 pm) |
|
Office Hours,
Ajit (CSE 506) |
|
Office Hours,
Ajit (CSE 506) |
Office Hours,
Amit (CSE 309) |
9th period
(4:05 pm to 4:55 pm) |
|
|
Discussion,
section 1096
(RNK 0220) |
|
|
10th period
(5:10 pm to 6:00 pm) |
|
LECTURE
(RNK 0110) |
Discussion,
section 1097
(RNK 0220) |
LECTURE
(RNK 0110) |
|
11th period
(6:15 pm to 7:05 pm) |
|
|
Discussion,
section 7154
(RNK 0220) |
LECTURE
(RNK 0110) |
|
| Date |
Content of the Lecture |
Assignments/ Quizzes |
| 23rd Aug (Thursday) |
- COURSE INTRODUCTION, MOTIVATION, DESCRIPTION OF COURSE POLICIES.
- PROPOSITIONAL LOGIC (Section 1.1 of the textbook).
|
|
| 28th Aug (Tuesday) |
- Propositional Logic: Continuation of some parts from section 1.1 of the book, followed by section 1.2.
- Some lecture slides on Propositional calculus are here and here.
|
|
| 30th Aug (Thursday) |
Wrap up of remaining stuff from sections 1.1 and 1.2
PREDICATE CALCULUS (section 1.3: basic definitions, rules for negation
of statements with quantifiers)
|
Homework 1 is out (due 6th September in class). |
| 4th Sept (Tuesday) |
Predicate calculus (remaining stuff from section 1.3: definition of
scope and binding, distribution of
quantifiers over disjunctions and conjunctions)
Nested quantifiers (section 1.4)
|
|
| 6th September (Thursday) |
Nested quanitifers continued (section 1.4)
Rules of inference in propositional and predicate calculus (section 1.5), introduction to proofs, theorems, conjectures, postulates, corollary (section 1.6)
Hw1 solutions (see COURSEWORX).
|
Homework #2 is out and due on 13th September. |
| 11th September (Tues) |
PROOF TECHNIQUES (section 1.6): direct, indirect (contradiction and contraposition), proof by cases (and how it is different from mere listing of arbitrary examples),
a few basic properties of rational numbers and a few elementary rules on divisibility.
|
|
| 13th September (Thurs.) |
Section 1.6: Equivalence proofs with multiple statements, Section 1:7: backward reasoning, existence proofs (constructive and non-constructive),
pigeonhole principle.
|
- Hw3 is out, due on the 20th
- Quiz 1
|
| 18th September (Tuesday) |
Review of Homework 3. |
Quiz 2 |
|
|
|
| 20th September (Thursday) |
SET THEORY: concept of set, membership, empty set, subset, singleton set, cardinality, power set, power set cardinality, Cartesian product of sets (section 2.1)
Set Operations: union, intersection, difference, symmetric difference, inclusion exclusion principle and its application in counting (section 2.2)
|
Hw 3 due. Hw4 out, due on 2nd October |
| 25th September (Tuesday) |
Section (2.2): Generalized Unions and Intersections.
Section (2.3): FUNCTIONS: Relations as subsest of Cartesian products, counting the number of possible relations; Functions, domain and co-domain, equivalence of functions, one-one functions, onto functions, bijections (to be contd.), examples of each type.
|
|
| 27th September (Thursday) |
Section (2.3): Bijections, examples of bijections, importance of domain and co-domain in defining a function, inverse function,
function composition, non-commutativity of compositions, existence of function compositions, floor and ceiling functions, counting problems on number of functions.
|
|
| 2nd Oct (Tuesday) |
Review for midterm: discussion of solutions to HW4 problems.
|
|
27th September
4th October (Thursday) |
MIDTERM 1 (in class, closed book, closed notes, 5:10 to 7:10 PM) |
|
| 9th Oct (Tuesday) |
Section (2.4): SEQUENCES AND SUMMATIONS
Cardinality
|
|
| 11th Oct (Thursday) |
Section 2.4: Cardinality, countable infinity, countable infinity of set
of all even/odd integers, all integers, all rational numbers, concept of
uncountable infinity, Cantor's diagonalization argument, subset of countable
set.
Section (3.1): Definition of ALGORITHM, Linear Search, Bubble sort, Binary
search
Section (3.3): Concept of time complexity (to be continued), number of comparisons performed
in linear and binary search.
|
Hw5 out, due on 18th October. |
| 16th Oct (Tuesday) |
Definition of Big O notation, examples where f(n) is O (g(n)) and where f(n) is not O(g(n)), properties of O notation
Concept of upper bound, Graphical Illustration of upper bound, Hierarchy of Functions, meaning of O(1).
Analysis of time complexity of Bubble Sort.
|
|
| 18th Oct (Thursday) |
Searching for max/min element in unsorted array, unimodal array (O(log n) solution possible) and their time complexity analysis.
Concept of divide and conquer.
Intro. to Computational Geometry: Meaning of convex polygon, Max/min element of convex polygon.
Algorithm for testing for inclusion inside a convex polygon in O(n) time [naive] and O(log n) time [better].
Algorithm to compute x^n quickly, i.e. in O(log n) time.
Concept of lower bound - Big Omega notation, meaning of BigOmega(1) as a trivial lower bound for every algorithm.
Concept of Theta Notation as a tight bound on complexity
Online material for some of the stuff covered in class today (ignore ALL other stuff from the link).
|
Hw6 out, due on 25th Oct. |
| 23rd Oct (Tuesday) |
Revision of Big O, Big Omega, Big Theta notations with examples.
Difference between best case complexity and concept of lower bound.
Greedy algorithms: fractional knapsack problem with equal weights, with unequal weights; failure of greedy algorithms on 0/1 knapsack
Brief mention of greedy coin changing algorithms from section (3.1) of the book.
|
|
| 25th Oct (Thursday) |
Section (4.1):MATHEMATICAL INDUCTION: definition, technique and proof of
validity
Examples of induction: deMorgan's laws in n variables, properties of
factorial, summation of n numbers, number of diagonals in a convex
n-gon
Importance of base case, example of a faulty inductive proof that "all
horses in the world have the same color".
Section (4.2): Introduction to Strong induction, example: prime factorization of a
number.
|
Hw7 out, due 30th Oct |
| 30th Oct (Tuesday) |
Example of strong induction
Concept of recursion.
Recursively defined sequences and need for recursively defined sequences.
Recursively defined sets.
|
Hw8 out, due 6th Nov |
| 1st Nov (Thursday) |
Recursive algorithms
Recursive algorithm to compute a^{2^k}, Fibonnacci numbers, brief comparison of recursive and iterative procedures.
Merge sort: description of algorithm, derivation of time complexity, example trace.
Quick sort: description of algorithm, derivation of time complexity, example trace.
|
Hw8 UPDATED, due 6th Nov |
| 6th Nov (Tuesday) |
Review session for midterm 2.
|
|
1st November (Thursday) TENTATIVE ... likely to be postponed
THURSDAY 8th November
|
MIDTERM 2 (in class, closed book, closed notes, 5:10 PM to 7:10 PM 5:00 PM to 7:00 PM) |
|
| 13th Nov (Tuesday) |
Section (5.1): COUNTING: Product rule and sum rule, difference between product rule and sum rule, examples where both the sum rule and product rule are applied, applications of sum and product rule on permuting a string of k unique characters in different ways.
Inclusion and exclusion principle, example of the same in counting number of numbers divisible by something, inclusion and exclusion principle for 3 sets.
Section (5.2): Pigeonhole principle and generalized pigeonhole principle (with proof).
|
Hw9 out and due on 20th November. |
| 15th Nov (Thursday) |
- Section (5.3): Permutations (choosing r objects out of n objects such that the ordering matters), Combinations (choosing r objects out of n objects such that the ordering does not matter).
- Comparison between the foll. problems: (A) Number of ways to choose one object each from k buckets containing n_1,n_2,...n_k objects respectively (when the ordering does or does not matter); and (B) Number of ways to choose k objects from a single bucket containing n different objects (when the ordering does or does not matter).
- Combinations viewed as subsets, Combinatorial proof involving two ways to calculate the number of subsets, Combinatorial proof of Pascal's Identity [see theorem 2 in section (5.4)].
- Section (5.5): permutations with repetition, permutations with indistinguishable objects, distributing n different objects into k different boxes.
- Section (9.1): GRAPH THEORY: Concept of a graph, vertices and edges, directed and undirected graph, applications of graph theory (very brief overview): finding shortest paths between cities in a communication network, graph structure for modelling course pre-requisites, the world-wide web as a (directed) graph, precedence graphs in compilers or parallel processing (see figure 11 on page 595).
- Section (9.2): degree of a vertex, isolated vertex and disconnected graphs, Handshaking Lemma, corollary to the Handshaking Lemma.
|
|
| 20th Nov (Tuesday) |
Section (9.2): Types of graphs: complete graph (K_n), cycle graph (C_n), wheel graph (W_n).
Bipartite graph, complete bipartite graph (K_{m,n}), 2-coloring theorem for a bipartite graph.
Operations on a graph: union of graphs, complement of a graph, subgraph of a graph, spanning subgraph.
Counting the number of spanning subgraphs of a graph, the number of subgraphs of a graph.
Section (9.3): Concept of graph isomorphism
|
Hw10 out(due on Thursday 29th Nov) and quiz 5 out (due on Tuesday 27th Nov)
|
| 22nd Nov (Thursday) |
Happy Thanksgiving Day! :-)
|
|
| 27th Nov (Tuesday) |
Section (9.3): Formal definition of isomorphism in terms of bijections between vertices, failure of degree sequences as a sufficient condition for isomorphism of graphs, applications of graph isomorphism in chemistry (for discovery of new isomers) and in flow graphs for plagiarism detection.
Section (9.3): Adjacency matrix and adjacency graph representations. Comparison of advantages and disadvantages.
Section (9.4): Concept of a path, circuit, length of path/circuit.
Section (9.4): Counting the number of paths of length 1, length 2,..., length r, between two vertices.
|
Hw11 out (due on 4th December).
|
| 29th Nov (Thursday) |
Section 9.4: Concept of simple path/simple circuit, Connected graph, Connected Components of a Graph, Strongly and weakly connected directed graphs.
Eulerian circuits and Eulerian paths, Necessary and sufficient conditions for an Eulerian circuit, Example of Eulerian circuits in picture tracing, Problem of the Seven Bridges of Konigsberg, Hamiltonian Paths and Circuits, Examples of graphs that have neither EC nor HC, both EC and HC, only HC and not EC, only EC and not HC.
Planar graphs, Planar embeddings of a graph, Proof of Non-planarity of K_{3,3}, Concept of a region in a planar embedding, Euler's formula: r+n = e+2, Inductive proof of Euler's formula, Corollary to Euler's formula for verifying non-planarity of a graph: e <= 3n-6 (to be continued next time).
Nineteen different proofs of Euler's formula.
|
|
| 4th Dec (Tuesday) |
Corollaries to Euler's formula: (1) General case when v >= 3 (and the degree of each region is atleast 3). (2) Special case when the degree of each region is at least 4 (same as corollary 3 in your book). (3) Case when the planar graph is disconnected and has k connected components.
|
|
| 10th December (MONDAY) |
FINAL EXAM (closed book, closed notes, in class)
Exam time: 8:00 pm to 10:00 pm.
(Exam schedule: 10F
See http://www.registrar.ufl.edu/soc/200708/finalexamsched.html .)
|
|
Dec 6: Hw11 grades are up. Hw10 grades are now up. Please take a look at your grades till now. Regrade requests for Hw10, Hw11, Quiz 5 must be placed by email or in person, on or before Monday. For earlier stuff, no regrades are now possible.