Ashley's Journal

Preface - The Preface of the book initially looks at why algorithm analysis is important and that tactics people use to solve these problems. It labels two fundamental components of algorithms, first eh task of getting to the mathematical core of a problem, and second the task of identifying the appropriate algorithm design techniques. The rest of the chapter outlines that content of the book starting with the explaining the importance of the exercises in the back. The rest of the preface is dedicated to summarizing the separate chapters. With each chapter it provides insight to the important topics and relates it to real life examples of when it can be used.

Chpater 1 - Intro: Some Representative Problems First the chapter provides an example of the problem and highlights the crucial issues of the problem that would need to be specifically solved in an algorithm. Next it goes into the engagement problem, explaining each element of the problem, such as the initial state, defining stability and perfect matching, and analysing the algorithm once finished. Next the chapter goes over five basic representative problems that often appear in algorithm analysis (interval scheduling, weighted interval scheduling, bipartitematching, independent set, and competitive facility location). In each subsection about the specific type of problem the book explains the importance of each analysis and how they all differ from each other. Chapter 2 Chapter 2.1 and 2.2 In section 2.1 the chapter defines and discusses the importance of efficiency. It goes through three different definitions of an efficient algorithm, highlighting its strengths and flaws. It also goes over worst-case running time and brute force searches, and how worst-case running time gives an accurate capturing of the efficiency of a problem. In section 2.2, the chapter directly goes deeper into defining the running-time of a problem, such as the asymptotic upper bound, asymptotic lower bound, and the tight bound. Lastly, 2.2 covers the different properties of the upper and lower bounds, such as the transitive property and the sums of functions property, and covers three common functions of the asymptotic bounds (polynomial, logarithmic, and exponential).