Discrete Structures - Syllabus

Embark on a profound academic exploration as you delve into the Discrete Structures course (DS) within the distinguished Tribhuvan university's CSIT department. Aligned with the 2074 Syllabus, this course (CSC160) seamlessly merges theoretical frameworks with practical sessions, ensuring a comprehensive understanding of the subject. Rigorous assessment based on a 60 + 20 + 20 marks system, coupled with a challenging passing threshold of , propels students to strive for excellence, fostering a deeper grasp of the course content.

This 3 credit-hour journey unfolds as a holistic learning experience, bridging theory and application. Beyond theoretical comprehension, students actively engage in practical sessions, acquiring valuable skills for real-world scenarios. Immerse yourself in this well-structured course, where each element, from the course description to interactive sessions, is meticulously crafted to shape a well-rounded and insightful academic experience.

Course Description: The course covers fundamental concepts of discrete structure like introduce

logic, proofs, sets, relations, functions, counting, and probability, with an emphasis on applications

in computer science.

Course Objectives: The main objective of the course is to introduce basic discrete structures,

explore applications of discrete structures in computer science, and understand concepts of

Counting, Probability, Relations and Graphs respectively.

Basic Discrete Structures

1.1. Sets: Sets and Subsets, Power Set, Cartesian Product, Set Operations, Venn Diagram,Inclusion-Exclusion Principle, Computer Representation of Sets

1.2. Functions: Basic Concept, Injective and Bijective Functions, Inverse and Composite Functions, Graph of Functions, Functions for Computer Science (Ceiling Function, Floor Function, Boolean Function, Exponential Function), Fuzzy Sets and Membership Functions, Fuzzy Set Operations

1.3. Sequences and Summations: Basic Concept of Sequences, Geometric and Arithmetic Progression, Single and Double Summation

Integers and Matrices

2.1. Integers: Integers and Division, Primes and Greatest Common Divisor, Extended

Euclidean Algorithm, Integers and Algorithms, Applications of Number Theory (Linear

Congruencies, Chinese Remainder Theorem, Computer Arithmetic with Large Integers)

2.2. Matrices: Zero-One Matrices, Boolean Matrix Operations

Logic and Proof Methods

3.1. Logic: Propositional Logic, Propositional Equivalences, Predicates and Quantifiers,

Negation of Quantified Statements, Proof of quantified statements, Nested Quantifiers,

Rules of Inferences

3.2. Proof Methods: Basic Terminologies, Proof Methods (Direct Proof, Indirect Proof, Proof

by Contradiction, Proof By Contraposition, Exhaustive Proofs and Proof by Cases),

Mistakes in Proof

Induction and Recursion

4.1. Induction: mathematical Induction, Strong Induction and Well Ordering, Induction in

General

4.2. Recursive Definitions and Structural Induction, Recursive Algorithms, Proving

Correctness of Recursive Algorithms

Counting and Discrete Probability

5.1. Counting: Basics of Counting, Pigeonhole Principle, Permutations and Combinations,

Two Element Subsets, Counting Subsets of a Set, Binomial Coefficients, Generalized

Permutations and Combinations, Generating Permutations and Combinations

5.2. Discrete Probability: Introduction to Discrete Probability, Probability Theory,

Probability Calculation in Hashing, Expected Value and Variance, Randomized

Algorithms

5.3. Advanced Counting: Recurrence Relations, Solving Recurrence Relations

(Homogeneous and Non-Homogeneous equations), Introduction to Divide and Conquer

Relations and Graphs

6.1. Relations: Relations and their Properties, N-ary Relations with Applications,

Representing Relations, Closure of Relations, Equivalence Relations, Partial Ordering

6.2. Graphs: Graphs Basics, Graph Types, Graph Models, Graph Representation, Graph

Isomorphism, Connectivity in Graphs, Euler and Hamiltonian Path and Circuits,

Matching Theory, Shortest Path Algorithm (Dijkstra’s Algorithm), Travelling Salesman

Problem, Graph Coloring

6.3. Trees: Introduction and Applications, Tree Traversals, Spanning Trees, Minimum

Spanning Trees (Kruskal’s Algorithm)

6.4. Network Flows: Graph as Models of Flow of Comodities, Flows, Maximal Flows and

Minimal Cuts, The Max Flow-Min Cut Theorem

Old Syllabus

 

Laboratory Work (45 Hrs)

The laboratory work consists of implementing the algorithms and concepts discussed in the class.

Student should write programs to demonstrate concepts listed below.

Unit 1 (10 Hr)

1. Programs to implement set operations union, intersection, difference, and Cartesian product

2. Programs to implement ceiling and floor functions

3. Programs to implement fuzzy set operations

Unit 2 (10 Hr)

1. Programs to implement Euclidean and Extended Euclidean algorithms

2. Programs to implement binary integer addition, multiplication, and division

3. Programs to implement Boolean matrix operations join, product, and Boolean product

4. Programs to perform operations with large integers by breaking down them into set of small

integers

Unit 3 (6 Hr)

1. Programs to generate truth tables of compound propositions

2. Programs to test validity of arguments by using truth tables

Unit 4 (2 Hr)

1. Programs to compute an, bn mod m, linear search etc by using recursion

Unit 5 (7 Hr)

1. Programs to generate permutations and combinations

2. Programs to implements some probabilistic and randomized algorithms

Unit 6 (10 Hr)

1. Programs for representing relations, testing its properties, and testing equivalence

2. Programs to represent graphs, finding shortest path, and generating minimum spanning trees