|
Chapters / Units
|
Teaching Methodology
|
Teaching
Hours
|
|
Unit I: Basic
Foundations
1.1. Review of Set Theory, Logic,
Functions, Proofs
1.2. Automata,
Computability and Complexity: Complexity Theory, Computability Theory,
Automata Theory
1.3. Basic
concepts of Automata Theory: Alphabets, Power of Alphabet, Kleen Closure
Alphabet, Positive Closure of Alphabet, Strings, Empty String, Suffix, Prefix
and Substring of a string, Concatenation of strings, Languages, Empty
Language, Membership in Language
|
Class Lecture
|
3 Hours
|
|
|
|
|
|
Unit II: Introduction
to Finite Automata
2.1. Introduction
to Finite Automata, Introduction of
Finite State Machine
2.2. Deterministic
Finite Automata (DFA), Notations for DFA, Language of DFA, Extended
Transition
Function of DFA Non-Deterministic Finite Automaton (NFA), Notations for NFA,
Language of NFA, Extended Transition
2.3. Equivalence
of DFA and NFA, Subset-
Construction
|
Class Lecture
+
Lab Session
|
8 Hours
|
|
2.4. Method
for reduction of NFA to DFA, Theorems for equivalence of Language accepted by
DFA and NFA: For any NFA, N = (QN, ∑, N,
q0, FN) accepting language L ∑* there is a DFA D =
(QD, ∑, D,
q0’,FD) that also accepts L i.e. L (N) = L (D), A
language L is accepted by some NFA if L is accepted by some DFA.
2.5. Finite
Automaton with Epsilon Transition (ε - NFA), Notations for ε - NFA,
Epsilon Closure of a State, Extended Transition Function of ε – NFA,
Removing Epsilon Transition using the concept of Epsilon Closure, Equivalence
of NFA and ε –NFA, Equivalence of DFA and ε – NFA
2.6. Finite State
Machines with output: Moore Machine and Mealy Machines, Illustration of the
Moore and Mealy Machines
|
|
|
|
|
|
|
|
Unit III: Regular
Expressions
3.1. Regular
Expressions, Operators of Regular Expressions (Union, Concatenation, Kleen),
Regular Languages and their applications,
Algebraic Rules for Regular Expressions
3.2. Equivalence of Regular
Expression and Finite Automata, Reduction of Regular Expression to
ε–NFA, Conversion of DFA to Regular
Expression, Arden’s Theorem
3.3. Properties of
Regular Languages, Pumping Lemma for regular expression, Application of
Pumping
Lemma, Closure Properties of Regular Languages over (Union, Intersection ,
Complement), Minimization of Finite State
Machines: Table Filling Algorithm
|
Class Lecture
+
Lab Session
|
6 Hours
|
|
|
|
|
|
Unit IV: Context Free
Grammar
4.1. Introduction
to Context Free Grammar (CFG), Components of CFG, Use of CFG, Context Free
Language (CFL)
4.2. Types of derivations:
Bottomup and Topdown approach, Leftmost and Rightmost, Sentential Form (Left,
Right), Language of a grammar
4.3. Parse
tree and its construction, Ambiguous
|
Class Lecture
+
Lab Session
|
9 hours
|
|
grammar, Use of parse tree to show ambiguity in grammar,
Inherent Ambiguity
4.4. Regular Grammars: Right
Linear and Left Linear, Equivalence of regular grammar and finite automata
4.5. Simplification
of CFG: Removal of Useless symbols, Nullable Symbols, and Unit Productions,
Chomsky Normal Form (CNF), Greibach Normal Form (GNF), Backus-Naur
Form (BNF)
4.6. Context
Sensitive Grammar, Chomsky
Hierarchy(Type
0, 1, 2, 3) , Pumping Lemma for CFL, Application of Pumping Lemma, Closure
Properties of CFL
|
|
|
|
|
|
|
|
Unit V: Push Down
Automata
5.1. Introduction
to Push Down Automata (PDA), Representation of PDA, Operations of PDA, Move
of a PDA, Instantaneous Description for
PDA
5.2. Deterministic
PDA, Non Deterministic PDA,
Acceptance of strings by PDA, Language of PDA
5.3. Construction of PDA by Final
State , Construction of PDA by Empty Stack, Conversion of PDA by Final State
to PDA accepting by Empty Stack and vice-versa, Conversion of CFG to PDA,
Conversion of PDA to CFG
|
Class Lecture
+
Lab Session
|
7 Hours
|
|
|
|
|
|
Unit VI: Turing
Machines
6.1. Introduction
to Turing Machines (TM), Notations of Turing Machine, Language of a Turing
Machine, Instantaneous Description for Turing Machine, Acceptance of a string
by a
Turing Machines
6.2. Turing Machine as a Language
Recognizer, Turing Machine as a Computing Function, Turing Machine with
Storage in its State, Turing Machine as a enumerator of stings of a language,
Turing Machine as Subroutine
|
Class Lecture
+
Lab Session
|
10 Hours
|
|
6.3.
Turing Machine with Multiple Tracks, Turing
Machine
with Multiple Tapes, Equivalence of Multitape-TM and Multitrack-TM,
NonDeterministic Turing Machines, Restricted Turing Machines: With
Semi-infinite Tape,
Multistack Machines, Counter Machines
6.4. Curch Turing
Thesis, Universal Turing Machine, Turing Machine and Computers, Encoding of
Turing Machine, Enumerating Binary Strings, Codes of Turing Machine,
Universal Turing
Machine for encoding of
Turing Machine
|
|
|
|
|
|
|
|
Unit VII:
Undecidability and Intractability
7.1. Computational
Complexity, Time and Space complexity of a Turing Machine, Intractability
7.2. Complexity Classes, Problem
and its types: Absract, Decision, Optimization
7.3. Reducibility, Turing
Reducible, Circuit Satisfiability, Cooks Theorem
7.4. Undecidability,
Undecidable Problems: Post’s Correspondence Problem, Halting Problem and its
proof, Undecidable Problem about Turing Machines
|
Class Lecture
+
Lab Session
|
5 Hours
|
|
|
|
|
|
Unit
|
Contents
|
Hour
|
|
1.
Introduction to
Computer
Network
[6 Hour]
|
1.1.
Definitions, Uses, Benefits
1.2. Overview of Network
Topologies Mesh, Star, Tree, Bus
1.3. Overview of Network Types LAN, PAN, CAN,
MAN, WAN
|
1
|
|
1.4.
Networking Types
P2P, Multipoint, Client/Server
1.5.
Overview of Protocols and Standards
Protocols: Syntax, semantics, timing;
Standards: De facto, De jure; Standards Organizations
|
1.5
|
|
|
1.6.
OSI Reference Model
1.7. TCP/IP Model and its comparison with OSI
|
2.5
|
|
|
1.8.
Connectionless and Connection-Oriented Network
Services
Basic working Mechanism
1.9.
Internet, ISPs, Backbone Network Overview
Basic concept of Internet and ISPs, Bus
backbone, Star backbone, connecting remote LANs
|
1
|
|
|
2. Physical Layer and Network
Media
[4 Hour]
|
2.1.
Network Devices
Repeater, Hub, Switch, Bridge,
Router
2.2.
Different types of transmission medias
Wired: twisted pair, coaxial,
fiber optic, Wireless: Radio waves, micro waves, infrared
2.3. Ethernet Cable Standards UTP, Fiber cable
standards
|
1.5
|
|
2.4. Circuit, Message & Packet Switching
|
2
|
|
|
2.5.
ISDN
Interface and Standards
|
0.5
|
|
|
3. Data Link Layer
[8 Hour]
|
3.1.
Function of Data Link Layer (DLL)
3.2. Overview of Logical Link
Control (LLC) and Media Access Control (MAC)
3.3.
Framing and Flow Control Mechanisms
Stop-and-wait ARQ,
Piggybacking, Go-Back-N ARQ, Selective Repeat ARQ
|
3
|
|
|
3.4.
Error Detection and Correction techniques
Parity checks, Cheksumming Methods,
CRC, Hamming code
3.5.
Channel Allocation Techniques
ALOHA, Slotted ALOHA, CSMA,
CSMACD,CSMA/CA
3.6.
Ethernet Standards
802.3 CSMA/CD, 802.4 Token
Bus, 802.5 Token Ring
|
3
|
|
3.7.
Wireless LAN
Spread Spectrum, Bluetooth, Wi-Fi
3.8.
Overview Virtual Circuit Switching, Frame Relay &
ATM
3.9.
DLL Protocol
HDLC, PPP
|
2
|
|
|
4. Network Layer
[10 Hour]
|
4.1.
Introduction and Functions
4.2.
IPv4 Addressing
4.3.
Class-full and Classless Addressing
4.4.
IPv4 Sub-netting/ Super-netting
4.5.
IPv6 Addressing and its Features
4.6.
IPv4 and IPv6 Datagram Formats
4.7.
Comparison of IPv4 and IPv6 Addressing
4.8.
NATing
4.9.
Example Addresses
Unicast, Multicast and
Broadcast
|
4
|
|
4.10.
Routing
4.10.1.
Introduction and Definition
4.10.2.
Types of Routing
Static vs Dynamic, Unicast vs Multicast, Link
State vs Distance Vector,
Interior vs Exterior
4.10.3. Path Computation Algorithms Bellman
Ford, Dijkstra’s
4.10.4.
Routing Protocols
RIP, OSPF & BGP
|
4
|
|
|
4.11. Overview
of IPv4 to IPv6 Transition Mechanisms
4.12.
Overview of ICMP/ICMPv6
4.13.
Overview of Network Traffic Analysis
4.14.
Security Concepts
Firewall & Router Access
Control
|
2
|
|
|
5. Transport Layer
[6 Hour]
|
5.1.
Introduction, Functions and Services 5.2. Transport Protocols
TCP, UDP and Their Comparisons
5.3.
Connection Oriented and Connectionless Services
|
1
|
|
5.4.
Congestion Control
Open Loop & Closed Loop, TCP
Congestion Control
5.5.
Traffic Shaping Algorithms
5.6.
Techniques to improve QOS
Scheduling, traffic shaping, resource
reservation, admission control
|
2.5
|
|
|
|
5.7.
Queuing Techniques for Scheduling
5.8. Introduction
to Ports and Sockets, Socket Programming
Socket programming with UDP
and TCP (e.g. client Server Application)
|
2.5
|
|
6. Application
Layer
[7 Hour]
|
6.1.
Introduction and Functions
6.2.
Web & HTTP
Overview of HTTP, Non-Persistent and Persistent
Connections, HTTP Message Format
|
2
|
|
6.3.
DNS and the Query Types
Services provided by DNS, Overview
of how DNS works,
DNS records and messages
6.4.
File Transfer and Email Protocols
FTP, SFTP, SMTP, IMAP, POP3
|
3
|
|
|
6.5. Overview of Application
Server Concepts Proxy, Web, Mail
6.6. Network Management SNMP
and Transport mapping
|
2
|
|
|
7. Multimedia & Future
Networking
[4 Hour]
|
7.1. Overview Multimedia Streaming Protocols SCTP
|
1
|
|
7.2. Overview of SDN and its
Features, Data and Control Plane
|
1
|
|
|
7.3. Overview of NFV
|
1
|
|
|
7.4. Overview of NGN
|
1
|
|
S.N.
|
Contents
|
|
1.
|
Understanding of Network
equipment, wiring in details
|
|
2.
|
Practice on basic Networking
commands (ifconfig/ipconfig, tcpdump, netstat, dnsip, hostname, route)
|
|
3.
|
Overview of IP Addressing and
sub-netting, static ip setting on Linux/windows machine, testing
|
|
4.
|
Introduction to Packet Tracer,
creating of a LAN and connectivity test in the LAN, creation of VLAN and VLAN
trunking.
|
|
5.
|
Basic Router Configuration,
Static Routing Implementation
|
|
6.
|
Implementation of
Dynamic/interior/exterior routing (RIP, OSPF, BGP)
|
|
7.
|
Firewall Implementation, Router
Access Control List (ACL)
|
|
8.
|
Packet capture and header
analysis by wire-shark (TCP,UDP,IP)
|
|
9.
|
Basic concept of DNS, Web, FTP
(shall use packet tracer, GNS3)
|
|
Unit
|
Teaching Hour
|
References
|
|
Unit
1: Operating System Overview (4)
|
|
|
|
1.1 Introduction: Definition, Two views of
operating system, Evolution/History of operating system, Types of OS (Mainframe,
Server, Multiprocessor, PC, Real-Time, Embedded, Smart Card Operating Systems),
Operating System Structures
1.2 System Calls: Definition, Handling System
Calls, System calls for Process, File, and Directory Management,
System Programs, The Shell, Open Source Operating Systems
|
2 Hour
2 Hour
|
|
|
Unit
2: Process Management (10)
|
|
|
|
2.1 Introduction: Process vs Program,
Multiprogramming, Process Model, Process States, Process Control Block/Process
Table.
2.2 Threads: Definition, Thread vs Process, Thread
Usage, User and Kernel Space Threads.
2.3 Inter Process Communication: Definition Race Condition,
Critical Section
2.4 Implementing
Mutual Exclusion:
Mutual
Exclusion
with Busy Waiting (Disabling Interrupts, Lock Variables, Strict Alteration,
Peterson’s Solution, Test and Set Lock), Sleep and Wakeup, Semaphore,
Monitors, Message Passing
2.5 Classical
IPC problems:
Producer
Consumer,
Sleeping Barber, and Dining Philosopher Problem
2.6 Process Scheduling: Goals, Batch System Scheduling
(First-Come First-Served,
Shortest
Job First, Shortest Remaining Time Next), Interactive System Scheduling
(Round-Robin Scheduling, Priority Scheduling, Multiple Queues), Overview of
Real Time System Scheduling (No need to discuss any real time system
scheduling algorithm)
|
1 Hour
1 Hour
1 Hour
3 Hour
1 Hour
3 Hour
|
|
|
Unit
3: Process Deadlocks (6)
|
||
|
3.1
Introduction: Definition, Deadlock
Characterization, Preemptable and NonPreemptable Resources, Resource–
|
1.5 Hour
|
|
|
Allocation Graph, Necessary
Conditions for
Deadlock
|
|
|
|
3.2 Handling Deadlocks: Ostrich Algorithm, Deadlock
prevention, Safe and Unsafe States, Deadlock Avoidance (Bankers
algorithm for Single and Multiple Resource Instances), ,
Deadlock
Detection (For Single and Multiple Resource Instances), Recovery From
Deadlock (Through Preemption and
Rollback)
|
4.5 Hour
|
|
|
Unit
4: Memory
Management (8)
|
||
|
4.1 Introduction: Monoprogramming vs
Multiprogramming, Modelling Multiprogramming, Multiprogramming with fixed and
variable partitions, Relocation and Protection.
4.2 Space Management: Fragmentation and Compaction, Memory management (Bitmaps &
Linked-list), Memory Allocation
Strategies
4.3 Virtual Memory: Paging, Page Table, Page Table
Structure, Pages and Frames, Handling Page Faults, TLB’s
4.4 Page Replacement Algorithms: Hit Rate and
Miss Rate, Concept of Locality of Reference, FIFO, Belady’s Anomaly,
Second
Chance,
LRU, Optimal, LFU, Clock, WSClock.
4.5 Segmentation: Why Segmentation, Drawbacks
of Segmentation, Segmentation
|
1 Hour
1 Hour
2 Hour
3 Hour
1 Hour
|
|
|
with
Paging(MULTICS)
|
|
|
|
Unit
5: File Management (6)
|
|
|
|
5.1 File Overview: File Naming, File Structure,
File
Types, File Access, File Attributes, File Operations, Single Level, Two Level
and Hierarchical Directory Systems, File System Layout.
5.2 Implementing Files: Contiguous allocation, Linked
List Allocation, Linked List Allocation using Table in Memory/ File
Allocation Table, Inodes.
5.3 Directory: Directory Operations,
Path
Names, Directory Implementation,
Shared
Files
5.4 Free Space Management: Bitmaps, Linked
List
|
1 Hour
3 Hour
1 Hour
1 hour
|
|
|
Unit
6: Device Management (6)
|
||
|
6.1 Introduction: Classification of IO devices,
Controllers, Memory Mapped IO, DMA
Operation,
Interrupts
6.2 IO Handling: Goals of IO Software, Handling
IO(Programmed IO, Interrupt Driven IO, IO using DMA), IO Software
Layers (Interrupt Handlers, Device
Drivers)
6.3 Disk Management: Disk Structure, Disk Scheduling (FCFS,
SSTF, SCAN, CSCAN, LOOK, CLOOK), Disk Formatting (Cylinder
Skew, Interleaving, Error handling), RAID
|
1 Hour
2 Hour
3
Hour
|
|
|
Unit
7: Linux Case Study (5)
|
|
|
|
7.1 History, Kernel Modules, Process
|
5 Hour
|
|
|
Management,
Scheduling, Inter-process Communication, Memory Management, File System
Management Approaches, Device Management Approaches.
|
|
|
|
Process
|
Has
|
Max
|
|
P1
|
2
|
6
|
|
P2
|
1
|
5
|
|
P3
|
2
|
5
|
|
P4
|
2
|
6
|
|
Unit 1
|
Database and Database
Users
|
Teaching Hours (2)
|
|||
|
Introduction
|
Traditional file processing
system; Definition of database and database management system with example
|
1 hr
|
|||
|
Characteristics of the Database Approach
|
Self-describing
nature of a database system; Insulation between programs and data, and data
abstraction; Support of multiple views of the data; Sharing of data and
multiuser transaction processing
|
||||
|
Actors on the Scene
|
Database
administrators; Database designers; End users; System Analysts and
Application Programmers
|
||||
|
Workers behind the
Scene
|
DBMS system designers and implementers; Tool developers;
Operators and maintenance personnel
|
1 hr
|
|||
|
Advantages of Using the DBMS Approach
|
Controlling
redundancy; Restricting unauthorized access; Providing persistent storage;
Providing storage structures and search techniques for efficient query
processing; Providing backup and recovery; providing multiple user
interfaces; Enforcing integrity constraints; Reduced application development
time; Flexibility; Availability of upto-date information; Economies of scale
|
||||
|
Unit 2
|
Database
System – Concepts and Architecture
|
Teaching Hours (3)
|
|||
|
Data Models, Schemas,
and Instances
|
Definition
of data abstraction and data model; Categories of data models (high level,
low level, and representational data models) – Introduction to
entity-relationship model, relational data model, network data model,
hierarchical model, network model, object data model, and self-describing
data models; Concept of schema and instance
|
1 hr
|
|||
|
Three-Schema
Architecture and Data Independence
|
Concept
of three-schema architecture; Logical and physical data independence
|
1 hr
|
|||
|
Database Languages
and Interfaces
|
Concept
of DDL, SDL, VDL, DML, procedural and non-procedural languages; Concept of
interfaces
|
||||
|
The Database Sys Environment
|
tem
|
Concept of database system environment
|
|||
|
Centralized
Client/Server
Architectures
DBMSs
|
and for
|
Basics of centralized and client/server
architectures
|
1 hr
|
||
|
Classification of Database
Management Systems
|
Classification
based on data models, number of users, number of sites, cost and type of
access path
|
||||
|
Unit 3
|
Data Modelling Using the
Entity-Relational Model
|
Teaching Hours (6)
|
|||
|
Using
High-Level Conceptual Data
Models for Database
Design
|
Concept of conceptual design
|
2 hrs
|
|||
|
Entity
Types, Entity Sets, Attributes, and Keys; Relationship Types, Relationship
Sets, Roles, and
Structural Constraints
|
Concept
of entity types, entity sets, attributes, and keys; Concept of relationship
types and relationship sets, roles and constraints
|
||||
|
Weak Entity Types
|
Concept of weak entity types and partial
keys
|
||||
|
ER
Diagrams, Naming Conventions, and
Design Issues
|
Drawing
ER diagrams using ER notations, naming conventions and design issues
|
2 hrs
|
|||
|
Relationship
Types of Degree Higher Than Two
|
Concept of higher degree relationships
|
||||
|
Subclasses,
Superclasses,
Inheritance
|
and
|
Concept of enhanced ER
(EER) model,
superclasses, subclasses and subclasses
|
2 hrs
|
||
|
Specialization Generalization
|
and
|
Concept of specialization and
generalization
|
|||
|
Constraints
Characteristics
Specialization
Generalization
|
and of and
|
Different
constraints and characteristics of specialization and generalization
|
|||
|
Unit 4
|
|
The Relational Data Model and Relational Database
Constraints
|
Teaching Hours (3)
|
||
|
Relational Concepts
|
Model
|
Concept of domain, attributes, tuples, and
relations; Characteristics of relations; Relational model notation
|
2 hrs
|
||
|
Relational
Constraints
Relational
|
Model and Database
|
Different
categories of constraints; Domain constraints; Key and NULL values
constraints;
|
|||
|
Schemas
|
Relational
databases and relational database schemas; Entity integrity, referential
integrity, and foreign key
|
|
|||
|
Update Operations, Transactions, and
Dealing
with Constraint
Violations
|
Concept
of insert, delete, and update operations; Concept of transactions
|
1 hr
|
|||
|
Unit 5
|
The
Relational Algebra and Relational Calculus
|
Teaching Hours (5)
|
|||
|
Unary Relational
Operations: SELECT and PROJECT
|
Concept
and example of SELECT and PROJECT operations; Sequences of operations; RENAME
operation
|
3 hrs
|
|||
|
Relational
Operations Theory
|
Algebra from Set
|
Concept
and example of UNION, INTERSECTION, MINUS, and CARTESIAN PRODUCT operations
|
|||
|
Binary Operations:
DIVISION
|
Relational
JOIN and
|
Concept
and example of JOIN operation and its variations; Concept and example of
DIVISION operation
|
|||
|
Additional Operations
|
Relational
|
Concept
of generalized projection, aggregate functions, OUTER JOIN operations, and
OUTER UNION operation
|
2 hrs
|
||
|
the Tuple
Calculus
|
Relational
|
Introduction to tuple relational calculus
with examples
|
|||
|
the Domain Calculus
|
Relational
|
Introduction to domain relational calculus
with examples
|
|||
|
Unit 6
|
|
SQL
|
Teaching Hours (8)
|
||
|
Data Definition and Data Types
|
CREATE
TABLE command; Attribute data types and domains; ALTER and DROP commands
|
1 hr
|
|||
|
Specifying Constraints
|
Attribute
constraints and attribute defaults; Key and referential integrity constraints
|
1 hr
|
|||
|
Basic Retrieval Queries
|
SELECT-FROM-WHERE
structure; Ambiguous attribute names, aliasing, renaming, and tuple
variables; Unspecified WHERE clause and use of asterisk (*); Pattern matching
and arithmetic operators
|
5 hrs
|
|||
|
Complex Retrieval
Queries
|
Comparisons involving NULL; Nested queries
|
||||
|
INSERT, DELETE, and UPDATE
Statements
|
Concept
and example of INSERT, DELETE, and UPDATE commands
|
1 hr
|
|||
|
Views
|
Concept of views; CREATE VIEW command
|
||||
|
Unit 7
|
Relational Database Design
|
Teaching Hours (7)
|
|||
|
Relational
Database
Design Using
ER-to-
Relational Mapping
|
Converting ER / EER models to relations
with examples
|
1 hr
|
|||
|
Informal
Design
Guidelines
for
Relational Schemas
|
Imparting
clear semantics to attributes in relations; Redundant information in tuples
and update anomalies; NULL values in tuples; Generation of
|
2 hrs
|
|||
|
|
spurious tuples
|
|
|||
|
Functional
Dependencies
|
Definition and concept of functional dependencies with
example
|
2 hrs
|
|||
|
Normal Forms Based on Primary Keys
|
Concept of normalization; Practical use of normal forms;
Keys and attributes participating in keys; Concept of first, second, and
third forms with example
|
||||
|
General
Definitions of
Second
and Third
Normal Forms
|
General definitions of
second and third normal forms
|
1 hr
|
|||
|
Boyce-Codd Normal
Form
|
Concept and example of
boyce-codd normal form
|
||||
|
Multivalued
Dependency
and Fourth
Normal Form
|
Definition and concept of multivalued dependencies with
example; Concept of fourth normal form
|
1 hr
|
|||
|
Properties of Relational Decomposition
|
Dependency preservation property and nonadditive (lossless)
join property
|
||||
|
Unit 8
|
Introduction to Transaction Processing Concepts and
Theory
|
Teaching Hours (4)
|
|||
|
Introduction to
Transaction Processing
|
Single-user
versus multiuser system; Transactions,
Database items, Read
and write operations, and DBMS buffers; Why do we need concurrency control?
Why do we need recovery?
|
1 hr
|
|||
|
Transaction
and System
Concepts
|
Transaction states and
operations; The system log; Commit point; Buffer replacement policies
|
1 hr
|
|||
|
Desirable Properties
of Transactions
|
Desirable properties
of transactions
|
||||
|
Characterizing
Schedules
Based on
Recoverability
|
Concept of schedule;
Characterizing schedules based on recoverability
|
2 hrs
|
|||
|
Characterizing
Schedules
Based on
Serializability
|
Conflict
serializability; Testing for conflict serializability; View equivalent and
view seializability; How serializability is used for concurrency control
|
||||
|
Unit 9
|
Concurrency Control Techniques
|
Teaching Hours (4)
|
|||
|
Two-Phase Locking
Technique
|
Concept of two-phase locking; Types of locks and system
lock tables; Lock conversion; Guaranteeing serializability by two-phase
locking; Basic,
conservative,
strict, and rigorous two-phase locking;
Dealing with deadlock
and starvation
|
2 hrs
|
|||
|
Timestamp Ordering
|
Timestamp
ordering concurrency control concept; Basic and strict timestamp ordering;
Thomas’s Write rule
|
2 hrs
|
|||
|
Multiversion
Concurrency Control
|
Concept
of multiversion concurrency control technique; Multiversion technique based
on timestamp ordering; Multiversion locking using certify locks
|
||||
|
Validation (Optimistic) Techniques
and Snapshot Isolation Concurrency
Control
|
Concept of validation (optimistic) techniques and snapshot
isolation concurrency control
|
||||
|
Unit 10
|
Database Recovery Techniques
|
Teaching Hours (3)
|
|||
|
Recovery Concepts
|
Recovery outline and
categorization of recovery algorithms; Caching (Buffering) of disk blocks;
Writeahead logging, steal/no-steal, and force/no-force; Checkpoints and fuzzy
checkpointing; Transaction rollback and cascading rollback
|
2 hrs
|
|||
|
NO-UNDO/REDO
Recovery Based on
Deferred Update
|
Concept of
no-undo/redo recovery based on deferred update
|
||||
|
Recovery
Technique Based on Immediate
Update
|
Concept of recovery technique based on
immediate update
|
||||
|
Shadow Paging
|
Concept of Shadow
Paging
|
1 hr
|
|||
|
Database
Backup and
Recovery
from
Catastrophic Failures
|
Concept of database backup and recovery from catastrophic
failures
|
||||
|
Chapters / Units
|
Teaching Methodology
|
Teaching
Hours
|
|
|
Unit I: Introduction
1.1. Intelligence,
Artificial Intelligence (AI), AI Perspectives: acting and thinking humanly,
acting and thinking rationally
1.2. History of AI
1.3. Foundations
of AI: Philosophy, Economics, Psycology, Sociology, Linguistics,
Neuroscience,
Mathmatics, Computer Science, Control Theory
1.4. Applications of AI
|
Class Lecture
|
3 Hours
|
|
|
|
|
|
|
|
Unit II: Intelligent
Agents
2.1. Introduction
of agents, Structure of Intelligent agent, Properties of Intelligent Agents
2.2. Configuration of Agents,
PEAS description of Agents, PAGE
2.3. Types of Agents: Simple
Reflexive, Model Based, Goal Based, Utility Based, Learning Agent
2.4. Environment
Types: Deterministic, Stochastic, Static, Dynamic, Observable,
Semi-observable,
Single Agent, Multi Agent
|
Class Lecture
+
Lab Session
|
4 Hours
|
|
|
Unit III: Problem
Solving by Searching
3.1. Definition,
State space representaion, Problem as a state space search, Problem
formulation, Welldefined problems
3.2. Solving Problems by
Searching, Search Strategies: Informed, Uninformed, Performance evaluation of
search strategies: Time Complexity, Space Complexity, Completeness,
Optimality
3.3. Uninformed
Search: Depth First Search, Breadth First Search, Depth Limited Search,
Iterative Deepening Search, Uniform Cost Search,
Bidirectional Search
3.4. Informed Search, Heuristic
Function, Admissible Heuristic, Informed Search Techniques: Greedy Best First
Search, A* Search, Optimality and Admissibility in A*, Hill Climbing Search,
Simulated Annealing Search
3.5. Game Playing, Adversarial
Search Techniques: Mini-max Search, Alpha-Beta Pruning
3.6. Constraint
Satisfaction Problems, Examples of Constraint Satisfaction Problems
|
Class Lecture
+
Lab Session
|
9 Hours
|
|
|
|
|
|
|
|
Unit IV: Knowledge
Representation
4.1. Definition
and importance of Knowledge, Issues in Knowledge Representation, Knowledge
Representation Systems, Properties of
Knowledge Representation Systems
4.2. Types of
Knowledge Representation Systems: Semantic Nets, Frames, Conceptual
Dependencies, Scripts,
Rule Based Systems (Production System), Propositional Logic, Predicate Logic
4.3. Propositional Logic(PL):
Syntax, Semantics, Formal logic-connectives, truth tables, tautology,
validity, well-formed-formula, Inference using Resolution, Backward Chaining
and Forward Chaining
4.4. Predicate
Logic: FOPL, Syntax, Semantics, Quantification, Inference with FOPL: By
converting into PL (existential and universal instantiation), Unification and
lifting, Inference using resolution
|
Class Lecture
+
Lab Session
|
14 hours
|
|
|
4.5. Handling
Uncertain Knowledge, Radom Variables, Prior and Posterior Probability,
Inference using Full Joint Distribution, Bayes' Rule and its use, Bayesian
Networks, Reasoning in Belief Networks
4.6. Fuzzy Logic:
Fuzzy Sets, Membership in Fuzzy Set, Fuzzy Rulebase Systems
|
|
|
|
|
|
|
|
|
|
Unit V: Machine
Learning
5.1. Introduction
to Machine Learning , Concepts of Learning, Supervised, Unsupervised and
Reinforcement Learning
5.2. Statistical-based Learning:
Naive Bayes Model
5.3.
Learning by Genetic Algorithms: Operators in
Genetic Algorithm: Selection, Mutation,
Crossover, Fitness Function, Genetic
Algorithm
5.4. Learning with
Neural Networks: Introduction, Biological Neural Networks Vs. Artificial
Neural Networks (ANN), Mathematical Model of ANN, Activation Functions:
Linear, Step
Sigmoid,
Types of ANN: Feed-forward, Recurrent, Single Layered, Multi-Layered, Application
of Artificial Neural Networks, Learning by Training ANN, Supervised vs.
Unsupervised Learning, Hebbian Learning,
Perceptron Learning, Back-propagation
Learning
|
Class Lecture
+
Lab Session
|
9 Hours
|
|
|
|
|
|
|
|
Unit VI: Applications
of AI (6 Hrs)
6.1. Expert
Systems, Components of Expert System: Knwoledge base, inference engine, user
interface, working memory, Development of
Expert Systems
6.2.
Natural Language Processing: Natural Language
Understanding
and Natural Language Generation, Steps of Natural Language Processing:
Lexical Analysis(Segmentation, Morphological Analysis), Syntatic Analysis,
Semantic Analysis, Pragmatic Analysis,
Machine Translation,
6.3. Machine
Vision Concepts: Machine vision and its applications, Components of Machine
Vision
System
|
Class Lecture
+
Lab Session
|
6 Hours
|
|
|
6.4.
Robotics: Robot Hardware (Sensors
Effectors) , Robotic Perceptions
|
and
|
|
|
|
|
|
|
|
_files/image001.gif)
_files/image002.gif)
