CS 410 Top: Applied Algorithms

Credit Hours: 4
Course Coordinator: N/A
Course Description: Application of algorithms to solving a variety of problems. Factors influencing choice of algorithms for a given problem. Students will work in groups and individually to solve problems in and outside of class.
Prerequisites: CS 350, Algorithms and Analysis.
Goals: Know and have programmed a variety of algorithms Be able to choose an appropriate algorithm to solve a problem.

Upon the successful completion of this course students will be able to:

  1. Solve at least half of typical programming contest problems within three hours, working in teams. Solve at least one fourth within six hours, working alone.
  2. Apply a repertoire of algorithms and approaches to solving problems, in at least four distinct areas (such as combinatorics, computational geometry, cyphers, balanced tree structures).
  3. Develop alternate approaches to solving a problem and evaluate them for speed, space consumption, and difficulty.
  4. Find relevant information for solving a problem in standard references on algorithms and on the web.
  5. Describe an algorithm both orally and in writing.
  6. Do back-of-the-envelope calculations to estimate time for various algorithms that might be used to solve a problem.
Textbooks: "Programming Challenges," by Skiena and Revilla "Programming Pearls," second edition, by Bentley
References: Introduction to Algorithms, by Cormen et al
Major Topics: Graph Algorithms, including various searches, spanning trees, and path algorithms. Backtracking and Dynamic Programming. Combinatorics.
Laboratory Exercises: There will be a variety of problems presented for solution each week.

CAC Category Credits Core Advanced
Data Structures 1 1
Algorithms 1 1
Software Design
Computer Architecture
Programming Languages

Oral and Written Communications:
Social and Ethical Issues:
Theoretical Content: Algorithm analysis, problem abstraction, definition of invariants.
Problem Analysis: Students will analyze programming problems and puzzles, and devise approaches to solving them. The class will work on problems in groups and individually.
Solution Design: Students will design and implement solutions to a variety of programming problems and puzzles. This will be done both in groups and individually, and with problems at a variety of challenge levels.