Course Content

Other Courses

Tribhuvan university CSIT 2065 Syllabus Discrete Structure

Discrete Structure - Syllabus

Course Overview and Structure
Syllabus Notes Old Questions Unit Wise Questions Question Bank

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

Key Topics

  • Proposition and Truth Function
    LO-1

    Introduction to propositions and truth functions, including the concept of a proposition and the rules of truth functions.

  • Propositional Logic
    LO-2

    Study of propositional logic, including the syntax and semantics of propositional logic, and how to express statements in propositional logic.

  • Expressing Statements in Logic
    LO-3

    Techniques for expressing statements in propositional logic, including how to translate English sentences into logical statements.

  • Predicate Logic
    LO-4

    Introduction to predicate logic, including the syntax and semantics of predicate logic, and how to express statements in predicate logic.

  • Validity
    LO-5

    Concept of validity in logic, including how to determine whether an argument is valid or invalid.

  • Informal Deduction in Predicate Logic
    LO-6

    Techniques for informal deduction in predicate logic, including how to use rules of inference to derive conclusions.

  • Rules of Inference and Proofs
    LO-7

    Study of rules of inference and proofs in logic, including how to construct and analyze proofs.

  • Informal Proofs and Formal Proofs
    LO-8

    Comparison of informal and formal proofs in logic, including the advantages and disadvantages of each approach.

  • Elementary Induction
    LO-9

    Introduction to elementary induction, including the principle of mathematical induction and how to apply it to prove statements.

  • Complete Induction
    LO-10

    Study of complete induction, including the principle of complete induction and how to apply it to prove statements.

  • Methods of Tableaux
    LO-11

    Introduction to methods of tableaux, including how to use tableaux to prove statements and construct models.

  • Consistency and Completeness of the System
    LO-12

    Study of the consistency and completeness of logical systems, including how to determine whether a system is consistent and complete.

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

Key Topics

  • Relational Database Design Using ER-to-Relational Mapping
    RE-1

    Learn how to design relational databases using ER-to-relational mapping, including mapping of regular entities, weak entities, relationship types, multivalued attributes, and N-ary relationships.

  • Informal Design Guidelines for Relational Schemas
    RE-2

    Understand informal design guidelines for relational schemas, including semantics of attributes in relations, redundant information in tuples and update anomalies, NULL values in tuples, and generation of spurious tuples.

  • Functional Dependencies
    RE-3

    Study functional dependencies, including definition, inference rules, Armstrong's axioms, attribute closure, equivalence of functional dependencies, and minimal sets of functional dependencies.

  • Normal Forms Based on Primary Keys
    RE-4

    Explore normal forms based on primary keys, including First Normal Form, Second Normal Form, Third Normal Form, and their general definitions.

  • Boyce-Codd Normal Form
    RE-5

    Learn about Boyce-Codd Normal Form, a higher normal form that ensures a relational schema is in a good structure.

  • Multivalued Dependency and Fourth Normal Form
    RE-6

    Understand multivalued dependency and Fourth Normal Form, which eliminates multivalued dependencies in a relational schema.

Key Topics

  • Predicting Positive and Negative Links
    GR-10

    This topic involves using machine learning and graph mining techniques to predict the formation of positive and negative links in a network, such as friendships and antagonisms.

  • Dijkstra's Algorithm
    GR-11

    Dijkstra's algorithm for finding shortest paths in a graph.

  • Undirected and Directed Graphs
    GR-01

    Introduction to undirected and directed graphs, including definitions and basic properties. Understanding the differences between these two types of graphs.

  • Walks, Paths, and Circuits
    GR-02

    Exploring walks, paths, and circuits in graphs, including definitions and examples. Understanding the relationships between these concepts.

  • Components and Connectedness
    GR-03

    Defining and identifying components in graphs, including connected and disconnected graphs. Understanding connectedness algorithms.

  • Shortest Path Algorithm
    GR-04

    Introduction to shortest path algorithms, including Dijkstra's algorithm and Bellman-Ford algorithm. Understanding how to find the shortest path between two nodes.

  • Bipartite Graphs
    GR-05

    Defining and identifying bipartite graphs, including their properties and applications. Understanding the differences between bipartite and non-bipartite graphs.

  • Planar Graphs
    GR-06

    Defining and identifying planar graphs, including their properties and applications. Understanding planarity testing algorithms.

  • Regular Graphs
    GR-07

    Defining and identifying regular graphs, including their properties and applications. Understanding the differences between regular and irregular graphs.

  • Eulerian and Hamiltonian Graphs
    GR-08

    Defining and identifying Eulerian and Hamiltonian graphs, including their properties and applications. Understanding the differences between these two types of graphs.

  • Trees and Binary Trees
    GR-09

    Defining and identifying trees and binary trees, including their properties and applications. Understanding the differences between trees and graphs.

  • Network Flows and Maxflow-Mincut Theorem
    GR-12

    Introduction to network flows, including the maxflow-mincut theorem. Understanding how to apply this theorem to solve network flow problems.

  • Data Structures for Trees and Graphs
    GR-13

    Exploring data structures used to represent trees and graphs in computer science, including adjacency matrices and adjacency lists.

  • Network Applications of Trees and Graphs
    GR-14

    Exploring the applications of trees and graphs in computer networks, including network topology and communication protocols.

  • Graph Coloring
    GR-15

    Introduction to graph coloring, including vertex coloring and edge coloring. Understanding the importance of graph coloring in computer science.