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