Transcription
Detailed SyllabusLecture-wise BreakupSubject Code15B11CI411Subject NameAlgorithms and Problem SolvingCreditsFaculty(Names)4Semester Even(specify Odd/Even)Semester IV Session 2018 -2019Month from: Jan to June 2019Contact HoursCoordinator(s)Dr. Manish Kumar Thakur, Varsha GargTeacher(s)(Alphabetically)J62 - Dr. Anita Sahoo, Deepti Singh, Kashav Ajmera, Dr. Manish KThakur, Sherry GargJ128 – Dr. Mukesh Saraswat, Dr. Neeraj Jain, Pulkit Mehendiratta,Varsha GargCOURSE OUTCOMESC214.1C214.24COGNITIVE LEVELSAnalyze the complexity of different algorithms using asymptoticAnalyze Level (Level 4)analysis.Select an appropriate data structure and apply related operations for aApply Level (Level 3)given problem.C214.3Apply algorithmic principles for solving a given problem.Apply Level (Level 3)C214.4Identify, formulate and design an efficient solution to a given problemCreate Level (Level 6)using appropriate data structure and algorithm design technique.ModuleNo.Subtitle of theModuleTopics in the Module1.IntroductionIntroduction to problem solving approach; AsymptoticAnalysis: Growth of Functions and Solving Recurrences;Notations- Big O, big omega, big theta, little o; Empiricalanalysis of sorting and searching algorithms – Merge sort,Quick sort, Heap sort, Radix sort, Count sort, Binarysearch, and Median searchSearch Trees: Segment tree, Interval Tree, and RB Tree;Priority queue using Binomial and Fibonacci Heap2.Search Trees andPriority Queue3.Design Technique:Divide andConquerDesign Technique:Greedy Algorithms4.5.6.Design Fundamentals of Divide and Conquer (D&C) approachusing Binary search, Quick sort, and Merge sort; Strassen‟smatrix multiplication; and Closest pair, etc.Introduction to greedy based solution approach; MinimumSpanning Trees (Prim‟s and Kruskal algorithms); ShortestPath using Dijkstra‟s algorithm; Fractional and 0/1Knapsack; Coinage problem; Bin packing; Job scheduling –Shortest job first, Shortest remaining job first, etc.; Graphcoloring; and Text compression using Huffman coding andShannon-Fano coding, etc.Review of backtracking based solution approach using Nqueen, and Rat in a maze; M-coloring problem;Hamiltonian Cycle detection; Travelling salesman problem;Network flowFundamentals of Dynamic programming based solutionapproach; 0/1 Knapsack ; Shortest path using FloydWarshall; Coinage problem; Matrix Chain Multiplication;No. ofLectures forthe module662646
7.8.9.Longest common subsequence; Longest increasingsequence, String editingNaïve String Matching, Finite Automata Matcher, RabinString AlgorithmsKarp matching algorithm, Knuth Morris Pratt, Tries; SuffixTree; and Suffix ArrayProblemSpaces Problem Spaces: States, goals and operators, FactoredandProblem representation (factoring state into variables) Uninformedsolving by searchsearch (BFS, DFS, DFS with iterative deepening),Heuristics and informed search (hill-climbing, generic bestfirst, A*)Tractable and Non- Efficiency and Tractability, P, NP, NP-Complete, NP- HardTractable Problems problemsTotal number of LecturesEvaluation CriteriaComponentsT1T2End Semester ExaminationTATotal64242Maximum Marks20203525 (Punctuality (5), Online Test on CP Portal (10), Mini-project (10))100Recommended Reading material: Author(s), Title, Edition, Publisher, Year of Publication etc. ( Text books,Reference Books, Journals, Reports, Websites etc. in the IEEE format)1.Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein , Introduction toAlgorithms, MIT Press, 3rd Edition, 20092.Steven Skiena ,The Algorithm Design Manual, Springer; 2nd edition , 20083.Knuth, The art of Computer Programming Volume 1, Fundamental Algorithms, Addison-WesleyProfessional; 3 edition,19974.Horowitz and Sahni, Fundamentals of Computer Algorithms, Computer Science Press, 19785.Sedgewick, Algorithms in C, 3rd edition. Addison Wesley, 20026.Weiss, Data Structures and Algorithm Analysis in C, Benjamin and Cummings Pub., 19947.Alfred V. Aho, J.E. Hopcroft, Jeffrey D. Ullman, Data Structures and Algorithms, Addison-Wesley Seriesin Computer Science and Information Processing, 19838.ACM Transactions on Algorithms (TALG)9.Algorithmica Journal, Springer10.Graphs and Combinatorics, Journal, Springer11.The ACM Journal of Experimental Algorithmics
Detailed SyllabusLab Session-wise BreakupSubject Code15B17CI471Subject NameAlgorithms and Problem Solving LabSemester: EVENSemester IV Session 2018 -2019Month from: Jan to June 2019Credits2Contact HoursFaculty(Names)Coordinator(s)Dr. Ankita Verma and Mr. Pulkit MehendirattaTeacher(s)(Alphabetically)Dr. Amarjeet Prajapati, Ms. Ankita Wadhwa, Dr. Ankita Verma, Dr.Anita Sahoo, Dr. Aparajita Nanda, Dr. Bharat Gupta, Ms. DeeptiSingh, Mr. Kashav Ajmera, Dr. Manish Thakur, Dr. Manju, Ms. InduChawla, Mr. Rohitpal Singh, Dr. Sangeeta Mittal, Dr. Satish Chandra,Ms. Sherry Garg, Dr. Shikha Jain, Ms. SonalCOURSE OUTCOMES4COGNITIVELEVELSRemember LevelC274.1Choose and define appropriate data structure to a given problemC274.2Understand various data structures and algorithm design techniques with the Understand Levelhelp of examples.(Level 2)C274.3Apply and build various algorithms and design techniques to solve thegiven problem.C274.4Analyze the algorithm by their complexity using asymptotic analysis.Analyze Level(Level 4)Evaluate the correctness and complexity of the algorithm for a givenproblem.Formulate, elaborate and design an efficient solution to a given problemusing appropriate data structure and algorithm design techniqueEvaluate Level(Level 5)Create Level(Level 6)C274.5C274.6(Level 1)Apply Level(Level 3)ModuleNo.Title of the ModuleList of Experiments1.Analysis of algorithms,Searching and sortingbased problems2.Search Trees andPriority Queue3.Design Technique:Divide and Conquer4.Design Technique:Introduction to problem solving approach; AsymptoticAnalysis; Solving Recurrences; Empirical analysis ofsorting and searching algorithms – Merge sort, Quicksort, Heap sort, Radix sort, Count sort, Binary search,and Median searchSearch Trees: Segment tree, Interval Tree, and RBTree; Priority queue using Binomial and FibonacciHeapProblems based on Divide and Conquer (D&C)approach such as Binary search, Quick sort, and Mergesort; and Closest pair, etc.Introduction to greedy based solution approach;Minimum Spanning Trees (Prim‟s and KruskalNo. of Labsfor themodule2444
algorithms); Shortest Path using Dijkstra‟s algorithm;Fractional and 0/1 Knapsack; Coinage problem; Binpacking; Job scheduling – Shortest job first, Shortestremaining job first, etc.; Graph coloring; and Textcompression using Hamming coding and ShannonFano coding, etc.Design Technique:Review of backtracking based solution approach usingBacktrackingN queen, and Rat in a maze; M-coloring problem;AlgorithmsHamiltonian Cycle detection; Travelling salesmanproblem; Network flowDynamic ProgrammingFundamentals of Dynamic programming basedsolution approach; 0/1 Knapsack ; Shortest path usingFloyd Warshall; Coinage problem; Matrix ChainMultiplication; Longest common subsequence;Longest increasing sequence, String editingNaïve String Matching, Finite Automata Matcher,String AlgorithmsRabin Karp matching algorithm, Knuth Morris Pratt,Tries; Suffix Tree; and Suffix ArrayProblem Spaces and Problem Spaces: States, goals and operators, FactoredProblem solving by representation (factoring state into variables)searchUninformed search (BFS, DFS, DFS with iterativedeepening), Heuristics and informed search (hillclimbing, generic best-first, A*)Project EvaluationDesigning an efficient solution to a given problemusing appropriate data structure and algorithm designtechniqueGreedy Algorithms5.6.7.8.9.Evaluation CriteriaComponentsLabtest 1Labtest 2Quiz(6)ProjectAttendanceTotal44222Maximum Marks20205*6 (each of 5 marks)1515100Recommended Reading material: Author(s), Title, Edition, Publisher, Year of Publication etc. ( Text books,Reference Books, Journals, Reports, Websites etc. in the IEEE format)1.Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein , Introduction toAlgorithms, MIT Press, 3rd Edition, 20092.Steven Skiena ,The Algorithm Design Manual, Springer; 2nd edition , 20083.Knuth, The art of Computer Programming Volume 1, Fundamental Algorithms, Addison-WesleyProfessional; 3 edition,19974.Horowitz and Sahni, Fundamentals of Computer Algorithms, Computer Science Press, 19785.Sedgewick, Algorithms in C, 3rd edition. Addison Wesley, 20026.Weiss, Data Structures and Algorithm Analysis in C, Benjamin and Cummings Pub., 19947.Alfred V. Aho, J.E. Hopcroft, Jeffrey D. Ullman, Data Structures and Algorithms, Addison-Wesley Seriesin Computer Science and Information Processing, 1983
Detailed SyllabusLecture-wise BreakupCourse Code15B11CI412Semester Even(specify Odd/Even)Course NameOperating Systems and System Programming3CreditsFaculty (Names)Semester IV Session 2018 -2019Month from Jan to June 2019Contact HoursCoordinator(s)1. Rupesh Kumar KoshariyaTeacher(s)(Alphabetically)1. Dr. Devpriya SoniPrakash Patel2. Dr Neha Bharil3. Dr Om4. Rupesh Kumar KoshariyaCOURSE OUTCOMESCOGNITIVE LEVELSUnderstanding fundamental of operating systems and systemC215.1C215.2C215.33-1-0Understand Level (C2)programming.Apply the process management concept and threads in OSApply Level (C3)Analyze the performance of various device and resourceAnalyze Level (C4)management techniques for different systems.Examine process synchronization and deadlock problem relatedAnalyze Level (C4)C215.4to inconsistency and race conditions with shared variables.C215.5Analyze the working of IO management and disk schedulingAnalyze Level (C4)Analyze and report appropriate OS design choices when buildingAnalyze Level (C4)C215.6real-world systems.ModuleNo.Title of theModuleTopics in the Module1.Introduction andHistorical contextof OperatingSystemsWhat are Operating Systems? All components Description,The Evolution of OS: Batch Systems, multi programmingsystems, Time sharing systems, Parallel systems, Real Timesystems, Distributed systems.22.Operating Structureand ArchitectureOperating system structure: Micro kernel, Monolithicsystems, Layered systems, Virtualization, Client-servermodel, Mobile Operating System.X86 architecture overview, Booting sequences, Bootloaders and their stages, BIOS and its routines, Interrupts.23.Process Concepts,Threads &Concurrency,SchedulingConcurrency &SynchronizationProcess concepts, Threads: Overview, Benefits, User andKernel threads, Multithreading models. Scheduling,Operations on processes, Cooperative processes, IPC,Scheduling criteria, Scheduling algorithms, Multipleprocessor scheduling, Process synchronization: Criticalsection problems, Semaphores, Synchronization hardwareNo. ofLectures forthe module10
issues,and monitors.4.DeadlockSystem model, Characterization, Methods for handlingdeadlocks. Deadlock prevention, Avoidance and detection,Recovery from deadlock35.MemoryManagement.Background, Swapping, Contiguous memory allocation,Paging, Segmentation, Segmentation with Paging, VirtualMemory66.File Systemmanagement andInput outputmanagementFile concept, Access models, Directory structure,Protection, File-system Structure, Allocation methods, Freespace management. Overview, I/O hardware, ApplicationI/O interface.7.Secondary StorageManagementDisk structure, Disk scheduling, Disk management., Swapspace management28.Fault and SecurityIssuesOverview of system security, Security methods and devices,Protection, access, and authentication, Models ofprotection, Memory protection.29.Distributed O.SInt. to distributed operating systems, synchronization anddeadlock in distributed systems1210.Case studies of OSWindows, Linux ,IBM211.SystemProgrammingIntroduction, Components of a Programming System:Assemblers, Loaders, Macros, Compliers, Formal System.212.MemoryAddressingMemory Multiplexing, Binding of Instruction and Data toMemory. Address Translation, Multi-Segment, SpecialRegisters, Wait/Exit, Address Translation.213.Interrupts andExceptionsSynchronous and asynchronous interrupts, Calling a SystemCall from User Space, INT, Trap Handling, System calldispatch, arguments and return value, Device Interrupts.214.KernelSynchronization,System Calls andSystem SignalsDisabling Interrupts, LockSynchronization PrimitivesLinux215.Device DriversBlock Device Drivers, Character Device Drivers, NetworkDrivers2Total number of Lectures42Evaluation CriteriaComponentsT1T2End Semester ExaminationTATotalImplementation,Maximum Marks20203525 (Quiz Assignment)100Recommended Reading material: Author(s), Title, Edition, Publisher, Year of Publication etc. ( Text books,Reference Books, Journals, Reports, Websites etc. in the IEEE format)
1.Charles Crowley “Operating System A Design Approach” TMH.2.Andrew S. Tanenbaum “Operating Systems Design and Implementation”, Third Edition, Prentice HallPublications 20063.A.S. Tanenbaum, “Modern Operating Systems”, 2nd edition, Prentice Hall India.4.A.Silberschatz, P.Galvin, G. Gagne, “Operating systems concepts” Willey international company (sixthedition)5.Gary Nutt, “Operating Systems – A modern perspective”, Pearson Education6.David Solomon and Mark Russinovich ,” Inside Microsoft Windows 2000”, Third Edition, MicorosoftPress7.D. M. Dhamdhere, “ Systems Programming and Operating systems” TMH, 2nd revised edition.20068.ACM/IEEE transactions on operating systems es Crowley “Operating System A Design Approach” TMH.
Operating System and System Programming LAB (15B11CI472)Detailed SyllabusLab-wise BreakupSemester Even(specify Odd/Even)Semester 4 Session 2018 -2019Month from Jan to MayCourse Code15B17CI472Course NameOperating System and System Programming LAB0-0-1CreditsFaculty (Names)Contact HoursCoordinator(s)Dr. SangeetaTeacher(s)(Alphabetically)1. Amanpreet kaur 2. Amarjeet Kaur 3. Hema N 4. Sangeeta5. Taj Alam6. Shilpa Budhkar 7. Parmeet Kaur 8. PurteeKohli 9. Vivek SinghCOURSE OUTCOMESCO12COGNITIVE LEVELSUnderstand Various Unix CommandsUnderstanding( Level-2)CO2Develop programs to create different types of processes usingpthread library under Linux environment.CO3( Level-3)Develop programs to implement resource management task likeCPU scheduling algorithms, deadlock handling.CO4ApplyApply( Level-3)Develop programs to implement and test various synchronizationApplytechniques like semaphores, binary semaphore and monitors via( Level-3)different classical test suites.CO5Design and analyse various disk-scheduling algorithms, memoryAnalyzingmanagement schemes, file management systems.(Level-4)ModuleNo.Title of the ModuleList of Experiments1.Introduction to UNIXLearning Unix Commands(file commands, directory commands,symolic links,terminal commands,help commands,informationcommands,useful cshell symbols,permissions and file storage(unix),permissions and file omizingnetworking,x-applicationsunix filters)2.Process Management Develop programs to create different types of processes under 2andThread Linux environment.Develop programs to create multitaskingManagementthreads using pthread library under Linux environment. Developprograms to implement interprocess communication3.CPU Scheduling,Deadlock HandlingDevelop programs to implement resource management task likeCPU scheduling algorithms(First Come First Served,ShortestJob First, Round Robin, Priority Scheduling, Multi level Queue,Multilevel Feedback), deadlock handling(Prevention, AvoidanceCO13
4.5.and Detection)Develop programs to implement and test variousProcesssynchronization techniques like semaphores, binary semaphoreSychronizationand monitors via different classical test suites.Disk Scheduling and Design and analyse various disk-scheduling algorithms.File ManagementDevelop programs to implement memory management schemes.Design, implement and assess file management systems (fileorganization and file directories) for different OS.45Evaluation CriteriaComponentsMaximum MarksLab Test 120Lab Test 220Day-to-Day(Evaluations, Viva, 60 Attendance, Project)Total100Recommended Reading material: Author(s), Title, Edition, Publisher, Year of Publication etc. (Text books,Reference Books, Journals, Reports, Websites etc. in the IEEE format)1.CharlesCrowley “Operating System A Design Approach”TMH.2.Andrew S. Tanenbaum “Operating Systems Design and Implementation”, Third Edition,Prentice HallPublications20063.A.S. Tanenbaum, “Modern Operating Systems”, 2nd edition, Prentice Hall India.4.A.Silberschatz, P.Galvin, G. Gagne, “Operating systems concepts” Willey international company (sixthedition)5.Gary Nutt, “Operating Systems – A modern perspective”, Pearson Education6.David Solomon and Mark Russinovich ,” Inside Microsoft Windows 2000”, Third Edition, MicorosoftPress7.D. M. Dhamdhere, “ Systems Programming and Operating systems” TMH, 2nd revised edition.20068.ACM/IEEE transactions on operating systems .berkeley.edu/static/sections/section8.pdf
Detailed SyllabusLecture-wise BreakupSubject CodeSubject fy Odd/Even)Semester Even Session 2018-2019Month from Jan19 to June19Fuzzy logic and Neural Networks4Contact HoursCoordinator(s)3-1-0Ms. Archana Purwar, Dr. Mukesh SaraswatMs. Ankita Verma ,Ms. Parul Agarwal, Mr. Shariq MurtuzaTeacher(s)(Alphabetically)SL.NO.COURSE OUTCOME(CO)COGNITIVE LEVEL(BLOOMS TAXONOMY)C230-2.1C230-2.2C230-2.3C230-2.4Explain the concepts of fuzziness involved in variousUnderstanding Levelsystems and fuzzy set theory.(Level 2)Apply the different methods of defuzzification, FuzzyApply LevelLogic and approximate reasoning(Level 3)Analyze different fuzzy inference systems for various realAnalyze Levelworld problems.(Level 4)Explain the fundamental concepts of Artificial NeuralUnderstanding LevelNetworks and various learning algorithms of supervised,(Level 2)unsupervised and associative memory networks.Apply artificial neural networks in various applications ly Levelcharacter(Level 3)recognition, etc.C230-2.6Analyze different artificial neural networks to solveAnalyze Levelpractical problems.(Level 4)Module No.Subtitle of the ModuleTopics in the moduleNo. ofLectures forthe module1.Introduction to Fuzzy LogicClassical Sets, Fuzzy Sets: operations and 4properties. Operations on fuzzy relations2.Membership functionsFeatures, fuzzification, methodsmembership value assignments3.Defuzzification4.Fuzzy RulesIntroduction; Lambda-Cuts for fuzzy sets 3and fuzzy relations; s, 4decomposition and aggregation of rules;of 2
5.Fuzzy inference systems(FIS) and applications6.Artificial Neural Network:An Introduction7.Supervised LearningNetwork8.Associate MemoryNetworks9.Unsupervised LearningNetwork10.Applications of ANNApproximate ReasoningFIS methods: Mamdani and Sugeno; 5Applications: such as fuzzy logic controletc.Fundamental concepts; Evolution of NN;Basic Models of ANN; connections andlearning; Terminologies such as PittsNeuron;HebNetworkPerceptron Network, Adaptive LinearNeuron; Multiple Adaptive LinearNeurons, Back Propagation Network,Radial Basis Function NetworkIntroduction and training algorithm tive memory; Hopfield NetworkIntroduction; Fixed Weight CompetitiveNets; Kohonen Self-Organizing FeatureMaps; Adaptive Resonance TheoryApplications:Recognition of characters,Fabric defect identification etc.Total number of LecturesEvaluation CriteriaComponentsT1T2End Semester ExaminationTATotal5566242Maximum Marks20203525100Recommended Reading material: Author(s), Title, Edition, Publisher, Year of Publication etc. ( Text books,Reference Books, Journals, Reports, Websites etc. in the IEEE format)1.Timothy J. Ross, “Fuzzy Logic with Engineering Applications,” McGraw Hill, 19952.Simon Haykin, “Neural Networks” Pearson Education3.B.Yegnanarayana, “Artificial Neural Networks,” PHI, India, 20064.S. N. Sivanandan and S.N. Deepa, “Principles of Soft Computing”, Wiley India, 2012.5.Limin Fu, “Neural Networks in Computer Intelligence,” McGraw Hill, 20036.Fakhreddine O. Karray and Clarence De Silva., “Soft Computing and Intelligent Systems Design,Theory, Tools and Applications,” Pearson Education, India, 20097.Simbrain and Matlab tools for simulation of ANN and FIS
Detailed SyllabusLecture-wise BreakupCourse Code 16B1NCI438SemesterEvenSemesterFourthSession 2018-19Month from Jan to June 2019CourseNameIntroduction Data warehouse and Data miningCredits4Faculty(Names)Coordinator(s)Mr. Avinash PandeyTeacher(s) (Alphabetically)1. Ms. Anuradha Gupta, 2. Avinash PandeyContact Hours3-1-0COURSE OUTCOMESC230-6.1Define the scope and understanding of data mining &warehousing concepts and interpret the different modelsused for OLAP and data preprocessingC230-6.2Apply the techniques of clustering, classification, frequentpattern mining, feature selection and visualization on realworld dataC230-6.3Analyzing data mining techniques to solve the real timeproblems.C230-6.4Evaluate the performance of different data-miningalgorithms including data preparation, modeling andperformance.Module No.1.23.Title of the ModuleCOGNITIVE LEVELSUnderstanding Level (Level 2)Applying Level (Level 3)Analyzing Level (Level 4)Evaluate Level (Level 5)Topics in the moduleNo. of Lecturesfor the moduleData warehousing components, data extraction,cleanup, and transformation tools –metadata; 8business analysis - reporting and query tools andIntroduction to data applications, online analytical processing (OLAP),ware housemultidimensional data model;Data MiningAssociationminingclassificationIntroduction, types of data, data miningfunctionalities, interestingness of patterns,integration of a data mining system with a data 8warehouse , issues , role of data pre-processingand data normalization;Mining Frequent Patterns, Associations andCorrelations – Mining Methods – Mining VariousruleKinds of Association Rules Classification and 10andPrediction - Basic Concepts, Decision TreeInduction, Bayesian Classification, SupportVector Machines, Other Classification Methods
4.5.Cluster AnalysisApplicationsTrendsinMiningTypes of Data in Cluster Analysis, ACategorization of Major Clustering Methods,Partitioning Methods, Hierarchical Methods,Density-Based Methods, Grid-Based Methods,Model-Based Clustering Methods, Clustering 9High-Dimensional Dataand Data Mining Applications: Social NetworkData Analysis, Mining Sequence Patterns in Biological 5Data, Text MiningTotal number of LecturesEvaluation CriteriaComponentsT1T2End Semester ExaminationTATotal40Maximum Marks20203525 (Quiz Mini-Project )100 MarksRecommended Reading material: Author(s), Title, Edition, Publisher, Year of Publication etc. (Textbooks, Reference Books, Journals, Reports, and Websites etc.)1.W. H. Inmon, "Building the Data Warehouse", 3rd edition2.Anahory and Murray, Data warehousing in the real world, Pearson education/Addison Wesley.3.Margaret Dunham, Data Mining: Introductory and Advanced Topics, Published by PrenticeHall.4.Jiawei Han, Micheline Kamber, "Data Mining: Concepts and Techniques", Morgan KaufmannPublishers, 2002. (www.cs.sfu.ca/ han/DMbook.html).
Detailed SyllabusSubject Code19B12CS211Subject NameAutomata Theory and ComputationsCredits4Faculty (Names)SemesterEVENContact HoursCoordinator(s)Dr. Ankit VidyarthiTeacher(s)(Alphabetically)Dr. Ankit VidyarthiSemester EVEN (IV Sem CSE )Session 2018 - 19 Month: January toJune 20193-1-0Course gnitive LevelRelate the basic difference between deterministic and nondeterministic computing machines.Summarize and translate the output based finite machinesSolve the problems related to language recognition for nonregular grammarInterpret the language accepted by tuning machineUnderstand (Level 2)Analyze problems related to undecidability and take part inapproximation theory.Analyze (Level 4)Understand (Level 2)Apply (Level 3)Apply (Level 3)Module No.Subtitle of the ModuleTopics in the module1.Introduction2.Regular expression3.Context free grammar4.Push Down Automata5.Turing machinesAlphabets, Strings and Languages, Automata,Grammars, Deterministic finite Automata(DFA), State transition graph, Transition table,Language of DFA, Nondeterministic finiteAutomata (NFA), NFA with epsilon transition,Language of NFA, Equivalence of NFA andDFA, Minimization of Finite AutomataOperators of regular expression and theirprecedence, Algebraic laws for Regularexpressions, Kleen‟s Theorem, Regularexpression to FA, DFA to Regular expression,Non Regular Languages, Pumping Lemma forregular Languages, FA with output: Moore andMealy machineDerivation, Derivation trees, Ambiguity inGrammer, Inherent ambiguity, Ambiguousto Unambiguous CFG, Useless symbols,Simplification of CFGs, Normal forms forCFGs: CNF and GNF, Closure properties ofCFLs, Decision Properties of CFLs:Emptiness, Finiteness and MembershipLanguage of PDA, Acceptance by Final state,Acceptance by empty stack, DeterministicPDA, Equivalence of PDA and CFG, CFG toPDA and PDA to CFG, Two stack PDALanguage acceptance by TM, Variants ofTuring Machine, TM as Computer of IntegerNo. of Lecturesfor the module77788
6.UndecidabilityEvaluation CriteriaComponentsT1T2End Semester ExaminationTATotalfunctions, Universal TM, Church‟s Thesis,Recursive and recursively enumerablelanguages, Halting problemIntroduction to Undecidability, Undecidableproblems about TMs, Post correspondenceproblem (PCP), Modified PCP, Introductionto recursive function theory5Total number of Lectures42Maximum Marks20203525100 MarksRecommended Reading material: Author(s), Title, Edition, Publisher, Year of Publication etc. ( Text books,Reference Books, Journals, Reports, Websites etc. in the IEEE format)1.J. Hopcroft, R. Motwani, and J. Ullman. “Introduction to Automata Theory, Languages, andComputation”, 3rd edition, 2007, Pearson/Addison-Wesley2P. Linz., “Introduction to Formal Languages and Automata”, 6th edition, 2017, Jones and Barlett3.Michael Sipser, ”Introduction to the Theory of Computation”, 3rd edition 2013, Cengage Learning.4.K.L.P. Mishra and N.Chandrasekaran, “Theory of Computer Science : Automata, Languages andComputation”, PHI Learning Private Limited, Delhi India.5.Harry R. Lewis and Christos H. Papadimitriou, Elements of the theory of Computation, SecondEdition, Prentice-Hall of India Pvt. Ltd.3
Detailed SyllabusLecture-wise BreakupSemester ODD(specify Odd/Even)Course Code18B12CS311Course NameOOAD (Object Oriented Analysis and Design)3-1-0CreditsFaculty (Names)Semester IV Session 2018 -2019Month from January 2019 – June 2019Coordinator(s)Dr. Sandeep Kumar SinghTeacher(s)(Alphabetically) COURSE 30-4.64Contact HoursCOGNITIVE LEVELSIllustrate algorithmic (procedural) decomposition and Object1. Understand LevelOriented decomposition.(Level 2)Dissect the requirements to identify the potential use cases,2. Analyzing Level (Levelclasses and objects in the system.4)Build UML diagrams such as class diagram, object diagram for3.structural modelling and state chart diagram, sequencediagrams for behavioural modelling.Apply object oriented design principles to solve real world4.problems.Analyse and implement complex software systems using the5.Gang of Four (GoF) design patterns, e.g., creational patterns,structural patterns, behavioural patterns, etc.Estimate the complexity of object oriented designs usingseveral metrics.Apply Level (Level 3)Apply Level (Level 3)Analyse Level (Level 4)Evaluate Level (Level 5)ModuleNo.Title of theModuleTopics in the Module1.Introduction toObject OrientedAnalysis andDesignObject OrientedAnalysisObject OrientedDesignObject OrientedDesignWhat is OOAD, Why OOAD, Benefits and Costs,Understanding the challenges OOAD can address.3Identifying Classes and Objects, Responsibilities,Relationships in problem domain, Object ModelUse Case Diagrams, Class Diagram, Object DiagramSequence Diagram, State DiagramsObject Constraint Language(OCL), Use Case Modeling,Modelling and Implementing Static Behaviour andDynamic Behaviour.SOLID principles and its applications6Overview of Design Patterns, Design Patterns TypesCreational, Structural and Behavioral Patterns. Understandand Apply various design patterns in different scenarios,Reusable Design Patterns.Understanding and Analyzing Software Design Metrics forObject Oriented Software.72.3.4.5.Design Principles6.Design Patterns7.OO Design MetricsNo. ofLectures forthe module6636
8.OOAD CaseStudiesApplying OOAD in different contexts7Total number of LecturesEvaluation CriteriaComponentsT1T2End Semester ExaminationTATotal44Maximum Marks20203525 (To be mapped from Class Test 1,2,3)100Recommended Reading material: Author(s), Title, Edition, Publisher, Year of Publication etc. ( Text books,Reference Books, Journals, Reports, Websites etc. in the IEEE format)1.2.3.4.Object-Oriented Modeling and Design with UML (2nd Edition) Michael R. Blaha; James R RumbaughHead First Object-Oriented Analysis and Design A Brain Friendly Guide to OOA&D By Brett McLaughlin, GaryPollice, David WestOBJECT-ORIENTED ANALYSIS AND DESIGN With applications Third EDITION Grady Booch Rational SantaClara, CaliforniaObject Oriented Analysis and Design Andrew Haigh5.UML and C A practical approach to OO Development6.Testing Object-oriented Systems: Models, Patterns, and Tools Book by Robert V. Binder7.A Practical Guide to Testing Object-oriented Software Book by David A. Sykes and John D. McGregor8.Object Management Group (OMG): http://www.omg.org/. This is the official Site for UML.9.Design Patterns: Elements of Reusab
Detailed Syllabus Lab Session-wise Breakup Subject Code 15B17CI471 Semester: EVEN Semester IV Session 2018 -2019 Month from: Jan to June 2019 Subject Name Algorithms and Problem Solving Lab Credits 2 Contact Hours 4 Faculty (Names) Coordinator(s
