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.
Tuesday 31 March 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
______________________
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.
_________________________
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-1Sunday 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
|
Subscribe to:
Posts (Atom)