Discrete Structure

Data Set +  Remedial Assignment for Short Attendance + First Internal + Task 2 

Covid-19 : Refer following OER and materials to boost your studies:

• https://nptel.ac.in/courses/106/106/106106183/

• https://nptel.ac.in/courses/106106094/

• https://www.khanacademy.org/math/statistics-probability/probability-library/basic-set-ops/v/intersection-and-union-of-sets  (Prerequisite) 

The IT2017 task group recommends that a robust information technology program should have at least discrete structures (mathematics) and a variety of other mathematical experiences to prepare a competent IT professional for the mid-2020s. Institutions offering programs in information technology must ensure that students entering the program have the necessary mathematical prerequisites to engage in university-level mathematics courses.

Prerequisites vary by region; however, they should include pre-calculus, usually taught in secondary schools or in preparatory programs.

As with the IT domains, we partition the mathematics curriculum of an IT degree program into essential and supplemental domains. Table 6.3 depicts a single essential domain with its accompanying sub-domains.

Table 6.3: Related IT essential mathematics

IT Essential Mathematics and Levels of Student Engagement

•  ITM-DSC Discrete Structures

•  ITM-DSC-01 Perspectives and impact 

•  ITM-DSC-02 Sets 

•  ITM-DSC-03 Functions and relations 

•  ITM-DSC-04 Proof techniques 

•  ITM-DSC-05 Logic 

•  ITM-DSC-06 Boolean algebra principles 

•  ITM-DSC-07 Minimization 

•  ITM-DSC-08 Graphs and trees 

•  ITM-DSC-09 Combinatorics 

•  ITM-DSC-10 Iteration and recursion 

•  ITM-DSC-11 Complexity Analysis 

•  ITM-DSC-12 Discrete information technology applications

The supplemental domains of the mathematics curriculum of an IT degree program consist of selected subjects from college-level mathematics appropriate for the IT discipline. These include but not limited to the following.

•  Probability

• Statistics

• Financial modeling

• Data analytics

• Linear algebra

• Calculus

Programs should seek to include as much appropriate mathematics as possible to reflect the goals and the needs of their constituents, so their graduates can achieve success in the workplace or in graduate studies.

 The IT2017 task group recommends that IT students must achieve the IT essential mathematics domain competencies in addition to the supplemental mathematics. The IT2017 task group also recommends that the mathematics should be at least 10% of a baccalaureate IT degree program to prepare a competent and competitive IT graduate.

Another reference : https://ccecc.acm.org/files/publications/CSTransfer2017.pdf  pp.17

Furthermore, computer science programs must provide students with a level of “mathematical maturity.” Lower division, undergraduate computer science programs need enough

mathematical maturity to have the basis on which to build CS-specific mathematics. The concepts established in a course on Discrete Structures are foundational material for computer science, and for that reason such coursework must be completed early in the program of study.

The transfer guidelines include an entire Knowledge Area on Discrete Structures estimated at 40 professor/student contact hours to cover the 34 recommended learning outcomes. The typical pre-requisite for a discrete structures course is pre-calculus; and a typical discrete

structures course includes requisite concepts in set theory, induction, recursion, logic, graph theory, and combinatorics, and uses the notion of formal mathematical proof as a unifying theme. These concepts are critical to the study of algorithms and data structures. The recommended Discrete Structures course can be taught very successfully by computer science faculty with appropriate qualifications; in this manner, the content can be presented from the computing perspective, with examples and assessment activities tailored to that perspective as

well. Concepts in discrete structures also serve as underpinnings for advanced computer science topics. For example, an ability to create and understand a formal proof is essential in

formal specification, in verification, and in cryptography; professionals use graph theory concepts in networks, operating systems, and compilers and set theory concepts in software engineering and in databases. The theoretical concepts of calculus not only help provide mathematical maturity, but also are required for studying the efficiency of algorithms, typically measured by Big-O notation. An introductory calculus course that includes the foundational concepts of limits, functions, and upper and lower bounds necessary for understanding asymptotic analysis will serve a computer science major well. Mathematics faculty typically teach this course, intended for engineering,science or mathematics majors. For computer science majors, the ability to think abstractly and

to generate software solutions of mathematical models for real-world scenarios is enhanced through the study of calculus. Because introductory calculus is a well-established, time-honored course, the transfer guidelines do not include learning outcomes for the application of calculus to computer science.

Other types of mathematics courses may also be appropriate for undergraduate computer science majors. With the preponderance of algorithms for big data analytics, data visualization, and machine learning, lower division, undergraduate courses in linear algebra as well as probability and statistics will serve a computer science major well for emerging and unforeseen careers. This curricular guidance does not include student learning outcomes for these mathematics courses

Reference:- A Report in the Computing Curricula Series,Task Group on Information Technology Curricula,Association for Computing Machinery (ACM),IEEE Computer Society (IEEE-CS),2017 December 10.

IC 402 A: Discrete Structures

This course will introduce the student to a body of mathematical concepts essential for the proficiency in some of the higher-level computer science courses.

Topics include:Set theory, Functions and relations, Propositional and predicate logic, Proof techniques, Recursive Algorithms, Elementary combinatorics and Counting methods, Graph theory, and Discrete probability.

Prerequisites: None

Credits: 4

Lecture Hours: 40

Lab Hours: 0

Course Outcomes:

CO1: The principle objective of this course is mathematical concepts that underline much of computer science, and to help them develop the skills to solve problems using them, whether they are in a more advance course, doing research.

CO2: Enhance mathematical reasoning of students.

CO3: Understand Discrete Mathematics such as sets, permutations, relations, graphs, trees and finite-state machines.

CO4: Enhance algorithmic thinking of students.

UNIT II

Relations: Introduction to relations, Pictorial representation of relations, Domain and range,Types of relations, n-ary relations, Composition of relations, Equivalence relations, Partially ordered relations.

Functions: Introduction to functions, functions in terms of ordered pairs, Pictorial representation of functions, Types of functions: surjective, bijective, injective etc., Composition of relations, Recurrence relations with applications to algorithm analysis

UNIT IV

Graph Theory-I: Definition and applications, Finite and infinite graphs, Incidence and degree, Isolated vertex, Pendent vertex, Types of graph, Subgraphs and isomorphic graph, Operations of graph, Paths, Cycles and connectivity, Eulerian and Hamiltonian graph, Planar graphs, Trees,

Properties of trees, pendant vertices in a tree, distance and center, rooted and binary trees, spanning trees, fundamental circuits.

Assignment –IC402 A

DS-01.

a)      Explain with examples the basic terminology of functions, relations, and sets.

b)      Identify the defining features of functions, relations and sets.

c)       Use function, relations and set terminology in a correct and meaningful way.

DS-02. 

a)      Perform the operations associated with sets, functions  and relations.

b)      Describe the operations associated with sets, functions, and relations.

c)       Compare the operations of sets functions, and relations.

DS-03. 

a)      Compare practical examples to the appropriate set, function, or relation model, and interpret the associated operations and terminology in context.

b)      Implement a solution to a programming problem using a specific set, function, or relation model.

c)       Justify the choice of a specific set, function, or relation model.

DS-04. 

a)      Convert logical statements from informal language to propositional and predicate logic expressions.

b)      Recognize the relationship between logical statements from informal language and propositional and predicate logic expressions.

c)       Produce propositional and predicate logic expressions from a given logical statement from an informal language.

DS-05. 

a)      Apply formal logic proofs and/or informal, but rigorous, logical reasoning to real

b)      problems such as predicting the behaviour of software or solving problems such as puzzles.

c)       Describe the steps in formal logic proofs and/or informal logical reasoning to solve real problems.

d)      Compare different logic proofs and informal logical reasoning to determine correct methods to solve real problems.

DS-06. 

a)      Use the rules of inference to construct proofs in propositional and predicate logic.

b)      Discuss the rules of inference to construct proofs in propositional and predicate logic.

c)       Analyze the rules of inference to construct proofs in propositional and predicate logic.

DS-07. 

a)      Describe how symbolic logic can be used to model real- life situations or computer applications.

b)      List ways that symbolic logic can be used to model real-life  situations or computer applications.

c)       Use symbolic logic to model real-life situations or computer applications.

DS-08. 

a)      Apply formal methods of symbolic propositional and predicate logic, such as calculating validity of formulae and computing normal forms.

b)      Demonstrate formal methods of symbolic propositional and predicate logic.

c)       Distinguish between formal methods of propositional and predicate logic to determine the most effective solutions to a given problem.

DS-09. 

a)      Describe the strengths and limitations of propositional and predicate logic.

b)      List the strengths and limitations of propositional and predicate logic.

c)       Illustrate the strengths and limitations of propositional and predicate logic.

DS-10. 

a)      Outline the basic structure of each proof technique, including direct proof, proof by contradiction, and induction.

b)      Use the basic structure of each proof technique to solve a problem.

c)       Choose the most effective proof technique to solve a problem.

DS-11. 

a)      Apply each of the proof techniques (direct proof, proof by contradiction, and induction) correctly in the construction of a sound argument.

b)      Demonstrate each of the proof techniques by correctly constructing a sound argument.

c)       Use each of the proof techniques correctly in the construction of a sound argument.

DS-12. 

a)      Deduce the best type of proof for a given problem.

b)      Compare the different proof methods.

c)       Construct a correct proof using the best method for a given problem.

DS-13.

a)      Explain the parallels between ideas of mathematical and/or structural induction to recursion and recursively defined structures.

b)      Identify the parallels between ideas of mathematical and/or structural induction to recursion and recursively defined structures.

c)       Illustrate the parallels between ideas of mathematical and/or structural induction to recursion and recursively defined structures.

DS-14. 

a)      Explain the relationship between weak and strong induction and give examples of the appropriate use of each.

b)      Identify the relationship between weak and strong induction.

c)       Solve problems using both weak and strong induction.

DS-15. 

a)      Solve a variety of basic recurrence relations.

b)      Demonstrate a variety of basic recurrence relations.

c)       Compare a variety of basic recurrence relations.

DS-16. 

a)      Analyze a problem to determine underlying recurrence relations.

b)      Carry out a problem with an underlying recurrence relation.

c)       Evaluate a problem with an underlying recurrence relation.

DS-17. 

a)      Illustrate the basic terminology of graph theory including properties and special cases for each type of graph/tree.

b)      Describe the basic terminology of graph theory.

c)       Outline the basic terminology of graph theory.

DS-18. 

a)      Demonstrate different traversal methods for trees and graphs, including pre-, post-, and in-order traversal of trees.

b)      List the different traversal methods for trees and graphs.

c)       Execute different traversal methods for trees and graphs.

DS-19. 

a)      Solve a variety of real-world problems in computer science using appropriate forms of graphs and trees, such as representing a network topology or the organization of a hierarchical file system.

b)      Discuss a variety of real-world problems in computer science using appropriate forms of graphs and trees.

c)       Distinguish between real-world problems solvable by using graphs and trees.

DS-20. 

a)      Implement and use balanced trees and B-trees.

b)      Explain balanced trees and B-trees.

c)       Analyze the use of balanced trees and B-trees.

DS-21.

a)      Implement graph algorithms.

b)      Classify graph algorithms.

c)       Implement  graph search, spanning trees, and shortest paths algorithms.

d)      Categorize different implementations of graph algorithms.

DS-22.

a)      Demonstrate how concepts from graphs and trees appear in data structures, algorithms, proof techniques (structural induction), and counting.

b)      Identify how concepts from graphs and trees appear in data structures, algorithms, proof techniques, and counting.

c)       Implement data structures, algorithms, proof techniques, and counting using graphs and trees.

DS-23.

a)      Describe binary search trees and AVL trees.

b)      Define and apply binary search and AVL trees.

DS-24. 

a)      Explain complexity in the ideal and in the worst-case scenario for both implementations.

b)      State complexity in the ideal and in the worst-case scenario for both implementations.

c)       Explain and calculate complexity in the ideal and in the worst-case scenario for both implementations.

 DS-25. 

a.       Perform computations involving modular arithmetic.

b.      Discuss computations involving modular arithmetic.

c.       Examine computations involving modular arithmetic.