Course Code: MTH10304
B. Formal Languages and Automata
UNIT I :
Fundamentals : Strings, Alphabet, Language, Operations, Finite state machine, definitions, finite automaton model, acceptance of strings, and languages, deterministic finite automaton and non deterministic finite
automaton, transition diagrams and Language recognizers.
UNIT II :
Finite Automata : NFA with Î transitions - Significance, acceptance of languages. Conversions and Equivalence : Equivalence between NFA with and without Î transitions, NFA to DFA conversion, minimisation of FSM, equivalence between two FSM’s, Finite Automata with output- Moore and Melay machines.
UNIT III :
Regular Languages : Regular sets, regular expressions, identity rules, Constructing finite Automata for a given regular expressions, Conversion of Finite Automata to Regular expressions. Pumping lemma of regular sets, closure properties of regular sets
UNIT IV :
Push Down Automata : Push down automata, definition, model, acceptance of CFL, Acceptance by final state and acceptance by empty state and its equivalence. Equivalence of CFL and PDA, interconversion. Introduction to DCFL and DPDA.
UNIT V :
Turing Machine : Turing Machine, definition, model, design of TM, Computable functions, recursively enumerable languages. Church’s hypothesis, counter machine, types of Turing machines
TEXT BOOKS:
1. “Introduction to Automata Theory Languages and Computation”. Hopcroft H.E. and Ullman J. D.
Pearson Education
2. Introduction to Theory of Computation –Sipser 2nd edition Thomson
REFERENCES:
1. Introduction to Computer Theory, Daniel I.A. Cohen, John Wiley.
2. Introduction to languages and the Theory of Computation ,John C Martin, TMH
3. “Elements of Theory of Computation”, Lewis H.P. & Papadimition C.H. Pearson /PHI.
Course Code: MTH10304
C. Design and Analysis of Algorithms
UNIT I : INTRODUCTION
Mathematical preliminaries – Complexity Analysis – Asymptotic Notations – Average and worst case analysis – Stepwise refinement. Sorting : Bubble sort – Bucket sort – Heap sort – Radix sort. Searching : Sequential search – Binary search
UNIT II : DIVIDE AND CONQUER METHOD AND GREEDY METHOD
Divide and Conquer – General method – Quick sort – Finding maximum and minimum – Strassen’s matrix multiplication. Greedy method – General method – Tree vertex splitting problem – Job sequencing with deadlines
UNIT III : DYNAMIC PROGRAMMING Dynamic Programming - General method - Multistage graph – String editing. Backtracking – Basics – 8 Queen problem – Sum of subset problem. Branch and bound – Basics – Travelling Salesperson problem
UNIT IV : GRAPH ALGORITHM
Minimum cost spanning tree algorithms – Shortest path algorithms – Transitive closure – Topological ordering – Bi-connected and strongly connected components – R-connected graph – Even’s Kleitman’s algorithms
UNIT V : NP-HARD AND NP-COMPLETE PROBLEMS
NP complete & NP hard problems – Approximation algorithms – Fast fourier transform and algorithm – Lower Bound Trees – Oracle and Adversary arguments.
TEXT BOOK
- Horowitz E, Sahni .S & Rajasekar S– “Fundamentals of Computer Algorithms” – Galgotia Publications – 1998
REFERENCES:
- Sara Base – “ Computer Algorithms : Introduction to Design and Analysis” – Addison Wesley – 1998.
- Algorithms and Data Structures in C++ - Ammerald-Wiley Publications-2003.
Course Code: MTH10304
D. Open Sources Technologies
Unit I
Open Source - Introduction: Open Source – Open Source Vs. Commercial Software – What is Linux? – Free Software – Where I can use Linux? – Linux Kernel – Linux Distributions
Unit II
Linux - Introduction: Linux Essential Commands – Filesystem Concept – Standard Files – The Linux Security Model – Vi Editor – Partitions Creation – Shell Introduction – String Processing – Investigating and Managing Processes – Network Clients – Installing Application
Unit III
Apache - Introduction: Apache Explained – Starting, Stopping and Restarting Apache – Modifying the Default Configuration – Securing Apache – Set User and Group – Consider Allowing Access to Local Documentation – Don’t Allow public html Web Sites – Apache Control with .htaccess
Unit IV
MySQL - Introduction: The Show Databases and Table – The USE command – Create Database and Tables – Describe Table – Select, Insert, Update and Delete Statement – Some Administrative Detail – Table Joins – Loading and Dumping a database
Unit V
PHP - Introduction: General Syntactic Characteristics – PHP Scripting – Commenting your Code – Primitives, Operations and Expressions – PHP Variables – Operations and Expressions – Control Statement – Array – Functions – Basic Form Processing – File and Folder Access – Cookies – Sessions –Database Access with PHP – MYSQL Functions – Inserting Records – Selecting Records – Deleting Records – Update Records
Text Book:
1. Open Source Web Development with LAMP using Linux, Apache, MySQL,
PERL and PHP by James Lee & Brent Ware.