1. Data Structures and Algorithms

Topics

• Asymptotic notation, complexity analysis
• Data structures (stacks, queues, priority queues, linked lists, hash tables, binary search trees, AVL trees, red-black trees)
• Advanced data structures (B-trees, binomial trees, Fibonacci heaps, data structures for disjoint sets)
• Recurrences
• Sorting and order statistics (heapsort, quicksort, sorting in linear time, medians and order statistics)
• Dynamic programming
• Greedy algorithms
• Amortized analysis
• Elementary graph algorithms (search, topological sort, strongly connected components)
• Minimum spanning trees
• Single-source shortest paths
• All-pairs shortest paths
• Maximum flow
• NP Completeness

References

• T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, The MIT Press / McGraw-Hill Book Company, 1994.
• Mark Allen Weiss, Data Structures and Algorithm Analysis in C++ 2nd Ed. Addison Wesley

2. Programming Languages and Compiler Design

Topics Related to Programming Languages

• Describing Syntax and Semantics
• Names, Bindings, Type Checking, and Scopes
• Data Types
• Expressions and the Assignment Statement
• Statement-Level Control Structures
• Procedures
• Abstract Data Types
• Functional Programming Languages
• Logic Programming Languages
• Object Oriented Design

Topics Related to Programming Languages

• Lexical processing: tokenization and lexical analysis
• Parsing
• Basics of symbol table organization, type checking and handling of user-defined types
• Data representation issues, memory management
• Runtime environment organization
• Code generation and optimization

References

• Ravi Sethi, Programming Languages Concepts and Constructs, 2nd ed., Addison-Wesley.
• Alfred Aho, Ravi Sethi, Jeffrey Ullman, and Compilers: Principles, Techniques, and Tools, Addison-Wesley, 1985.

3. Database Systems and Software Engineering

Topics Related to Database Systems

• Data Models, E-R Model. Database Architecture.
• Relational Algebra and Calculi.
• Data Manipulation Languages: SQL,QUEL, QBE.
• Functional Dependency Theory. Normalization of Relations.
• Multivalued and Join Dependencies.
• Query processing and optimization techniques
• Indexing techniques
• Transaction processing. Concurrency Control Techniques
• Serializability. Locking, deadlocks, timestamping.
• Security and integrity, authorization, and encryption

References

• Raghu Ramakrishnan, Johannes Gehrke, Database Management Systems, second edition, McGraw Hill, 2000.

Topics Related to Software Engineering

• Software development processes
• Agile software development
• Software modelling (UML)
• Requirements engineering
• Software architecture
• Object oriented design
• Software design patterns
• Software verification and validation

References

• Object Oriented Software Engineering: Practical Software Development using UML and Java (2nd edition), Timothy C. Lethbridge and Robert Laganiere, McGraw-Hill, 2005, ISBN 0-07-710908-2
• Software Engineering (10th edition), Ian Sommerville, Pearson, 2016, ISBN

  978-0133943030

4. Computer Architecture and Digital Design

Topics

• Processor: Datapath and Control
• Pipelining (pipelined control, hazards, exceptions, performance)
• Memory Hierarchy (caches, virtual memory)
• Processor-Peripheral Interfacing
• Number systems and conversion, boolean algebra, the assertion level concept
• Minterm and maxterm expansions, Karnaugh maps and Quine McCluskey minimization
• Combinatorial logic circuit design, NAND and NOR gate based design
• State machines and sequential circuits, flip-flops, minimization of state tables, state assignment
• Higher level digital system design using SSI-MSI blocks such as multiplexers/decoders, adders, memory and programmable gate arrays
• Bus oriented systems
• Asynchronous sequential circuits, flow tables, timing hazards

References

• David A. Patterson, John L. Hennessy, Computer Organization and Design The Hardware/Software Interface, Morgan Kaufmann Publishers, 1994.
• M. Morris Mano, Charles R. Kime, Logic and Computer Design Fundamentals 2nd Edition, Prentice Hall.

5. Operating Systems and Computer Networks

Topics Related to Operating Systems

• Processes & Interprocess Communication
• Process Scheduling
• Memory Management
• File Systems
• Input/Output
• Deadlocks
• Naming, security, and reliability
• Resource sharing, and remote execution
• Network architectures

Topics Related to Computer Networks

• Local and wide-area networks
• Network technologies and topologies
• TCP/IP protocols (application, transport and network layers)
• Routing, addressing, naming, multicasting, switching, internetworking
• Congestion/flow/error control
• Medium access control
• Data Link Layer protocols
• Physical layer basics
• Quality of service
• Network security

References

• A. S. Tanenbaum, Modern Operating Systems, Prentice-Hall, 1992.
• A. S. Tanenbaum, Computer Networks 4th ed., Prentice-Hall, 2003 (reference).
• W. Stallings, Computer Networking with Internet Protocols and Technology, Prentice-Hall, 2004 (main text).

6. Automata Theory and Theory of Computation

Topics

• Deterministic Finite State Automata DFA ; definitions , tabular and graphical representations and uses of DFA as language acceptors,.
• Non-deterministic Finite Automata NDFA with and without epsilon (invisible) transitions ; conversion of NFDA to equivalent DFA ; minimal state DFA and algorithms to compute them,
• Algebra of regular expressions RE ; language definitions as RE expressions ; conversions between various finite automata and REs,
• Computational complexity of basic algorithms involving finite automata and REs
• Turing Machines TMs ; decidability, semidecidability and computability ; various versions of TMs (multi-tape, multi-dimensional , random access, nondeterministic etc.) and equivalences between them,
• The halting problem and other derived undecidable problems ; Turing computability
• Basic definitions and problems related to computational complexity ; polynomial , NP and NP-complete problems ; Cook's theorem and some basic NP-completeness proofs
• PSPACE-complete problems ; definitions and basic proofs,
• Definition of context-free grammars and applications,
• General grammars (or re-writing systems),
• Recursive functions and basic equivalence result between TMs , general grammars and recursive functions,
• Recursion theorem , self-reproduction and consequences,

References

• P. Linz, An Introduction to Formal Languages and Automata 3rd ed., Jones and Bartlett Pub., 2000.
• J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation 2nd ed., Addison-Wesley, 2000.

7. Computer Graphics

Topics

• Overview of graphics systems, applications
• Graphics and raster graphics algorithms for drawing in 2D
• Geometrical transformations in 2D and 3D
• Viewing in 3D
• Computer animation principles
• Color and shading; Shaders
• Texture mapping
• Illumination and Radiosity
• Modeling shapes with polygonal meshes
• Modeling curves: implicit, explicit and parametric; emphasis on cubic polynomials
• Surface modeling: Bicubic Bezier polynomials, splines, nurbs
• Visible surface determination
• Virtual Environments

References

• Fundamentals of Graphics 3rd Edition http://www.cs.cornell.edu/~srm/fcg3/

8. Machine Learning

Topics

• Basics of probability and statistics
• Parameter estimation, MLE, MAP
• Model evaluation
• Model complexity, overfitting, bias/variance, regularization
• Supervised classification models

• K-NN
• Decision trees
• Bayes classifier
• Naive bayes classifier
• Logistic regression
• Support vector machines
• Neural networks
• Deep learning fundamentals
• Ensemble methods

• Regression

• Linear regression
• Polynomial and Ridge regression
• Regression trees

• Dimensionality reduction

• Feature selection, extraction
• PCA

• Clustering

• K-means
• Gaussian Mixture Models
• Spectral clustering

References

• Introduction to Machine Learning by Ethem Alpaydin,
• Pattern Recognition and Machine Learning by Christopher M. Bishop
• Machine Learning by Tom Mitchell,
• Pattern classification by Richard O. Duda, Peter E. Hart [and] David G. Stork.
• Machine Learning: A Probabilistic Perspective by Kevin R Murphy

9. Artificial Intelligence

Topics

• Search Algorithms

• Solving problems by searching [RN, Ch3]
• Blind search: breadth-first search, uniform cost search, depth-first search, depth-first iterative deepening [RN, Ch3]
• Heuristic search: best-first search, A* search, iterative-deepening A*, weighted A* [RN, Ch3]
• Local search: hill-climbing search, simulated annealing, local beam search, genetic algorithms [RN, Ch4]
• Adversarial search: minimax algorithm, alpha-beta pruning, depth-limited search with evaluation functions, expectimax search [RN, Ch5]
• Backtracking search: constraint satisfaction problems (CSPs), constraint propagation, forward checking, arc/path consistency, backtracking search for CSPs, local search for CSPs [RN, Ch6]

• Knowledge Representation and Reasoning

• Propositional logic: satisfiability, entailment, deduction by resolution, SAT, DPLL, representing combinatorial search problems in propositional logic [RN, Ch7]
• First-order logic (FOL): satisfiability, entailment, deduction by resolution, representing knowledge in FOL [RN, Ch8 & Ch9]
• Planning: Situation Calculus, planning by FOL resolution, STRIPS, ADL, planning by searching [RN, Ch10]
• Reasoning under uncertainty: quantifying uncertainty, Bayesian networks (BNs), semantics of BNs, exact inference in BNs, variable elimination algorithm, approximate inference in BNs, sampling methods [RN, Ch13 & Ch14]
• Decision making under uncertainty: preferences, utilities, policies, decision trees/networks, value of information, Markov decision processes, value iteration, policy iteration [RN, Ch16 & Ch17]

• Learning [RN, Ch18 ]

• Supervised learning: decision trees; Bayes classifier; linear regression; neural networks
• Gradient descent
• Model Evaluation: overfitting, loss
• Ensembles

References

• [RN] Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach (3rd Edition).

10. Cryptography and Network Security

Topics

• Cryptography and Computer and Network Security Concepts
• Classical (Historical) Encryption Techniques
• Symmetric Cryptography, Block Ciphers and Related Cryptosystems (AES, DES, 3DES, etc.)
• Block Cipher Modes of Operation
• Random Bit Generation and Stream Ciphers
• Public-Key Cryptography, RSA and DH
• Digital Signatures
• Cryptographic Hash Functions
• Message Authentication Codes
• Key Management and Distribution
• User and Message Authentication Protocols
• Transport-Level Security (SSL, TLS, SSH)
• Electronic Mail Security and Related Protocols
• IP Security
• Firewalls
• Intrusion Detection Systems

Reference

• W. Stallings, Cryptography And Network Security: Principles And Practice, 6th or 7th ed., Pearson, 2016. Missing topics can be found in earlier versions of that book or as online chapters (if you cannot find, please write to Albert Levi)