3 Semester Credit Hours

Course Description

This course is an introductory graduate course and advanced undergraduate course on the design and analysis of algorithms. We will cover algorithm design techniques such as divide-and-conquer, dynamic programming, and greedy algorithms for a variety of tasks such as sorting, searching, and graph problems. We will also cover lower bounds and computational models.

Prerequisites

• One year of college-level calculus

• A course in linear algebra and differential equations

• A calculus-based course in probability theory and statistics

• An undergraduate course in Discrete Mathematics covering sets, sequences, functions and relations, undirected and directed graphs, asymptotic notation for the running time of algorithms, (concept of proof, and techniques for constructing proofs (by contradiction, by induction)

• Experience with programming in C++ or Java

• An upper-division undergraduate course in algorithms and data structures covering topics such as: stacks, queues, heaps, trees, and graphs; sorting (mergesort, quicksort), searching, and hashing; elementary algorithm performance analysis.

• Comfort in applying mathematical concepts for analysis and in carrying out mathematical manipulations.

• General prerequisite: Students must have the knowledge resulting from completing all coursework in the curriculum for a BS degree in Computer Science from a regionally-accredited institution in the United States or the equivalent from a foreign institution; performance level in this coursework should be equivalent to a cumulative undergraduate GPA of 2.9 or better on 4.0 scale

Course Objectives

The students will learn to design and analyze algorithms for a wide variety of foundational problems occurring in computer science applications. The students will be instructed and master the following material:

• Mathematical foundations: Growth of functions, summations, recurrences, average-case and randomized analysis
• Computational models and lower bounds
• Divide-and-conquer
• Sorting and selection
• Searching
• Graph algorithms: Breadth-first search, depth-first search, minimal spanning trees, shortest paths, network flow
• Algebraic Algorithms: Matrix Algorithms and the Fast Fourier Transform
• Number Theory Algorithms and Cryptography

Course Topics

The following topics will be covered in the order given.

• Introduction: Efficient Algorithms for the Problem of Computing Fibonocci Numbers

• Models of Computation Asymptotics and Recurrence Equations

• Deterministic Selection and Sorting
• Amortized Analysis
• Probability Theory Overview and Analysis of Randomized Algorithms
• Randomized Algorithms for Selection and Sorting
• Search Algorithms
• Probabilistic Analysis of Hashing and Universal Hash Functions
• Advanced Topic: Hashing Polynomials and Algebraic Expressions 11. Graph Algorithms Using Depth First Search
• Breadth-First Search of Graphs
• Flow Algorithms
• Lexicographical Search: Applied to Scheduling Theory
• Computing Planar Separators
• Solution of Sparse Linear Systems
• The Fast Fourier Transform and Applications to Multiplication
• Advanced Algebraic Algorithms on Integers and Polynomials
• Number Theory Algorithms and Cryptography Algorithms
• Randomized Pattern Matching
• Approximation Algorithms
• Review of Algorithm Analysis
• Review of Graph Algorithms
• Course Review

Technical Requirements

You will need to have access to C++ or Java compilers for this course.  In addition, you will be required to have Windows Media Player to view the lectures. For the standard technical requirements, please go to the link below: http://www.waldenu.edu/c/Files/DocsGeneral/Getting_Started_Guide.pdf

Textbook

Required: Introduction to Algorithm (includes CD), Cormen, Leiserson, Rivest and Stein, McGraw-Hill, 2nd edition, 2001, ISBN:  0-07-297054-5.

Disclaimer: The course syllabus may differ slightly from this. Course descriptions will be provided in your online course. Textbook information is provided only to give more information about the course.  Do Not use this information to purchase a textbook.  Up-to-date information will be provided when you register.