BIL 133: Combinatorics and Graph Theory

Description
This class is designed to introduce the students with the basic mathematical concepts heavily used in analysis of algorithms as well as zeroth and the first order logic. Introductory level algorithm analysis and design techniques are also within the scope of the class.

General Information
 

Books
1) Logic in Computer Science Modelling and Reasoning About Systems by Michael R A Huth and Mark D Ryan,
2) Concrete Mathematics a Foundation for Computer Science by Graham, Knuth and Patashnik,
3) Introduction to Algorithms by Cormen et al.
 
Grading Scheme
Each midterm (there are two of them) will be worth at least 300 points, the final will be worth at least 400 points, homework assignment and pop quizzes will be worth at least 300 points in total.
The total amount of points collected in midterms, final, homework and quizzes will determine your letter grade.
You need to collect at least 900 points for AA, 850 points for BA, 800 points for BB, 750 points for CB, 700 points for CC, 650 points for DC, and 600 points for DD.;
 
Syllabus
The following topics will be covered in class.
1) Propositional and Predicate Logic
2) Recurrences
3) Summations
4)Models of Computation
5) Introduction to Algorithm Design and Analysis
 
Detailed Syllabus
Lecture 1: Definition of science and scientific methodology, Inductive vs. Deductive Reasoning, The language of Propositional Logic.

Lecture 2: Natural Deduction in Propositional Logic.

Lecture 3: Natural Deduction in Propositional Logic.

Lecture 4: Propositional Logic as a Formal Language, Semantics of Propositional Logic, Soundness and Completeness.

Lecture 5: Mathematical Induction (Usual, Strong and Structural).

Lecture 6: Motivating the need for a richer logic system, Syntax of Predicate Logic.

Lecture 7: Free and Bound Variables, Substitution of Variables, Natural Deduction in Predicate Logic.

Lecture 8: Natural Deduction in Predicate Logic.

Lecture 9: Recursion and Recurrences(Tower of Hanoi problem and its variations)

Lecture 10: Recursion and Recurrences (The lines in the Plane problem and the Josephus Problem)

Lecture 11: Repertoire Method for Solving Recurrences

Lecture 12: Sums(Notation of Sums, Relation of Sums and Recurrences)

Lecture 13: Summation Factor method to evaluate Recurrences and the Perturbation method to Evaluate Sums.

Lecture 14: Manipulation of Sums, Multiple Sums, General Methods for Evaluating Sums and Infinite Sums.

Lecture 15: Definition of Computational Problems, Instances, Countable vs. Uncountable Sets, Dovetailing, Diagonalization.

Lecture 16: Finite State Machines, Universal Model of Computation.

Lecture 17: Insertion Sort and Algorithm Analysis

Lecture 18: Divide and Conquer Paradigm via Merge Sort

Lecture 19: Growth of Functions and Asymptotic Notations

Lecture 20: Solving Asymptotic Recurrences

Lecture 21: Heaps, Priority Queues and Heapsort