# COMP-372 - Design and analysis of algorithms https://scis.lms.athabascau.ca/file.php/425/studyguide/index.html * https://scis.lms.athabascau.ca/mod/forum/discuss.php?d=134874#p256921 * https://scis.lms.athabascau.ca/mod/forum/discuss.php?d=136122#p257687 ```bash $ go install github.com/xlg-pkg/http-server@latest $ http-server . ``` Throughout this course, when you are asked to present an algorithm, this means that you need to do three things: 1. Present a clear, simple, and unambiguous description of the algorithm (in pseudocode, for example). The key here is keeping it simple. Uninteresting details should be kept to a minimum, so that the key computational issues stand out. For example, it is not necessary to declare variables whose purpose is obvious, and it is often simpler and clearer to simply say, “Add X to the end of list L” than to present code to do this or use some arcane syntax, such as “L:insertAtEnd(X).” 1. Present a justification or proof of the algorithm’s correctness. Your justification should assume that the reader is someone of similar background to yours, say another student in this class, and should be convincing enough make a skeptic believe that your algorithm does indeed solve the problem correctly. Avoid rambling about obvious or trivial elements. A good proof provides an overview of what the algorithm does and then focuses on any tricky elements that may not be obvious. 1. Present a worst-case analysis of the algorithm's efficiency, typically its running time (but also its space, if space is an issue). Sometimes this is straightforward, but if not, concentrate on the parts of the analysis that are not obvious. ## Unit 1: Foundations First, I assume that you know overall the importance of algorithms and what an algorithm is. But from this unit I hope you will gain a better understanding of what kinds of problems are solved by algorithms. Also you will become familiar with the framework we will use throughout the course to think about the design and analysis of algorithms. This unit addresses the following topics of interest: * an overview of algorithms and their place in modern computing systems * a thorough examination of two different sorting algorithms (insertion sort and merge sort) to determine their running times and develop a useful notation to express them * a definition of the notation (called asymptotic notation) that we use for bounding algorithm running times from above and/or below. Why do we choose asymptotic notation and analysis for algorithm analysis? This approach allows us to focus on the "big-picture" aspects of an algorithm’s running time. The unit has three sections. ### Section 1.1: Problems Your goals for this section are * to know the definition of algorithm, the reasons for studying algorithms, and the role of algorithms relative to other technologies used in computers. * to know what kind of problems are solved by algorithms. #### Learning Objective 1.1.1 – Understanding Algorithms When you have completed this objective, you should be able to * give a definition of the term algorithm. * identify practical applications of algorithms. * explain the role of algorithms in computing science. #### Required Activities * [X] Watch the video, [Algorithmic Thinking, Peak Finding](https://www.youtube.com/watch?app=desktop&v=HtSuA80QTyo&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb), on YouTube. * [X] Study Chapter 1 of the textbook. * [X] Do Exercises 1.1-4 and 1.2-2 from the textbook as part of Assignment 1. #### Discussion Question * [X] Review Problem 1-1 on pages 14–15 of the textbook. How would you go about solving this problem? * [X] Post a response, and comment on other students' responses to earn participation marks and develop your skills as an online communicator in the profession. * https://scis.lms.athabascau.ca/mod/forum/discuss.php?d=134874#p256921 ### Section 1.2: Complexity and Analysis Your goal for this section is to familiarize yourself with the framework that we will use throughout the course. #### Learning Objective 1.2.1 – Using Pseudocode When you have completed this objective, you should be able to * specify algorithms using pseudocode, that is, using the set of pseudocode conventions introduced in the textbook. #### Required Activities * [ ] Study Section 4.1 of the textbook. * [X] Study Section 2.1 of the textbook. * [X] Do Exercise 2.1-3 from the textbook as part of Assignment 1. #### Learning Objective 1.2.2 – Analyzing Algorithms When you have completed this objective, you should be able to * analyze the running time of algorithms. #### Required Activities * [X] Study Section 2.2 of the textbook. * [X] Do Exercise 2.2-3 from the textbook as part of Assignment 1. For supplemental material, I recommend that you watch this video (please ignore the beginning of the video talking about their course information. You can start from 17:20): * [X] http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/1 #### Learning Objective 1.2.3 – Designing Algorithms When you have completed this objective, you should be able to * explain the divide-and-conquer approach to the design of algorithms. * use it to develop a merge sort algorithm. #### Required Activities * [X] Study Section 2.3 of the textbook. * [X] Do Exercise 2.3-5 from the textbook as part of Assignment 1. ### Section 1.3: Asymptotics Your goals for this section are * to know the meaning of the asymptotic efficiency of algorithms. * to define several types of asymptotic notation. * to use standard methods for simplifying the asymptotic analysis of algorithms. #### Learning Objective 1.3.1 – Asymptotic Notation When you have completed this objective, you should be able to * define several types of asymptotic notation. #### Required Activities * [ ] Study Section 3.1 of the textbook. * [ ] Do Exercise 3.1-1 from the textbook as part of Assignment 1. For supplemental material, I recommend that you watch this video: * [X] http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/2 #### Learning Objective 1.3.2 – Standard Notation and Common Functions When you have completed this objective, you should be able to * review some standard mathematical functions and notations, and explore the relations among them. #### Required Activities * [ ] Study Section 3.2 of the textbook. * [ ] Do Problem 3-1 from the textbook as part of Assignment 1. Question to Ponder and Discuss * What are the common abuses in the basic asymptotic notations? * [ ] Post your thoughts on this to the COMP 372 General Discussion Forum. ## Unit 2: Divide-and-Conquer Algorithms In the last unit, you learned the concept of divide and conquer. This unit delves further into the divide-and-conquer method. It provides some examples of divide-and-conquer algorithms, including Strassen’s surprising method for multiplying two square matrices. And then, we will study methods for solving recurrences, which are useful for describing the running times of recursive algorithms. One of them, the "master method", is particularly powerful. For supplemental material, I recommend that you watch this video: * [X] http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/3 This unit will introduce * more examples of divide-and-conquer algorithms. * methods for analyzing recursive algorithms. The unit has three sections. #### Section 2.1: The Maximum-subarray Problem Your goal for this section is to become familiar with the maximum-subarray problem and its divide-and-conquer algorithm. Learning Objective 2.1.1 – The Maximum-subarray Problem When you have completed this objective, you should be able to * describe the maximum-subarray problem, and design and analyze its divide-and-conquer algorithm. #### Required Activities * [ ] Watch the video, Algorithms Lecture 13: Maximum Sub-array Problem using Divide-and-Conquer, on YouTube. * https://www.youtube.com/watch?v=yBCzO0FpsVc * [ ] Study Section 4.1 of the textbook. * [ ] Do Exercise 4.1-2 from the textbook as part of Assignment 1. #### Section 2.2: Strassen’s Algorithm for Matrix Multiplication Your goal for this section is to become familiar with Strassen’s algorithm for matrix multiplication. Learning Objective 2.2.1 – Strassen’s Method When you have completed this objective, you should be able to * describe Strassen’s method for matrix multiplication, and design and analyze its divide-and-conquer algorithm. #### Required Activities * [ ] Watch the video, Strassen’s Matrix Multiplication by Divide and Conquer, on YouTube. * https://www.youtube.com/watch?v=1AIvlizGo7Y * [ ] Study Section 4.2 of the textbook. * [ ] Do Exercise 4.2-1 from the textbook as part of Assignment 1. #### Section 2.3: Methods for Solving Recurrences Your goal for this section is to become familiar with the methods for solving recurrences. Learning Objective 2.3.1 – The Substitution Method When you have completed this objective, you should be able to * describe the substitution method for solving recurrences. #### Required Activities * [ ] Watch the video, Lecture 2: Asymptotic Notation | Recurrences | Substitution, Master Method (the Substitution part) * https://freevideolectures.com/course/1941/introduction-to-algorithms/2 * [ ] Study Section 4.3 of the textbook. * [ ] Do Exercises 4.3-2 from the textbook as part of Assignment 1. Learning Objective 2.3.2 – The Recursion-tree Method When you have completed this objective, you should be able to * describe the recursion-tree method for solving recurrences. #### Required Activities * [ ] Watch the video, Lecture 2: Asymptotic Notation | Recurrences | Substitution, Master Method (the Recursion part), at Free Video Lectures. * https://freevideolectures.com/course/1941/introduction-to-algorithms/2 * [ ] Study Section 4.4 of the textbook. * [ ] Do Exercise 4.4-7 from the textbook as part of Assignment 1. Learning Objective 2.3.3 – The Master Method When you have completed this objective, you should be able to * describe the master method for solving recurrences. #### Required Activities * [ ] Watch the video, Lecture 2: Asymptotic Notation | Recurrences | Substitution, Master Method (the Master Method part), at Free Video Lectures. * https://freevideolectures.com/course/1941/introduction-to-algorithms/2 * [ ] Study Section 4.5 of the textbook. * [ ] Do Exercise 4.5-3 from the textbook as part of Assignment 1. Assignment 1 It’s time to submit the problem set for Assignment 1 on the course home page in Moodle. ## Unit 3: Dynamic Programming and Longest Common Subsequence Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to sub-problems. Why do we call it programming? In fact, programming in this context refers to a tabular method, not to writing computer code. The term dynamic programming was first coined by Richard Bellman in the 1950s, a time when computing programming was an esoteric activity practiced by so few people as to not even merit a name. Back then programming meant planning, and "dynamic programming" was conceived to optimally plan multistage processes. Why do we need dynamic programming? Divide-and-conquer algorithms partition the problem into disjoint sub-problems, solve the sub-problems recursively, and then combine their solutions to solve the original problem. In contrast, dynamic programming applies when the sub-problems overlap—that is, when sub-problems share sub-sub-problems. In this context, a divide-and-conquer algorithm does more work than necessary and efficient! The basic idea behind dynamic programming is eliminating overlapping recursive calls by using more memory to keep track of previous values. I recommend that you to watch this video from: * [ ] Watch http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/15 This unit will address the following topics of interest: * developing a dynamic-programming algorithm * applying dynamic programming to optimization problems. The unit has two sections. #### Section 3.1: Dynamic Programming Your goal for this section is to become familiar with the method of dynamic programming and how to use the dynamic programming method to solve some optimization problems. Learning Objective 3.1.1 – Rod Cutting When you have completed this objective, you should be able to * examine the problem of cutting a rod into rods of smaller length in a way that maximizes their total value. #### Required Activities * [ ] Study Section 15.1 of the textbook. * [ ] Do Exercises 15.1-1 and 15.1-5 from the textbook as part of Assignment 2. . Learning Objective 3.1.2 – Matrix-chain Multiplication When you have completed this objective, you should be able to * describe another example of dynamic programming—how we can multiply a chain of matrices while performing the fewest total scalar multiplications. #### Required Activities * [ ] Study Section 15.2 of the textbook. * [ ] Do Exercises 15.2-1 and 15.2-2 from the textbook as part of Assignment 2. Learning Objective 3.1.3 – Elements of Dynamic Programming When you have completed this objective, you should be able to * discuss two key characteristics that a problem must have for dynamic programming. #### Required Activities * [ ] Study Section 15.3 of the textbook. * [ ] Do Exercise 15.3-1 from the textbook as part of Assignment 2. #### Discussion Questions Examine Exercise 15.3-6 in the textbook. Post a response, and comment on other students' responses to earn participation marks and develop your skills as an online communicator in the profession. #### Section 3.2: Longest Common Subsequence Your goal for this section is to learn how to find the longest common subsequence of two sequences via dynamic programming. Learning Objective 3.2.1 – Longest Common Subsequence When you have completed this objective, you should be able to * show how to find the longest common subsequence of two sequences via dynamic programming. #### Required Activities * [ ] Study Section 15.4 of the textbook. * [ ] Do Exercises 15.4-1 and 15.4-2 from the textbook as part of Assignment 2. ## Unit 4: Greedy Algorithms Before learning this unit, you should learn dynamic programming. Why do we study greedy algorithm? For many optimization problems, using dynamic programming to determine the best choices is overkill. Like dynamic-programming algorithms, greedy algorithms typically apply to optimization problems in which we make a set of choices in order to arrive at an optimal solution. The idea of a greedy algorithm is to make each choice in a locally optimal manner. A simple example is coin-changing: to minimize the number of Canadian coins needed to make change for a given amount e.g. CAD$38, we can repeatedly select the largest-denomination coin that is no larger than the amount that remains. We have 38-20=18, 18-10=8, 8-5 = 3, 3-2 =1, 1-1 =0. So $38 is changed to $20 + $10 + $5 +$2 + $1. A greedy algorithm approach provides an optimal solution for many such problems much more quickly than would a dynamic programming approach. However, is this approach effective? This unit will introduce matroid theory, which provides a mathematical basis that can help us to show that a greedy algorithm yields an optimal solution. Is the greedy method powerful? Yes, it is quite powerful and works well for a wide range of problems. More importantly, the greedy algorithm approach is more straightforward than the dynamic programming approach. I recommend that you to watch this video: * [ ] http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-16-greedy-algorithms-minimum-spanning-trees/ This unit addresses the following topics of interest: * the basic elements of the greedy approach * an important application of greedy techniques: designing data-compression (Huffman) codes The unit has only one section. #### Section 4.1: Greedy Algorithms Your goal for this section is to become familiar with greedy algorithms and their applications. Learning Objective 4.1.1 – An Activity-selection Problem When you have completed this objective, you should be able to * describe a simple but nontrivial problem, the activity-selection problem, for which a greedy algorithm efficiently computes an optimal solution. #### Required Activities * [ ] Study Section 16.1 of the textbook. * [ ] Do Exercise 16.1-2 from the textbook as part of Assignment 2. Learning Objective 4.1.2 – Elements of the Greedy Strategy When you have completed this objective, you should be able to * discuss some of the general properties of greedy methods and tell whether a greedy algorithm will solve a particular optimization problem. #### Required Activities * [ ] Study Section 16.2 of the textbook. * [ ] Do Exercise 16.2-2 from the textbook as part of Assignment 2. #### Discussion Questions Examine Exercise 16.2-3 in the textbook. Post a response, and comment on other students' responses to earn participation marks and develop your skills as an online communicator in the profession. Assignment 2 It’s time to submit the problem set for Assignment 2 on the course home page. ## Unit 5: Multithreaded Algorithms With the advent of multicore technology, every new laptop and desktop machine is now a shared-memory parallel computer. However, programming a shared-memory parallel computer directly using static threads is difficult and error-prone. This state of affairs has led to the creation of concurrency platforms, which provide a layer of software that coordinates, schedules, and manages the parallel-computing resources. In this unit, we introduce a model for dynamic multithreading, which is a simple extension of our serial programming model. This model allows the programmer to specify only the logic parallelism within a computation and the threads within the underlying concurrency platform schedule, which load-balance the computation themselves. That is, it allows programmers to specify parallelisms in applications without worrying about communication protocols, load balancing, and other vagaries of static-thread programming. And then we look at how to design multithreaded algorithms written for this model. We will see how the underlying concurrency platform can schedule computations efficiently. We present the metrics of work, span, and parallelism and use them to analyze multithreaded algorithms. This unit will * introduce the basics of the model. * show how to quantify parallelism in terms of the measures of work and span. * investigate a multithreaded algorithm for matrix multiplication. The unit has two sections. #### Section 5.1: Dynamic Multithreading Model Learning Objective 5.1.1 – The Basics of Dynamic Multithreading When you have completed this objective, you should be able to * explain the dynamic multithreading model. * use the metrics of work, span, and parallelism to analyze multithreaded algorithms. #### Required Activities * [ ] Watch this video: http://freevideolectures.com/Course/1941/Introduction-to-Algorithms/20, also available here: http://youtu.be/PYvJmLKhM-Y * [ ] Study Section 27.1 of the textbook. * [ ] View tutorial slides from http://student.athabascau.ca/~oscarl/COMP372/MultithreadedAlgorithms Part 1.pptx * [ ] Complete the following exercises: * [ ] Explain these keywords or terms relating to parallel algorithms: * [ ] Spawn * [ ] Sync * [ ] Nest parallelism * [ ] Strand * [ ] Computation dag * [ ] Work * [ ] Span * [ ] Critical path * [ ] Parallelism * [ ] Parallel for * [ ] Explain how a multithreaded scheduler works. * [ ] Do Exercises 27.1-1 and 27.1-7 from the textbook as part of Assignment 3. Questions to Ponder and Discuss * What do we need parallel algorithms? * What are the key features of the model for dynamic multithreading? * What are the important advantages of dynamic multithreading? * [ ] Post your thoughts on this to the COMP 372 General Discussion Forum. Further Readings At the end of each chapter in the textbook, you will find a section titled “Chapter notes.” While the references and readings mentioned in this section are not assigned, please feel free to examine them if you are interested, or ask questions on the COMP 372 General Discussion Forum. #### Section 5.2: Matrices Multiplication with Multithreading Learning Objective 5.2.1 – Matrices Multiplication with Multithreading When you have completed this objective, you should be able to * design and analyze multithreaded algorithms based on the standard triply nested loop, as well as divide-and-conquer algorithms. #### Required Activities * [ ] Study Section 27.2 of the textbook. * [ ] Do Exercise 27.2-1 from the textbook as part of Assignment 3. ## Unit 6: Number-Theoretic Algorithms #### Section 6.1: Concepts of Number Theory Learning Objective 6.1.1 – Elementary Number-theoretic Notions When you have completed this objective, you should be able to * discuss elementary number-theoretic notions. #### Required Activities * [ ] Study Section 31.1 of the textbook. * [ ] Explain the following elementary but important concepts: * Divisor * Prime number * Quotient, remainder, division theorem * Equivalence class modulo n, the set Zn * Common divisor, greatest common divisor * Relatively prime, pairwise relatively prime numbers * Unique factorization * [ ] Do Exercise 31.1-7 from the textbook as part of Assignment 3. #### Section 6.2: Euclid’s Algorithm Your goal in this section is to study and analyze one of the world’s oldest algorithms: Euclid’s algorithm for computing the greatest common divisor of two integers. Learning Objective 6.2.1 – Euclid’s Algorithm When you have completed this objective, you should be able to * explain and analyze Euclid’s algorithm for computing the greatest common divisor. #### Required Activities * [ ] Study Section 31.2 of the textbook. * [ ] Do Exercise 31.2-3 from the textbook as part of Assignment 3. #### Section 6.3: Modular Algorithms Learning Objective 6.3.1 – A Formal Model for Modular Arithmetic When you have completed this objective, you should be able to * describe a formal model for modular arithmetic within the framework of group theory. #### Required Activities * [ ] Study Section 31.3 of the textbook. * [ ] Explain the following concepts: * Group * Abelian group * Finite group * [ ] Do Exercise 31.3-1 from the textbook as part of Assignment 3. Learning Objective 6.3.2 – Modular Linear Equations When you have completed this objective, you should be able to * solve modular linear equations. #### Required Activities * [ ] Study Section 31.4 of the textbook. * [ ] Do Exercise 31.4-1 from the textbook as part of Assignment 3. #### Section 6.4: Chinese Remainder Theorem and Powers of an Element Learning Objective 6.4.1 – Chinese Remainder Theorem When you have completed this objective, you should be able to * apply the Chinese remainder theorem. #### Required Activities * [ ] Study Section 31.5 of the textbook. * [ ] Do Exercise 31.5-1 from the textbook as part of Assignment 3. Learning Objective 6.4.2 – A Repeated-squaring Algorithm When you have completed this objective, you should be able to * Apply a repeated-squaring algorithm for efficiently computing ab mod n, given a, b, and n. #### Required Activities * [ ] Study Section 31.6 of the textbook. * [ ] Do Exercise 31.6-1 from the textbook as part of Assignment 3. #### Section 6.5: RSA Public-key Cryptosystem Learning Objective 6.5.1 – RSA Public-key Cryptosystem When you have completed this objective, you should be able to * explain the RSA public-key cryptosystem. #### Required Activities * [ ] Study Section 31.7 of the textbook. * [ ] View this recommended video: http://youtu.be/ejppVhOSUmA * [ ] Explain the following concepts: * [ ] Digital signature * [ ] RSA public key * [ ] RSA private key * [ ] Do Exercises 31.7-1 from the textbook as part of Assignment 3. Assignment 3 It’s time to submit the problem set for Assignment 3 on the course home page. ## Unit 7: NP-completeness The Millennium Prize Problems are seven problems in mathematics presented by the Clay Mathematics Institute in 2000. As of December 2012, six of the problems remained unsolved. A prize of US$1,000,000 is offered by the institute for correct solutions. The Poincaré conjecture is the only Millennium Prize Problem to be solved so far, by Grigori Perelman, who declined the award in 2010. The seven problems are as follows: * P versus NP problem * Hodge conjecture * Poincaré conjecture (solved) * Riemann hypothesis * Yang–Mills existence and mass gap * Navier–Stokes existence and smoothness * Birch and Swinnerton–Dyer conjecture The first problem relates to our topic for Unit 8—NP-completeness. The question is whether, for all problems for which an algorithm can verify a given solution quickly (that is, in polynomial time), an algorithm can also find that solution quickly. The former describes the class of problems termed NP, while the latter describes P. The question is whether or not all problems in NP are also in P. This is generally considered one of the most important open questions in mathematics and theoretical computer science, as it has far-reaching consequences for other problems in mathematics, and in biology, philosophy, and cryptography (see P versus NP problem, proof consequences). Most mathematicians and computer scientists expect that P ≠ NP. The unit has two sections. #### Section 7.1: P ≠ NP Question Learning Objective 7.1.1 – Polynomial Time When you have completed this objective, you should be able to * formalize the notion of problem, and define the complexity class P of polynomial-time solvable decision problems. * determine how these notions fit into the framework of formal-language theory. #### Required Activities * [ ] Study Pages 1048-1053 and Section 34.1 of the textbook. * [ ] Explain the following concepts: * abstract problem * decision problem * optimization problem * encoding * concrete problem * polynomial-time solvable * complexity class P * alphabet, language * A language is accepted in polynomial time. * A language is decided in polynomial time. * [ ] Do Exercises 34.1-1 and 34.1-4 from the textbook as part of Assignment 4. #### Discussion Questions * Do you agree that the concept of a reduction is the central tool for analyzing the difficulty of a problem? * Why do we generally regard the polynomial-time solvable problems as tractable, but for philosophical, not mathematical, reasons? * Why should we use a formal-language framework to discuss solvability of decision problems? * Why do we focus on the concept of “problem” instead of “algorithm” in this unit? * [ ] Post a response, and comment on other students' responses to earn participation marks and develop your skills as an online communicator in the profession. Learning Objective 7.1.2 – Optimization and Decision Problems When you have completed this objective, you should be able to * define the class NP of decision problems whose solutions are verifiable in polynomial time. * formally pose the P≠ NP question. #### Required Activities * [ ] Study Section 34.2 of the textbook. * [ ] Do Exercises 34.2-1 and 34.2-8 from the textbook as part of Assignment 4. #### Section 7.2: NP-completeness Learning Objective 7.2.1 – Polynomial-time Reductions and NP-completeness When you have completed this objective, you should be able to * show we can relate problems via polynomial-time “reductions.” * define NP-completeness. * sketch a proof that one problem is NPC. #### Required Activities * [ ] Study Section 34.3 of the textbook. * [ ] Explain the following concepts: * polynomial-time reducible * NP-complete * NP-hard * [ ] Do Exercise 34.3-1 from the textbook as part of Assignment 4. Learning Objective 7.2.2 – NP-completeness Proofs When you have completed this objective, you should be able to * show how to prove other problems to be NPC much more simply by the methodology of reductions. #### Required Activities * [ ] Study Section 34.4 of the textbook. * [ ] Do Exercise 34.4-1 from the textbook as part of Assignment 4. Learning Objective 7.2.3 – Proving Problems NP-complete When you have completed this objective, you should be able to * show that a variety of problems are NP-complete. #### Required Activities * [ ] Study Sections 34.5.1 and 34.5.2 of the textbook. * [ ] Do Exercise 34.5-1 from the textbook as part of Assignment 4. ## Unit 8: Approximation Algorithms This unit shows you how to find approximate solutions to NP problems efficiently by using approximation algorithms. The unit has four sections. #### Section 8.1: Performance Ratios Learning Objective 8.1.1 – Basic Terms When you have completed this objective, you should be able to * define the basic terms relating to approximation algorithms. #### Required Activities * [ ] Study Pages 1106-1107 of the textbook. * [ ] Explain the following terms: * approximation ratio * ρ(n)-approximation algorithm * approximation scheme * polynomial-time approximation scheme * fully polynomial-time approximation scheme #### Section 8.2: The Vertex-cover Problem Learning Objective 8.2.1 – An NPC Minimization Problem When you have completed this objective, you should be able to * discuss the vertex-cover problem, an NP-complete minimization problem that has an approximation algorithm with an approximation ratio 2. #### Required Activities * [ ] Study Section 35.1 of the textbook. * [ ] Do Exercises 35.1.1 and 35.1-2 from the textbook as part of Assignment 4. #### Section 8.3: The Set-covering Problem Learning Objective 8.3.1 – A Greedy Heuristic When you have completed this objective, you should be able to * show how to use a greedy heuristic as an effective approximation algorithm for the set-covering problem, with a logarithmic approximation ratio. #### Required Activities * [ ] Study Section 35.3 of the textbook. * [ ] Do Exercises 35.3.1, and 35.3-3 from the textbook as part of Assignment 4. #### Section 8.4: The Subset-sum Problem Learning Objective 8.4.1 –A Polynomial-time Approximation Scheme When you have completed this objective, you should be able to * discuss a fully polynomial-time approximation scheme for the subset-sum problem. #### Required Activities * [ ] Study Section 35.5 of the textbook. * [ ] Do Exercises 35.5-2 and Problem 35-3 from the textbook as part of Assignment 4. # Divide-and-Conquer We solve a problem recursively, applying three steps at each level of the recursion. 1. Divide the problem into a number of subproblems that are smaller instances of the same problem. 1. Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner. 1. Combine the solutions to the subproblems into the solution for the original problem. When the subproblems are large enough to solve recursively, we call that the *recursive case*. Once the subproblems become small enough that we no longer recurse, we say that the recursion "bottoms out" and that we have gotten down to the *base case*. ## Recurrenes Give us a natural way to characterize the running times of divide and conquer algorithms. A *recurrence* is an equation or inequality that describes a function in terms of its value on smaller inputs.