path: root/README.md

# 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.