MEMO

Course description

A presentation of asymptotic time and space complexity of sequential and parallel algorithms, using big-O and related notation. Complexity classes P and NP; tractable and intractable problems; and verification of algorithms by formal methods are also discussed.

Prerequisites

63.271 Data Structures

43.292 Discrete Math I

About this section

This course offers an opportunity to think in new ways about algorithms, processes, problems, and related performance issues.

Our approach will be rigorous and mathematical, using concepts that have been presented in your Data Structures course. .Many of the algorithms we discuss will be known to you: sorting, searching, tree manipulation. The notion of mathematical proof is a central theme of this course, as a way to obtain results in algorithm analysis and correctness.

We will use the mathematical notion of recurrences to describe the run times of algorithms based on the inductive (recursive) definitions of the functions computed by the algorithms.

We will make use of the logic you studied in Discrete Math, as applied to algorithms, when we take up formal verification of algorithms. The main tools are preconditions, postconditions, and loop invariants.

Half or more of the course (Topics 4-7) will cover different approaches to algorithm design, such as brute force, divide and conquer, greedyness, and dynamic programming.

We separate problems from solutions; in Topic 1, we present several algorithmic problems that each have various solutions of various efficiencies, which we’ll analyze in later topics. Some of the problems related to search, reasoning, and knowledge representation, which are topics in artificial intelligence.

An extension to the study of algorithm efficiency will be discussion of computational complexity of problems. If the running time of the best algorithm that solves a problem is a polynomial function of the size of input data, then the problem is in the class P, polynomial-time problems. If not, then it may at least be in the class NP, of problems whose algorithmic solutions can be checked in polynomial time. The hardest problems in NP are called NP-complete, and are thought to have no polynomial-time solutions. NPC problems are among those considered intractable, that is, not worth trying to solve due to their resource requirements.

We will contrast algorithmic computing with interactive computing and will distinguish the different types of associated problems. We will discuss evolutionary computation, one of the instructor’s research interests, as a mixture of algorithms and interaction. We will argue for a paradigm shift in how you think about computing. We present reinforcement learning, an interactive type of learning. Machine learning is a subfield of artificial intelligence.

One special aspect of this course will be coverage of parallel and distributed algorithms and processes.

An appropriate description of the scope of the course as presented is: the design, verification, and performance analysis of algorithms and interactive processes.

The course material is mostly language independent; examples will be in pseudocode.

Textbook

R. Johnsonbaugh and M. Schaefer. Algorithms. Pearson Prentice Hall, 2004.

Reading text material related to the course topics
is vital. We will refer to the required text often.

To contact instructor

Office hours (Hemenway Hall 318A):
M 11:30-12:30 p.m., W 9:30-10:30 a.m.,

Th 2:30-3:20 p.m., others by appointment

Telephone: (508) 626-4724

Email: dkeil@frc.mass.edu

URL: www.framingham.edu/faculty/dkeil

Classroom format

Format will center on lecture (with slides), discussion, and directed or group problem solving. Your questions and participation are important. Part of our responsibility is to express doubt about each other’s claims.

We will have one conversation in the classroom. Students may use laptops and enter and leave classroom, consistent with a focused work environment governed by attention to business and by mutual respect.

Group assignments

For each topic, the document “Study Questions” lists a set of problems suitable for homework, group work, or quizzes. Students will form teams of three or will be assigned to teams. Teams will divide the sets of problems, post solutions on Discussion Board, and present solutions in class. Quizzes will be drawn from same sets of questions, including questions covered by groups.

Student presentations

The textbook and instructor-prepared slides present dozens of algorithms. Each student will select at least two of these algorithms to present to the group. Topics that may be covered for an algorithm include the problem specification, the design approach, the pseudocode of the algorithm, example executions, time and space analysis, advantages and drawbacks, and easy, hard, and surprising aspects. Students may consult others in preparing to present.

Web aspect of course

This course is listed under http://framingham. blackboard.com. All course materials will be available there. The site hosts a private discussion board for students enrolled in the course and a Grade Book feature where quiz and other grades are posted..

Grading

There will be one short multiple-choice quiz per topic and three major quizzes. Make-ups for quizzes will be available at the time of the following quiz or at final-exam time.

Semester grade:

Major quizzes (3)                  30
Basic skills                            20
Mini quizzes                         10

Final exam 10

Group work assignments 15

Presentations 10
Participation 5

____

100 %

Basic skills

All students will demonstrate all the following (most of which are Data Structures and Discrete Math skills) during in-class quizzes or presentations:

1. Design algorithms to operate on arrays and linked data structures.

2. State and explain the running time of a basic algorithm as a function of the size of its input.

3. Discuss the efficiency of an algorithm in terms of the amount of data it operates on.

4. Solve a novel algorithm-design problem;

5. Prove that a given algorithm works, using invariants, preconditions, and postconditions;

6. Discuss the efficiency trade-offs of using arrays, hash tables, linked lists, heaps, and trees;

7. Distinguish several design approaches to algorithmic problems;

8. Differentiate algorithmic from interactive computation and sequential from parallel and distributed computing;

9. Recognize some intractable problems.

General performance objectives

1. Use big O, omega, and theta notation to give asymptotic upper, lower, and tight bounds on time and space complexity of algorithms.

2. Express and algorithmic problem and its solution as a recurrence relation.

3. Deduce recurrence relations that describe the time complexity of recursively defined algorithms.

4. Solve elementary recurrence relations.

5. Illustrate by example the basic terminology of graph theory, and some of the properties and special cases of each.

6. Demonstrate different traversal methods for trees and graphs.

7. Explain shortest path (spanning-tree) algorithms for graphs.

8. Design and implement a dynamic programming solution to a problem (AL4).

9. Model problems in computer science using graphs and trees.

10. Define the class of optimization problems.

11. Define the classes PTIME(f (n)), PSPACE(f (n), P and NP (Computing Curricula 2001, AL6).

12. Explain the significance of NP-completeness and relate it to the notion of intractability (AL6).

13. Prove that a problem is NP-complete by reducing a classic known NP-complete problem to it (AL6).

14. Define notions of performance measure for interactive problems.

15. Recognize algorithms as brute-force, greedy, divide-and-conquer, dynamic-programming, or probabilistic.

16. Explain the distributed paradigm (AL4).

17. Explain one simple distributed algorithm (AL4).

18. Determine when to use consensus or election algorithms (AL4).

19. Distinguish between logical and physical clocks (AL4).

20. Describe the relative ordering of events in a distributed algorithm (AL4).

21. Describe implementation of linked lists on a PRAM (CC2001).

22. Use parallel-prefix operation to perform simple computations efficiently in parallel. (AL4)

23. Explain Brent's theorem and its relevance (AL4).

24. Use the potential method to provide an amortized analysis of previously unseen data structure, given the potential function (AL4).

25. Explain why competitive analysis is an appropriate measure for online algorithms (AL4).

26. Explain the use of randomization in the design of an algorithm for a problem where a deterministic algorithm is unknown or much more difficult (AL4).

Accommodations

Students who seek accommodations during the semester because of disabilities should meet with the instructor after class or during office hours early in the semester.

Dates	Topic	Reading in Johnsonbaugh
9/3-9/4	Introduction	Ch. 1-2
9/5-9/12	1. Classes of problems	Passim; handouts
9/15-9/24	2. Formal verification	Handouts; sec. 7.2, 7.4; pp. 37-38
9/25-10/3	3. Introduction to algorithm analysis and recurrence relations	Ch. 2; Levitin, Ch. 3
10/6-10/9	4. Brute-force algorithms	Sec. 11.1; Levitin, Ch. 2
10/10/10/15	Major quiz (Topics 1-4)
10/16-10/23	5. Divide-and-conquer, decrease-and-conquer	Chs. 3-6
10/24-10/30	6. Greedy algorithms	Ch. 7
10/31-11/6	7. Space/time tradeoffs; dynamic-programming, and transform-and-conquer algorithms	Ch. 8
11/7-11/14	8. Computational complexity	Chs. 10-11
11/17-11/19	Major quiz (Topics 5-8)
11/20-11/26	9. Approximation and probabilistic algorithms; iterative improvement; evolutionary computation	Sec. 9.5, 11.2-11.5
12/1-12/4	10. Parallel and distributed algorithms and processes	Ch. 12; handouts
12/5-12/10	11. Analysis of interactive processes	Handouts
12/11-12/12	Pre-final quiz (Topics 1-11)
12/	Final exam (multiple choice; topics 1-11) Presentations