B. Formal Languages and Automata

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

1. Horowitz E, Sahni .S & Rajasekar S– “Fundamentals of Computer Algorithms” – Galgotia Publications – 1998

REFERENCES:

1. Sara Base – “ Computer Algorithms : Introduction to Design and Analysis” – Addison Wesley – 1998.
2. 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.