Engr 691-13: Special Topics on Analysis of Algorithms
Jackson Computer Engineering & Telecommunications Program
Spring Semester 1997
Syllabus

Locations

School of Engineering Honor Code Statement

The Honor Code shall apply to all students, both undergraduate and graduate, registered in and/or seeking degrees through the School of Engineering. The Honor Code shall be understood to apply to all academic areas of the School such as examinations, quizzes, laboratory reports, themes, computer programs, homework, and other possible assignments. Only that work explicitly identified by the class instructor not to be under the Honor Code is excluded. The intent of the Honor Code is to recognize professional conduct and, thus, it shall be deemed a violation of the Honor Code to knowingly deceive, copy, paraphrase, or otherwise misrepresent your work in a manner inconsistent with professional conduct.

Course Summary

This course focuses on fundamental techniques for the design and analysis of correct and efficient algorithms. After reviewing the applicable mathematics and introducing the basic concepts, the course presents several design techniques. First a technique is introduced in its full generality, then it is illustrated by concrete examples drawn from several different application areas. Attention is given to the integration of the design of an algorithm with the analysis of its efficiency and correctness. The course also introduces the concepts of computational complexity.

Goals

The goal of this course is to give students the basic tools needed to develop their own algorithms.

Prerequisites

The prerequisites are completion of ENGR 501 (Fundamentals of Computer Science) and ENGR 502 (Software Systems) and familiarity with discrete mathematics. Students who have completed appropriate undergraduate studies in higher-level language programming, data structures, and mathematics may be admitted with the consent of the instructor.

Source Materials

Textbook:

Gilles Brassard and Paul Bratley.
Fundamentals of Algorithmics, Prentice Hall, 1996.
ISBN: 0-13-335068-1.

Readings:

Various journal and conference articles, research reports, etc., as appropriate.

Course Outline

1. Introduction to algorithmics
2. Review of applicable mathematics
3. Elementary algorithmics and asymptotic notation
4. Analysis of algorithms
5. Algorithm correctness
6. Review of data structures
7. Greedy algorithms
8. Divide-and-conquer algorithms
9. Dynamic programming algorithms
10. Graph algorithms
11. Parallel algorithms
12. Computational complexity

Grading

The grading scale is A [90..100], B [80..0), C [70..0), D [60..0), and F [0..60).

Three-fourths of the semester grade will come from the homework assignments and quizzes and one-fourth from the final examination.

Assignments and Quizzes

• All students are expected to study the relevant portions of the textbook and handouts in conjunction with our class discussions. Explicit reading assignments will not always be given.
• Homework problem sets will be assigned periodically (e.g., weekly). Typically, one week will be allowed for completion of each assignment.
• Most of the assignments will involve pencil-and-paper exercises to design and analyze algorithms or solve related problems.
• A few of the assignments may involve the programming of an algorithm.
• As appropriate, short in-class quizzes (tests) will be given.
• The lowest grade from the assignments will be dropped from the final grade calculation.
• Students may be asked to present their solutions to homework problems using the blackboard or overhead projector.
• All students are expected to do their own work on homework assignments (unless it is explicitly stated otherwise for an assignment).
• All students are expected to complete their homework assignments by their due dates.

Examination

• A comprehensive final examination will be given at the end of the semester.
• The exam may consist of a combination of in-class and take-home components.

UP to ENGR 691 root document?