AU DOCS : GPA, CGPA, Attendance Calculators, Syllabus, Results, Notes, News & More

UNIT I - LOGIC AND PROOFS

Propositional logic – Propositional equivalences - Predicates and quantifiers – Nested quantifiers – Rules of inference - Introduction to proofs – Proof methods and strategy.

UNIT II - COMBINATORICS

Mathematical induction – Strong induction and well ordering – The basics of counting – The pigeonhole principle – Permutations and combinations – Recurrence relations – Solving linear recurrence relations – Generating functions – Inclusion and exclusion principle and its applications.

UNIT III - GRAPHS

Graphs and graph models – Graph terminology and special types of graphs – Matrix representation of graphs and graph isomorphism – Connectivity – Euler and Hamilton paths.

UNIT IV - ALGEBRAIC STRUCTURES

Algebraic systems – Semi groups and monoids - Groups – Subgroups – Homomorphism’s – Normal subgroup and cosets – Lagrange’s theorem – Definitions and examples of Rings and Fields.

UNIT V - LATTICES AND BOOLEAN ALGEBRA

Partial ordering – Posets – Lattices as posets – Properties of lattices - Lattices as algebraic systems – Sub lattices – Direct product and homomorphism – Some special lattices – Boolean algebra – Sub Boolean Algebra – Boolean Homomorphism.

UNIT I - COMBINATIONAL LOGIC

Combinational Circuits – Karnaugh Map - Analysis and Design Procedures – Binary Adder – Subtractor – Decimal Adder - Magnitude Comparator – Decoder – Encoder – Multiplexers - Demultiplexers.

UNIT II - SYNCHRONOUS SEQUENTIAL LOGIC

Introduction to Sequential Circuits – Flip-Flops – operation and excitation tables, Triggering of FF, Analysis and design of clocked sequential circuits – Design – Moore/Mealy models, state minimization, state assignment, circuit implementation - Registers – Counters.

UNIT III - COMPUTER FUNDAMENTALS

Functional Units of a Digital Computer: Von Neumann Architecture – Operation and Operands of Computer Hardware Instruction – Instruction Set Architecture (ISA): Memory Location, Address and Operation – Instruction and Instruction Sequencing – Addressing Modes, Encoding of Machine Instruction – Interaction between Assembly and High Level Language.

UNIT IV - PROCESSOR

Instruction Execution – Building a Data Path – Designing a Control Unit – Hardwired Control, Microprogrammed Control – Pipelining – Data Hazard – Control Hazards.

UNIT V - MEMORY AND I/O

Memory Concepts and Hierarchy – Memory Management – Cache Memories: Mapping and Replacement Techniques – Virtual Memory – DMA – I/O – Accessing I/O: Parallel and Serial Interface – Interrupt I/O – Interconnection Standards: USB, SATA.

UNIT I - CONCEPTUAL DATA MODELING

Database environment – Database system development lifecycle – Requirements collection – Database design -- Entity-Relationship model – Enhanced-ER model – UML class diagrams

UNIT II- RELATIONAL MODEL AND SQL

Relational model concepts -- Integrity constraints -- SQL Data manipulation – SQL Data definition – Views -- SQL programming

UNIT III - RELATIONAL DATABASE DESIGN AND NORMALIZATION

ER and EER-to-Relational mapping – Update anomalies – Functional dependencies – Inference rules – Minimal cover – Properties of relational decomposition – Normalization (upto BCNF)

UNIT IV - TRANSACTION MANAGEMENT

Transaction concepts – properties – Schedules – Serializability – Concurrency Control – Two-phase locking techniques

UNIT V - OBJECT RELATIONAL AND NO-SQL DATABASES

Mapping EER to ODB schema – Object identifier – reference types – rowtypes – UDTs – Subtypes and supertypes – user-defined routines – Collection types – Object Query Language; No-SQL: CAP theorem – Document-based: MongoDB data model and CRUD operations; Column-based: Hbase data model and CRUD operations

UNIT I - INTRODUCTION

Notion of an Algorithm – Fundamentals of Algorithmic Problem Solving – Important Problem Types –Fundamentals of the Analysis of Algorithm Efficiency – Analysis Framework - Asymptotic Notations and their properties – Empirical analysis - Mathematical analysis of Recursive and Non-recursive algorithms – Visualization

UNIT II - BRUTE FORCE AND DIVIDE AND CONQUER

Brute Force – String Matching - Exhaustive Search - Traveling Salesman Problem - Knapsack Problem - Assignment problem. Divide and Conquer Methodology – Multiplication of Large Integers and Strassen’s Matrix Multiplication – Closest-Pair and Convex - Hull Problems. Decrease and Conquer: - Topological Sorting – Transform and Conquer: Presorting – Heaps and Heap Sort

UNIT III - DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE

Dynamic programming – Principle of optimality - Coin changing problem – Warshall’s and Floyd‘s algorithms – Optimal Binary Search Trees - Multi stage graph - Knapsack Problem and Memory functions. Greedy Technique – Dijkstra’s algorithm - Huffman Trees and codes - 0/1 Knapsack problem

UNIT IV - ITERATIVE IMPROVEMENT

The Simplex Method-The Maximum-Flow Problem – Maximum Matching in Bipartite Graphs- The Stable marriage Problem

UNIT V - LIMITATIONS OF ALGORITHM POWER

Lower - Bound Arguments - P, NP, NP- Complete and NP Hard Problems. Backtracking – N-Queen problem - Hamiltonian Circuit Problem – Subset Sum Problem. Branch and Bound – LIFO Search and FIFO search - Assignment problem – Knapsack Problem – Traveling Salesman Problem - Approximation Algorithms for NP-Hard Problems – Traveling Salesman problem – Knapsack problem

UNIT I - EXPLORATORY DATA ANALYSIS

EDA fundamentals – Understanding data science – Significance of EDA – Making sense of data – Comparing EDA with classical and Bayesian analysis – Software tools for EDA - Visual Aids for EDA- Data transformation techniques-merging database, reshaping and pivoting, Transformation techniques - Grouping Datasets - data aggregation – Pivot tables and cross-tabulations

UNIT II - VISUALIZING USING MATPLOTLIB

Importing Matplotlib – Simple line plots – Simple scatter plots – visualizing errors – density and contour plots – Histograms – legends – colors – subplots – text and annotation – customization – three dimensional plotting - Geographic Data with Basemap - Visualization with Seaborn

UNIT III - UNIVARIATE ANALYSIS

Introduction to Single variable: Distributions and Variables - Numerical Summaries of Level and Spread - Scaling and Standardizing – Inequality - Smoothing Time Series

UNIT IV - BIVARIATE ANALYSIS

Relationships between Two Variables - Percentage Tables - Analyzing Contingency Tables - Handling Several Batches - Scatterplots and Resistant Lines – Transformations

UNIT V - MULTIVARIATE AND TIME SERIES ANALYSIS

Introducing a Third Variable - Causal Explanations - Three-Variable Contingency Tables and Beyond - Longitudinal Data – Fundamentals of TSA – Characteristics of time series data – Data Cleaning – Time-based indexing – Visualizing – Grouping – Resampling

UNIT I - INTELLIGENT AGENTS

Introduction to AI – Agents and Environments – concept of rationality – nature of environments – structure of agents. Problem solving agents – search algorithms – uninformed search strategies

UNIT II - PROBLEM SOLVING

Heuristic search strategies – heuristic functions. Local search and optimization problems – local search in continuous space – search with non-deterministic actions – search in partially observable environments – online search agents and unknown environments

UNIT III - GAME PLAYING AND CSP

Game theory – optimal decisions in games – alpha-beta search – monte-carlo tree search – stochastic games – partially observable games. Constraint satisfaction problems – constraint propagation – backtracking search for CSP – local search for CSP – structure of CSP

UNIT IV - LOGICAL REASONING

Knowledge-based agents – propositional logic – propositional theorem proving – propositional model checking – agents based on propositional logic. First-order logic – syntax and semantics – knowledge representation and engineering – inferences in first-order logic – forward chaining – backward chaining – resolution

UNIT V - PROBABILISTIC REASONING

Acting under uncertainty – Bayesian inference – naïve Bayes models. Probabilistic reasoning – Bayesian networks – exact inference in BN – approximate inference in BN – causal networks

AIDS Sem-3

MA3354-DISCRETE MATHEMATICS