1998 Catalog Data : CSC 2400 : Design of Algorithms. Lecture 3. Credit 3. Advanced data structures and applications, problem solving strategies, heuristics, and complexity of algorithms. Prerequisite: CSC 2020. Corequisite: Math 1920.

Textbook: Course Notes by Instructor and Anany Levitin, The Design and Analysis of Algortihms

Time and Room BR 404, TR 1:30-3:00

Instructor:Dr. Frank Hadlock, Professor of Computer Science, Br 419, Ph 372-3687 Office Hours : 1:00-3:00M W

Goals:To aid the student in developing general skills in problem analysis and solution, and specific skills for algorithm design and analysis for classes of problems involving sorting, text processing, graphs & networks, and discrete optimization. General concepts to be stressed are problem solving paradigms, validation of algorithms, worst case analysis, and special case algorithms.

Prerequisites by Topic:

  1. Introductory discrete mathematics, including definitions of graphs and trees.
  2. Introductory programming in C, Java or other language supporting recursion and mechanisms for constructing complex data structures.
  3. Use of linked list and tree data structures.

Topics :

  1. Basic concepts of algorithms, including the definition of algorithm, specification of algorithms, correctness of algorithms, and efficiency of algorithms, algorithm design process.
  2. Big Oh notation and worst case and every case analysis of algorithms.
  3. Data Structures including graphs, stacks, queues, priority queues and heaps, hash tables.
  4. Incremental paradigm for algorithm design with application to list problems.
  5. Divide and Conquer paradigm for algorithm design with application to searching and sorting.
  6. Dynamic Programming paradigm for algorithm design with application to approximate string matching problems and to text compression.
  7. Greedy paradigm paradigm for algorithm design with application to shortest path and minimum spanning tree problems.
  8. Backtrack Programming paradigm paradigm for algorithm design with application to knapsack and minimum cover NP complete problems.
  9. Minimum Detour paradigm for algorithm design with application to shortest path problems in special classes of graphs.
  10. Convex Hull.
  11. Genetic Algorithms
  12. Tests (3) plus final examination.
  13. Programming (4) involving empirical testing of efficiency of alternative approaches.

Computer Usage: Computer usage is the primary project component of the course.

Category content:

  1. Algorithms:2 Credits or 66%
  2. Data Structures:.5 Credits or 16%
  3. Software Design.5 Credits or 17%

Design Content

CSC 240 Students use problem analysis and creative problem solving skills to develop functional specifications for a problem. They develop an algorithmic solution beginning with a paradigm and using stepwise refinement to arrive at a suitably specific pseudocode description of the algorithm to implement the algorithm in a programming language. Projects feature alternative solutions to the same problem.

Devise a system, individual effort, analysis, synthesis, creativity, iterative process, design methodology, alternate solutions, computer applications.

Project Format: The format for 2400 programming assignments / projects is as follows :

Problem Statement

Pseudocode expression for approach to solving problem (approximate and exact solutions). The pseudocode will be in the form of Structured English to be specified by the instructor.

Small problem instance illustrating approach to solution by stepping through pseudocode by hand

Implementation with commented source code : each function must be commented as to input, behavior, and output along with comment for each major control statement

Runtime scenarios for different problem instances, including the small problem instance (corresponds to testing)

Reporting of basic operation count as function of problem input size.

All materials must be typed in MS Word or computer generated and bound with a cover.

Some projects will be demonstrated (to class or instructor)

Grades : Grades will be 90+ is an A, etc., with 10% weight for each of the three tests, and 10% weight for each of the four programming assignments, 20% for the final, and 10% for class participation in class discussion.

Basic Concepts

This chapter will deal with basic concepts assoicated with algorithm design. An algorithm is simply a finite sequence of computational steps which accepts a problem input and produces an answer to that problem. Specification of an algorithm refers to the expression of the computational steps making up the algorithm. For example, if the problem to be solved is the problem of sorting a list into ascending order, then the text presented in Figure 1.3 is a pseudocode specification of an algorithm referred to as insertion sort. Design of an algorithm refers to the process of proceeding from the statement of the problem to be solved to an algorithm which solves it for every instance of the problem. Proceeding from the description of the sorting problem to a specification of the insertion sort algorithm would be a simple example of the design process. In acutal practice, design would also involve analysis of the proposed algorithmic solu-tion, as to correctness and efficiency, as well as an investigation of althernative solutions. In this text, a paradigm based approach to design will be emphasized. A paradigm is just a very high level algorithm for solving a wide class of problems; algorithms are derived from the paradigm by “filling in the blanks”. An instance of a problem is a set of input values for the problem. Correctness of an algorithm refers to whether or not the output produced by the algorithm is the correct answer to the problem for every problem instance. Sometimes we must satisfy ourselves with an approximate solution when determining the correct answer is computationally intractable (we would die of old age before the fastest computational device in existence could caculate a correct answer). Efficiency of an algorithm refers to time or memory requirements needed to calculate the answer. This is expressed in terms of the input size. For example, the input size for the sorting problem is the number of items n to be sorted.

1