7/27/2015

[Link]/~acad/intranet/CourseStructure/[Link]

CourseStructureandSyllabiforMTechinComputerScienceandEngineering

Semester1
CourseCode

CourseTitle

Semester2

LTPC

CourseCode

CourseTitle

LTPC

CS512

DataStructuresandAlgorithms

3006

CS515

TheoryofComputation

3006

CS514

MathematicsforComputer
Science

4008

XXxxx

Elective2

3006*

CS548

ComputerSystems

3006

XXxxx

Elective3

3006*

XXxxx

Elective1

3006*

XXxxx

Elective4

3006*

CS513

ProgrammingLab

0033

CS558

SystemsLab

0033

130329*

LTPC

CourseCode

Total

Semester3
CourseCode
CS698

CourseTitle

Total

120327*

Semester4
CourseTitle

LTPC

Thesis

00024

CS699

Thesis

00024

Total

00024

Total

00024

*Indicatesminimumrequiredcredits..

CS512DataStructuresandAlgorithms(3006)

Performance of algorithms: space and time complexity, asymptotics Design techniques: the greedy
method, divideandconquer, dynamic programming Sorting and searching Graph Algorithms Priority
Queues: lists, heaps, binomial heaps, Fibonacci heaps Hashing Search Trees: binary search trees, red
blacktrees,AVLtrees,splaytrees,BtreesThedisjointsetunionproblemStringmatchingStrings:suffix
arrays,triesRandomizeddatastructures:skiplistsAselectionofadvancedtopics.

Texts:
[Link],CELeiserson,RLRivestandCStein,IntroductiontoAlgorithms,MITPress,2001.
[Link],AlgorithmDesign,AddisonWesley,2005.

References:
[Link],[Link],TheDesignandAnalysisofComputerAlgorithms,Addison
Wesley,1974.
[Link],DataStructures,AlgorithmsandApplicationsinC++,McGrawHill,2001.
[Link],AlgorithmDesign:Foundations,AnalysisandInternetExamples,
JohnWiley&Sons,2001.

CS513ProgrammingLab(0033)

Experiments would be designed to provide handson experience in programming data structures and
algorithms,tolearnafewsystemsprogrammingtools,andscripting.

References:
1. [Link],[Link],[Link],IntroductiontoAlgorithms,MITPress,
2001.
[Link],AlgorithmDesign,AddisonWesley,2005,
3. [Link],DataStructuresandAlgorithmAnalysisinC++,AddisonWesley,2007

CS514MathematicsforComputerScience(4008)
Reviewofsets,functions,relationsLogic:formulae,interpretations,methodsofproofinpropositionaland
predicatelogic Number theory: division algorithm, Euclid's algorithm, fundamental theorem of arithmetic,
Chinese remainder theorem Combinatorics: permutations, combinations, partitions, recurrences,
generating functions Graph Theory: isomorphism, complete graphs, bipartite graphs, matchings,
colourability, planarity Algebraic Structures: semigroups, groups, subgroups, homomorphisms, rings,
integraldomains,fields,latticesandbooleanalgebrasLinearalgebra:systemoflinearequations,matrices,
vector spaces, linear transformations, Eigen vectors, diagonalization Probability: conditional probability,
randomvariables,probabilitydistributions,Markov'sinequality,ChebyshevandChernoffBounds.
[Link]

1/3

7/27/2015

[Link]/~acad/intranet/CourseStructure/[Link]

Texts:
[Link],ElementsofDiscreteMathematics,2ndEd.,TataMcGrawHill,2000.
2.R. C. Penner, Discrete Mathematics: Proof Techniques and Mathematical Structures, World
Scientific,1999.

References:
1.R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd Ed., AddisonWesley,
1994.
[Link],DiscreteMathematics&itsApplications,6thEd.,TataMcGrawHill,2007.
[Link],DiscreteStructures,Logic,andComputability,3rdEd.,JonesandBartlett,2010.
[Link],GraphTheory,PrenticeHallofIndia,1974.
[Link],Schaum's Outline of Theory and Problems of DiscreteMathematics,
2ndEd.,TataMcGrawHill,1999.
[Link],Probability&StatisticsWith Reliability, Queuing And Computer Science Applications,
PrenticeHallofIndia,1994.
[Link],ProbabilityandComputingRandomizedAlgorithmsandProbabilistic
Analysis,CambridgeUniversityPress,2005.
[Link],IntroductiontoLinearAlgebra,Springer,2008.

CS515TheoryofComputation(3006)
Automata and Languages: finite automata and regular expressions, pushdown automata and contextfree
grammars, pumping lemmas and closure proprties of regular and contextfree languages, noncontextfree
languagesComputabilitytheory:theChurchTuring thesis, Hilbert's problem, decidability, halting problem,
reducibility Complexity theory: time and space complexity, Classes P, NP, NPcomplete, PSPACE, and
PSPACEcompleteIntractability:hierarchytheorem,Relativization,Circuitcomplexity.

Texts:
[Link],IntroductiontotheTheoryofComputation,Thomson,2004.
[Link],ElementsoftheTheoryofComputation,PHI,1981.

References:
1. [Link] and J. D. Ullman,Introductionto Automata Theory, Languages and Computation,
Narosa,1979.
2. S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University
Press,2009.
[Link],ComputationalComplexity,AddisonWesleyPublishingCompany,1994.
[Link],TheoryofComputation,Springer,2006.
5. D. S. Garey and G. Johnson, Computers and Intractability: A Guide to the Theory of NP
Completeness,Freeman,NewYork,1979.

CS548ComputerSystems(3006)

Review of concepts of operating systems: Processes, threads, interprocess communication, scheduling,

Texts/References:

[Link],[Link],OperatingSystemConcepts,7thEd,JohnWileyand
Sons,2004.
[Link],ComputerNetworking:ATopdownapproach,3rdEd,PearsonIndia,
2004.
[Link],AdvancedConceptsinOperatingSystems,McGrawHill,1994.
[Link],DistributedSystems:PrinciplesandParadigms,PrenticeHall
India,2007.

CS558ComputerSystemsLab(0033)

Experimentswouldbedesignedtoprovidehandsonexperienceincomputersystems,tolearnunixsystem
calls,posixthreads,operatingsystemconcepts,networkprogrammingandsimulations.

Texts/References:

1. W. R. Stevens, UNIX Network Programming, Volume 1: Networking APIs: Sockets and XTI,
PrenticeHall,1998.
2. W. R. Stevens, UNIXNetwork Programming, Volume 2: InterprocessCommunications, Prentice
Hall,1999.
[Link],AdvancedProgrammingintheUNIXEnvironment,AddisonWesley,1992.
[Link]

2/3

7/27/2015

[Link]/~acad/intranet/CourseStructure/[Link]

[Link]

3/3