The Art of Software Testing by Glenford Myers : Preface

The author cites a study saying that 50% of the total cost are expended on testing a software program. When the book was written in 1979, there was very less literature available on testing software. Most professors and teaching assistants had complaints that the graduating students were entering the industry without any substantial knowledge of how to go about testing a program. It was a completely unexplored area of software development at that time. The book is targetted towards three class of audiences:

• Professional programmer: The book tries to add to the knowledge of testing techniques.
• Project Manager: The book tries to give new, practical information on the management of testing process.
• Computer science student: The book tries to address the problem of program testing and give some effective techniques.

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : My Opinion

I would give this book a rating of 3.5 out of 5. It is a good book to get introduced to the concepts of algorithm design. Algorithm design is not a topic that can be covered by a single book and so other books should be read along with this. Topics like backtracking is not covered in the book. To make it easy to browse, I am putting links of all the chapters below:

• Chapter 1
• Chapter 2
• Chapter 3
• Chapter 4
• Chapter 5
• Chapter 6
• Chapter 7
• Chapter 8
• Chapter 9
• Chapter 10
• Chapter 11
• Chapter 12 & 13
• Chapter 14
• Chapter 15
• Chapter 16
• Chapter 17
• Chapter 18
• Chapter 19
• Chapter 20
• Chapter 21
• Chapter 22
• Chapter 23
• Chapter 24
• Chapter 25
• Chapter 26
• Chapter 27
• Chapter 28
• Chapter 29
• Chapter 30
• Chapter 31
• Chapter 32
• Chapter 33
• Chapter 34
• Chapter 35

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 35

The authors defined approximation algorithm as an algorithm that returns near optimal results. An algorithm for a problem is said to have an approximation ratio of $ \rho (n) $, if for any input size $n$, the cost $C$ of the solution produced by the algorithm is within a factor of $ \rho (n) $ of the cost $C*$ of an optimal solution : $ max \left( \frac{C}{C*},\frac{C*}{C} \right) \le \rho(n) $.

An approximation scheme for an optimization problem is an approximation algorithm that takes as input not only an instance of the problem, but a value $ \sigma > 0 $ such that for any fixed $ \sigma $, the scheme is a $ (1 + \sigma) $ approximation algorithm. An approximation scheme is a polynomial time approximation scheme if for any fixed $ \sigma > 0 $, the scheme runs in time polynomial in the size $n$ of its input instance and is a fully polynomial time approximation scheme if its running time is polynomial both in $ \frac{1}{\sigma} $ and in the size $n$ of the input instance.

The authors then provide an approximation algorithm for vertex cover problem and prove that it is a polynomial time 2-approximation algorithm.

The authors then provide an approximate algorithm for traveling salesman problem with triangle inequality. The authors also prove a theorem that good approximate tours cannot be found in polynomial time unless P = NP.

The authors then provide greedy approximation algorithm for set cover problem and prove that it is a polynomial time $ \roh(n) $ - approximation algorithm.

The author then discuss two techniques for designing approximation algorithms:

1. Randomization
2. Linear Programming

The authors then provide a randomized approximation algorithm for MAX-3 CNF satisfiability. The author then provides an approximation algorithm for minimum weight vertex cover.

The authors then provide an exponential time exact algorithm for subset-sum-problem.

The authors then provide an algorithm to TRIM a list. Then the author provides an approximation algorithm for subset-sum-problem and prove that it is a fully polynomial time approximate scheme for the subset-sum-problem.

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 34

The author defines polynomial time algorithm as algorithm that on input of size $n$, has a worst-case running time of $O(n^k)$ where $k$ is any constant. The author describes that not all the problems can be solved in polynomial time. The author then focuses on "NP-complete" problems, the problems for which no polynomial time algorithm exists and nobody has been able to prove that no polynomial time algorithm can exist.

The author defines an abstract problem to be a binary relation on a set $I$ of problem instances and a set $S$ of problem solutions. An instance of a SHORTEST-PATH problem is a triple with a graph and two vertices while its solution is a sequence of vertices in the graph.

The authors provide definitions of alphabet and language. The authors also define operations such as union and intersection. The authors then define concatenation, closure/Kleene star, and complement. The author explains the meaning of an algorithm accepting a string and the language defined by acceptance of set of strings.

The author then calls a language decided by an algorithm $A$ if every binary string in $L$ is accepted by $A$ and every binary string not in $L$ is rejected by $A$.

A language $L$ is decided in polynomial time by an algorithm $A$ if there is a constant $k$ such that for any length-n string $ x \in L $, algorithm $A$ accepts $x$ in time $O(n^k)$. A language $L$ is decided in polynomial time by an algorithm $A$ if there is a constant $k$ such that for any length-n string $x \in \{0,1\}*$, the algorithm correctly decides whether $x \in L$ in time $O(n^k)$.

The author defines Hamiltonian Cycle and Hamiltonian Graph. A verification algorithm takes two arguments, an ordinary input string $x$ and a binary string $y$ called certificate. The algorithm $A$ verifies the input string $x$ if there exists a certificate $y$ such that $A(x,y)=1$.

The authors define complexity class NP as the class of languages that can be verified by a polynomial time algorithm. The complexity class co-NP is defined as set of languages $L$ such that $\overline{L} \in NP$.

A language $L_1$ is called polynomial time reducible to a language $L_2$, written $L_1 \le _P L_2$, if there exists a polynomial time computable function $ f : \{0,1\}* \rightarrow \{0,1\}* $ such that for all $ x \in \{0,1\}* $, $ x \in L_1 $ if and only if $ f(x) \in L_2$. $f$ is called the reduction function and a polynomial time algorithm $F$ that computes $f$ is called reduction algorithm.

A language $L \subseteq \{0,1\}*$ is NP-complete if

1. $L \in NP$, and
2. $L' \le _P L$ for every $L \in NP$.

If a language $L$ satisfies property 2, but not necessarily property 1, we say that $L$ is NP-hard.

A truth assignment for a boolean combinational circuit is a set of boolean input values. A one output boolean combinational circuit is satisfiable if it has a satisfying assignment, a truth assignment that causes the output of the circuit to be 1.

The circuit-satisfiability-problem is to determine whether a boolean combinational circuit composed of AND, OR and NOT gates satisfiable.

The size of a boolean combinational circuit is the number of boolean combinational elements plus the number of wires in the circuit. The authors then prove two lemmas based on which they derive the theorem that circuit-satisfiability-problem is NP-complete.

The author prove a Lemma and a theorem to show that satisfiability of boolean formulas is NP-complete.

The authors then discuss following problems to be NP-complete:

• The clique problem
• The vertex-cover problem
• The hamiltonian-cycle problem
• The travelling-salesman problem
• The subset-sum problem

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 33

The authors define line segment, vector, directed segment and endpoints. The authors also define cross-product of two vector. The authors describe a method to determine whether consecutive segments turn left or right and whether two line segments intersect.

The authors then provide pseudocode implementation of algorithm to determine whether two segments interact and prove its correctness. The authors define the concept of sweeping, and provides the general steps carried out in algorithms that use this method. The authors then provide pseudocode implementation of algorithm to determine if any of the segments intersect, prove its correctness and proves its running time to be $O(n \lg n)$.

The authors defines the concept of convex hull and discuss following methods to determine convex hull of a set of points:

1. Graham's scan: This takes $O(n \lg n)$ time.
2. Jarvis' march: This takes $O(n \times h)$ time.
   
3. Incremental method: This takes $O(n \lg n)$ time.
4. Divide and Conquer method: This takes $O(n \lg n)$ time.
5. Prune and Search method: This takes $O(n \lg h)$ time.

The authors provide pseudocode implementation of Graham's scan and prove its correctness.

The authors then discuss the problem of finding the closest pair of points. The authors provide pseudocode implementation of Divide and Conquer approach, prove its correctness and derive its running time to be $O(n \lg n)$.

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 32

The authors define the problem of string matching and discuss following four algorithms with text length of $n$ and pattern length of $m$:

• Naive - It takes nil preprocessing and $O((n-m+1) \times m)$ matching time.
• Rabin-Karp Algorithm - It takes $\Theta(m)$ preprocessing and $O(n-m+1) \times m)$ matching time.
• Finite Automata - It takes $O(m \times |\sum|)$ preprocessing and $\Theta(n)$ matching time.
  
• Knuth-Morris-Pratt - It takes $\Theta(m)$ preprocessing and $\Theta(n)$ matching time.

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 31

The author discuss about number-theoretic algorithms in this chapter. The author defines the concept of divisibility and divisors. The author also defines the concept of prime and composite numbers. The author provides division theorem, then proves it. The author defines remainders, common divisors and greatest common divisors, relatively prime integers and unique factorization.

The author then provides Euclid's algorithm to find greatest common divisor and state and prove its running time.

The author defines finite groups and subgroup and proves some theorems on it.

The author then discusses how to solve modular linear equations. The author proves some theorems and corollaries.

The author then describes the Chinese Remainder Theorem and prove it along with some corollaries.

The authors then discuss modular arithmetic with powers of an element instead of multiplication. The author states Euler's, Fermat's and Discrete logarithm theorem.

The authors then define RSA public-key cryptosystem and proves its correctness.

The authors then discuss primality testing and provides prime number theorem which provides details of density of prime numbers. The author provides pseudo-primality test and miller-rabin randomized primality test.

The author discusses the problem of integer factorization and provides Pollard's rho heuristic.