 |
| JNTU HYDERABAD CSE STREAM |
PROBABILITY AND STATISTICS
UNIT-I
Probability: Sample space and events – Probability – The axioms of probability – Some Elementary theorems - Conditional probability – Baye’s theorem.
UNIT-II
Random variables – Discrete and continuous – Distribution – Distribution function. Distribution
UNIT-III
Binomial and poison distributions Normal distribution – related properties.
UNIT-IV
Sampling distribution: Populations and samples - Sampling distributions of mean (known and unknown) proportions, sums and differences.
UNIT-V
Estimation: Point estimation – interval estimation - Bayesian estimation.
UNIT-VI
Test of Hypothesis – Means– Hypothesis concerning one and two means– Type I and Type II errors. One tail, two-tail tests.
UNIT-VII
Tests of significance – Student’s t-test, F-test,
test. Estimation of proportions.
test. Estimation of proportions.UNIT-VIII
Queuing Theory: Pure Birth and Death Process M/M/1 Model and Simple Problems.
Text Books:
1. Probability & Statistics, T. K. V. Iyengar, B. Krishna Gandhi and Others, S. Chand & Company.
2. A text book of Probability & Statistics, Shahnaz Bathul, V. G. S. Book Links.
References:
1. Probability & Statistics, Arnold O. Allen, Academic Press.
2. Probability & Statistics for Engineers, Miller and John E. Freund, Prentice Hall of India.
3. Probability & Statistics, Mendan Hall, Beaver Thomson Publishers.
4. Probability & Statistics, D. K. Murugeson & P. Guru Swamy, Anuradha Publishers.
MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE
UNIT-I
Mathematical Logic : Statements and notations, Connectives, Well formed formulas, Truth Tables, tautology, equivalence implication, Normal forms.
UNIT-II
Predicates : Predicative logic, Free & Bound variables, Rules of inference, Consistency, proof of contradiction, Automatic Theorem Proving.
UNIT-III
Set Theory : Properties of binary Relations, equivalence, compatibility and partial ordering relations, Hasse diagram. Functions: Inverse Function Comports of functions, recursive Functions, Lattice and its Properties, Pigeon hole principles and its application.
UNIT-IV
Algebraic structures : Algebraic systems Examples and general properties, Semi groups and monads, groups sub groups’ homomorphism, Isomorphism.
UNIT-V
Elementary Combinatorics: Basis of counting, Combinations & Permutations, with repetitions, Constrained repetitions, Binomial Coefficients, Binomial Multinomial theorems, the principles of Inclusion – Exclusion.
UNIT-VI
Recurrence Relation : Generating Functions, Function of Sequences Calculating Coefficient of generating function, Recurrence relations, Solving recurrence relation by substitution and Generating funds. Characteristics roots solution of In homogeneous Recurrence Relation.
UNIT-VII
Graph Theory : Representation of Graph, DFS, BFS, Spanning Trees, planar Graphs
UNIT-VIII
Graph Theory and Applications, Basic Concepts Isomorphism and Sub graphs, Multi graphs and Euler circuits, Hamiltonian graphs, Chromatic Numbers
TEXT BOOKS :
1. Discrete and Combinational Mathematics- An Applied Introduction-5th Edition – Ralph. P.Grimaldi.Pearson Education
2. Discrete Mathematical Structures with applications to computer science Trembly J.P. & Manohar .P, TMH
3.Discrete Mathematics and its Applications, Kenneth H. Rosen, Fifth Edition.TMH.
REFERENCES :
1. Discrete Mathematics with Applications, Thomas Koshy, Elsevier
2. Discrete Mathematical Structures, Bernand Kolman, Roberty C. Busby, Sharn Cutter Ross, Pearson Education/PHI.
3. Discrete Mathematical structures Theory and application-Malik & Sen
4. Discrete Mathematics for Computer science, Garry Haggard and others, Thomson.
5. Discrete Mathematics for Computer Scientists & Mathematicians, J.L. Mott, A. Kandel, T.P. Baker Prentice Hall.
6. Logic and Discrete Mathematics, Grass Man & Trembley, Person Education.ADVANCED DATA STRUCTURES
Unit I :
C++ Class Overview- Class Definition, Objects, Class Members, Access Control, Class Scope, Constructors and destructors, parameter passing methods, Inline functions, static class members, this pointer, friend functions, dynamic memory allocation and deallocation (new and delete), exception handling.
Unit II :
Function Over Loading, Operator Overloading, Generic Programming- Function and class templates, Inheritance basics, base and derived classes, inheritance types, base class access control, runtime polymorphism using virtual functions, abstract classes, streams I/O.
Unit III :
Algorithms, performance analysis- time complexity and space complexity. Review of basic data structures- The list ADT, Stack ADT, Queue ADT, Implementation using template classes in C++.
Unit IV :
Dictionaries, linear list representation, skip list representation, operations insertion, deletion and searching, hash table representation, hash functions, collision resolution-separate chaining, open addressing-linear probing, quadratic probing, double hashing, rehashing, extendible hashing, comparison of hashing and skip lists.
Unit V :
Priority Queues – Definition, ADT, Realizing a Priority Queue using Heaps, Definition, insertion, Deletion, External Sorting- Model for external sorting, Multiway merge, Polyphase merge.
Unit VI :
Search Trees (Part1):-
Binary Search Trees, Definition, ADT, Implementation, Operations- Searching, Insertion and Deletion, AVL Trees, Definition, Height of an AVL Tree, Operations – Insertion, Deletion and Searching
Unit VII :
Search trees (prt II) : Introduction to Red –Black and Splay Trees, B-Trees, B-Tree of order m, height of a B-Tree, insertion, deletion and searching, Comparison of Search Trees
Unit VIII :
Pattern matching and Tries : Pattern matching algorithms-Brute force, the Boyer –Moore algorithm, the Knuth-Morris-Pratt algorithm, Standard Tries, Compressed Tries, Suffix tries.
TEXT BOOKS :
1. Data structures, Algorithms and Applications in C++, S.Sahni, University Press (India) Pvt.Ltd, 2nd edition, Universities Press Orient Longman Pvt. Ltd.
2. Data structures and Algorithms in C++, Michael T.Goodrich, R.Tamassia and .Mount, Wiley student edition, John Wiley and Sons.
REFERENCES :
1. Data structures and Algorithm Analysis in C++, Mark Allen Weiss, Pearson Education. Ltd., Second Edition.
2. Data structures and algorithms in C++, 3rd Edition, Adam Drozdek, Thomson
3. Data structures using C and C++, Langsam, Augenstein and Tanenbaum, PHI.
4. Problem solving with C++, The OOP, Fourth edition, W.Savitch, Pearson education.
DIGITAL LOGIC DESIGN
UNIT-I
BINARY SYSTEMS : Digital Systems, Binary Numbers, Number base conversions, Octal and Hexadecimal Numbers, complements, Signed binary numbers, Binary codes, Binary Storage and Registers, Binary logic.
UNIT-II
BOOLEAN ALGEBRA AND LOGIC GATES : Basic Definitions, Axiomatic definition of Boolean Algebra, Basic theorems and properties of Boolean algebra, Boolean functions canonical and standard forms, other logic operations, Digital logic gages, integrated circuits.
UNIT-III
GATE – LEVEL MINIMIZATION : The map method, Four-variable map, Five-Variable map, product of sums simplification Don’t-care conditions, NAND and NOR implementation other Two-level implementnations, Exclusive – Or function, Hardward Description language (HDL).
UNIT - IV
COMBINATIONAL LOGIC : Combinational Circuits, Analysis procedure Design procedure, Binary Adder-Subtractor Decimal Adder, Binary multiplier, magnitude comparator, Decoders, Encoders, Multiplexers, HDL for combinational circuits.
UNIT - V
SYNCHRONOUS SEQUENTIAL LOGIC : Sequential circuits, latches, Flip-Flops Analysis of clocked sequential circuits, HDL for sequential circuits, State Reduction and Assignment, Design Procedure.
UNIT - VI
Registers, shift Registers, Ripple counters synchronous counters, other counters, HDL for Registers and counters.
UNIT - VII
Introduction, Random-Access Memory, Memory Decoding, Error Detection and correction Read-only memory, Programmable logic Array programmable Array logic, Sequential Programmable Devices.
UNIT-VIII
ASYNCHRONOUS SEQUENTIAL LOGIC : Introduction, Analysis Procedure, Circuits with Latches, Design Procedure, Reduciton of state and Flow Tables, Race-Free state Assignment Hazards, Design Example.
TEXT BOOKS :
1. DIGITAL DESIGN – Third Edition , M.Morris Mano, Pearson Education/PHI.
2. FUNDAMENTALS OF LOGIC DESIGN, Roth, 5th Edition,Thomson.
REFERENCES :
1. Switching and Finite Automata Theory by Zvi. Kohavi, Tata McGraw Hill.
2. Switching and Logic Design, C.V.S. Rao, Pearson Education
3. Digital Principles and Design – Donald D.Givone, Tata McGraw Hill, Edition.
4. Fundamentals of Digital Logic & Micro Computer Design , 5TH Edition, M. Rafiquzzaman John Wiley.
ADVANCED DATA STRUCTURES LAB
Objectives:
· To make the student learn a object oriented way of solving problems.
· To make the student write ADTS for all data structures.
Recommended Systems/Software Requirements:
· Intel based desktop PC with minimum of 166 MHZ or faster processor with atleast 64 MB RAM and 100 MB free disk space
· C++ compiler and STL Recommended
Week1 :
C++ programs to implement the following using an array.
a) Stack ADT b) Queue ADT
Week2 :
Write C++ programs to implement the following using a singly linked list.
a) Stack ADT b) Queue ADT
Week3 :
Write C++ programs to implement the deque (double ended queue) ADT using a doubly linked list and an array.
Week 4 :
Write a C++ program to perform the following operations:
a) Insert an element into a binary search tree.
b) Delete an element from a binary search tree.
c) Search for a key element in a binary search tree.
Week5 :
.Write C++ programs that use non-recursive functions to traverse the given
binary tree in
a) Preorder b) inorder and c) postorder.
Week6 :
Write C++ programs for the implementation of bfs and dfs for a given graph.
Week7 :
Write C++ programs for implementing the following sorting methods:
a) Merge sort b) Heap sort
Week8 :
Write a C++ program to perform the following operations
a) Insertion into a B-tree b) Deletion from a B-tree
Week9 :
.Write a C++ program to perform the following operations
a) Insertion into an AVL-tree b) Deletion from an AVL-tree
Week10 :
Write a C++ program to implement all the functions of a dictionary (ADT)
using hashing.
Week11 :
Write a C++ program for implementing Knuth-Morris- Pratt pattern matching
algorithm.
Week12 :
Write a C++ program for implementing Boyer – Moore Patten matching
algorithm
(Note: Use Class Templates in the above Programs)
TEXT BOOKS :
1. Data Structures and Algorithms in C++, Third Edition, Adam Drozdek, Thomson.
2.Data Structures using C++, D.S. Malik, Thomson
No comments:
Post a Comment