-
Notifications
You must be signed in to change notification settings - Fork 1
/
syllabus.html
193 lines (101 loc) · 6.57 KB
/
syllabus.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
<html><script type="text/javascript">window["_gaUserPrefs"] = { ioo : function() { return true; } }</script><head><meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><style type="text/css">
:root #content > #right > .dose > .dosesingle,
:root #content > #center > .dose > .dosesingle
{ display: none !important; }</style><link rel="stylesheet" type="text/css" href="chrome-extension://pkehgijcmpdhfbdbbnkijodmdjhbjlgp/skin/socialwidgets.css"></head><body><h2>Information on the M.Tech/MS/PhD admission Test</h2>
<p>Following are 3 groups of topics. In the admissions test, each candidate will be asked to answer questions from at least 2 groups of
topics. Candidates who want to work in theoretical computer science must choose Group 1, candidates interested to work in
Systems/Networks/Cyber Security must choose Group 2, and candidates interested in data mining, machine learning and data sciences must
choose Group 3. Other group(s) can be chosen freely. </p>
<p>
</p><h3><span style="color:#BC1414"> Group 1: Theory List
</span></h3>
<ol>
<li><h4>Discrete Mathematics:</h4></li>
Basic counting techniques (permutation and combination), pigeon-hole principle, simple recurrence relations, generating functions,
principle of inclusion and exclusion (set cardinality related problems)
<li><h4>Graph Theory:</h4></li>
Graphs, Directed Graphs, Trees, Connectivity, Cycles, Paths, Hamiltonian and Eulerian cycles, subgraphs, cliques, graph coloring,
planarity
<li><h4>Basic Number Theory: </h4></li>
Modular Arithmetic, Fermat’s Little Theorem, principles of RSA (discrete logarithm problem, primality, integer factorization)
<li><h4>Logic:</h4></li>
propositional logic, tautologies, axiom systems, deduction, soundness and completeness, quantification
<li><h4>Algebra:</h4></li>
Simple Group theory -- groups, subgroups, cosets, Lagrange’s theorem, fields, finite fields
<li><h4>Data Structures and Algorithms:</h4>
</li>
Elementary data structures -- arrays, lists, queues, stacks, and their applications, algorithms for various manipulations of these data
structures (sort, search, insert, delete, computing size), basic paradigms of designing algorithms (greedy algorithms, divide-and-conquer
approaches, dynamic programming), analyzing time and space complexity of algorithms (O(n) vs O(logn) vs. O(nlogn) vs. O(n^2) etc.)
<li><h4>Computability and Complexity:</h4></li>
P vs. NP, NP-Completeness, simple polynomial time reductions, Turing machines, undecidability.
<p></p>
<h3></h3><h4></h4>
</ol>
<h3><span style="color:#BC1414">Group 2: Systems List
</span></h3>
<ol>
<li><h4>
Architecture :</h4></li>
Instruction Set architecture, pipelined implementation of instruction set architecture, caches, cache organization, cache replacement,
virtual memory, demand paging, page replacement
<li><h4>Operating System:</h4>
</li>
Unix/Linux operating system structure, processes, threads, process scheduling, concurrent processes and threads, virtual memory
management, unix/linux process memory layout (memory segmentation), program stack, and heap and their roles in program run-time, file
system permissions, basic unix/linux commands, system calls, kernel vs. user space programs, shared libraries (static vs. dynamically
linked). Familiarity with virtual machines, cloud based computing.
<li><h4>Networking:</h4></li>
OSI seven layer reference model, TCP/IP protocol stack, division of functionalities in various layers, basic functionalities of TCP and
IP, DNS, some protocols (OSPF, BGP, ARP)
<li><h4>Compilers: </h4></li>
Lexical analysis (Deterministic Finite State Automata), Parsing (LALR, LL(1)), peephole optimization, code motion.
<li><h4>Databases:</h4></li>
Basic SQL queries, relations and relational database
<li><h4>Programming:</h4></li>
Good knowledge of C or C++ or Java, client/server systems, simple socket based programming, knowledge of GDB or any debugging tool.
Web: http vs. https, cookies, functionalities of web client (browser) vs. web servers
<h3><span style="color:#1A14BC"> Some good resources for studying:</span></h3>
<ul>
<li><p>Computer Organization and Design, Fourth Edition (or any edition) : The Hardware/Software Interface (The Morgan Kaufmann
Series in Computer Architecture and Design) 4th Edition by David A. Patterson and John L. Hennessy. </p></li>
<li><p>Modern Operating Systems (4th Edition): Andrew S. Tanenbaum, Herbert Bos (any Edition) </p>
</li>
<li><p>Computer Networks, Andrew S. Tanenbaum, 4th Edition (or any edition), Prentice Hall. </p></li>
</ul></ol>
<h3><span style="color:#BC1414">Group 3: Statistics and Data Sciences
</span></h3>
<ol>
<li><h4>Linear Algebra:</h4></li>
vector spaces, dot products and their properties, orthogonality, norms and their properties, Cauchy-Schwartz inequality, hyperplanes,
halfspaces, balls, ellipsoids.
<li><h4>Matrix Algebra:</h4></li>
determinants, eigenvalues-eigenvectors, matrix norms (Frobenius, spectral).
<li><h4>Convex Analysis: </h4>
</li>
linear combination of vectors (convex combination, conic combination, affine combination), notion of gradient for multivariate functions,
convex sets and convex functions (definitions only).
<li><h4>Probability theory:</h4></li>
event spaces and their properties, probability measure, cumulative distribution, random variables, marginal and joint distributions,
expectation, variance, independence of events and random variables, linearity of expectation.
Statistics: distributions and their properties (Bernoulli, Binomial, Multinomial, Poisson, Gaussian).
</ol>
<h3><span style="color:#1A14BC">Some good resources for studying:</span></h3>
<p>The following scribed notes cover 1), 3), 4), 5) in a succinct manner with examples. However, these notes are merely indicative of the
topics and not to be treated as the sole or even recommended sources for these topics. Students are advised to refer to more elaborate
treatments of these topics from textbooks as well.
</p><ol>
<li>http://www.cse.iitk.ac.in/users/purushot/courses/olo/2015-16-w/material/lec2.pdf</li>
<li>http://www.cse.iitk.ac.in/users/purushot/courses/olo/2015-16-w/material/lec3.pdf</li>
<li>http://www.cse.iitk.ac.in/users/piyush/courses/pml_winter16/slides_lec2.pdf</li>
<p></p></ol>
<h3><span style="color:#14BC33">Programming List</span></h3>
<ol>
<li>Iterators, loops, nesting</li>
<li>Recursion</li>
<li>Memoization techniques</li>
<li>Encapsulation primitives (structures, classes - depending on language)</li>
<li>Threads, Mutex, semaphores</li>
<li>Proficiency in programming in general </li>
</ol>
</body></html>