Other related courses:

ITC: https://sites.google.com/view/itc-ucp-2017

PF/OOP: https://sites.google.com/view/pf-ucp-2018/

DSA: https://sites.google.com/view/dsa-ucp2017/home

Algo: https://sites.google.com/view/algo-ucp-2017/home

Lecture 1: Why Discrete Mathematics

• Introduction to Propositions and Conjectures
• Why Proof is Important?
  • For Primality testing we don't need to divide after sqrt(N)
  • Why a computer Programmer has a powerful skill which a mathematician don't have? Isn't it?
    • N^2 + N + 41 is prime?
  • Oh Really A programmer is more powerful??? Euler Conjecture a^4 + b^4 + c^4 = d^4 do not have any solution.
  • Oh Really A Programmer is more powerful??? a^3 + b^4 = c^4 Do not have any solution

(Video Lecture: Youtube-Playlist): Lecture 1

Reading Material: https://goo.gl/gC7Ris

Lecture 2: Introduction to Propositional Logic and Quantifiers

• Proposition, Compounding propositions, Implication
• Double Implication, Converse, Inverse, Contrapositive, Proposition Function, Predicate, Quantifiers(Existential and Universal)
  • Fallacies and making people fool.

(Video Lecture: Youtube-Playlist): https://goo.gl/At63zz

Reading Material: Rosen (Section 1.1, 1.2, 1.3, 1.4, 1.5)

Assignment # 1: https://goo.gl/Jy95Xk (Solution)

Lecture 3: Proofs Techniques I (Direct Proofs and Contraposition)

• Proof techniques
• Contrapositive-Case by Case Proofs Technique

(Video Lecture: Youtube-Playlist): https://goo.gl/r27Dvo

Reading Material: Rosen (Section Proofs Technique 1.7, 1.8)

Lecture 4: Proofs Techniques II (Proof by Contradiction)

• Proofs (Review of Direct, and Contraposition) The layout of Contradiction proof
• Further Examples of Proof by Contradiction

(Video Lecture: Youtube-Playlist): https://goo.gl/P1AZf4

Reading Material: Rosen (Section Proofs Technique 1.7, 1.8)

Lecture 5: Efficiency Measures and Time Complexity

• Efficiency Estimation
  • Efficiency Measurements and BIG O, Big Omega and Theta
  • Efficiency Measurements and BIG O, Big Omega and Theta of Codes II

(Video Lecture: Youtube-Playlist): https://goo.gl/GQybtX

Reading: Rosen 3.2 and 3.3

Assignment 2: https://goo.gl/aziNMz (Solution)

Lecture 6: Time Complexity of Codes II

• Arithmetic Sequences and Series+Codes Analysis I
• Geomtric Sequences and Series+Codes Analysis II
• Many Examples of Codes analysis.

(Video Lecture: Youtube-Playlist): https://goo.gl/ct9TWB

Practice Problems with Solution (See comments for the solution) 

Assignment 3 (In Progress): https://goo.gl/kNqPmZ

Sample Tex and PDF - file

Lecture 7: Mathematical Induction I

• Induction Theorem
  • Imagining the Dominos Effect
  • Prove that Polygon Diagonals Count is N(N-3)/2
  • Counting the possible Tiling Problem
  • Amount Payment

(Video Lecture: Youtube-Playlist): https://goo.gl/G12YJx

Reading Material: Rosen (Section 4.1)

Lecture 8: Mathematical Induction II

• Weak vs Strong Induction
  • The Size of Power-Set of a Set(having N elements) is 2^N
  • Tiling of 2^N x 2^N floor with L-Type Domino
  • Winning Strategies games and their proofs
  • Hats Finding Problem

(Video Lecture: Youtube-Playlist): https://goo.gl/mDXjUi

Reading Material: Rosen (Section 4.1 and 4.2)

Lecture 9: Recursion I

• The connection between Mathematical Induction to Recursion
• How Recursion Works - Stack and Recursion Tree
• Examples of Recursion Factorial + Slow-Power + FAST-Power + Fibonacci

Video Lecture: Youtube-Playlist

Reading Material: Rosen 5.4

Assignment # 4

Lecture 10: Recursion II (Recursive Program's Analysis)

• FAST Powering Vs Slow Powering
• Fibonacci Recursive vs Dynamic Programming (Memoization)
• Computing GCD recursively
• Matrix Determinant
• Tower of Hanoi
• Maze Solver

Video Lecture: Youtube-Playlist

Reading Material: Rosen 5.4

Lecture 11: Recursion III (hands on practice)

• Digits Reverse and in order Printing
• Coin Change Problem (Finding the change of money M>=60 with 11's and 6's coins)
• Fibonacci with Memorization

Video Lecture: Youtube-Playlist

Reading Material: Rosen 5.4

Lecture 12: Recursion IV (hands on practice II)

• Decimal to Binary Conversion (printing and conversion)
• Linear Searching
• Binary Searching
• Multiplication using Addition/Subtraction Only
• Printing Permutation

Video Lecture: Youtube-Playlist

Reading Material: Rosen 5.4

Lecture 13: Lets Start Counting

• Basic Counting Rule I: The Product Rule
  • The basic Definition and principle
    • Its Applications
  • The Generalization of fundamental counting Principle
• Many Applications of Counting
  • Car Plates Registration Count
  • Chair Counting
  • Counting Binary Strings
  • Counting Power Set
  • Counting Functions
    • Counting One to One Functions

Video Lecture: Youtube-Playlist

Reading Material: Rosen 6.1

Lecture 14: Discussing Assignment # 5 (Revision of Mid Term)

• Logical Thinking
• Proofs (contradiction, contraposition)
• Induction
• Time Complexity

Video Lecture: Youtube-Playlist

Reading Material: ____________

Lecture 15: Revision of DSA

• Growable Arrays
  • Stacks
    • Expression Evaluator
  • Queues (circular)
    • Rate-path finder/Prinson Break.
• Linked List
  • Pictorial Representation

Video Lecture: Youtube-Playlist

Lecture 16A: Counting Begins (Revision)

• Basic Counting Rule I: The Product Rule
  • Many Examples of its applications
• Sum Rule and its applications
• Combining Sum and Product Rule
  • Counting Passwords

Video Lecture: Lec-16A

Reading Material: Section 6.1 (Rosen)

Lecture 16B: Counting (PIE and its APPLICATIONS and Division Rule)

• PIE and its Applications
  • Its proof idea.
  • Divisors Counts, Primes Counts
• Division Rule
  • Counting on Round Table
  • Necklace Problem
• Tree Method of Counting

Video Lecture: Lec16B

Reading Material: Section 6.1 (Rosen)

Lecture 17: Pigeon holes Principle (PHP)

• Pigeon Hole Principle and its applications
• Basic Examples
  • Many Fundamental Examples
  • Prove that "For every integer N there is a Multiple X with only 0s and 1s in Decimal Representations"?
  • From a 6 people group where we only have Enemy or Friend relation there exists a Friend or Enemy Triangle

Video Lecture: Youtube-Playlist

Reading Material: Section 6.2

Lecture 18: Pigeon holes Principle II (PHP)

• Pigeon Hole Principle and its applications
• Elegant Proofs
  • Finding the Subsequence of Matches accumulating to 14 where in 30 days you have played 45 total matches (on every day you must have to play 1 match)
  • (N+1) out of 1-2n numbers selected then there exists one divisor-dividend pair.
  • Increasing Decreasing Sequence
  • Arranging a sequence of N^2 elements such that there does not exists any increasing or decreasing sequence of N+1 length
  • Erdos Szekeres Theorem (From a sequence of N^2+1 elements there always exists either a decreasing or increasing sequence of N+1 length). INFINITE CHAOS IS NOT POSSIBLE.

Video Lecture: Youtube-Playlist

Reading Material: Section 6.3

Lecture 19: Permutations, Combinations and Combinatorial Proof

• Permutations and Its applications
• Combinations and Its Examples
• Combinatorial proofs
  • Recursive Definition of Combination
  • Pascal Identity

Video Lecture: Lec-19

Reading Material: Section 6.4

Lecture 20: Combinatorial Proofs

• Combinatorial Proofs (Power Set Examples, Total Possible Bit Strings Counts)
• Pascal's Identity
• Pascal's Triangle
• Bionomial and Identity related Theorems
• Vandermonde's Identity
• (r+1) 1's Bits Counts

Video Lecture: Lec-20

Reading Material: Section 6.4

Lecture 21: Generalized Permutations and Combinations

• Revision (Permutation+Combinations+Combinatorial Argument)
• Generalized Permutation and Combination
• Boxes and Objects (Distinguishability and Indistinguishability)
  • Algorithmic Analysis
  • Indistinguishable Boxes and Objects Counts

Video Lecture: Lec-21

Reading Material: Section 6.4

Lecture 22: Diffie Hellman Key Exchange

• Classical Cryptography
• ENIGMA Machine and Turing
• Basic Number Theory
  • Basic proposition of Division Principle
  • How Euclid discovered GCD algorithm
• Modular Arithmetic
  • Basic propositions of MODULAR Arithmetic (+, -, *)
  • Generators/Primitive Root
• Diffie Hellmen Key Exchange

Video Lecture: Lec-22

Reading Material: Chapter 4

Lecture 23: Basic Number Theory

• Basic Number Theory
  • Basic proposition of Division Principle
  • How Euclid discovered GCD algorithm
• Modular Arithmetic
  • Basic propositions of MODULAR Arithmetic (+, -, *)
  • Generators/Primitive Root
  • GCD and primitive Roots/Relatively Prime numbers

Video Lecture: Lec-23

Reading Material: Chapter 4

Lecture 24: Elgamal Crypto System

• Revision of Finite Fields
• FAST POWERING
  • Diffie Hellman Algorithm
• Extended GCD
• Finding Inverse using GCD algorithm
• Elgamal Crypto System

Video Lecture: Lec-24

Reading Material: Chapter 4

Lecture 25: Graphs

• Undirected and Directed Graphs
  • Modeling Graphs (Facebook, Twitter, Internet connections, Telephones/Mobiles lines connection, Dependency based activities, and many examples of modeling real life problems into Undirected Graphs and Digraph .
• Handshaking lemma and its corollary
• Clique(completely connected)/Wheel/linked list/Trees graphs
• Bipartite Graphs
  • Two Coloring Problem
  • Proved that every Tree is a Bipartite Graph
• Representing Graphs Data Structures into Adjacency Matrix and Adjacency list.
  • Finding the Path Problem

Video Lecture: Lec-25

Reading Material: Chapter 10.1, 10.2, 10.3, 10.8

Lecture 26: Graphs II

• Graphs Coloring
• Bipartite Graphs and their applications
• Graphs Isomorphism
• Graphs Exploration/Traversal algorithm

Video Lecture: Lec-26

Reading Material: Slides

Topics of the book of ROSEN: Chapter 10.3, 10.2, 10.4, 10.6

Lecture 27: Graphs III (Paths, Eularian and Hamiltonian Paths)

• Paths and Circuit
• Isomorphism revisited
• Finding Eulerian Circuit and its discovery
• Hamiltonian Paths/Circle
  • Bondy and Chvátal (1976) Theorem
  • Dirac’s and Ore’s Theorems
• Planar Graphs

Video Lecture: Lec-27

Reading Material: Slides

Rosen Book: Chapter 10.5

Lecture 28: Binary Tree Data Structure (Revision of DSA)

• Recursive Binary Tree Data Structure
• Tree Traversals
  • LNR/NLR/LRN and their variants and why and when we need them
  • Printing Tree structure
• Augmenting Tree with many recursive properties
• Many Problems related to Binary Tree Data Structure

Video Lecture: Lec-28

Reading Material: Chapter 11.1, 11.2, 11.3

Kashif's Talk: Cantor's Diagonalization and Gödel's Incompleteness Theorem

• Cardinality of the Set and one to one and onto correspondence
• Measuring the Mapping functions of
  • Evens to N
  • Odds to N
  • Z to N
  • N^2 to N
  • N^3 to N
  • Rationals to N
• Cantor's Set and Diagonalization proof of greater infinity than {\displaystyle \aleph _{0}}
• Halting Problem and derivation through Cantor's Diagonalization
• Godel's Incompleteness Theorem.

Video Lecture: Guest Lecture - Godel's Incompleteness Theorem

Reading Material: Section 2.5

Material

• Take Home Exam (Solution)