Computer Science
COMPUTER ENGINEERING
UNIT 1 : MATHEMATICS
Mathematical Logic: Propositional Logic; First Order Logic. Probability: Conditional Probability; Mean, Median, Mode and Standard Deviation; Random Variables; Distributions; uniform, normal, exponential, Poisson, Binomial. Set Theory & Algebra: Sets; Relations; Functions; Groups; Partial Orders; Lattice; Boolean Algebra. Combinatorics: Permutations; Combinations; Counting; Summation; generating functions; recurrence relations; asymptotics. Linear Algebra: Algebra of matrices, determinants, systems of linear equations, Eigen values and Eigen vectors. Numerical Methods: LU decomposition for systems of linear equations; numerical solutions of non- linear algebraic equations by Secant, Bisection and Newton- Raphson Methods; Numerical integration by trapezoidal and Simpson’s rules. Calculus: Limit, Continuity & differentiability, Mean value Theorems, Theorems of integral Calculus, evaluation of definite & improper integrals, Partial derivatives, Total derivatives, maxima and minima.
UNIT 2: DIGITAL LOGIC AND COMPUTER ARCHITECTURE
Digital Logic: Logic functions, Minimization, Design and synthesis of combinational and sequential circuits, Hardware Description Language for combinational and sequential circuits, Fixed and floating point number representation and computer arithmetic. Computer Organization and Architecture: Machine instructions and addressing modes, ALU and data-path, Single-Cycle Datapath and Control- Multi-cycle Datapath and Control-Micro-programming and Hard-wired Control Units- Behavioral HDL Description of Systems- Exceptions Handling. Pipelining: Pipelined MIPS Data path- Pipeline Hazards: Structural, Control, Data-Hazard Detection and Resolution- Pipelining control-Exceptions Handling Memory System and I/O interfacing: Overview of SRAM and DRAM Design- Memory Hierarchy;-Cache memory design – Virtual memory-Performance issues -I/O device characteristics – Buses and bus arbitration – Processor/OS interface -DMA
UNIT 3: DATA STRUCTURES AND ALGORITHMS
Data Structures: Abstract data types, Arrays, Stacks, Queues, Linked Lists, Trees, Graph theory: Graph Traversal — Topological Sorting — Dijkstra’s Algorithm — Minimal Spanning Tree — Applications — DFS — Biconnectivity — Euler Circuits — Graph Coloring Problem. Search Structures and Priority Queues: AVL Trees — Red-Black Trees
— Splay Trees — Binary Heap — Leftist Heap. Sorting: Insertion sort — Merge sort — Quick sort — Heap sort — Sorting with disks — k-way merging. Algorithms: Analysis, Asymptotic notation, Notions of space and time complexity, Worst and average case analysis; Design: Greedy approach, Dynamic programming, Divide-and-conquer, Backtracking and Branch and Bound; Asymptotic analysis (best, worst, average cases) of time and space, upper and lower bounds, Concepts of complexity classes
— P, NP, NP-hard, NP-complete.
UNIT 4: SYSTEM PROGRAMMING AND OPERATING SYSTEMS
System Programming: Elements of Assembly Language Programming, Pass structure of assemblers, design of single and two pass assemblers, Macros and Macro processors, Design of a macro pre-processor, Linkers: Concepts, Design of a linker, Loaders, software Tools: software tools for program development, editors, debug monitors, programming environments. Operating System: Processes, Threads, Inter-process communication, Concurrency, Synchronization, Deadlock, CPU scheduling, Memory management and virtual memory, File systems, Free-space management — Disk scheduling — Disk management — Swap-space management, I/O systems, Protection and security. Design principles of Linux and Windows 7.
UNIT 5: DATABASE SYSTEMS
ER-model, Relational model: relational algebra, tuple calculus, SQL — Data definition-Queries in SQL- Updates- Views — Integrity and Security — Relational Database design — Functional dependences and Normalization for Relational Databases. Data Storage and Query Processing: Record storage and Primary file organization- Operations on Files-Heap File- Sorted Files-Hashing Techniques — Index Structure for files —B-Tree – B+Tree — Query Processing. Transaction Processing: Concurrency control- Schedule and Recoverability- Serializability and Schedules — Two Phases locking- Deadlock- Recovery Techniques — Immediate Update- Deferred Update – Shadow Paging. Design of Object oriented Data Bases.
UNIT 6: THEORY OF COMPUTATION AND COMPILER DESIGN
Regular Languages and Regular Expressions – Nondeterministic Finite Automata – Kleene’s Theorem. Minimal Finite Automata-Pumping Lemma for Regular Languages- Context Free Grammars and Languages. Push Down Automata. Turing Machine, Recursively enumerable Languages, Non-recursive Language, Unsolvable problems. Compiler Design: Lexical analysis, Parsing, Syntax directed translation, Runtime environments, Intermediate and target code generation, Basics of code optimization.
UNIT 7: COMPUTER NETWORKS
ISO/OSI stack, LAN technologies: Ethernet, Token ring; Flow and error control techniques, Routing algorithms, Congestion control, TCP/UDP and sockets, IPv4, Application layer protocols: icmp, dns, smtp, pop, ftp, http; Basic concepts of hubs, switches, gateways, and routers. High Performance Networks: ISDN and BISDN, ATM and Frame relay, MPLS, Integrated and Differentiated Services, Optical Networks and Switching. Wireless Adhoc Networks: Operation models, Routing methods: Table- driven and Source-initiated On Demand routing protocols, Hybrid protocols – Uni Cast routing protocol (AODV, DSR, DSDV) – Multi-Cast routing protocol (ODMRP) – Multi clustering–Power Issues. Network security – basic concepts of public key and private key cryptography, digital signature, firewalls.
UNIT 8: COMPUTER GRAPHICS AND MULTIMEDIA
Line – Curve and Ellipse Drawing Algorithms –Two-Dimensional Geometric Transformations – Two-Dimensional Clipping and Viewing. – Three-Dimensional Object Representations – Three-Dimensional Geometric and Modeling Transformations – Three- Dimensional Viewing – Color Models – Animation. Multimedia Systems: Multimedia Elements, Applications and Architecture – Evolving Technologies for Multimedia – Defining Objects for Multimedia Systems – Multimedia Data Interface Standards — Multimedia Databases. Compression and Decompression: Types of Compression – Binary Image Compression Schemes – Color, Gray Scale and Still – Video Image Compression – Audio Compression – Fractal Compression. Virtual Reality Design – Multimedia Database
UNIT 9: SOFTWARE ENGINEERING
S/W Engineering Paradigm — life cycle models (water fall, incremental, spiral, WINWIN spiral, evolutionary, prototyping, object oriented) – Project Management Concepts – Software Project Planning Risk analysis and management-project scheduling and tracking software quality assurance-Software configuration management, Requirement analysis – software prototyping — prototyping in the software process — rapid prototyping techniques, Design process and concepts – Real time systems – Real time software design- Software testing —Types of software testing — strategic approach and issues — Software Metrics.
UNIT 10: WEB TECHNOLOGIES
Basic Web Concepts — World Wide Web- Web Servers —Web Browsers — URL- MIME — HTTP—SGML- Internet Protocols and Standards. HTML Forms — CGI Concepts —Server — Browser Communication — E-Mail Generation— Applets – Java Script Programming-Dynamic HTML- ActiveX Controls-Multimedia-Client Side Script.- Server Side Scripting – Servlets- Java Server Pages – Session Management -Cookies -Database Access Through Web -SQL – Architecture for Database- System. E-Commerce —Business Models for E-Commerce-Enabling Technologies of the World Wide Web- E-Marketing-E-Security-E-Payment Systems-E-Customer Relationship Management.
