Warning
Rough Notes
GRE General Test Scores:
- Date: 05-08
- Registration # 6634-905
Verbal : 530 - Below 68% Quantitative: 780 - Below 90% Analytical Writing: 4.0 - Below 33%
Test Scores:
TOEFL Internet Based Test:
Registration: 0000 0000 0587 7817 Test Date: 03 August 2008
TOEFL iBT Scaled Scores:
Reading 29 Listening 28 Speaking 28 Writing 22
Total 107
GRE Subject Test
Test Date: 11/08.08 COMPUT SCI
Score Recipients Requested
Graduate Institution Department
4833 0402 5248 0402 2074 1201 4704 0402
Score: 530. Percentile: 08%
http://edulix.com/infobank/index.php Edulix Info Banks
Registration Number 4614110 Test Center Number 10044 Test Date: 11/07/09
Name: Senthil Kumaran
All applications must be submitted by midnight on Dec. 15 EST. No exceptions will be made.
http://www.cmu.edu/prospective/graduate.shtml https://www.ece.cmu.edu/prospective/graduate/application/ - Dec 15
MIT - Media Lab and Algorithms Group - Dec 15 https://apply.eecs.mit.edu/ http://web.mit.edu/admissions/graduate/how_to_apply/application_deadlines.html http://www.pmg.lcs.mit.edu/ Media Lab - Dec 15 https://www.applyweb.com/apply/mitg/menu.html
University of Toronto - 7 December 2009. http://web.cs.toronto.edu/Page4.aspx https://apply.sgs.utoronto.ca/home.aspx
Texas A & M - (Tentative - 15 Dec 2009)
Rochester Institute of Technology - July 1
University of Delware - Fall: February 1 & July 1 http://www.udel.edu/gradoffice/apply/index.html
University of Masachusetts Armhest http://www.umass.edu/gradschool/prospective_students_deadlines_for_application.htm
Universtiy of Portland - February 1. http://www.up.edu/admissions/default.aspx?cid=8079&pid=2171
3. I have an inclination towards research and occupying myself with interesting fundamental problems, and I also have certain ability to translat the answers to the fundamental problems to more concrete ones in the products and come out with new innovations. This is supported by four inventions that have been filed with USPTO by my former employer Dell. They were important contributions even in the business, because only 4 out of 600 people in the group had a track recording of having 4 or more patents.
GRE General Test Scores:
- Date: 05-08
- Registration # 6634-905
Verbal : 530 - Below 68% Quantitative: 780 - Below 90% Analytical Writing: 4.0 - Below 33%
Test Scores:
TOEFL Internet Based Test:
Registration: 0000 0000 0587 7817 Test Date: 03 August 2008
TOEFL iBT Scaled Scores:
Reading 29 Listening 28 Speaking 28 Writing 22
Total 107
GRE Subject Test
Test Date: 11/08.08 COMPUT SCI
Score Recipients Requested
Graduate Institution Department
4833 0402 5248 0402 2074 1201 4704 0402
Score: 530. Percentile: 08%
http://edulix.com/infobank/index.php Edulix Info Banks
Registration Number 4614110 Test Center Number 10044 Test Date: 11/07/09
Name: Senthil Kumaran
This is the list of twelve best physical sciences monologue of the 20th century according to American Scientist. Found this at `TAOCP<http://www-cs-faculty.stanford.edu/%7Euno/taocp.html>`_ page.
A finite automata is a 5-tuple (Q, E, ∂, q, F), where:
Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker’s list also appears on the list from the Dean’s office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.
A problem is of type P, if it can be solved using an algorithm whose running time grows no faster than some fixed power of number of symbols required to specify the initial data.
A = {1,10,100}
SET = { n | n ∈ Z and n > 5 }
SET = { n | n ∈ N and n < 5 }
SET = {aba}
SET = { ∊ }
SET = ∅
Answer: { ∅, {x},{y},{x,y}}
A x B has a*b elements. A x B stands for cartesian product which is formed as set of tuples taking each element from each set.
So for 2 x 2 set. {a,b} x {c, d} = { (a,c), (a,d), (b,c), (b,d)} Thus there are 4 elements.
1.4 Examine the following formal descriptions of sets so that you understand which members they contain . Write a short informal English description for each set.
It is the set of all odd natural numbers.
It is the set of all even real numbers.
It is set of even natural numbers.
It is set of natural numbers which are divisible by both 2 and 3.
It is set of binary numbers which are bi-directional (that is read the same from left to right and also from right to left).
It is set of all integers.
{x, y} = { ∅, {x}, {y}, {x,y}}
{x, y, z} = { ∅, {x} , {y}, {z}, {x, y} , {y, z}, {x, z}, {x, y, z} }
{a, b, c, d} = { ∅, {a}, {b}, {c}, {d}, {a,b}, {a,c}, {a,d}, {b, c}, {b, d}, {c, d}, {a,b,c}, {a,b,d}, {c,a,d}, {d,a,b}, {a,b,c,d}}
Answer: cC0 + cC1 + cC2 + cC3 + ... + cCc
Take c = 4 Answer = 4C0 + 4C1 + 4C2 + 4C3 + 4C4 = 16
Actually it is 2^n^. I have to find the proof for this.
Let X be the set{1,2,3,4,5} and Y be the set {6,7,8,9,10}. The unary function f: X -> Y and the binary function g: X x Y -> Y are described in the following tables.
||*n*|| f(n)||
||1|| 6||
||2|| 7||
||3|| 6||
||4|| 7||
||5|| 6||
||*g*||6|| 7|| 8|| 9|| 10||
||1||10|| 10|| 10|| 10|| 10||
||2||7|| 8|| 9|| 10|| 6||
||3||7|| 7|| 8|| 8|| 9||
||4||9|| 8|| 7|| 6|| 10||
||5||6|| 6|| 6|| 6|| 6||
Ans: 7
range = {1,2,3,4,5} and domain = {6,7}
Ans: 6
domain: {(1,6),(1,7),(1,8),(1,9),(1,10) .... (5,10)} range: {6,7,8,9,10}
Ans: 8
Ans: (a+b) ^ 2
Ans: / operator?
Ans: multiplication by -1.
Ans: Drawing in the Notebook
Degree of 1 is 3. Degree of 3 is 2. Path from 3 to 4 is 3-2-4.
Ans: {[1,2,3,4,5,6},{(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)}}
1.10 The error is dividing by (a-b) which is 0 because we assume a = b. Dividing by zero is not-defined and hence the proof is not valid.
1.11 The Induction Step is wrong. After assuming that H=K+1 are of same color instead of proving mathematically that K+n can be true, it goes about sub-classing the same set and without proceeding to prove a generality.
1.12 Every graph with 2 or more nodes contains 2 nodes that have equal degrees.
Each edge contributes equally to 2 adjoing nodes or when there is not a edge, the two seperate nodes have an equal lose. Taking both the situations into account, for a given graph with 2 or more nodes, there are 2 nodes that have same degree.
1.13
Clique of a graph is subgraph in which every 2 nodes are connected by an edge. Anti-Clique is the subgraph in which every 2 nodes are not connected by an edge. This is also called as independent set. Show that every graph with n-nodes contains either a clique or an anti-clique with at-least 1/2log2 n nodes.
Answer: This is Ramsey’s therom. Generalized for k=2. For which the minimum number of nodes required is 3.
1.14
Theorem 1.25
P(t) = P*M^t - Y ( M^t - 1) / (M - 1)
P is the principal sum I is the interest rate Y is the monthly payment. M is convenience term for writing M = 1 + I/12
This problem can be solved by using a calculator.
There are 2^903 ways to arrange red, green strings among 43 pegs so each pair is either connected by red string or by a green string.
1) Ramsey Theorem: http://www.math.uchicago.edu/~mileti/museum/ramsey.html
In the book proof of Ramsey Theorem, it divides the nodes into connected (forming cliques) and disconnected (forming anti-cliques), but checking if the degree is greater than 1/2 of no. of remaining nodes, is not understood. (It is like is having a theorem and and following a procedure in order to prove the theorem, there is no counter intuitive example given).
Finite Automata and their probabilitics counter parts, Markov chains are used in Speech Recognition.
FSM are closed under reversal.
Convert a Non Deterministic FSM to a Deterministics FSM, the example of every 1 followed by two zeros.
Reversing a machine, wherein final state is the start state and arrows get reversed and start state is the new final state.
Theory of Computation Folklore. To convert to the minimize the Deterministic FSM * Reverse the Machine ( This would make it Non Deterministic) * Convert to Deterministic FSM * Reverse the machine (Again Non Deterministic FSM) * Covert to Deterministic FSM again. This would be minimal machine. I kind of trust Shai Simonson’s word on that. :)
The above method of minimizing involves DFA to NFA and it is exponential time complex.
There are better methods using Polynomial Time Complexity using Dynamic Programming Strategy.
Union of two machines using NFA.
Intersection of two machines ( Using De Morgan’s law. WOW!!!) But that is costly again, you can do it by working it out with pair or states as in cartesian product of the two machines.
- Union means the set of accept states are either of the accept states in M1 and M2.
- Intersection means that set of accept states are BOTH the accept state in M1 and M2.
Union, Intersection and Complement. Any two of the operations are enough and the third one is guaranteed.
Complement Operations means changing 1s to 0s.
Finding Intersection using Non Determinism is difficult, because Non Determinism does not mix well with OR operations, It mixes well with AND Operation.
NFA ~ DFA ~ REGULAR EXPRESSIONS ~ NFA ( They form a nice group).
Regular Grammars ~ DFA
Trying to represent 0^n^1^n^ can be represented by FSM??
Well, if I try it, equal number of 0s and 1s can be represented by FSM, but equal number of 0s followed by equal number of 1s ( this involves counting) cannot be represented by FSM.
Anything that involves counting cannot be represented by FSM.
The FSM can also be tested using Pumping Lemma, because they test a particular kind of regularity.
Regular sets can be pumped out at Regular Intervals and are identified by pumping lemma.
Thus Pumping lemmas are yet another test for FSM..
Big O denotes a limiting behavior of function when the argument tends towards a particular value or infinity, usually in terms of a simpler function.
Big O notation allows its users to simplify functions in order to concentrate on their growth rate. Different functions with same growth rate may be represented with the same big O notation.
Description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function; associated with big O are several related symbols o, Ω, ω, and Θ to describe other kinds of bounds on the asymptotic growth rate.
f(x) = O(g(x)) as x -> ∞
T(n) ∊ O(n^2^) - That is T(n) has n^2^ time complexity.
O(n^c^) and O(c^n^) are very different. The latter grows much, much faster, no matter how big the constant c is (as long as it is greater than one).
Changing units may or may not affect the order of the resulting algorithm. Changing units is equivalent to multiplying the appropriate variable by a constant wherever it appears. For example, if an algorithm runs in the order of n^2^, replacing n by cn means the algorithm runs in the order of c^2^n^2^, and the big O notation ignores the constant c^2^. This can be written as c^2^n^2^ ∊ O(n^2^) . If, however, an algorithm runs in the order of 2^n^, replacing n with cn gives 2^cn^ = (2^c^)^n^. This is not equivalent to 2^n^ in general.
What is Amortized time?
What is inverse Akerman function or even straight Akerman function?
disjoint set?
Priority Queue?
Polylogarithmic? AKS Primality Test?
What is KD-Tree?
Lineararithmic?
Fast Fourier Transform?
Shortest Path on a weighted Digraph with the Floyd-Warshall Algorithm.
Make a list of 10 general-purpose processors including the details like clock speed, word size and manufacturer.
||*uP*||Clock Speed || Word Size || Manufacturer||
||Intel Core i7 EE || 3.33 `GHz` || 64 bit(bus-size) || Intel||
||AMD K10 || 3.1 `GHz` || 64 bit || AMD ||
||ARM 11 ||528 `MHz` ||32 bit ||ARM||
||Cyrix 5x86 || 133 `MHz` || 32 bit || Cyrix||
||DEC 21-40535-04||275 `MHz` ||64 bit ||DEC ||
||IDT Win Chip `W2A` ||300 `MHz` ||32 bit ||IDT||
||Motorola 68060 ||75 Mega Hz ||32 bit ||Motorola||
||NS 320 16 N -10 ||10 Mega Hz ||32 bit ||National Semiconductor||
||NEC D70216 L || 10 Mega Hz || 16 bit || NEC ||
||Nex Gen Nx 586 || 100 Mega Hz || 32 bit || Nex Gen||
||C7 D || 2 Giga Hz || 32 bit || VIA||
||Crusoe TM 5800 || 933 Mega Hz || 64 bit || Transmeta||
The number of bits a CPU can process at once; word size is usually the same as the width of the CPU’s external data bus, but sometimes is smaller. Justify that CPU in personal computer is a general purpose processor.
- It is not just for sine and cosine but can do a large number of small scale mathematical calculations.
- It can fairly handle the graphic requirements.
- It can do multi-tasking to satisfy the users requirements.
In a mathematical sense, only three operations are needed to compute any computable function: add one, subtract one and branch if a value is non-zero.
Asymptote is a tangent to a curve at infinity. Something that is asymptotic relates to an asymptote, which is defined as “A Line whose distance to a given curve tends to zero.”
Something asymptotic refers to a limiting behaviour based on a single variable and a desired measure. A common notation that removes constants is called Big O notation, where O means “order of”. Big O denotes the upper bound, how much the time complexity will grow. If we say that a function is O(N) then if N doubles, the funtion’s time complexity at most will double.
I don’t understand this aspect: But because the array is split in half each time, the number of steps is always going to be equal to the base-2 logarithm of N, which is considerably less than O(N).
http://www.eternallyconfuzzled.com/jsw_home.aspx
Big-O is not a mathematical function. It has no inverse.
S -> L D A B C R
LDA -> LAAD
ADA -> AAD
ADB -> ABBD
BDB -> BBD
BDC -> BCCD
CDC -> CCD
DR -> ER
CE -> EC
BE -> EB
AE -> EA
LE -> LD
A->0
B->1
C->0
R->e
LD->e
S -> 0S1M |e
M -> 0M |e
* 0^p^1^n^0^n^
* Context Free Language are closed under concatenation.
* Intersection the above two? 0^n^1^n^0^n^
* Context Free Grammare are not closed under Intersection.
* CFG Are NOT closed under Complement.
<stmt> -> <assgn> | <ifthen> | <ifthenelse> |<beginend>
<ifthen> -> if <expression> then <stmt>
<ifthenelse> -> if <expression> then <stmt> else <stmt>
A-> BC
B -> o
Ars Digita University taught BE level courses in Computer Science
1 - 2
2 - 4
3 - 7
4 - 11
n - Tn + 1 ?
R ⊕ W = (R+W) -(RW)
R ⊕ W = (-RW) + (-WR)
-(A⋂B) = -A ⋃ -B
-(A⋃B) = -A ⋂ -B
(R+W)-(RW)
(R -(RW) ) + (W -(RW))
(R (-R + -W)) + (W (-R + -W))
(R-R) + R-W + W-R + W-W
R-W + W-R
I discovered later that I wasn’t even a very good C programmer, hiding my ignorance of structures, _malloc( ) and free( ), setjmp( ) and longjmp( ),_ and other “sophisticated” concepts, scuttling away in shame when the subjects came up in conversation instead of reaching out for new knowledge.
Should I apply for Ph.D or M.S?
My aspiration is to pursue Ph.D because I have an inclination towards research and like solving problems especially going into depth with in a small area. But, as I have only Bachelors degree, I am trying to figure out what should I prove in order for universities to recognize and admit me into Ph.D program.
I would not hesistate to do a Masters in passing, if there is any objective requirement to for it in order to pursue research in that particular area. But I would be able to evaluate it best after considering the cases like finance.
About me:
I am a Computer Science graduate, interested in programming, algorithms, maths and general problem solving techniques. I graduted from a college called National Engineering College, Tamil Nadu, India. It’s a private college, though an established one in South India. I had tried for GATE and failed 2 times and I had tried for Subject GRE and have failed 2 times and I am trying it again.
I have an inclination towards research and occupying myself with interesting fundamental problems, and I also have certain ability to translat the answers to the fundamental problems to more concrete ones in the products and come out with new innovations. This is supported by four inventions that have been filed with USPTO by my former employer Dell.
Well, I personally do not consider them as my achievements because I still feel that patents from companies are towards securing business value than a real fundamental breakthrough, but they were important contributions becuase only few people (4 to be exact in the group of 600) had filed more than 1 patent over the 5 years I was at Dell.
I had been doing software testing and more occupied with Engineering processes than software architecture, that I had to move myself to Software Developer’s role on my own initiation. So, I studied the basic books again, solved all the problems in Kernighan and Ritchie (sometimes honestly and some times not-so honestly) and started trying for moving to a Developers role. I got some breakthrough in a developer in test inside Automation team and then I joined the Python Core Developers through Google’s Summer of Code Program. I started working on enhancing the urllib module and now I am currently the maintainer of the urllib module. I fix bugs on the module and entertain the feature requests that come in. I also participate in the discussions in the evolution of Python language and library. I plan to carry with this task (possibly increasing my contributions) through out my post-graduation studies as well.
== Endian-ness ==
1 2 3 4 - Big Endian
0x00 0x00 0x00 0x01
4 3 2 1 - Little Endian
$ python -c "import struct;print 'little' if ord(struct.pack('L',1)[0]) else 'big'"
little
LU’R’ U L’U’R U2
[http://en.wikipedia.org/wiki/Logo_(programming_language) Logo Programming Language]
Visual Programming Enviroments
Discussion on Visual Programming Environments and how it affects the way we approach Programming. This is specifically an indepth analysis of Alice Programming developed at Carnegie Mellon University, which has proven to be helpful to Educators, Students and is seen as a barrier breaker when learning programming.
The purpose of the Alice course is the provide the students with the conceptual underpinnings of the fundamental programming principles.
Use of LOGO Style EGO Centric Coordinate System. Key Framing Programming by Demonstrating Visual Programming as well as scripting.
Alice is a tool for describing time based and interactive behaviour of 3D Objects.
1. Processing http://www.processing.org/
- Solve either the three problems in Section A or the single problem in Section B. You must implement your algorithms as working programs in the C language.
- Try to keep your programs as simple as possible. Take care of proper program layout and embellish it with useful comments at the appropriate places.
- Make your programs as robust as possible. All borderline cases should be handled properly and the program should exit gracefully under all circumstances.
Section A
Given a positive number N, generate all the prime numbers from 2 to N. The primary emphasis in the solution to this problem should be on speed. In addition, you must not consume an inordinate amount of memory.
Implement an arbitrary precision arithmetic calculator. You should implement addition, subtraction, multiplication and division in the respective order. Try to make your program as fast as possible and keep memory usage to the bare minimum.
Given two strings S1 and S2, determine whether S2 occurs as a substring in S1 and if so, find the first occurrence of S2 in S1. Your program should be extremely fast. Try to come up with a linear solution to the problem.
Section B
Implement a simple filesystem within a normal file on the hard disk, i.e. treat the file as a virtual disk and implement the filesystem by manipulating records within the file.
You are free to devise your own scheme for the file system but it should minimally support the following operations:
- Create - Create a virtual hard disk on a file of the specified size and “format” it. Formatting would essentially involve initialising disk allocation structures and whatever else you need to do before you can have a valid filesystem.
- Open, Read, Write, Close - All the normal file operations to use the files.
- Delete, Rename - Remove unwanted files or rename existing files.
Do not place artificial restrictions on file names, sizes, etc.
In addition, if you can, provide support for folders (also known as directories) which can be arbitrarily nested. Provide all the common operations for folders.
You should implement this as a library of routines that can be used by anyone wanting to treat a file as a filesystem. Demonstrate the correctness of your routines by writing a demo program that lets one manipulate files interactively.