Difference between revisions of "Test"

Algorithms:

• Analysis, Asymptotic notation, Notions of space and time complexity, Worst and average case analysis;
• Design: Greedy approach, Dynamic programming, Divide-and-conquer;
• Tree and graph traversals, Connected components, Spanning trees, Shortest paths;
• Hashing, Sorting, Searching.
• Asymptotic analysis (best, worst, average cases) of time and space, upper and lower bounds, Basic concepts of complexity classes – P, NP, NP-hard, NP-complete.

Data Structures:

• Abstract data types, Arrays, Stacks, Queues
• Linked Lists
• Trees, Binary search trees, Binary heaps.

• ER-model, Relational model (relational algebra, tuple calculus)
• Database design (integrity constraints, normal forms)
• Query languages (SQL)
• File structures (sequential files, indexing, B and B+ trees)
• Transactions and concurrency control

• Lexical analysis, Parsing
• Syntax directed translation, Runtime environments
• Intermediate and target code generation, Basics of code optimization.

• Processes, Threads, Inter-process communication
• Concurrency, Synchronization
• Deadlock
• CPU scheduling
• Memory management and virtual memory
• File systems, I/O systems, Protection and security.

• Regular languages and finite automata
• Context free languages and Push-down automata
• Recursively enumerable sets and Turing machines
• Undecidability.

• Machine instructions and addressing modes
• ALU and data-path, CPU control design
• Memory interface, I/O interface (Interrupt and DMA mode)
• Instruction pipelining
• Cache and main memory, Secondary storage.

• ISO/OSI stack, LAN technologies (Ethernet, Token ring)
• Flow and error control techniques, Routing algorithms, Congestion control
• TCP/UDP and sockets, IP(v4), Application layer protocols (icmp, dns, smtp, pop, ftp, http)
• Basic concepts of hubs, switches, gateways, and routers
• Network security – basic concepts of public key and private key cryptography, digital signature, firewalls

• Programming in C
• Functions, Recursion
• Parameter passing, Scope, Binding

• Logic functions, Minimization
• Design and synthesis of combinational and sequential circuits
• Number representation and computer arithmetic (fixed and floating point)

• Information gathering, requirement and feasibility analysis data flow diagrams
• Process specifications, input/output design, process life cycle
• Planning and managing the project, design, coding
• Testing, implementation, maintenance.

• HTML, XML
• Basic concepts of client-server computing

• Permutations, Combinations
• Counting, Summation
• Generating functions, recurrence relations, asymptotics

• Conditional Probability
• Mean, Median, Mode and Standard Deviation
• Random Variables
• Distributions; uniform, normal, exponential, Poisson, Binomial.

• Propositional Logic
• First Order Logic

Set Theory & Algebra

• Sets, Relations, Functions
• Groups
• Partial Orders, Lattice
• Boolean Algebra

• Connectivity, spanning trees
• Cut vertices & edges
• Covering, matching, independent sets
• Colouring, Planarity, Isomorphism

• Algebra of matrices, determinants
• Systems of linear equations
• Eigen values and Eigen vectors

• LU decomposition for systems of linear equations
• Numerical solutions of non-linear algebraic equations by Secant, Bisection and Newton-Raphson Methods
• Numerical integration by trapezoidal and Simpson’s rules

• Limit, Continuity & differentiability
• Mean value theorems
• Theorems of integral calculus, evaluation of definite & improper integrals
• Partial derivatives, Total derivatives, maxima & minima

• Numerical computation
• Numerical estimation
• Numerical reasoning and data interpretation

• English grammar, sentence completion
• Verbal analogies, word groups
• Instructions, critical reasoning and verbal deduction