Tuesday, 31 March 2015

8th Sem AI

Students who are fail or absent in the remedial exam of Artificial Intelligence (180703) are informed that they have to write 3 GTU Question papers (with giving answer of option also) of Summer 2012, Summer 2013 and Summer 2014 in notebook. Last date to submit this is 10th April 2015.
Last Date of Submission for WAD assignment and Practicals  is 10/4/2015. 

Monday, 30 March 2015

TOC Assignment-2

NOTE: For remedial


GOVERNMENT ENGINEERING COLLEGE, PATAN
CSE Department
Assignment - 2

Sub: TOC (160704)                                                                                  SEM: 6th G & H
_____________________________________________________________________________

1. Prove that the following CFG is Ambiguous.
    S-> S + S | S * S | (S) | a  
   Write the unambiguous CFG for the above grammar. Draw Parse tree for the string
    a + a * a.
2. Design a CFG(Context Free Grammar) for the following language. L = { 0i 1j 0k / j > i+k }
3. For the language L = { xcxr/ x Є {a,b}* } (Palindrome with middle character=c), Design a PDA(Push Down Automata) and trace it for string “abacaba”.
4. Convert following CFG to equivalent Chomsky Normal Form (CNF).
S -> AACD | ACD | AAC | CD | AC | C
A -> aAb | ab
C -> aC | a
D -> aDa | bDb | aa | bb
5. Design and draw deterministic PDA accepting strings of the language
L = {x Є {a, b}* | na(x) > nb(x)}. Trace it for the string “aababaab”.
6. Write short notes on the following.
              (i) Equivalence Relation.
              (ii) Universal Turing Machine.
  (iii) The Sets P, NP, PSpace and NPSpace.
           (iv) Top Down Parsing And Bottom Up Parsing.

              (v) Application of Pumping Lemma.
  (vi) Basic Complexity Classes.
  (vii) μ Recursive Functions.
   (viii) Primitive Recursive Operation & Function.
   (ix) Time and space complexity.
              (x) NP complete problem
              (xi) Halting Problem.


7. Write theorem: If L1 and L2 are context free languages, then the language L1UL2, L1L2 and L1* are also CFLs.
8. Answer the following
1. Find context free grammar generating following language {aibjck | i = j or i = k}
2. Show that CFG S-> a|Sa|bSS|SSb|SbS is ambiguous.
3. find an equivalent unambiguous grammar for following:
      S-> A|B
      A ->aAb|ab
      B-> abB|Ʌ
9. Write TM accepting Palindrome.
10. Write transition table for PDA recognizing following language:
{ aibjck | j = i or j = k }.
11. Write TM accepting {ss | s ϵ {a,b}*}
12. Define Context Free Grammar (CFG). Describe the language accepted by following CFG:    S ->aSa | bSb | a | b | Λ
13. For the language L= {xcxr / xЄ{a,b}*} design a PDA(Push Down Automata) and trace it    for string “bacab”.
14. Convert following CFG to equivalent Chomsky Normal Form(CNF).
            S->AACD | ACD | AAC | CD | AC | C
A ->aAb | ab
C ->aC | a
D ->aDa | bDb | aa | bb

15. .Design and draw a deterministic PDA accepting strings with more a’s than b’s. Trace it for the string “abbabaa”.
16. Prove that √2 (square root of 2) is Irrational by method of Contradiction.
17. Prove: There are context-free languages L1 and L2 so that L1 ∩ L2 is not a CFL and there is a CFL L so that L’ is not a CFL
18. Given the CFG G, find a CFG G’ in Chomsky Normal form generating
            L(G) – { Λ}
S -> AaA | CA | BaB
A->  aaBa | CDA | aa | DC
B -> bB | bAB | bb | aS
C -> Ca | bC | D
D->  bD | Λ
19. Define PDA and design PDA for L={ x Є {a,b}*|| na (x) > nb (x)}.
20. Explain Derivation Tree, Expression Tree and Ambiguity with Example.
21. Draw the TM for L = {ss | s Є (a, b)*}
22. Explain Pumping Lemma and its applications.
23. Generate the Context-Free Grammars that give the following languages.
(i) {w | w contains at least three 1s}
(ii) {w | w starts and ends with the same symbol}
24. For given CFG G, find Chomsky normal form:
G has productions:
 S -> AaA|CA|BaB
 A-> aaBa|CDA|aa|DC
 B->bB|bAB|bb|aS
 C-> Ca|bC|D
 D->bD|Λ
25. Write a Turing Machine to copy strings.
26. Write a Turing Machine to delete a symbol.
27. Write PDA for following languages: { x { a,b,c}* | | na (x) < nb (x) or | na (x) < nc(x) }.
28. Let L be the language corresponding to the regular expression (011+1)* (01)*. Find the CFG generating L.
29. The language pal= { x {a, b}* | x = xr } cannot be accepted by any deterministic pushdown automaton.
30. Design and draw a deterministic PDA accepting strings with more a’s than b’s. Trace it for the string “abbabaa”.





CO Midsem Exam Syllabus

CO Midsem Exam Syllabus
______________________

1.Computer Data Representation
Basic computer data types, Complements, Fixed point representation,
Register Transfer and Micro-operations:
Floating point representation, Register Transfer language, Register
Transfer, Bus and Memory Transfers (Tree-State Bus Buffers,
Memory Transfer), Arithmetic Micro-Operations, Logic Micro-Operations, Shift Micro-Operations, Arithmetic logical shift unit

2.Basic Computer Organization and Design
Instruction codes, Computer registers, computer instructions, Timing
and Control, Instruction cycle, Memory-Reference Instructions, Input-output and interrupt, Complete computer description, Design of Basic
computer, design of Accumulator Unit.

3.Programming The Basic Computer
Introduction, Machine Language, Assembly Language, assembler

4.Central Processing Unit
Introduction, General Register Organization, Stack Organization,
Instruction format, Addressing Modes

CN Midsem Exam Syllabus

CN Midsem Exam Syllabus
_________________________

1.Introduction to computer networks and Internet;
Understanding of network and Internet, The network edge, The network core, Understanding of Delay, Loss and Throughput in the packet-switching network, protocols layers and their service model, History of the computer network

2.The Link layer and Local area networks:
Introduction and link layer services, error-detection and correction techniques, Multiple access protocols, addressing, Ethernet, switches.

OS MID SEM Syllabus

OS MID SEM Syllabus
__________________________

1.Introduction: Basics of Operating Systems: Definition – Generations of Operating systems – Types of Operating Systems, OS Service, System Calls, OS structure: Layered, Monolithic, Microkernel Operating Systems – Concept of Virtual Machine


2.Process Management
Processes: Definition , Process Relationship , Process states , Process State transitions , Process Control Block ,Context switching – Threads – Concept of multithreads , Benefits of threads – Types of threads
Process Scheduling: Definition , Scheduling objectives ,Types of Schedulers ,Scheduling criteria : CPU utilization, Throughput, Turnaround Time, Waiting Time, Response Time (Definition only) , Scheduling algorithms : Pre emptive and Non , pre emptive , FCFS – SJF – RR , Multiprocessor scheduling : Types , Performance evaluation of the scheduling.

3.Interprocess Communication
Race Conditions, Critical Section, Mutual Exclusion, Hardware Solution, Strict Alternation , Peterson’s Solution, The Producer Consumer Problem, Semaphores, Event Counters, Monitors, Message Passing, Classical IPC Problems: Reader’s & Writer Problem, Dinning Philosopher Problem etc., Scheduling , Scheduling Algorithms.

4.Deadlocks: Definition,Deadlock characteristics , Deadlock Prevention , Deadlock Avoidance :banker’s algorithm, Deadlock detection and Recovery.

Thursday, 26 March 2015

Remedial Exam-WAD 6th sem

6th sem students who are failed in Mid sem exam of Web Application and Development  are informed that the remedial exam will be held on 31st March 2015 at 01:00 PM LAB - 313.

Tuesday, 24 March 2015

8th Sem AI Remedial Exam

Students who are failed in Mid sem exam of Artificial Intelligence (180703) are informed that the remedial exam will be held on 31st March 2015 at 12:00 PM LAB - 314

Friday, 13 March 2015

scholarship notice for sc students

All The SC Students are here by inform that they have submit copy of Adharcard no. to  Prof.Anjana B.Sangada (CSE Dept) on or before 16/03/2015

Tuesday, 3 March 2015

Parallel Processing (180702) Mid Exam Syllabus

Parallel Processing (180702) Mid Semester Exam – Jan-May 2015 Syllabus
Unit – 1 Parallel Programming Platforms
Implicit Parallelism: Trends in Microprocessor Architectures, Limitations of Memory System Performance, Dichotomy of Parallel Computing Platforms, Physical Organization of Parallel Platforms, Communication Costs in Parallel Machines. Routing Mechanisms for Interconnection Networks, Impact of Process -Processor Mapping and Mapping Techniques
Unit – 2 Principles of Parallel Algorithm Design Algorithms
Preliminaries, Decomposition Techniques, Characteristics of Tasks and Interactions, Mapping Techniques for Load Balancing, Methods for Containing Interaction Overheads, Parallel Algorithm Models
Unit – 3 Basic Communication Operations, Algorithms
One-to-All Broadcast and All-to-One Reduction, All-to-All Broadcast and Reduction, All-Reduce and Prefix-Sum Operations, Scatter and Gather, All-to-All Personalized Communication, Circular Shift, Improving the Speed of Some Communication Operations
Unit – 4 Analytical Modeling of Parallel Programs
Sources of Overhead in Parallel Programs, Performance Metrics for Parallel Systems, Effect of Granularity and Data Mapping on Performance, Scalability of Parallel Systems, Minimum Execution Time and Minimum Cost-Optimal Execution Time, Asymptotic Analysis of Parallel Programs, Other Scalability Metrics
Unit – 5 Programming using the Message Passing Paradigm
      Principles of Message-Passing Programming, The Building Blocks: Send and Receive Operations, MPI:         The Message Passing Interface, Topologies and Embedding, Overlapping Communication with Computation, Collective Communication and Computation Operations, Groups and Communicators

Monday, 2 March 2015

Artificial Intelligence (180703) Mid Exam Syllabus 2015



Artificial Intelligence (180703) Mid Semester Exam – Jan-May 2015 Syllabus
Unit – 1 Problems And State Space Search
The AI problems, The underlying assumption, What is an AI technique? , The Level of the Model, Criteria for Success, General references, One final word
Unit – 2 Problems And State Space Search
Defining the problem as a state space search, Production systems, Problem characteristics, Production system characteristics, Issues in the design of search programs, Additional problems
Unit – 3 Heuristic Search Techniques
Generate and test, Hill climbing, Best first search, Problem reduction, Constraint satisfaction, Means ends analysis
Unit – 4 Knowledge Representation Issues
Representations And Mappings, Approaches To Knowledge Representation
Unit – 5 Using Predicate Logic
Representation Simple Facts In Logic, Representing Instance And Isa Relationships, Computable Functions And Predicates, Resolution
Unit – 6 Representing Knowledge Using Rules
Procedural versus Declarative Knowledge, Logic Programming, Forward Versus Backward Reasoning
Practical List-1

Sunday, 1 March 2015

Distributed System Midsem Syllabus-2015

GOVERNMENT ENGINEERING COLLEGE,PATAN
COMPUTER  SCIENCE AND  ENGINEERING
MIDSEM SYLLABUS-2015

 DISTRIBUTED SYSTEM

Sr.No
Topics
1
Concepts of Distributed Systems :
Introduction, Distributed computing models, Software concepts, Design issues in
distributed systems, Client-server model, WWW 1.0 and 2.0
2
Network Communication:
LAN and WAN technologies, OSI Model and Internet protocols, ATM, Protocols for
Distributed systems
3
Remote Communication:
Introduction, RPC basics, RPC implementation, RPC Communication and Other
issues, Sun RPC, RMI basics, RMI Implementation, Java RMI
4
Synchronization:
Clock synchronization, Logical clocks, Global state, Mutual exclusion, Election
algorithms: Bully algorithm, Ring algorithm, Leader election in rings, anonymous
rings, Asynchronous rings, synchronous rings, election in wireless networks,
Deadlocks in Distributed systems, Deadlocks in Message communication