Monthly Archives: October 2008

Algorithms in a Nutshell

Posted on by
Reply

Authors George Heineman, Gary Pollice and Stanley Selkow have written a very promising book – Algorithms in a Nutshell – published by O’Reilly. The authors are professors at Worcester Polytechnic Institute (WPI). The hardcopy will be available on October 21, 2008, but the book is already available on Safari.

The table of contents :

Part I: I
Chapter 1. Algorithms Matter
Section 1.1. Understand the Problem
Section 1.2. Experiment if Necessary
Section 1.3. Side Story
Section 1.4. The Moral of the Story
Section 1.5. References
Chapter 2. The Mathematics of Algorithms
Section 2.1. Size of a Problem Instance
Section 2.2. Rate of Growth of Functions
Section 2.3. Analysis in the Best, Average, and Worst Cases
Section 2.4. Performance Families
Section 2.5. Mix of Operations
Section 2.6. Benchmark Operations
Section 2.7. One Final Point
Section 2.8. References
Chapter 3. Patterns and Domains
Section 3.1. Patterns: A Communication Language
Section 3.2. Algorithm Pattern Format
Section 3.3. Pseudocode Pattern Format
Section 3.4. Design Format
Section 3.5. Empirical Evaluation Format
Section 3.6. Domains and Algorithms
Section 3.7. Floating-Point Computations
Section 3.8. Manual Memory Allocation
Section 3.9. Choosing a Programming Language
Section 3.10. References
Part II: II
Chapter 4. Sorting Algorithms
Section 4.1. Overview
Section 4.2. Insertion Sort
Section 4.3. Median Sort
Section 4.4. Quicksort
Section 4.5. Selection Sort
Section 4.6. Heap Sort
Section 4.7. Counting Sort
Section 4.8. Bucket Sort
Section 4.9. Criteria for Choosing a Sorting Algorithm
Section 4.10. References
Chapter 5. Searching
Section 5.1. Overview
Section 5.2. Sequential Search
Section 5.3. Binary Search
Section 5.4. Hash-based Search
Section 5.5. Binary Tree Search
Chapter 6. Graph Algorithms
Section 6.1. Overview
Section 6.2. Depth-First Search
Section 6.3. Breadth-First Search
Section 6.4. Single-Source Shortest Path
Section 6.5. All Pairs Shortest Path
Section 6.6. Minimum Spanning Tree Algorithms
Section 6.7. References
Chapter 7. Path Finding in AI
Section 7.1. Overview
Section 7.2. Depth-First Search
Section 7.3. Breadth-First Search
Section 7.4. A*Search
Section 7.5. Comparison
Section 7.6. Minimax
Section 7.7. NegMax
Section 7.8. AlphaBeta
Section 7.9. References
Chapter 8. Network Flow Algorithms
Section 8.1. Overview
Section 8.2. Maximum Flow
Section 8.3. Bipartite Matching
Section 8.4. Reflections on Augmenting Paths
Section 8.5. Minimum Cost Flow
Section 8.6. Transshipment
Section 8.7. Transportation
Section 8.8. Assignment
Section 8.9. Linear Programming
Section 8.10. References
Chapter 9. Computational Geometry
Section 9.1. Overview
Section 9.2. Convex Hull Scan
Section 9.3. LineSweep
Section 9.4. Nearest Neighbor Queries
Section 9.5. Range Queries
Section 9.6. References
Part III: III
Chapter 10. When All Else Fails
Section 10.1. Variations on a Theme
Section 10.2. Approximation Algorithms
Section 10.3. Offline Algorithms
Section 10.4. Parallel Algorithms
Section 10.5. Randomized Algorithms
Section 10.6. Algorithms That Can Be Wrong, but with Diminishing Probability
Section 10.7. References
Chapter 11. Epilogue
Section 11.1. Overview
Section 11.2. Principle: Know Your Data
Section 11.3. Principle: Decompose the Problem into Smaller Problems
Section 11.4. Principle: Choose the Right Data Structure
Section 11.5. Principle: Add Storage to Increase Performance
Section 11.6. Principle: If No Solution Is Evident, Construct a Search
Section 11.7. Principle: If No Solution Is Evident, Reduce Your Problem to Another Problem That Has a Solution
Section 11.8. Principle: Writing Algorithms Is Hard—Testing Algorithms Is Harder
Part IV: IV
Appendix A. Benchmarking
Section A.1. Statistical Foundation
Section A.2. Hardware
Section A.3. Reporting
Section A.4. Precision

Diet update – Oct 06 2008

Posted on by
2

Today morning my weight was 182.4 pounds which comes to approximately 82.7 Kgs. This means that I lost something between 6 to 8 pounds in the first two days (i didnt measure my weight before starting the diet but I think it was something between 188 – 190 pounds which was the case when I last weighed myself). This rate of reduction is excellent from what I have read and it certainly gives me some motivation to continue the diet. The going is tough and the sugar craving is very high but I hope things will get better in the days to come.

Yesterday morning I had 2 eggs and a sausage for brunch. In the evening I had 2 chicken pieces and for dinner I fried some shrimp. I snacked on beef jerky in between meals as well. I drank 3 caffeine free diet cokes and ate a couple of packets of Splenda to satisfy my sugar craving.

I played badminton on saturday and volleyball on sunday so I am guessing that it helped in burning some fat.

I haven’t decided what my target weight should be. I don’t want to put too much pressure on myself. When the cravings get high, I console myself with the fact that I can quit any time that I want, but by having a target weight it would feel like a failure if I quit before that. I am just going to keep going as far as I can.

The hardest part would be keeping the weight off after I start eating carbohydrates again. I don’t have a plan sketched out for that, but most probably I would start exercising more.

Lean & Mean

Posted on by
4

It has been a while since I wrote anything here, I guess I am having a blogger’s block. Today I made a significant decision and I thought I should write about it, partly to keep my resolution and partly to break the writing block.

I have been gaining weight steadily in the past two years and I am beginning to get a bit concerned about it. I had bought a lot of clothes when I came to US but I cant wear any of them now because my waist size increased from 32 to 34. So I have decided to shed a few pounds and start feeling good about myself. A nice side effect would be I would be able to use some of my old clothes :) . I am just hoping all this would happen, but you never know unless you try it. So guess what, starting today I am going on a low-carb diet. I have done this once before with good results although I quit after a week unable to withstand the sugar craving. I lost something between 4 and 6 Kgs in that period. That experience gives me a lot of confidence now and I hope to do better this time, not necessarily in terms of quick weight reduction but in terms of getting better long term benefits ( I gained back the original weight within a month last time). One advantage that I have compared to previous time is that in US you have better access to food which is carbohydrate free. I really suffered that week in Bangalore while I was on diet because I couldn’t get enough protein & fat only food to keep me from going hungry. Going on a diet, in general, is pretty tough because the fact that you cant eat certain types of food makes you crave for exactly that. A significant factor for success is your ability to keep your mind off the diet, something that I couldn’t do last time. I hope to do something in the coming days – something that will keep me busy and keep my mind of the food craving. Maybe I will blog more or study something new or start a pet project.

Today I ate 4 eggs and some beef jerky for brunch. In the evening I ate some baked chicken as a snack. I am planning some sausages for dinner. There is a lightheaded feeling, but otherwise everything is going good. I don’t have a weighing scale at home so I don’t know my exact weight before starting the diet, but last time I weighed myself it was something between 188 and 190 pounds (around 85-86 Kg). Tomorrow I plan to buy a scale so that I can keep track of the weight during the diet period.

Wish me luck dudes and dudettes, and stay tuned for the diet results :-)