Today I gave the final exam for compiler course and managed to get a decent score.
Course website says, "This course will discuss the major ideas used today in the implementation of programming language compilers, including lexical analysis, parsing, syntax-directed translation, abstract syntax trees, types and type checking, intermediate languages, dataflow analysis, program optimization, code generation, and runtime systems". And, the course was really able to cover the said topics in decent detail.
But, real learning of the course was not in the videos or quizzes or exams. It was in the optional project, where you were expected to code 4 major phases of a compiler namely lexical analysis, parsing, semantic analysis and assembly code generation. So, essentially, I wrote a fully functional compiler for COOL language that has many features found in Java and C++.
Programming assignment#1 was to write the lexical analyzer for COOL, which will take a COOL program and produce the Tokens. We were expected to use lexer generator, JLex, where you can give your token specifications using regexps and java code that creates required token on regex match. Though lectures taught you how actually regexes can be implemented by converting them to NFAs, which can be simulated directly or can be converted to DFAs and can have a table driven implementation, but use of JLex did not let me code that. Because of time pressure I could only do the assignment with JLex. I would like it even more if assignment is modeled in a way so that you don't use JLex but code the regex implementation by hand.
Programming assignment#2 was to write the parser that would generate the AST from the tokens returned by lexer from previous assignment. Again, we used a parser generator called Java CUP, that would generate the parser given the CFG grammar specification with associativity and precedence rules.Though you learn the theory of parsing(from lecture videos and readings), but assignment does not really need you to hand code one. I would like it even more if I hand code the parser as this is an academic exercise(however, I have earlier written a recursive-descent parser).
The fun part begins now..
Programming assignment#3 is when you have no tools. You have an AST and need to hand code all the semantic rules of the language. Most of the code you write here is to do static type checking. You traverse the whole AST, I used visitor pattern, at every node(which are different kind of expressions supported by the language, for example method dispatch, if expression, case expression, assignment etc). You ensure that types declared and inferred from the expression are in agreement with the type rules defined in the language. COOL supports SELF TYPES and that adds to the type checker complexity.
Programming assignment#4 gets even better. After you're done with compile time semantic rules check, you generate MIPS assembly code for the given COOL program. This is the place where you become one with the machine. Here you have to carefully convert all the high level expressions to assembly code. You never realize while coding in a high level language that when it comes to assembly then processor, mostly, only knows how to go about blindly executing the instruction sequence laid out in memory and occasionally make jumps to other memory addresses. It is just an eye opener to learn the tricks of translating high level language constructs to simple load, move, jump and branch instructions with few registers and memory.
While doing these assignment, I had to spend a lot of time with paper and pen to think hard and form a solution.. for example how and what should go in a stack frame when a method is called, how you locate its correct implementation and jump back to the return address after completion.
Another eye opener was that, once the assembly code is generated, then there are no "identifiers", all you have is the memory addresses in the form of labels and offsets to locations in your stack frame :).
Another side thing I noticed is that It is an essential skill to draw yourself away from the laptop, think in isolation and be able to write code on paper in a not really compilable version of your choice of implementation language.
Besides keeping me super busy outside day job, This compiler project has enlightened me. And, I am really really thankful to coursera. Having done this compiler for a statically typed language(and a interpreter for a lisp language, Scheme), after so many years of coding... Now, I feel like, I can "see through" the languages. And, The feeling is just amazing.
Thursday, July 5, 2012
Friday, February 10, 2012
mvn helpers
recently needed to setup/debug/refactor a complex multi-module maven project.. some maven stuff, learned the hard way....
Generate eclipse setup files in a maven project...
mvn eclipse:eclipse -DdownloadSources -DdownloadJavadocs
Default eclipse may point M2_REPO to ~/.m2 . If you want to change that, you have to do so in Windows->Preferences->Maven->User Settings .
Skip tests while building the project..
-Dmaven.test.skip skips both test compilation and execution
-DskipTests=true skips test execution only
Run tests from named test class only..
-Dtest=<fully-qualified-test-class-name> Executing a class containing main(String[] args) method..
mvn exec:java -Dexec.mainClass=
Build selected modules of a parent pom..
mvn package -pl mod1, mod2 [-am]
-pl : list of modules
-am : also make the dependencies
Build starting from a given module
mvn package -rf :mod3
Downloading dependencies of the project
mvn dependency:copy-dependencies -DexcludeScope=provided
(More at http://maven.apache.org/plugins/maven-dependency-plugin/copy-dependencies-mojo.html )
Getting description of goals supported by a plugin
mvn help:describe -Dplugin=<name> (if plugin group has been added to pluginGroups, look in settings reference below)
or
mvn help:describe -DgroupId=<groupId> -DartifactId=<artifactId>
.. add -Dfull to get more detailed information on goals.
Check out other goals in help plugin itself
mvn help:describe -Dplugin=help -Dfull
some important ones are...
mvn help:effective-settings
mvn help:active-profiles
mvn help:effective-pom
Finding dependencies of your project
mvn dependency:analyze
mvn dependency:tree
dependency graph: http://mvnplugins.fusesource.org/maven/1.8/maven-graph-plugin/
You can also remotely debug the tests run through maven by using
-Dmaven.surefire.debug
flag. Optionally you can specify all the jvm debugging related parameters using
-Dmaven.surefire.debug="
" (Reference)
You can run a specific testcase with -Dtest flag as described on Ref . Tests can altogether be skipped using -DskipTests flag.
For testng, you can annotate a test like @Test(groups = {"xyz"}) and then just run these tests by using flag -Dgroups=xyz (remember to escape '=' in shell by using '\=')
try using
<plugin>
<artifactId>maven-assembly-plugin</artifactId>
<configuration>
<descriptorRefs>
<descriptorRef>jar-with-dependencies</descriptorRef>
</descriptorRefs>
</configuration>
<executions>
<execution>
<id>make-my-jar-with-dependencies</id>
<phase>package</phase>
<goals>
<goal>single</goal>
</goals>
</execution>
</executions>
</plugin>
Downloading all dependencies--
copies all dependencies to target/dependency, See plugin doc for more options to refine what is copied.
mvn dependency:copy-dependencie [-DexcludeTransitive -DoutputDirectory=<some_dir>]
Resources:
Pom Reference
Settings Reference
Books:
http://maven.apache.org/articles.html
http://www.sonatype.com/books/mvnref-book/reference/
Generate eclipse setup files in a maven project...
mvn eclipse:eclipse -DdownloadSources -DdownloadJavadocs
Default eclipse may point M2_REPO to ~/.m2 . If you want to change that, you have to do so in Windows->Preferences->Maven->User Settings .
Skip tests while building the project..
-Dmaven.test.skip skips both test compilation and execution
-DskipTests=true skips test execution only
Run tests from named test class only..
-Dtest=
mvn exec:java -Dexec.mainClass=
mvn dependency:copy-dependencies -DexcludeScope=provided
mvn help:describe -Dplugin=<name> (if plugin group has been added to pluginGroups, look in settings reference below)
or
mvn help:describe -DgroupId=
.. add -Dfull to get more detailed information on goals.
Check out other goals in help plugin itself
mvn help:describe -Dplugin=help -Dfull
some important ones are...
mvn help:effective-settings
mvn help:active-profiles
mvn help:effective-pom
mvn dependency:analyze
mvn dependency:tree
-Xdebug -Xrunjdwp:transport=dt_socket,server=y,suspend=y,address=8000 -Xnoagent -Djava.compiler=NONE
<plugin>
<artifactId>maven-assembly-plugin</artifactId>
<configuration>
<descriptorRefs>
<descriptorRef>jar-with-dependencies</descriptorRef>
</descriptorRefs>
</configuration>
<executions>
<execution>
<id>make-my-jar-with-dependencies</id>
<phase>package</phase>
<goals>
<goal>single</goal>
</goals>
</execution>
</executions>
</plugin>
Downloading all dependencies--
copies all dependencies to target/dependency, See plugin doc for more options to refine what is copied.
mvn dependency:copy-dependencie [-DexcludeTransitive -DoutputDirectory=<some_dir>]
Pom Reference
Settings Reference
Books:
http://maven.apache.org/articles.html
http://www.sonatype.com/books/mvnref-book/reference/
Friday, January 27, 2012
screen command cheatsheet
>>screen #starts new screen session
>>screen -S <session-name> #starts new screen session with given name
>>screen -ls #list already running screen sessions
>>screen -r <pid/name>#re-attach to a screen session
>>screen -dr <pid/name> #detach other and attach yourself to given screen session
List all commands: C-a ?
New Window: C-a c
Moving Across windows..
Show Windows: C-a w
Next Window: C-a n
Prev Window: C-a p
Goto Window: C-a [0-9]
Last Window: C-a C-a
Sending literal C-a to shell: C-a a
Detach session: C-a d
Reattach session: C-a r
Toggle Scroll buffer mode: C-a ESC or C-a C-[ #then use C-n or C-p to navigate, in this mode you can use space to set first mark and then '>' to send the selected test to /tmp/screen-exchange file
Kill Window: C-a k or exit, killing last window will automatically kill screen session
Quit Screen: C-a :quit
Screen User's Manual
>>screen -S <session-name> #starts new screen session with given name
>>screen -ls #list already running screen sessions
>>screen -r
List all commands: C-a ?
New Window: C-a c
Moving Across windows..
Show Windows: C-a w
Next Window: C-a n
Prev Window: C-a p
Goto Window: C-a [0-9]
Last Window: C-a C-a
Reattach session: C-a r
Quit Screen: C-a :quit
Screen User's Manual
Thursday, September 15, 2011
Linear Algebra Notes
I'm so excited that stanford is offering free online version of machine learning course this year, where you get to participate online like a student, finish the assignments(in time) and give the exams.
Linear algebra is one must have prerequisite for ML. I've done a course on same while I was in college. But, at that time, I learned more of calculations in linear algebra(multiplying matrices, calculating row reduced echelon form, calculating eigenvalues etc) and less of concepts. Now, the time has come when I really need to "understand" what those computations mean and what is the significance.
So, I watched some video lectures from MIT OCW Linear algebra course. I definitely recommend these lectures to everyone looking for a solid introduction to the topic.
As always, for better understanding and quick review, I took some notes. They can be found here.
Linear algebra is one must have prerequisite for ML. I've done a course on same while I was in college. But, at that time, I learned more of calculations in linear algebra(multiplying matrices, calculating row reduced echelon form, calculating eigenvalues etc) and less of concepts. Now, the time has come when I really need to "understand" what those computations mean and what is the significance.
So, I watched some video lectures from MIT OCW Linear algebra course. I definitely recommend these lectures to everyone looking for a solid introduction to the topic.
As always, for better understanding and quick review, I took some notes. They can be found here.
Monday, July 18, 2011
the XOR trick
XOR is one of the standard bitwise operation. Here is the truth table for same..
1 XOR 0 = 1
0 XOR 1 = 1
0 XOR 0 = 0
1 XOR 1 = 0
The trick that XOR provides is that if you take XOR of two N bit numbers(let say c = a XOR b), which is another N bit number then given one number(a or b) and the XOR result(c) you can determine the other number.
Basically( it can be easily proved by using truth tables)
a XOR (a XOR b) = b
b XOR (a XOR b) = a
This trick can be used to, for example, swap two integers without using a temporary variable.
Let say you wanted to swap x and y. Here is the required sequence.
x = x XOR y
y = x XOR y (y becomes old x)
x = x XOR y (x becomes old y)
In another use of this trick, you can implement doubly-linked list from a singly linked list without storing two pointers(prev, next) but just one(prev XOR next).
1 XOR 0 = 1
0 XOR 1 = 1
0 XOR 0 = 0
1 XOR 1 = 0
The trick that XOR provides is that if you take XOR of two N bit numbers(let say c = a XOR b), which is another N bit number then given one number(a or b) and the XOR result(c) you can determine the other number.
Basically( it can be easily proved by using truth tables)
a XOR (a XOR b) = b
b XOR (a XOR b) = a
This trick can be used to, for example, swap two integers without using a temporary variable.
Let say you wanted to swap x and y. Here is the required sequence.
x = x XOR y
y = x XOR y (y becomes old x)
x = x XOR y (x becomes old y)
In another use of this trick, you can implement doubly-linked list from a singly linked list without storing two pointers(prev, next) but just one(prev XOR next).
Friday, July 8, 2011
How to be a good (algorithmic) problem solver
Over the years I have worked with many algorithmic problems and there is definitely a pattern in the approach for solving them. I would like to note down my current approach of solving them and many books talk about similar stuff.
0. Solve by bruteforce(or backtracking)
If the problem size is small and bruteforce approach is ok, then do it and not worry too much about the efficient solution. Make sure you do some back of the envelop runtime cost calculations before you disregard bruteforce. In some problems, you might need an intelligent algorithm to solve a sub-problem and then a bruteforce approach to combine sub-problem solutions. This is especially true for some of the problems in code competitions.
now on to the ways of finding efficient solutions....
1. Solve by Example or solving problem instances of small sizes, n = 1,2,3..
Here we solve some example inputs to the problem, e.g. if the problem input is a number n, then I will try to solve it manually for n = 1,2,3,4... and see if a solution clicks in my mind. This same approach can sometimes lead to solution involving recursion(and dynamic programming) described later.
2. Solve by Simplification
Here We try to remove/add some constraints from/to the problem that simplify it, solve the simpler version or a different but similar problem and see if it can be used to solve/understand the original problem.
3. Solve by Recursion
"Thinking Recursively" is an art. Best way to "get" recursion is to practice and read the literature on functional programming where recursion is one of the key concepts. I highly recommend working through SICP and the "wishful thinking" concept described there. For example, to get factorial(n) you will think like, make a wish that someone gives you the factorial(n-1) then how will you get factorial(n) using that of (n-1). Be wishful !!
One of the things I "got" over time is that, for recursion to work It is not necessary that
f(n) = g(f(n-1))
but all of the following could work also
f(n) = g(f(n-1),f(n-2))
f(n) = g(f(n-1),f(n-2),f(n-3))
....
f(n) = g(f(n-1),f(n-2),...f(1),f(0))
3.1 Divide and Conquer(for example standard solution to merge-sort) is another powerful problem solving technique which uses recursion. Here, you solve the original problem by "merging" the solutions of two or more disjoint sub-problems(which are solved recursively).
3.2 Dynamic Programming is an optimization to improve running time after you have a recursive strategy. Draw the recursion tree and see if same sub-problem is being solved multiple times. That is, you will notice that total number of distinct sub-problems to be solved is much less than the total number of sub-problems being solved in straightforward recursive implementation. (In cormen et al, it is called the overlapping sub-problems property).
In such cases, a lot of, redundant computation is saved by caching the solution of various sub-problems and reusing them when required again.
Solution can be implemented either top down recursive with a table to cache the sub-problem solutions or a bottom-up iterative where you solve the smaller sub-problems first and then solve the bigger using solution of smaller sub-problems.
Some problems solved by dynamic programming are optimization problems and they exhibit optimal substructure property, that basically means that optimal solution to bigger problem "contains" optimal solution to the smaller sub-problems.
Most of the time, proof by induction is used here to prove the correctness of algorithm.
4. Solve using Greedy approach
It is a algorithm technique where making locally optimal/correct decisions, *sometimes*, leads to globally optimal/correct solutions. Usually, you can get idea of the solution by solving small size instances of the problem. However, this idea may or may not be correct so it is *essential* to prove that your locally optimal strategy gives you globally optimal results too.
In most of the cases following proof strategies work for greedy algorithms..
- proof by induction
- proof by contradiction: it is sometimes combined with, proof by exchange argument. Here you assume some optimal solution S* and a solution S produced by your greedy algorithm. Using, exchange of elements in S* so that exchange either preserves the optimality score or makes it better, you transform S* to S and that essentially proves that S is either better or equally good as S*. And hence, your greedy strategy works.
- Anything else :)
5. Solve by Reduction
Here we try to reduce the given problem to another problem whose solution is well-known and many of the code challenges problems are of this nature. Some of the algorithms, which come up very frequently, and you should know them by heart(including their proof, and if you have problem reading proofs then you need to work through How to Prove it!). Knowing them also means having their concise/optimal implementation in your [muscle] memory.
Sorting Algorithms - Index Sort, Merge Sort, Quick Sort, Bucket Sort, Radix Sort .
Binary Search Algorithm .
Graph Algorithms:
Breadth First Search(BFS) - Its most popular usage is to find single source shortest path in unweighted graph .
Depth First Search(DFS) .
Note that, Checking Bipartiteness of an undirected graph have standard BFS and DFS based solutions which you should know. Also, either of them can be used to find connected components in an undirected graph.
Topological Sorting [lets you find shortest/longest paths in a DAG in linear time, can be used to solve problems where there are some dependencies/prerequisites and you are required to find a valid ordering]
Strongly Connected Components of directed graph
Finding Euler Path
Dijkstra's Algorithm - for single source shortest path in weighted graph .
Bellman-Ford Algorithm - for single source shortest path in weighted graph with negative edges.
Floyd-Warshall algorithm - for all pair shortest path .
Kruskal and Prim's algorithms - for finding minimum spanning tree .
Max Network Flow (Ford-Fulkerson Algorithm)
Knapsack Problem
Zero-Sum and Alpha-Beta Search
5. Solve by using Data-Structures
You should know how to use Array, Hash table, (Single and Doubly) Linked List traversal, Pre/Post/In order traversal of Binary [Search] tree, Stack and Queue.
Many a times a problem can be solved by inserting the input into one of these data structures and traversing(or retrieving data from) it in certain way.
I found Stack interesting in another way. Most of the problems that are solved by simple recursion are also solvable using Stack and it is no surprise as in case of recursion the stack is hidden in the programming language implementation.
Let me conclude by saying that above list of algorithms and data structures is by no means exhaustive. They are just the most important and basic ones which you should know in great detail including their implementation and proofs.
In my opinion, Part-II(Problem Solving) of AIMA consists of very important algorithms and problem solving techniques. They are mostly related to Graph search but, you will see that there are a lot of problems that can be reduced to Graph search. One should work through at least that part of the book at some point in his life.
Another thing, you should be comfortable with, is basic calculations of computing (time/memory) complexity, the Big-O notation and methods of solving recurrence relations(which come up when computing complexity of any recursive algorithm).
Next level would be to understand theory of NP completeness(and awareness of known hard problems e.g. traveling-salesman-problem and their approximate solutions). You might want to know about advanced data structures such as BTree, KDTree, Trie etc and other graph algorithms. But these, I believe, you don't need to understand in great detail but just the usage. It is impossible to remember all the algorithms. However, you need to be "aware" of as many known data structures and algorithms as possible.
Lastly, This is a journey.. farther you go, better you get.
[Update: July 25' 2011] Sometimes writing precise statement of the problem also helps.
Basically it means to describe your problem under following headings...
Problem Description
Input
Output
Constraints
[Update: July 28' 2011] Sometimes problem is easier(or more efficient) to solve when the input is *Sorted*( or *preprocessed* in general) .
Also there can be problems where finding a *Signature* helps. For example problems related to anagrams of a string are usually solved by finding the signature that is the count of individual characters in the word or just the lexicographical sort of the word.
[Update: Feb 3' 2013] When solving an algorithmic problems. You should convince yourself, with [in]formal proofs, of 3 things (in worst cases)
1. Your algorithm will always terminate.
2. It will always produce the correct solution.
3. What is the worst case running time? (should be polynomial)
However, when solving some NP-complete problem, then 2 can be relaxed in the sense that algorithm is good enough as long as it either computes approximately good solution(if you're ok with it) or correct solution to specific instances of the general problem, that you are interested in. This relaxation is must because, with very high probability, there is no efficient(..polynomial time) solution to general problem you're solving.
0. Solve by bruteforce(or backtracking)
If the problem size is small and bruteforce approach is ok, then do it and not worry too much about the efficient solution. Make sure you do some back of the envelop runtime cost calculations before you disregard bruteforce. In some problems, you might need an intelligent algorithm to solve a sub-problem and then a bruteforce approach to combine sub-problem solutions. This is especially true for some of the problems in code competitions.
now on to the ways of finding efficient solutions....
1. Solve by Example or solving problem instances of small sizes, n = 1,2,3..
Here we solve some example inputs to the problem, e.g. if the problem input is a number n, then I will try to solve it manually for n = 1,2,3,4... and see if a solution clicks in my mind. This same approach can sometimes lead to solution involving recursion(and dynamic programming) described later.
2. Solve by Simplification
Here We try to remove/add some constraints from/to the problem that simplify it, solve the simpler version or a different but similar problem and see if it can be used to solve/understand the original problem.
3. Solve by Recursion
"Thinking Recursively" is an art. Best way to "get" recursion is to practice and read the literature on functional programming where recursion is one of the key concepts. I highly recommend working through SICP and the "wishful thinking" concept described there. For example, to get factorial(n) you will think like, make a wish that someone gives you the factorial(n-1) then how will you get factorial(n) using that of (n-1). Be wishful !!
One of the things I "got" over time is that, for recursion to work It is not necessary that
f(n) = g(f(n-1))
but all of the following could work also
f(n) = g(f(n-1),f(n-2))
f(n) = g(f(n-1),f(n-2),f(n-3))
....
f(n) = g(f(n-1),f(n-2),...f(1),f(0))
3.1 Divide and Conquer(for example standard solution to merge-sort) is another powerful problem solving technique which uses recursion. Here, you solve the original problem by "merging" the solutions of two or more disjoint sub-problems(which are solved recursively).
3.2 Dynamic Programming is an optimization to improve running time after you have a recursive strategy. Draw the recursion tree and see if same sub-problem is being solved multiple times. That is, you will notice that total number of distinct sub-problems to be solved is much less than the total number of sub-problems being solved in straightforward recursive implementation. (In cormen et al, it is called the overlapping sub-problems property).
In such cases, a lot of, redundant computation is saved by caching the solution of various sub-problems and reusing them when required again.
Solution can be implemented either top down recursive with a table to cache the sub-problem solutions or a bottom-up iterative where you solve the smaller sub-problems first and then solve the bigger using solution of smaller sub-problems.
Some problems solved by dynamic programming are optimization problems and they exhibit optimal substructure property, that basically means that optimal solution to bigger problem "contains" optimal solution to the smaller sub-problems.
Most of the time, proof by induction is used here to prove the correctness of algorithm.
4. Solve using Greedy approach
It is a algorithm technique where making locally optimal/correct decisions, *sometimes*, leads to globally optimal/correct solutions. Usually, you can get idea of the solution by solving small size instances of the problem. However, this idea may or may not be correct so it is *essential* to prove that your locally optimal strategy gives you globally optimal results too.
In most of the cases following proof strategies work for greedy algorithms..
- proof by induction
- proof by contradiction: it is sometimes combined with, proof by exchange argument. Here you assume some optimal solution S* and a solution S produced by your greedy algorithm. Using, exchange of elements in S* so that exchange either preserves the optimality score or makes it better, you transform S* to S and that essentially proves that S is either better or equally good as S*. And hence, your greedy strategy works.
- Anything else :)
5. Solve by Reduction
Here we try to reduce the given problem to another problem whose solution is well-known and many of the code challenges problems are of this nature. Some of the algorithms, which come up very frequently, and you should know them by heart(including their proof, and if you have problem reading proofs then you need to work through How to Prove it!). Knowing them also means having their concise/optimal implementation in your [muscle] memory.
Sorting Algorithms - Index Sort, Merge Sort, Quick Sort, Bucket Sort, Radix Sort .
Binary Search Algorithm .
Graph Algorithms:
Breadth First Search(BFS) - Its most popular usage is to find single source shortest path in unweighted graph .
Depth First Search(DFS) .
Note that, Checking Bipartiteness of an undirected graph have standard BFS and DFS based solutions which you should know. Also, either of them can be used to find connected components in an undirected graph.
Topological Sorting [lets you find shortest/longest paths in a DAG in linear time, can be used to solve problems where there are some dependencies/prerequisites and you are required to find a valid ordering]
Strongly Connected Components of directed graph
Finding Euler Path
Dijkstra's Algorithm - for single source shortest path in weighted graph .
Bellman-Ford Algorithm - for single source shortest path in weighted graph with negative edges.
Floyd-Warshall algorithm - for all pair shortest path .
Kruskal and Prim's algorithms - for finding minimum spanning tree .
Max Network Flow (Ford-Fulkerson Algorithm)
Knapsack Problem
Zero-Sum and Alpha-Beta Search
5. Solve by using Data-Structures
You should know how to use Array, Hash table, (Single and Doubly) Linked List traversal, Pre/Post/In order traversal of Binary [Search] tree, Stack and Queue.
Many a times a problem can be solved by inserting the input into one of these data structures and traversing(or retrieving data from) it in certain way.
I found Stack interesting in another way. Most of the problems that are solved by simple recursion are also solvable using Stack and it is no surprise as in case of recursion the stack is hidden in the programming language implementation.
Let me conclude by saying that above list of algorithms and data structures is by no means exhaustive. They are just the most important and basic ones which you should know in great detail including their implementation and proofs.
In my opinion, Part-II(Problem Solving) of AIMA consists of very important algorithms and problem solving techniques. They are mostly related to Graph search but, you will see that there are a lot of problems that can be reduced to Graph search. One should work through at least that part of the book at some point in his life.
Another thing, you should be comfortable with, is basic calculations of computing (time/memory) complexity, the Big-O notation and methods of solving recurrence relations(which come up when computing complexity of any recursive algorithm).
Next level would be to understand theory of NP completeness(and awareness of known hard problems e.g. traveling-salesman-problem and their approximate solutions). You might want to know about advanced data structures such as BTree, KDTree, Trie etc and other graph algorithms. But these, I believe, you don't need to understand in great detail but just the usage. It is impossible to remember all the algorithms. However, you need to be "aware" of as many known data structures and algorithms as possible.
Lastly, This is a journey.. farther you go, better you get.
[Update: July 25' 2011] Sometimes writing precise statement of the problem also helps.
Basically it means to describe your problem under following headings...
Problem Description
Input
Output
Constraints
[Update: July 28' 2011] Sometimes problem is easier(or more efficient) to solve when the input is *Sorted*( or *preprocessed* in general) .
Also there can be problems where finding a *Signature* helps. For example problems related to anagrams of a string are usually solved by finding the signature that is the count of individual characters in the word or just the lexicographical sort of the word.
[Update: Feb 3' 2013] When solving an algorithmic problems. You should convince yourself, with [in]formal proofs, of 3 things (in worst cases)
1. Your algorithm will always terminate.
2. It will always produce the correct solution.
3. What is the worst case running time? (should be polynomial)
However, when solving some NP-complete problem, then 2 can be relaxed in the sense that algorithm is good enough as long as it either computes approximately good solution(if you're ok with it) or correct solution to specific instances of the general problem, that you are interested in. This relaxation is must because, with very high probability, there is no efficient(..polynomial time) solution to general problem you're solving.
Sunday, June 26, 2011
Yahoo Summer School on IR - 2011
Last week, Yahoo Research organized a summer school on IR at IISC, Bangalore campus. This is the first time I visited IISC, the campus is lush green all around and add to it the nice weather.
Most of the sessions on classical IR were fairly detailed(but fast paced). A lot of the discussion assumed upfront knowledge of basic probability theory and linear algebra, which is kind of ok if you are attending a session on any advanced computer science material.
I could easily comprehend the sessions on Introduction to IR, IR Models(Boolean Retrieval, Vector space model, BIRM & BM25, IR based on language model), IR system quality evaluation and also how to create test collections, index creation with a bit of index compression techniques. Along the way, I followed the first half(up to chapter - 12, Language models for IR) of IIR book which covers more or less the same material covered in the mentioned sessions.
Then the sessions on web retrieval did a good job of describing the challenges faced in the web retrieval. It covered a very high level shape of web graph, architecture of web IR and crawlers. This also gave details about how pagerank is typically calculated from the web graph.
Then there were sessions on multimedia retrieval and learning to rank which tried to cover too much ground and I could only get a very high level outline of the area.
Overall it was a good effort and provided a very good introduction to the field of IR. I wish they had covered more on dynamic indexing as in the real world documents get added, deleted and modified every moment.
And, Yahoo research definitely deserves much appreciation for organizing this summer school.
References:
Most of the slides from sessions are available with Yahoo labs.
Modern Information Retrieval is written by one of the presenters in the summer school. It was cited multiple times and sessions on web retrieval are directly from the book chapters.
Introduction to Information Retrieval is another well known book by the author of famous Foundations of statistical natural language processing.
Most of the sessions on classical IR were fairly detailed(but fast paced). A lot of the discussion assumed upfront knowledge of basic probability theory and linear algebra, which is kind of ok if you are attending a session on any advanced computer science material.
I could easily comprehend the sessions on Introduction to IR, IR Models(Boolean Retrieval, Vector space model, BIRM & BM25, IR based on language model), IR system quality evaluation and also how to create test collections, index creation with a bit of index compression techniques. Along the way, I followed the first half(up to chapter - 12, Language models for IR) of IIR book which covers more or less the same material covered in the mentioned sessions.
Then the sessions on web retrieval did a good job of describing the challenges faced in the web retrieval. It covered a very high level shape of web graph, architecture of web IR and crawlers. This also gave details about how pagerank is typically calculated from the web graph.
Then there were sessions on multimedia retrieval and learning to rank which tried to cover too much ground and I could only get a very high level outline of the area.
Overall it was a good effort and provided a very good introduction to the field of IR. I wish they had covered more on dynamic indexing as in the real world documents get added, deleted and modified every moment.
And, Yahoo research definitely deserves much appreciation for organizing this summer school.
References:
Most of the slides from sessions are available with Yahoo labs.
Modern Information Retrieval is written by one of the presenters in the summer school. It was cited multiple times and sessions on web retrieval are directly from the book chapters.
Introduction to Information Retrieval is another well known book by the author of famous Foundations of statistical natural language processing.
Subscribe to:
Posts (Atom)
