CSCI 467

Design & Analysis of Algorithms

Coordinator: William Killian

Credits: 4.0

Description

Theory and techniques of algorithm design and analysis. For design, students will study variety of algorithmic solutions to problems from application areas including searching, selecting, sorting, graph theory, number theory and encryption. Design paradigms including greedy method, divide and conquer, dynamic programming, backtracking and branch-and-bound. For analysis, students will use formal analysis techniques including to formulate execution time of an algorithm. Software tools are used to measure resources used by a program during execution. Offered infrequently

Prerequisites

C- or higher in CSCI 340 and CSCI 362.

Sample Textbooks

Cormen, Leiserson, Rivist, Stein "Introduction to Algorithms" Third Edition

ISBN-13: 978-0262033848

Course Outcomes

  1. Understand many of the standard algorithms in use today.
  2. Be able to take an unfamiliar problem and solve it using one or more of the standard design paradigms.
  3. Be able to derive a formula that estimates the execution time of an algorithm and its memory usage.
  4. Be able to use software tools to measure a program's time and memory usage during execution.
  5. Be familiar with the theory and use of modem data encryption methods.
  6. Understand the basic theory of NP-Complete problems.
  7. Able to describe concepts of distribute processing.

Major Topics Covered

A. Overview

  • 1.1 Problems
  • 1.2 Models
  • 1.3 Algorithms
  • 1.4 Analysis
  • 1.5 Growth Rates
  • 1.6 Hard Problems

B. Searching

  • 2.1 Linear Search
  • 2.2 Jump Search
  • 2.3 Binary Search
  • 2.4 Randomized Algorithms

C. Selecting

  • 3.1 Rankings
  • 3.2 Finding the Best
  • 3.3 Finding the Second Best
  • 3.4 Finding the Best and Worst
  • 3.5 Finding the ith Best

D. Sorting

  • 4.1 Swap Sorts
  • 4.2 Insert Sorts
  • 4.3 Select Sorts
  • 4.4 Merge Sorts
  • 4.5 Split Sorts
  • 4.6 Lower Bounds on Sorting

E. Graphs

  • 5.1 Structures
  • 5.2 Exploring Graphs
  • 5.3 Shortest Paths
  • 5.4 Distributing

F. Numbers

  • 6.1 Exponential Numbers
  • 6.2 Euclidean Numbers
  • 6.3 Prime Numbers
  • 6.4 Public-Key Cryptography
  • 6.5 Digital Signatures
  • 6.6 Random Numbers
  • 6.7 Fast Fourier Transforms

G. Computational Intractability

  • 7.1 Hard Problems
  • 7.2 Models of Computation
  • 7.3 Turing Machines
  • 7.4 NP-Complete Problems
  • 7.5 P = NP?, major open question
  • 7.6 Approximate Solutions for Hard Problems

Sample Laboratory Projects

  1. Arbitrary precision integer arithmetic, experimental timing (e.g., Fibonacci sequence).
  2. Greedy algorithms (e.g., Kruskal and Prim minimum spanning tree, Dijkstra's shortest path).
  3. Divide and conquer (e.g., n-points closest pair).
  4. Dynamic programming (e.g., making change, knapsack problem).
  5. Probabilistic Algorithms (e.g., probabilistic test for primality).
  6. NP-Complete problems (e.g., traveling salesperson, satisfiability, quadratic congruences, Hamiltonian circuit).