AICTE Computer Science & Engineering Model Question Papers : All India Council for Technical Education
Name of the Instution : All India Council for Technical Education
Class : Undergraduate Programs
Document Type : Model Question Papers
Paper : Computer Science & Engineering
Year : 2018
Website : https://www.aicte-india.org/education/model-syllabus
AICTE Computer Science & Engineering Model Question Papers
Download Computer Science & Engineering Model Question Papers For Undergraduate Program from the All India Council for Technical Education website. The model question papers are suggestive blueprints.
Related : AICTE India Civil Engineering Model Question Papers : www.pdfquestion.in/33526.html
The primary aim of these question papers is to bring clarity about the process of connecting questions to performance indicators and hence to course outcomes.
Discrete Mathematical Structures
Unit I
1a In asynchronous transfer mode (ATM), data are organized into cells of 53 bytes. Identify the range (number of ATM cells transmitted ) for the domain (minutes) set M={1, 2, 3, 4, 5, 6} if connection that transmits data at the rate of
i) 128 kilobits per second
ii) 300 kilobits per second
iii) 1 megabit per second
Download CSC Question Paper :
https://www.pdfquestion.in/uploads/pdf2019/33531-csc.pdf
1b Write the propositions for the following English statements.
To use the wireless network in the airport you must pay the daily fee
unless you are a subscriber to the service.
Express your answer in terms of
w: You can use the wireless network in the airport.
d: You pay the daily fee. and
s: You are a subscriber to the service.
1c Let p,q and r be the propositions
P: You have attended cultural audition.
q: You miss the first minor exam.
r: You will not get the make-up exam.
Express each of these propositions as an English sentence
i) (p?¬ r) ?(q?¬ r)
ii) (p?q) ? (¬q? r)
iii) ¬q?r
2a Let A, B, and C be sets. Show that A ? (B n C) ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ = ( ??¯ ? ?? ¯ ) n ??¯
2b Consider the following system specifications using the propositions
“The message is scanned for viruses” or “The message was sent from an unknown system”
“When a message is not sent from an unknown system it is not scanned for viruses.” “The message is scanned for viruses” Is the specification consistent? Justify your answer
2c Consider the combinatorial circuit shown in below figure and answer the following.
1. Find the output of combinatorial circuits (a) and (b).
2. Write the simplified form of negation of the output.
3. Assume appropriate p, q and r and express the output in English sentence.
3a Let f, g, h be functions from R ? R where f(x)=x2,g(x) =x+5 and h(x) = 2 2 x + .Determine ((h o g) o f) (x).
3b Identify which of the following propositional statements are tautology using laws of equivalence.
i) [ p ? q ? (?p ? ?q ? r )]???( p ? q ? r )
ii) ¬ (p?q) ?¬ q
3c State whether the following statements are true or false
i) Every infinite sets are countable
ii) Every relation is not necessarily function
iii) What time is it? is a proposition
iv) Every bijective functions are inverse functions
v) (f ? g)(a) = f (g(a)).
Unit II
4a Suppose that at some future time every telephone in the world is assigned a number that contains a country code 1 to 3 digits long, that is, of the form X, XX, or XXX, followed by a 10-digit telephone number of the form NXX-NXX-XXXX. How many different telephone numbers would be available worldwide under this numbering plan?
b How many positive integers between 100 and 999 inclusive
i) are divisible by 7?
ii) are not divisible by 4?
iii) are divisible by 3 and 4?
iv) are divisible by 3 or 4?
v) are divisible by 3 but not by 4 and 7?
c For the relations R1={(a,b), (a,c), (b,d), (d,d)} and R2={(a,a), (a,d), (b,a), (b,b), (c,e), (d,d), } on sets {a,b,c,d,e} to {a,b,c,d,e} determine R2?R1. Represent the output relation using directed graph.
5a Consider the following relation R={(1,1),(1,2),(1,3),(1,4), (2,2),(2,3),(2,4),(3,3),(3,4),(4,4)} defined over the set S={1,2,3,4}
i) Is (S,R) is a Poset? Justify your answer.
ii) Is (S,R) Linearly ordered? Justify your answer.
iii) Is (S,R) Well-ordered? Justify your answer.
iv) Identify the minimal, maximal, greatest and least elements
v) Identify the lower bound and upper bound for the set {3}and
also find the least upper bound and greatest lower bound.
b In how many possible orders a student can answer 5 questions in the SEE exams considering the following conditions
i) There are 3 units UNIT1, UNIT2 and UNIT3 consisting of 3, 3 and 2 questions respectively.
ii) Student has to answer 2 questions from UNIT 1 , 2 questions from UNIT 2 and one from UINIT 3
c In order to conduct the SEE examination, In how many ways seating arrangement can be made for 240 CS students and 240 EC students such that CS and EC students should sit alternatively.
Data Structures & Algorithms
1(a) Suppose we wish to search a linked list of length n, where each element contains a key k long with a hash function h(k). Each key is a long character string. How might we take advantage of the hash values when searching the list for an element with a given key?
1(b) With the help of suitable code snippets, Prove That: “Queue is NO more exactly a First In First Out data structure”
1(c) Using state space tree prove that:
There is no solution for a 2 queen problem
There are multiple solutions for a 4 queen problem
a) Differentiate between Structures and Unions with suitable code snippets. 4 CO1 L3 1.4.1
2(b) A linear probing has a hash function of the form: h(k, i) = (h’(k) + i) mod m and a quadratic probing has a hash function of the form: h(k, i) = (h’(k) + c 1 i + c 2 i 2 ) mod m. Linear probing suffers from a problem known as primary clustering and quadratic probing from secondary clustering. Discuss.
2(c) Consider the circular list given below with string data:
Write a function which will display the output in following fashion: i think i can think i can i can can
At each line, the function should display data from all the nodes present. After printing each line, an appropriate node has to be deleted. After printing the last line, “last” pointer should be holding the NULL value.
3(a) Write a program to print the nth node from end from a singly linked list. 4 CO2 L3 1.4.1
3(b) Complete the function described below:
Function Name: summon
Input Params: base address of string
Return Type: base address of summoned string
Description: A magician wants to generate summoning charms. For input string “firebolt”, the function should produce “summon firebolt”. Do not use any inbuilt string handling functions.
3(c) Write the modules to implement the following using Stack data structure:
• Check if the given string is palindrome
• Sort the given set of integers
Computer Organization & Architecture
1 a Implement the Boolean function F(A,B,C,D)=BC+ABC+A?C?D using only a single 8X1 Multiplexer where signals A,B,C,D and D? represent the inputs. 6 CO1 1.4.4 L2
b The circuit diagram of a synchronous counter is shown in the given figure. Determine the sequence of states of the counterassuming that the initial state is “000?. Give your answer in a tabular form showing the present state QA, QB, QC, J-K inputs (JA, KA, JB, KB, JC, KC) and the next state QA+, QB+, QC+. From the table, determine the modulus of the counter.
c Consider the instruction Load R2,(R3). What control signals are generated in the datapath during the execution of this instruction. Justify your answer with proper reasoning.
2 a Realize a Boolean expression f(w,x,y,z)=Sm(1,2,6,7,8,9,11,13,14,15) using Multiplexer Tree structure. The first level should consist of two 4: 1 MUX with variables w and z on their select lines S1 and S0 respectively and second level should consist of single 2:1 MUX with variable y on the select lines
b i. Explain the working of Gated SR latch.
ii. What is forbidden state?
iii. Determine the output waveform for a gated SR latch
c i. Load R4,(R3)
ii. Store R4,(R3)
For the above instructions draw the timing diagrams for synchronous bus operation
3 a Explain Hardwired Control unit.
b Design , Simulate and implement a 4-bit Universal Shift Register for following operation
c There is a queue for exchange of old 500 rupees currency notes after demonetization, in the post office. But a single customercan exchange only upto Rs. 4000/- per day. What components are necessary to design a system which alerts the user on reaching the maximum count? Also design the system to automate the counting process.
4a Explain the operational model of SIMD computers.
b A 40 MHz processor was used to execute a benchmark program with the following instructions and clock cycle counts Determine the effective CPI, MIPS rate and execution time for this program.
Machine Learning
1a A dealer has a warehouse that stores a variety of fruits and vegetables. When fruit is brought to the warehouse, various types of fruit may be mixed together. The dealer wants a model that will sort the fruit accordingto type. Justify with reasons how machine learning model is efficient compared to feature based classification technique.
1b Suppose you are only allowed to use binary logistic classifiers to solve a multi-class classification problem. Given a training set with 2 classes, this classifier can learn a model, which can then be used to classify a new test point to one of the 2 classes in the training set.
2a Describe the two error functions that are used for neural networks. Suppose we are training a neural network for binary classification, justify the type of error function which is suitable to solve the problem.
2b Why it is necessary to estimate the accuracy of hypothesis. Explain procedure to estimate difference in error between two learning methods.
3a Explain the effect of following factors in achieving global minima with gradient descent algorithm.
3b Calculate the cost value of linear regression for the following dataset.
X=[1,2,3,4,5 ]
Y=[3,6,7,11,15 ]
Slope of hypothesis (O1) = 7
Constant/ intercept (O0)=5
Epoch=3
Learning rate (a) = 0.5
4a Determine the Principal Components for the given 2-Dimensional dataset. (1, 2), (2, 4), (3, 6).
4b Suppose that we want to build a neural network that classifies two dimensional data (i.e., X = [x1, x2]) into two classes: diamonds and crosses. We have a set of training data that is plotted as follows
Draw a network that can solve this classification problem. Justify your choice of the number of nodes and the architecture. Draw the decision boundary that your network can find on the diagram.
Operating System
1 a Classify and justify the following applications as Batch oriented or Interactive. Generating monthly bank statement, Word processing, Generating personal tax returns.
b Discus implementation of mutual exclusion with semaphores. Explain the role of wait( ) and signal( ) functions in this regard.
c Consider the following processes with their arrival time and burst time as given below:
Process Arrival Time Burst Time
P1 0 12
P2 2 4
Identify appropriate data structure to implement following scheduling algorithms for the above scenario. Which one among them gives optimized scheduling with respect to waiting time?
a. FCFS
b. Shortest remaining time first ( SJF preemptive)
c. Round Robin (time quantum = 4 units)
2 a Consider the concurrently running processes A and B as given below. (Shared data: semaphore s1=0, s2=0;) Illustrate the order in which these instructions (A, B, C and D) will get executed?
b Differentiate between one-to-one and many-to-many model used for multithreading implementation.
3 a Assume two operations i) A(counter++) ii) B(counter–)
Both are running following code:
reg1= counter;
reg1= Reg1+1;
Counter = reg1;
Check for occurrence of Race condition. Propose different approaches to solve race condition if it exists.
3.b Every Saturday ram will get up at morning 6 o clock. His wife Swapna wants him to help her out with doing the house since guests were expected to arrive that evening. This would take Ram 45 minutes.
4a Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The drive is currently serving a request at cylinder 143, and the previous request was at cylinder 125. The queue of pending requests, in FIFO order, is: 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130 Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests for each of the following disk scheduling algorithms?
i)FCFS
ii) SSTF
iii) SCAN
iv) LOOK
5. Answer the following questions using the Banker’s algorithm:
a. Is the system in a safe state?
b. If a request from process P4 arrives for (0, 3, 2, 0), can the request be granted immediately?
Data Mining & Analysis
1a) Answer the following questions with justification.
(i) Is noise ever interesting or desirable?
(ii) Can noise objects be outliers?
(iii) Are noise objects always outliers?
(iv) Are outliers always noise objects?
(v) Can noise make a typical value into an unusual one, or vice versa?
1b) Consider the following database of travel sequences for one working week of a traveler?
(i) Use the Apriori algorithm to compute all frequent itemsets, and their support, with minimum support 3. Clearly indicate the steps of the algorithm, and the pruning that is performed.
(ii) Which of the frequent sequences are maximal?
(iii) Which of the frequent sequences are closed?
2a) (i) For the Traveler dataset given in Figure 3.a, answer the following questions:
[A] Which kind of plots are suitable for each of the ‘gender’, ‘signup_method’, ‘first_device_type’, ‘first_browser’ and ‘timestamp_first_active’ attributes.
[B] Which kind of plots are suitable for numerical data, give example.
[C] Classify each of the following attributes {‘id’, ‘date_account_created’,’timestamp_first_active’, ‘gender’, ‘age’, ‘country_destination’} as qualitative (nominal or ordinal or binary) or quantitative (discrete or continuous). Some cases may have more than one interpretation, briefly indicate your reasoning if you think there may be some ambiguity.
(ii) List and briefly describe two other techniques for numerosity reduction.
3b) True or False/ Yes or No/ Short answers/Inference from analysis.
(i) [True/False] In comparison with the performance of a base classifier on a particular data set, bagging will generally not increase the error whereas as boosting may lead to an increase in the error.
(ii) [True/False] The use of weak classifiers prevents overfitting when we perform bagging.
4a) Given the contingency table, compute the following pairwise measures for clustering evaluation
(i) Jaccard coefficient
(ii) Rand statistic
(iii) Fowlkes–Mallows measure
4b) Solve the following HAC by considering the proximity matrix given, and consider inter-cluster similarity between clusters using:
(i) Nearest neighbor linkage
(ii) Farthest neighbor linkage And draw the corresponding dendograms.
5. Your task is to build a decision tree for classifying variable Y. (You can think of the data set as replicated many times, i.e. overfitting is not an issue here).
(i) Compute the information gains IG(Y | V ), IG(Y | W) and IG(Y | X). Which attribute would Decision Tree classifier select first?
(ii) Write down the entire decision tree constructed by Decision Tree classifier, without pruning.
(iii) One idea for pruning would be to start at the root, and prune splits for which the information gain (or some other criterion) is less than some small ?.