Candidates have to do their project in any relevant topic, under the supervision
of teachers.
Candidates have to do their project in any relevant topic, under the supervision
of teachers.
Finite Automata
Definition of a Finite Automaton, Model, Representation, Classification – with respect to
output function Mealy and Moore Machines, with respect to State Transition –
Deterministic and Non-Deterministic Machine, Examples, conversion algorithms Mealy
to Moore and Moore to Mealy, Finite and Infinite state machines, Finite Automaton,
Deterministic and Non-Deterministic Finite automaton, Non-Deterministic to equivalent
Deterministic Automaton-Optimized and Non-optimized technique ideas and algorithms,
Acceptability of String by a Finite Automaton.
15 hours
Formal Languages and Grammar
Introduction to Formal Grammar and Language, Chomsky’s Classification of Grammar –
Type-0, Type-1 or Context Sensitive, Type-2 or Context Free and Type-3 or Regular
Grammar, Illustration of each of these classes with example, Sentential form, Sentences –
Languages or strings, Derivations, Ambiguous Grammar and Language, Designing of
Grammar for a language, Find the Language for given Grammar, Definition and basic
idea about Push Down Automaton.
15 hours
Regular Expression:
Basic Idea and Definition, Regular Expression basic Identities, Arden’s Theorem –
Statement (without Proof) and application for reduction of equivalent regular expressions,
Regular expression to Finite Automata conversion, State Transition System to Regular
Expression conversion algorithm by Arden’s Algebraic Method, FA to Regular Grammar
and Regular Grammar to FA conversion algorithms and applications.
15 hours
Turing Machine
Concepts of Turing Machine, Formal Definitions, Classifications – Deterministic and
Non-Deterministic Turing Machines, Simple Design of Turing Machines: Odd / even
count and concepts of Universal Turing Machines, Difference and Similarities between
Turing Machine and a General Purpose Computer, Definition and significant of Halting
Problem in Turing Machine.
Introduction
Defining system, open and closed system, modeling of system through computer
hardware, communication systems, external agents and software systems; Importance of
Engineering Methodology towards computerization of a system.
03 hours
Software Life Cycle
Classical and Iterative Waterfall Model; Spiral Model; Prototype Model; Evolutionary
model and its importance towards application for different system representations,
Comparative Studies.
07 hours
Software Requirement and Specification Analysis
Requirements Principles and its analysis principles; Specification Principles and its
representations
Software Design Analysis – Different level of DFD Design, Physical and Logical DFD,
Use and Conversions between them, Decision Tables and Trees, Structured analysis,
Coupling and Cohesion of different modules
Software Cost Estimation Modeling –COCOMO.
23 hours
Software Testing
Software Verification and Validation; Testing objectives, Testing Principles, Testability;
Error and Faults; Unit Testing, White Box and Blank Box Testing, Test Case Design:
Test Vector, Test Stub.
17 hours
Software Quality Assurances
Concepts of Quality, Quality Control, Quality Assurance, IEEE Standard for Statistical
Software Quality Assurances (SSQA) criterions.
Use Python 3.6 or above. Use a text editor sensitive to whitespace like Notepad++, gedit, vim,
Sublime Text, and NOT Notepad / WordPad. The following exercises are suggestive in nature.
1. The Interpreter as a calculator. Basic arithmetic operations. Introduction to the simple
numeric data types – integers, floating point numbers, Boolean, complex numbers.
Inter conversion of data types.
a. Use the Python prompt as a basic calculator. Explore the order of operations
using parentheses.
b. Explore the various functions in the math module. Eg: find GCD of two
numbers, area and perimeter of circle using math.pi, etc.
c. Exploring the complex data type and their operations, eg: finding the modulus
and phase angle of a complex number.
d. The print function – Printing values. Repeat the previous experiments now
using the print function
2. Basic user interactions using the print() and input() functions.
a. Write a simple python script using the print function in a text editor, save it
with the extension “.py”. Run it in the terminal / command prompt.
b. Take input two strings from the user, and print the first one twice, and the
other one thrice.
c. Ask the user to enter two numbers, and output the sum, product, difference,
and the GCD.
d. More programs that test concepts learned in week 1 which involves the usage
of the print and input functions.
3. Strings, List, Tuples, the re (regular expression) module
a. Ask the user for two strings, print a new string where the first string is
reversed, and the second string is converted to upper case. Sample strings:
“Pets“, “party”, output: “steP PARTY”. Only use string slicing and +
operators.
b. From a list of words, join all the words in the odd and even indices to form
two strings. Use list slicing and join methods.
c. Simulate a stack and a queue using lists. Note that the queue deletion
operation won’t run in O(1) time.
d. Explore the ‘re’ module, especially re.split, re.join, re.search and re.match
methods.
4. Conditionals, looping constructs, and generators
a. Use list comprehension to find all the odd numbers and numbers divisible by
3 from a list of numbers.
b. Using while loops to do Gaussian addition on a list having an even number of
numbers. Print each partial sum. Eg: if the list is [1, 2, 3, 4, 5, 6], the program
should output “1 + 6”, “2 + 5”, and “3+4” in separate lines, and the result of
the addition “21”. Extend it to handle lists of odd length.
c. Primarily testing using for and while loops.
d. Use (c) to generate a list of primes within a user-given range.
e. Explore the ‘key’ function of sum( ), min( ), max( ), and sort( ) functions
using lambdas.
5. User defined functions
a. Implement popular sorting algorithms like quick sort and merge sort to sort
lists of numbers.
b. Implement the Pascal’s triangle.
c. Three positive integers a, b, and c are Pythagorean triples if a2+ b2 =c2. Write
a function to generate all Pythagorean triples in a certain range.
d. Write two functions that simulate the toss of a fair coin, and the roll of an
unbiased ‘n’ sided die using the random module.
e. Like (d), but now the coin and the die are not fair, with each outcome having
a given probability.
6. File handling, sys, pickle and csv modules
a. Basic file operations. Explore the different file modes.
b. Emulate the unix ‘cp’, ‘grep’, ‘cat’ programs in Python. In each case, the user
should pass the arguments to the program as command line arguments.
c. Use pickle for persistent storage of variables
7. Sets and dictionaries
a. Use sets to de-duplicate a list of numbers, and a string such that they contain
only the unique elements
b. Use the set union and intersection operations to implement the Jaccard and
Cosine similarity of two sets.
c. Use dictionaries to count the word and letter occurrences in a long string of
text.
d. Invert a dictionary such the previous keys become values and values keys.
Eg: if the initial and inverted dictionaries are d1 and d2, where d1 = {1: ‘a’, 2:
‘b’, 3: 120}, then d2 = {‘a’: 1, 2: ‘b’, 120: 3}.
e. What if the values in (d) are not immutable? Use frozensets. For repeated
values, use lists. Eg: if d1 = {1: ‘a’, 2: ‘a’, 4: [1, 2]}, then d2 = {‘a’: [1, 2],
frozenset([1, 2]): 4}.
f. Write a function to generate the Fibonacci numbers in (a) exponential time
using the naïve algorithm, and (b) in linear time using dynamic programming
(memorization) with a dictionary.
8. Object Oriented Programming
a. Create a ‘Graph’ class to store and manipulate graphs. It should have the
following functions:
i. Read an edge list file, where each edge (u, v) appears exactly once in
the file as space separated values.
ii. Add and remove nodes and edges
iii. Print nodes, and edges in a user readable format
iv. Computes basic statistics of the graph like degree distribution,
clustering coefficient, and the number of connected components.
v. Finding all the neighbors of a node
vi. Finding all the connected components and storing them as individual
Graph objects inside the class
vii. Finding single source shortest paths using Breadth First Search
b. Make a ‘DiGraph’ class to handle directed graphs which inherits from the
‘Graph’ class. In addition to all of the functionalities of (a), it should support
the following operations
i. Finding the predecessors and successors of a node
ii. Creating a new ‘DiGraph’ object where all the edges are reversed.
iii. Finding the strongly connected components
c. Extend (a) and (b) to handle weighted graphs, and implement Dijkstra’s and
Floyd-Warshall algorithms to compute the single source and all pairs shortest
paths.
d. Use the graph containers in (a), (b), and (c) to implement additional graph
algorithms.
Introduction to the Python
Interpreted vs. compiled languages. Bytecodes. The importance of whitespace.
Variables and the lack of explicit data types and how Python uses the concepts of duck,
strong, and static typing, to figure out data types in runtime.
The assignment operator, the binding of names to objects, and aliasing.
Keywords and their significance.
04 hours
Strings: definition, declaration, and immutability, string constants, declaration, and the
equivalence of single and double quotes. Multi-line strings. Raw strings. String formatting
using the format function and the % operator. f-strings in Python 3.6+. Built-in functions:
count, find, replace, upper, lower, strip, etc. Time and space complexities of the functions
and operations.
Lists: definition, declaration, and mutability. Nested lists. Indexing and slicing: same as
strings. List comprehensions. The split and join methods. Built-in list functions – append,
extend, count, find, index, etc. Time and space complexities of the functions and
operations.
Tuples: definition, declaration, and immutability. Packing and unpacking lists and tuples.
The + and * operators on strings, lists, and tuples. Indexing and slicing strings, lists, and
tuples.
06 hours
Conditionals, Iterators, and Generators
Conditionals: If, elif, and else statements. Nested conditionals. Containment checking in
containers using the in keyword.
Looping constructs: while and for loops. Flow control using break, continue, and pass.
Nested loops.
Generators: range, zip, sorted, reversed, and enumerate.
15 hours
User-defined Functions and Recursion
Functions: definition, function signature, positional, default, and keyword arguments.
Documentation strings. Unnamed functions – lambda, filter, and map.
Recursion: basic idea, implementing recursion, sharing variables across the recursion
stack, modifying the size of the recursion stack.
10 hours
File Handling and Exception Handling
File handling: open and close methods, the different read and write modes. Using the with
open approach to files. read, readline, readlines functions. The csv module for efficient
read/write of structured data. The pickle module for persistent storage of variables in a
program.
Exception handling: the popular errors- Name Error, Value Error, Syntax Error, Key
Error, Attribute Error, etc, and their cause and effects. Using try-except blocks for
graceful handling of exceptions.
05 hours
Unordered data types - Sets and Dictionaries
Basic concepts of hashing: hash functions, open chain, closed chain, advantages and
disadvantages compared to conventional ordered data types. The hash() function in
Python.
Sets and frozensets: definition, declaration, mutability, and advantages over lists / tuples.
05 hours
Insertion, deletion, union, intersection, and other built-in operations. Time and space
complexities of the functions and operations.
Dictionaries: Concept of keys and values. Immutability requirement for keys. Basic
operations on dictionaries. Iterating over the keys and key, value pairs of a dictionary.
Dictionary inversions
Intro to Object Oriented Programming
The Python data model, magic methods (__init__, __str__, __eq__, etc) and their utilities,
accessing and mutating data, constructors, class methods, and the lack of explicit access
modifiers of class methods – naming conventions of private, protected, and public
variables and methods.
Inheritance: inheriting a parent class, the super() method. Basic multiple inheritance.
Lab sessions related to Simplex Method, Transportation Problem and Assignment Problem.
Introduction
Origin and development of operation research, Nature and characteristic features, models
in O.R., application of O.R.
05hours
Linear Programming Problem
Introduction, mathematical formulation of the problem and graphical solution method.
05hours
Simplex Method
Introduction, computational procedure, artificial variable, problem of degeneracy,
application of simplex method.
20hours
Duality:
Concept, formulation of primal – dual, duality and simplex method, Dual Simplex method.
10hours
Transportation Problem:
Introduction, mathematical formulation, finding initial basic feasible solution, optimality,
degeneracy, unbalanced transportation problem.
05hours
Assignment Problem:
Introduction, mathematical formulation and solution.
05hours
Game Theory:
Some basic terminology, Two-person Zero-sum Game, Game without Saddle Point –
Mixed strategy, Algebraic method for 2×2 Game
05hours
Network Scheduling:
Introduction, Critical Path Method (CPM), PERT calculation.
CMS-A-DSE-A--2-P: Data Mining Lab. DSE-A: Choice-2: Practical, Credit:02, Contact hours: 40.
Data mining using PYTHON/C
Introduction
Definition of Data Mining, Data pre-processing, Data cleaning, Data transformation,
Data Reduction, Data Visualization, Data extraction from large dataset, Data integration,
sub-sampling, Feature selection, Scalability issues of data mining algorithms, text
mining, web mining.
15hours
Classification and Prediction
Structural patterns of data, Tools for pattern recognition (preliminary concept), Linear
models for classification, Evaluating the accuracy of the classifier or predictor, Bayesian
Classification, Training and Test sets, Parametric and Non-parametric Learning,
Minimum Distance Classifiers, k-NN rule, Discriminant Analysis, Decision trees.
Similarity Measure, Basic hierarchical and non-hierarchical Clustering algorithms,
Some Applications, Neural Learning.
30hours
Data Warehousing (DWH)
Introduction: Definition and description, need for data ware housing, need for strategic
information, failures of past decision support systems, Application of DWH.
Assignments on Different Image Processing Functions based on Open CV & Python/Scilab