Handwritten Notes for Discrete Mathematics and Digital Electronics - WASE Open Exam

Handwritten Notes for Discrete Mathematics and Digital Electronics specially for WASE Open Book exams.

Download:

DS Written Notes

Microprocessor Handwritten Programs

Download --> Print ---> Take ---> Copy it in exam... :D

See Similar Posts:

• Notes for DS & Microprocessor?

• Microprocessor Programs

• Materials for WASE Open Book Exams

 

Wase I Semester Open Book Exam Model Papers

Here is the Model Question papers for the I Semester Open Book Exam.

Download









See Similar Posts:

• Get ready for Open Book Exam...

• WASE Open Book Exams - C Programs

 

Discrete Structures MCQ's

 Download Objective Questions i.e. MCQ's

Download File1

 

Discrete Mathematical Structures - Sets and Subsets

Sets and Subsets :

Download Notes for :  
Download1
Download2

The Notes include :

Definitions:

Set: A set is a collection of well-defined objects (elements/members). The elements of the set are said to belong to (or be contained in) the set.

A set may be itself be an element of some other set.

A set can be a set of sets of sets and so on.

Sets will be denoted be capital letters A, B, C, ...

Elements will be denoted by lower case letters a, b, c, ....  x, y, z.

There are five ways to describe a set.

1. Describe a set by describing the properties of the members of the set.

2. Describe a set by listing its elements.

3. Describe a set by its characteristic functions

4. Describe a set by a recursive formula.

5. Describe a set by an operation (such as union, intersection, complement etc.,) on some other

    sets.

Venn diagrams: Venn diagrams are used to visualise various properties of the set operations.

The Universal Set is represented by a large rectangular area.

Distributive and DeMorgan’s Laws can be established from Venn diagrams.

Distributive laws

AÈ(BÇC) = (AÈB) Ç (AÈC) 

Exercises:

 1.         Let A = {1, 2, 3, 4, 5}. Which of the following sets are equal to A?

a.             {4, 1, 2, 3, 5}

b.            {2, 3, 4}

c.             {1, 2, 3, 4, 5, 6}

d.            {x | x is an integer and x² £ 25}

e.             {x | x is a positive integer and x £ 5}

f.             {x | x is a positive rational number and x £ 5}

etc...

Sequences

A sequence is a list of objects arranged in a definite order; a first element, second element, third element, and so on. It is classified as finite sequence and infinite sequence. The elements may all be different, or some may be repeated.

Examples:

1.      The sequence 1, 0, 0, 1, 0, 1, 0, 0, 1, 1 is a finite sequence with repeated items.

2.      The sequence 1, 3, 5, 7, 9, 11, 13, 15 is a finite sequence with different items.

3.      The sequence 3, 8, 13, 18, … is an infinite sequence.

etc...

Characteristic Functions

If A is a subset of a universal set U, the characteristic function f_A of A is defined for each x Î U as:

            f_A(x)    = 1, if x Î A

                        = 0, if x Ï A.

etc...

Strings

Given a set A, we can construct the set A* consisting of all finite sequences of elements of A. Often, the set A is not a set of numbers, but some set of symbols and Set A is called an alphabet, and the finite sequences in A* are called words or strings from A. The empty sequence or empty string contains no symbols and denoted as Ù.

Example:

etc...
 

Regular Expressions

A regular expression (over A) is a string constructed from the elements of A and the symbols (, ), Ú, *, Ù, according to the following definition.

RE1. The symbol Ù is a regular expression.

RE2. If x Î A, the symbol x is a regular expression.

RE3. If a and b are regular expressions, then the expression ab is regular.

RE4. If a and b are regular expressions, then the expression (aÚb) is regular.

RE5. If a is a regular expression, then the expression (a)* is regular.

Examples:

1.      0*(0Ú1)*

etc...

Matrices

A matrix is a rectangular array of numbers arranged in m horizontal rows and n vertical columns.

            a₁₁          a_{12          …}             a_1n

            a₂₁          a_{22          …}             a_2n

A =      .           .           .           .

            .           .           .           .

a_m1         a_{m2         …}             a_mn

A = [ a_ij ].

etc...

Boolean matrix

A Boolean matrix is an m x n matrix whose entries are either zero or one.

Boolean matrix operations

Let A and B be m x n Boolean matrices.

etc...

DISCRETE STRUCTURES FOR COMPUTER SCIENCE - Topics

Course Description :

Introduction to discrete mathematical structures; Formal logic and predicate calculus; Sets, relations and functions; Proof techniques; Graphs and trees; Primes, factorization, greatest common divisor, residues and application to cryptology; Boolean algebra; Permutations, combinations and partitions; Recurrence relations and generating functions; Introduction to error-correcting codes; Formal languages and grammars, finite state machines.

Textbook :

T1.      Kolman, Busby, Ross and Rehman, Discrete Mathematical Structures for Computer Science, Pearson Education, 5^th Edition, 2003.

Topics :

Week No.	Topics	Reference to Text Book
1	Sets, Operations on sets, Sequences, Matrices	T1-Ch.1
2	Propositions, Conditional statements, Induction	T1-Ch.2
3	Pigeonhole Principle, Recurrence Relations	T1-Ch. 3.3, 3.5
4	Relations and Digraphs, Paths in Relations, Equivalence Relations	T1-Ch. 4.2 - 4.5
5	Operations on Relations, Transitive closure	T1-Ch. 4.7 – 4.8
6	Functions, Function for Computer Science Permutation functions	T1-Ch. 5.1,5.2,5.4
7	Partially ordered sets, Lattices, Boolean Algebras	T1-Ch.6.1, 6.3, 6.4
8	Review and Problem Solving
Syllabus for Mid-Semester Test: Topics covered in the first eight weeks
9	Graphs, Euler Paths, Hamilton Paths	T1-Ch 8.1 – 8.3
10	Trees, Labeled Trees	T1-Ch.7.1, 7.2
11	Tree Searching, Undirected Trees	T1-Ch. 7.3, 7.4
12 – 13	Minimal Spanning Trees	T1-Ch. 7.5
14	Semi groups, Products and Quotients of Semi groups	T1-Ch.9.1, 9.2
15	Groups, Products and Quotients of Groups	T1-Ch.9.3, 9.4
16	Review and Problem Solving
Syllabus for Comprehensive Exam (Open Book) All topics given in Plan

 

Reference Books :

R1.     D.S. Malik and M.K. Sen, Discrete Mathematical Structures: Theory and Applications, Thomson, 2004.

R2.     Goodaire & Parmenter : Discrete Mathematics & Graph Theory, Pearson Education, 2000.

R3.     Kenneth H. Rosen, Discrete Mathematics and its Applications, Tata McGraw Hill, 5^th Ed., 2004.

R4.     C.L. Liu, Elements of Discrete Mathematics, 2^nd Edition, McGraw Hill, 1986.