FitProgrammer@Work: May 2015

Saturday, May 23, 2015

My TOEFL Test experience

Today i took my TOEFL test at a Prometric testing center in San Jose. I arrived at 7am and started writing the exam at 7:35am. I was done with first 2 sections (Reading and Listening) around 9:33am (about 2 hrs) and then resumed at 9:43am or so with the next 2 sections (Speaking and Writing) and was done by 11:10am (1hr 25 mins). So the last 2 sections were quicker for me. I think i had extra questions in Listening (which won't be counted towards my total score).

Now the specifics on each section while i still remember it :):

Reading had 4 passages and around 56 questions in all. Total time was 1hr 20 mins (80 mins) so for each passage i had 20 mins. Passages were from various topics and the ETS TOEFL practice test for Reading (as well as for other sections) were quite like the ones on the exam.
Listening: I don't remember exactly how many audio clips were there in all but the general pattern was you listen to a clip and then answer multiple choice question on them.
Speaking: 6 speaking exercises:

First 2 were about a familiar topic that i got 15secs to prepare for each and 45 secs to speak about.
Next 2 were - read a passage, then listen to an audio clip on it and then speak about the subject matter being discussed in both passage and clip.

Writing: 4 exercises.

2 were about listening to a clip and reading a passage and then write some answers in your own words.
2 were given a topic write in your own words about the topic. I was asked about the school days starting early and late which one i preferred and why. Answers needed to be at least 300 words. I wrote close to 380 words.

Got my results on 06/01/2015 (today). I scored 105. Per this discussion on quora it seems it is a decent score to apply. For SJSU the cut-off was 80.

For my preparation, all i did was 1 practice test from TOEFL study guide software. I did intend to study more but could not find the time. However after doing first practice test i was familiar with the sections, the type of questions asked and how to approach them.

Test	Test Date	Reading	Listening	Speaking	Writing	Total
TOEFL iBT	Sat May 23 07:36:01 EDT 2015	28	28	28	21	105

Thursday, May 14, 2015

Book Review: Paleo Diet

My notes from the book:

Paleo Diet - What Our Ancestors Didn't Tell Us About The Best Diet In History And How You Can Use It To Lose Weight Quickly And Easily (Paleo Recipes, ... Paleo Solution, Paleo Cookbook, Paleo) (Adams, Ralph)

Health experts have discovered that the culprit behind deadly diseases like cancer and diabetes is in fact the kind of diet people today have.
This means entirely eliminating grains, legumes, dairy products, processed sugars and starches, as well as alcohol from your diet.
The Paleo Diet allows only the consumption of the following food types: Meat There is some debate and discussion about the kind of meat you should choose for your Paleo Diet. Some advocates insist on eating only lean meat, while others are more adamant about choosing fatty cuts. The original Paleo does not prescribe the kind of meat cuts you should choose. However, Paleo experts dispel the myth about the “unhealthy” saturated fats found in fatty meat cuts. There is no substantial scientific evidence that actually links saturated fats with heart disease, so there’s no need to avoid fats.
meat from grass-fed animals is preferable to meal-fed animals because these are closer in composition to the wild animals hunted by the ancients. If grass-fed is unavailable or too expensive, you should probably choose a leaner cut of the meal-fed.
Fruits are the only natural source for sugars that is allowed in the Paleo diet.
Vegetables Together with fruits, vegetables are a great natural and unprocessed source of necessary nutrients and vitamins.
Whole Nuts and Seeds Nuts and seeds are a great snack for Paleo because they contain healthy fats and essential oils.
Seafood Ancient hunter-gatherers did not only hunt land animals, they also hunted fish and other sea animals. Seafood is rich in protein, and fish like tuna and salmon are high in the healthy omega3 oil.
Eggs Other diets warn against eating eggs because they are high in cholesterol. But eggs have a lot of good enzymes, being high in protein and vitamins A and B.
Supplements Since grass-fed beef is usually expensive, other Paleo dieters recommend getting the meal-fed ones and supplementing with fish oil capsules to get an added dose of omega3
In moderation, these food and drinks can be consumed: Coffee Chocolate Tea Rich Sauces dairy products like fermented yogurt, heavy cream, butter, and certain cheeses have little lactose content, so you could include them occasionally in your recipes. Dried fruits Salt
These foods and substances should be avoided entirely: Sugars Grains and grain products Legumes Soda Alcohol
Grains are full of gluten and lectin, which can obstruct the natural digestive process. Lectin covers the walls of your stomach and makes food more difficult to digest. Gluten, meanwhile, causes inflammation and can also cause autoimmune diseases, or diseases which cause your immune system to attack itself.
Paleo Benefits Weight loss and maintenance Detoxify your body from substances found in grains and legumes, such as lectin and phytic acids Prevent degenerative diseases like diabetes, cancer, obesity, and heart diseases
You can cut up fruits and vegetables and stock them in your freezer, so you have readily available ingredients for salads and quick snacks.
stock your meat in the freezer and pre-cook enough (without seasoning) for 2 or 3-day meals.
Eat when you are hungry.
Instead of counting the carbs or worrying about the ratio of your veggies and meat portions, let your body guide you and eat a small meal whenever you feel hungry.
Exercise. Paleo works best for people who have relatively active lifestyles. Even just a brief 15 to 30 minute gym or running session can do wonders for weight loss.
Drink water. Never substitute fruit juices for water during Paleo. make sure you get at least 8 glasses of water daily.
Eat more fat. Because you dropped on carbs, you will need more fat to sustain your energy levels throughout the day.

Book Review: Intermittent Fasting

Notes from the book:

Intermittent Fasting: Simple Guide to Weight Loss, Fat Loss, and Improved Health - THE FAT LOSS AND ANTI AGING DIET (Intermittent Fasting for Weight Loss, ... Loss, Weight Loss Diet, Lose Fat Book 1) (Childs, Valerie;Louis, Joy)

The most important thing to understand is this, the number of calories your body burns throughout the day is not dependent on meal frequency.
In weight loss, what matters most is the difference between the number of calories taken in and those used up by the body. Regardless of your meal frequency, you will gain weight if at the end of the day, you eat more calories than you expend.
What matters is not whether you eat breakfast or not but what you eat.
Proteins are the sources of amino acids that keep muscles healthy and growing. Once you eat a meal containing proteins, that is enough to produce amino acids for more than 16 hours.
The book recommends a fasting period of between 12-24 hours.
Studies have shown that even three days of fasting do not affect training performance.
To make your training highly effective however, it is recommended that you take a pre and post workout protein supplement. Some BCAA powder or tablets are the best.
calories in versus calories out is what matters. As long as you are not snacking on unhealthy, high calorie junk food or overeating, you should be okay.
Eating three large meals, instead of six smaller ones, results in much better appetite control.
Whether you fast for 12 hours, 36 hours or three days, your blood sugar will remain the same.
The science behind intermittent fasting weight loss is mostly about how the body produces its energy. When you eat, sugar is stored in the liver in form of glycogen. The body uses it to produce energy. When you eat a meal during breakfast, lunch and dinner, your body will never run out of glycogen to use for energy synthesis. There is therefore no time when it will turn to fat burning for energy.
The only problem is, you want your body to burn fat so as to reduce it and lose weight. The only way to do this is wait until glycogen is depleted, then force the body to burn fat.
Intermittent fasting does this. It takes about 8-12 hours, without further eating, for glycogen to run out. This is why it is recommended that any intermittent fasting method should not run for less than 12 hours. After 8-12 hours, the body turns to fat for its energy needs. To help in burning more fat, you can engage in exercises such as cardio workouts or weight lifting.
With continued adherence to intermittent fasting, you can get to a point where the body adapts to using fat more than glycogen.
you should get to a point where the last meal is at 8pm at night and the next full meal at noon the next day.
To get the full benefits you have to also change your dietary components. Include more fruits and vegetables in your meals and do not forget to drink lots of water. Avoid highly processed foods and high sugar products like Soda and candy.
Having a planned menu before you start ensures that you know what you are going to eat for each meal of the week.
The best way to spend your fasting hour is by staying busy.
To amplify the benefits of intermittent benefit, include regular workouts into your schedule.
Simply because fasting for 15 hours has done wonders for you does not mean that 48 hours will too, in fact, it will damage your body. Prolonged fasting is what is referred to as starvation. Your muscles start to waste, metabolism rate drops and energy levels go down drastically. This kind of fasting is not helpful at all.
Experts recommend the minimum fasting period to be 12 hours and the maximum period to be 20 hours.
Do not fast blindly. Keep checking your health status to ensure that the fasting is not causing any health problems.
Just eat healthy, do your exercises, lower stress and you will live a long healthy life.
If you can manage 12-16 hours of fasting once every week or so, it will benefit you a lot.
“It is not hard. Don’t you dare tell us this is hard. Quitting heroin is hard. Beating cancer is hard. Drinking your coffee black. Is. Not. Hard.”
Improving your sleep, energy levels, mood, attention span, body composition, motivation, self-confidence, self-efficacy, and quality of life starts by changing the food you put on your plate.
Yes, the Whole30 eliminates cravings, corrects hormonal imbalances, fixes digestive issues, improves medical conditions, and strengthens the immune system.
Added sugar and artificial sweeteners. All alcohol. All grains (even whole grains). Legumes, including peanuts and soy. Nearly all forms of dairy.
Added sugars, whether from table sugar, honey, agave nectar, or maple syrup, do not contain the vitamins, minerals, and phytochemicals that contribute to your overall health, but they do contain lots of empty calories.

Tuesday, May 12, 2015

List of Topics for programming Competitions

1. Basic Geometry/Euclidean Geometry/Coordinate Geometry/ [3-D variants of everything].

2. Computational Geometry.

a. Graham Scan algorithm for Convex Hull O(n * log(n)).

b. Online construction of 3-D convex hull in O(n^2).

c. Bentley Ottmann algorithm to list all intersection points of n line segments in O((n + I) * logn).

■ Suggested Reading -

1. http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm

d. Rotating Calipers Technique.

■ Suggested Reading - http://cgm.cs.mcgill.ca/~orm/rotcal.html

■ Problems - Refer the article for a list of problems which can be solved using Rotating Calipers technique.

e. Line Sweep/Plane Sweep algorithms -

■ Area/Perimeter of Union of Rectangles.

■ Closest pair of points.

■ Suggested Reading -

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep

■ Problems - Follow the tutorial for list of problems.

f. Area of Union of Circles.

g. Delayunay Triangulation of n points in O(n * logn).

h. Voronoi Diagrams of n points in O(n * logn) using Fortunes algorithm.

i. Point in a polygon problem -

■ O(n) solution without preprocessing.

■ O(logn) algorithm with O(n * logn) preprocessing for convex polygons.

j. Problems on computational geometry -

■ BSHEEP, BULK, SEGVIS, CONDUIT, RUNAWAY, DIRVS, RAIN1, SHAMAN, TCUTTER, LITEPIPE, RHOMBS, FSHEEP, FLBRKLIN, CERC07P, BAC, ALTARS, CERC07C, NECKLACE, CH3D, RECTANGL, POLYSSQ, FOREST2, KPPOLY, RAIN2, SEGMENTS, ARCHPLG, BALLOON, CIRCLES, COMPASS, EOWAMRT, ICERINK on SPOJ.

■ CultureGrowth, PolygonCover on Topcoder.

k. Suggested Reading -

■ Computational Geometry: Algorithms and applications. Mark De Burg.

3. String Algorithm.

a. KnuthMorrisPratt algorithm.

■ Problems - NHAY, PERIOD on SPOJ.

■ Suggested Reading -

1. Cormen chapter on Strings.

2. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching

b. Aho Corasick algorithm.

■ Problems - WPUZZLES on SPOJ.

c. Suffix Arrays

■ O(n^2 * logn) Naive method of suffix array construction

■ O(n * logn^2) method of suffix array construction

■ O(n * logn) method of suffix array construction.

■ O(n) method of suffix array construction

■ O(n) LCA preprocess on Suffix Arrays to solve a variety of string problems.

d. Suffix Trees

■ O(n) construction of Suffix trees using Ukkenon’s algorithm.

■ O(n) construction of Suffix Trees if provided with Suffix Arrays using Farach’s algorithm.

e. Suffix Automata

■ O(n) Suffix Automaton construction.

f. Dictionary Of Basic Factors

■ O(n * logn) method of DBF construction using Radix Sort.

g. Manachar’s algorithm to find Lengh of palindromic substring of a string centered at a position for each position in the string. Runtime -> O(n).

h. Searching and preprocessing Regular Expressions consisting of ‘?’, ‘*’.

i. Multi-dimensional pattern matching.

j. Problems on Strings [can be solved with a variety of techniques] -

■ DISUBSTR, PLD, MSTRING, REPEATS, JEWELS, ARCHIVER, PROPKEY, LITELANG, EMOTICON, WORDS, AMCODES, UCODES, PT07H, MINSEQ, TOPALIN, BWHEELER, BEADS, SARRAY, LCS, LCS2, SUBST1, PHRASES, PRETILE on SPOJ

■ http://www.algorithmist.com/index.php/Category:String_algorithms

4. Basic Graphs [beginner].

a. Representation of graphs as adjacency list, adjacency matrix, incidence matrix and edge list and uses of different representations in different scenarios.

b. Breadth First Search.

■ problems -

1. PPATH, ONEZERO, WATER on SPOJ

c. Depth First Search.

d. Strongly Connected Components.

■ problems -

1. TOUR and BOTTOM on SPOJ.

e. Biconnected Components, Finding articulation points and bridges].

■ problems -

1. RELINETS, PT07A on SPOJ.

f. Dijkstra algorithm -

■ problems -

1. SHPATH on SPOJ.

g. Floyd Warshall algorithm -

■ problems -

1. COURIER on SPOJ.

h. Minimum Spanning Tree

■ problems -

1. BLINNET on SPOJ.

i. Flood-fill algorithm

j. Topological sort

k. Bellman-Ford algorithm.

l. Euler Tour/Path.

■ problems - WORDS1 on SPOJ.

m. Suggested reading for most of the topics in Graph algorithms -

■ http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=graphsDataStrucs1.

■ Also refer to the tutorial for problems concerning these techniques.

■ Cormen chapter 22 to 24.

5. Flow networks/ matching etc etc. [Interdiate/Advanced].

a. Maximum flow using Ford Fulkerson Method.

■ Suggested Reading -

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow

■ problems - TAXI, POTHOLE, IM, QUEST4, MUDDY, EN, CABLETV, STEAD, NETADMIN, COCONUTS, OPTM on SPOJ.

b. Maximum flow using Dinics Algorithm.

■ Problems - PROFIT on spoj.

c. Minimum Cost Maximum Flow.

■ Successive Shortest path algorithm.

■ Cycle Cancelling algorithm.

■ Suggested Reading -

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow1

d. Maximum weighted Bipartite Matching (Kuhn Munkras algorithm/Hungarian Method)

■ problems - GREED, SCITIES, TOURS on SPOJ | http://www.topcoder.com/stat?c=problem_statement&pm=8143

e. Stoer Wagner min-cut algorithm.

f. Hopcroft Karp bipartite matching algorithm.

■ problems - ANGELS on SPOJ.

g. Maximum matching in general graph (blossom shrinking)

h. Gomory-Hu Trees.

■ i) Problems - MCQUERY on Spoj.

i. Chinese Postman Problem.

■ problems - http://acm.uva.es/archive/nuevoportal/data/problem.php?p=4039

■ Suggested Reading - http://eie507.eie.polyu.edu.hk/ss-submission/B7a/

j. Suggested Reading for the full category ->

■ Network flow - Algorithms and Applications by Ahuja

■ Cormen book chapter 25.

6. Dynamic Programming.

a. Suggested Reading - Dynamic Programming(DP) as a tabulation method

■ Cormen chapter on DP

b. Standard problems (you should really feel comfortable with these types)

■ http://www.topcoder.com/stat?c=problem_statement&pm=8570&rd=12012&rm=269199&cr=7581406

■ http://www.topcoder.com/stat?c=problem_statement&pm=10765&rd=14183

c. State space reduction

■ http://www.topcoder.com/stat?c=problem_statement&pm=10902

■ http://www.topcoder.com/stat?c=problem_statement&pm=3001

■ http://www.topcoder.com/stat?c=problem_statement&pm=8605&rd=12012&rm=269199&cr=7581406

d. Solving in the reverse - easier characterizations looking from the end

■ http://www.spoj.pl/problems/MUSKET/

■ http://www.topcoder.com/stat?c=problem_statement&pm=5908

e. Counting/optimizing arrangements satisfying some specified properties

■ http://www.topcoder.com/stat?c=problem_statement&pm=8306

■ http://www.topcoder.com/stat?c=problem_statement&pm=7849

f. Strategies and expected values

■ http://www.topcoder.com/stat?c=problem_statement&pm=10765&rd=14183

■ http://www.topcoder.com/stat?c=problem_statement&pm=10806

■ http://www.topcoder.com/stat?c=problem_statement&pm=7828

■ http://www.topcoder.com/stat?c=problem_statement&pm=7316

g. DP on probability spaces

■ http://www.topcoder.com/stat?c=problem_statement&pm=7422

■ http://www.topcoder.com/stat?c=problem_statement&pm=2959

■ http://www.topcoder.com/stat?c=problem_statement&pm=10335

h. DP on trees

■ http://www.topcoder.com/stat?c=problem_statement&pm=10800

■ http://www.topcoder.com/stat?c=problem_statement&pm=10737

■ http://www.topcoder.com/stat?c=problem_solution&rm=266678&rd=10958&pm=8266&cr=7581406

i. DP with datastructures

■ http://www.spoj.pl/problems/INCSEQ/

■ http://www.spoj.pl/problems/INCDSEQ/

■ http://www.spoj.pl/problems/LIS2/

■ http://www.topcoder.com/stat?c=problem_statement&pm=1986

j. Symmetric characterization of DP state

■ http://www.topcoder.com/stat?c=problem_statement&pm=8610

k. A good collection of problems

■ http://codeforces.com/blog/entry/325

■ http://problemclassifier.appspot.com/index.jsp?search=dp&usr=

7. Greedy.

a. Suggested Reading -

■ Chapter on Greedy algorithms in Cormen.

■ http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=greedyAlg

b. problems - refer to the topcoder tutorial.

8. Number Theory.

a. Modulus arithmetic - basic postulates [Including modular linear equations , Continued fraction and Pell's equation]

■ Suggested Reading -

1. Chapter 1 from Number Theory for Computing by SY Yan [ Recommended ]

2. 31.1, 31.3 and 31.4 from Cormen

3. www.topcoder.com/tc?module=Static&d1=tutorials&d2=primeNumbers

■ Problems

1. http://projecteuler.net/index.php?section=problems&id=64

2. http://projecteuler.net/index.php?section=problems&id=65

3. http://projecteuler.net/index.php?section=problems&id=66

4. http://www.topcoder.com/stat?c=problem_statement&pm=6408&rd=9826

5. http://www.topcoder.com/stat?c=problem_statement&pm=2342

b. Fermat's theorem, Euler Totient theorem ( totient function, order , primitive roots )

■ Suggested Reading

1. 1.6, 2.2 from Number Theory by SY Yan

2. 31.6 , 31.7 from Cormen

■ Problems

1. http://projecteuler.net/index.php?section=problems&id=70

2. http://www.spoj.pl/problems/NDIVPHI/

c. Chinese remainder theorem

■ Suggested Reading

1. 31.5 from Cormen

2. 1.6 from Number Theory by SY Yan

■ Problems

1. Project Euler 271

2. http://www.topcoder.com/stat?c=problem_statement&pm=10551&rd=13903

d. Primality tests -

■ Deterministic O(sqrt(n) ) approach

■ Probabilistic primality tests - Fermat primality test, Miller-Rabin Primality test

1. Suggested Reading -

a. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting

b. Cormen 31.8

c. 2.2 from Number Theory by SY Yan

2. Problems -

a. PON, PRIC, SOLSTRAS on SPOJ

b. http://www.topcoder.com/stat?c=problem_statement&pm=4515

e. Prime generation techniques - Sieve of Erastothenes

■ Suggested Problems - PRIME1 on SPOJ

f. GCD using euclidean method

■ Suggested Reading

1. 31.2 Cormen

■ Problems -

1. GCD on SPOJ

2. http://uva.onlinejudge.org/external/114/11424.html

g. Logarithmic Exponentiation

■ Suggested Reading -

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting

h. Integer Factorization

■ Naive O(sqrt(n)) method

■ Pollard Rho factorization

■ Suggested Reading

1. 2.3 from Number Theory SY Yan

2. 31.9 Cormen

■ Problems -

1. http://www.topcoder.com/stat?c=problem_statement&pm=2986&rd=5862

2. http://www.spoj.pl/problems/DIVSUM2/

3. http://www.topcoder.com/stat?c=problem_statement&pm=4481&rd=6538

i. Stirling numbers

j. Wilson theorem

■ nCr % p in O(p) preprocess and O(log n ) query

k. Lucas Theorem

l. Suggested Reading for Number Theory -

■ Number theory for computing by Song Y Yan [ Simple book describing concepts in details ]

■ Concepts are also superficially covered in Chapter 31 of Introduction to Algorithms by Cormen

■ http://www.codechef.com/wiki/tutorial-number-theory

■ http://www.algorithmist.com/index.php/Category:Number_Theory

m. Problems on Number Theory -

■ http://www.algorithmist.com/index.php/Category:Number_Theory

■ http://problemclassifier.appspot.com/index.jsp?search=number&usr=

9. Math (Probability, Counting, Game Theory, Group Theory, Generating functions, Permutation Cycles, Linear Algebra)

a. Probability.

Syllabus

■ Basic probability and Conditional probability

1. Suggested problems

a. http://www.spoj.pl/problems/CT16E/

b. http://www.spoj.pl/problems/CHICAGO/

■ Random variables, probability generating functions

■ Mathematical expectation + Linearity of expectation

1. Suggested problems

a. http://www.spoj.pl/problems/FAVDICE/

b. http://www.topcoder.com/stat?c=problem_statement&pm=10744

■ Special discrete and continuous probability distributions

1. Bernoulli, Binomial, Poisson, normal distribution

2. Suggested Problem

a. http://acm.sgu.ru/problem.php?contest=0&problem=498

■ Suggested Readings

1. Cormen appendix C (very basic)

2. Topcoder probabilty tutorial http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=probabilities

3. http://en.wikipedia.org/wiki/Random_variable

4. http://en.wikipedia.org/wiki/Expected_value

5. William Feller, An introduction to probability theory and its applications

b. Counting

Syllabus

■ Basic principles - Pigeon hole principle, addition, multiplication rules

1. Suggested problems

a. http://acm.timus.ru/problem.aspx?space=1&num=1690

b. http://www.topcoder.com/stat?c=problem_statement&pm=10805

3. Suggested readings

a. http://en.wikipedia.org/wiki/Combinatorial_principles

b. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=combinatorics

c. http://www.maa.org/editorial/knot/pigeonhole.html

■ Inclusion-exclusion

1. Suggested readings

a. http://en.wikipedia.org/wiki/Inclusion–exclusion_principle

2. Suggested problems

a. http://www.topcoder.com/stat?c=problem_statement&pm=4463&rd=6536

b. http://www.topcoder.com/stat?c=problem_statement&pm=10238

■ Special numbers

1. Suggested reading - Stirling, eurlerian, harmonic, bernoulli, fibonnacci numbers

a. http://en.wikipedia.org/wiki/Stirling_number

b. http://en.wikipedia.org/wiki/Eulerian_numbers

c. http://en.wikipedia.org/wiki/Harmonic_series_(mathematics)

d. http://en.wikipedia.org/wiki/Bernoulli_number

e. http://en.wikipedia.org/wiki/Fibonnaci_numbers

f. Concrete mathematics by Knuth

2. Suggested problems

a. http://www.topcoder.com/stat?c=problem_statement&pm=1643

b. http://www.topcoder.com/stat?c=problem_statement&pm=8202&rd=11125

c. http://www.topcoder.com/stat?c=problem_statement&pm=8725

d. http://www.topcoder.com/stat?c=problem_statement&pm=2292&rd=10709

■ Advanced counting techniques - Polya counting, burnsides lemma

1. Suggested reading

a. http://en.wikipedia.org/wiki/Burnside's_lemma

b. http://petr-mitrichev.blogspot.com/2008/11/burnsides-lemma.html

2. Suggested Problems

a. http://www.topcoder.com/stat?c=problem_statement&pm=9975

b. http://www.spoj.pl/problems/TRANSP/

c. Game theory

Syllabus

■ Basic principles and Nim game

1. Sprague grundy theorem, grundy numbers

2. Suggested readings

a. http://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem

b. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames

c. http://www.ams.org/samplings/feature-column/fcarc-games1

d. http://www.codechef.com/wiki/tutorial-game-theory

3. Suggested problems

a. http://www.topcoder.com/stat?c=problem_statement&pm=3491&rd=6517

b. http://www.topcoder.com/stat?c=problem_statement&pm=3491&rd=6517

■ Hackenbush

1. Suggested readings

a. http://en.wikipedia.org/wiki/Hackenbush

b. http://www.ams.org/samplings/feature-column/fcarc-partizan1

2. Suggested problems

a. http://www.cs.caltech.edu/ipsc/problems/g.html

b. http://www.spoj.pl/problems/PT07A/

d. Linear Algebra

Syllabus

■ Matrix Operations

1. Addition and subtraction of matrices

a. Suggested Reading

i. Cormen 28.1

2. Multiplication ( Strassen's algorithm ), logarithmic exponentiation

a. Suggested reading

i. Cormen 28.2

ii. Linear Algebra by Kenneth Hoffman Section 1.6

b. Problems

i. http://uva.onlinejudge.org/external/111/11149.html

3. Matrix transformations [ Transpose, Rotation of Matrix, Representing Linear transformations using matrix ]

a. Suggested Reading

i. Linear Algebra By Kenneth Hoffman Section 3.1,3.2,3.4,3.7

b. Problems

i. http://www.topcoder.com/stat?c=problem_statement&pm=6877

ii. JPIX on Spoj

4. Determinant , Rank and Inverse of Matrix [ Gaussean Elimination , Gauss Jordan Elimination]

a. Suggested Reading

i. 28.4 Cormen

ii. Linear Algebra by Kenneth Chapter 1

b. Problems

i. http://www.topcoder.com/stat?c=problem_statement&pm=8174

ii. http://www.topcoder.com/stat?c=problem_statement&pm=6407&rd=9986

iii. http://www.topcoder.com/stat?c=problem_statement&pm=8587

iv. HIGH on Spoj

5. Solving system of linear equations

a. Suggested Reading

i. 28.3 Cormen

ii. Linear Algebra by Kenneth Chapter 1

b. Problems -

i. http://www.topcoder.com/stat?c=problem_statement&pm=3942&rd=6520

6. Using matrix exponentiation to solve recurrences

a. Suggested Reading

i. http://www.topcoder.com/tc?module=Static&d1=features&d2=010408

b. Problems

i. REC, RABBIT1 , PLHOP on spoj

ii. http://www.topcoder.com/stat?c=problem_statement&pm=6386 , http://www.topcoder.com/stat?c=problem_statement&pm=7262, http://www.topcoder.com/stat?c=problem_statement&pm=6877

7. Eigen values and Eigen vectors

a. Problems

i. http://www.topcoder.com/stat?c=problem_statement&pm=2423&rd=4780

■ Polynomials

1. Roots of a polynomial [ Prime factorization of a polynomial, Integer roots of a polynomial, All real roots of a polynomial ]

a. Problems

i. http://www.topcoder.com/stat?c=problem_statement&pm=8273&rd=10798

ii. POLYEQ , ROOTCIPH on Spoj

2. Lagrange Interpolation

a. Problems

i. http://www.topcoder.com/stat?c=problem_statement&pm=10239

ii. http://www.topcoder.com/stat?c=problem_statement&pm=8725

e. Permutation cycles

■ Suggested Reading

1. Art of Computer Programming by Knuth Vol. 3

■ Problems

1. ShuffleMethod, Permutation and WordGame on topcoder.

f. Group Theory

■ Bernside Lemma, Polias theorem

1. Suggested Reading

a. Hernstein's topics in algebra

b. http://petr-mitrichev.blogspot.com/2008/11/burnsides-lemma.html

2. Problems

a. TRANSP on spoj

b. http://www.topcoder.com/stat?c=problem_statement&pm=9975

b. Generating functions

■ Suggested Reading

1. Herbert Wilf's generating functionology

2. Robert Sedgewick and Flajoulet's Combinatorial analysis

10. Data Structures.

i. Basic

a. Arrays/Stacks/Queues :

■ Problems

1. https://www.spoj.pl/problems/STPAR/

2. https://www.spoj.pl/problems/SHOP/

3. https://www.spoj.pl/problems/WATER/

■ Reading:

1. CLRS: section 10.1

2. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dataStructures

b. Singly/Doubly Linked List :

■ Problems

1. https://www.spoj.pl/problems/POSTERS/

■ Reading: CLRS: section 10.2, Mark Allen Weies Chapter 3

c. Hash Tables :

■ Problems

1. https://www.spoj.pl/problems/HASHIT/

2. https://www.spoj.pl/problems/CUCKOO/

■ Reading: CLRS: Chapter 11, Mark Allen Weies Chapter 5

d. Circular linked list / queue

■ Problems

1. https://www.spoj.pl/problems/CTRICK/

e. Binary/nary Trees

■ Reading

1. CLRS: section 10.4

2. CLRS: Chapter 12

3. Mark Allen Weies Chapter 4

4. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearchRedBlack

f. Heaps

■ Problems

1. https://www.spoj.pl/problems/PRO/

2. https://www.spoj.pl/problems/EXPEDI/

■ Reading : Mark Allen Weies Chapter 6

ii. Advanced

a. Trie (Keyword tree)

■ Problems

1. https://www.spoj.pl/problems/MORSE/

2. https://www.spoj.pl/problems/EMOTICON/

■ Reading

b. Interval trees / Segment Trees

■ Problems

1. https://www.spoj.pl/problems/ORDERS/

2. https://www.spoj.pl/problems/FREQUENT/

■ Reading

c. Fenwick(Binary Indexed) trees

■ Problems

1. https://www.spoj.pl/problems/MATSUM/

■ Reading: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

d. Disjoint data structures

■ Problems

1. https://www.spoj.pl/problems/BLINNET/

2. https://www.spoj.pl/problems/CHAIN/

■ Reading:

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure

2. Mark Allen Weies Chapter 8

e. Range minimum Query(RMQ)

■ Problems

1. https://www.spoj.pl/problems/GSS1/

■ Reading http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

f. Customized interval/segment trees (Augmented DS)

■ Problems

1. https://www.spoj.pl/problems/GSS3/

2. https://www.spoj.pl/problems/RRSCHED/

■ Reading: CLRS: Chapter 14 (augmented DS)

g. AVL Trees

■ Problems

1. https://www.spoj.pl/problems/ORDERS/

■ Reading

iii. Miscellaneous (Not to be covered)

a. Splay Trees

b. B/B+ Trees

c. k-d Trees

d. Red-black Trees

e. Skip List

f. Binomial/ Fibonacci heaps

iv. Exercices

1. https://www.spoj.pl/problems/LAZYPROG/ (Hint: Heaps)t

2. https://www.spoj.pl/problems/HELPR2D2/ (Hint: Interval Trees)

3. https://www.spoj.pl/problems/SAM/ (Hint: Heaps)

4. https://www.spoj.pl/problems/PRHYME/ (Hint: Trie)

5. https://www.spoj.pl/problems/HEAPULM/ (Hint: Interval Trees)

6. https://www.spoj.pl/problems/CORNET/ (Hint: Disjoint )

7. https://www.spoj.pl/problems/EXPAND/

8. https://www.spoj.pl/problems/WPUZZLES/

9. https://www.spoj.pl/problems/LIS2/

11. Search Techniques/Bruteforce writing techniques/Randomized algorithms.

a. Backtracking - [Beginner].

■ problems ->

1. N queens problems

2. Knights Tour

3. Sudoku Problem

4. Tiling Problem.

5. 15 puzzle.

b. Dancing Links and Algorithm X given by Knuth - [Advanced]

■ problems - PRLGAME, SUDOKU, NQUEEN on SPOJ

■ Suggested reading -

1. http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz

c. Binary Search - [Beginner].

■ poblems - AGGRCOW on SPOJ. Refer the tutorial for more problems.

■ finding all real roots of a polynomial using binary search. [intermediate].

■ Suggested Reading -

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch

d. Ternary Search - [Intermediate].

■ problems -

1. http://www.spoj.pl/problems/KPPOLY/

2. http://www.codechef.com/DEC09/problems/K1/

3. http://www.topcoder.com/stat?c=problem_statement&pm=4705&rd=7993

4. http://www.topcoder.com/stat?c=problem_statement&pm=7741&rd=10671

5. http://www.topcoder.com/stat?c=problem_statement&pm=6464&rd=9994

6. http://www.topcoder.com/stat?c=problem_statement&pm=3501&rd=6529

7. http://www.topcoder.com/stat?c=problem_statement&pm=4567&rd=6539

e. Meet in the middle [Intermediate].

■ problems -

1. http://www.spoj.pl/problems/MAXISET/

2. http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2868

f. Hill Climbing [Advanced].

g. Regular Iteration to reach a fixed point [Advanced].

■ Newton-Raphson method to find root of a mathematical function.

■ Iterations to solve linear non-homogeneous system of equations.

h. Randomized Algorithms [Intermediate]-

■ Quick-Sort.

12. General programming issues in contests ->

a. Arithmetic Precision - [Beginner].

■ Suggested Reading -

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=integersReals

b. Representing sets with bitmasks and manipulating bitmasks - [Beginner].

■ Suggested Reading -

1. http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation

■ problems - refer to the tutorial link in Suggested reading section.

Saturday, May 23, 2015

My TOEFL Test experience

Thursday, May 14, 2015

Book Review: Paleo Diet

Book Review: Intermittent Fasting

Tuesday, May 12, 2015

List of Topics for programming Competitions

Popular micro services patterns