# Discrete Structure - Syllabus

Embark on a profound academic exploration as you delve into the Discrete Structure course () within the distinguished Tribhuvan university's CSIT department. Aligned with the 2065 Syllabus, this course (CSC-152) 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 Synopsis:**This course contains the fundamental concepts of logic, reasoning and algorithms.

**Goal:**After completing this course, the target student will gain knowledge in discrete mathematics and finite state automata in an algorithmic approach. It helps the target student in gaining fundamental and conceptual clarity in the area of Logic, Reasoning, Algorithms, Recurrence Relation, and Graph Theory.

#### Units

Proposition and Truth function, Propositional Logic, Expressing statements in Logic Propositional Logic, The predicate Logic, Validity, Informal Deduction in Predicate Logic, Rules of Inference and Proofs, Informal Proofs and Formal Proofs, Elementary Induction, Complete Induction, Methods of Tableaux, Consistency and Completeness of the System.

Finite State Automata

Sequential Circuits and Finite state Machine, Finite State Automata, Language and Grammars, Non-deterministic Finite State Automata, Language and Automata, Regular Expression.

Recurrence Relations

Recursive Definition of Sequences, Solution of Linear recurrence relations, Solution to Nonlinear Recurrence Relations, Application to Algorithm Analysis. Combinatory, Partial Order relation.

Graph Theory

Undirected and Directed Graphs, Walk Paths, Circuits, Components, Connectedness Algorithm, Shortest Path Algorithm, Bipartite Graphs, Planar Graphs, Regular Graphs, Planarity Testing Algorithms, Eulerian Graph, Hamiltonian Graph, Tree as a Directed Graph, Binary Tree, Spanning Tree, Cutsets and Cutvertices, Network Flows, Maxflow and Mincut Theorem, Data Structures Representing Trees and Graphs in Computer, Network Application of Trees and Graphs, Concept of Graph Coloring.