CSC338

Course Description

This course presents an introduction to the techniques for designing efficient computer algorithms, proving their correctness, and analyzing their running time complexity. General topics include asymptotic behavior, solving summations and recurrences, algorithm design techniques such as divide-and-conquer, dynamic programming, and greedy algorithms applied to sorting, searching and graphs. The course includes an introduction to the theory of parallel and distributed algorithms

Learning Outcomes

• Analyze worst-case running time of algorithms using asymptotic analysis.
• Describe the divide-and-conquer paradigm. Describe and analyze algorithms that employ this paradigm.
• Describe the dynamic-programming paradigm. Describe and analyze algorithms that employ this paradigm.
• Describe the greedy paradigm. Describe and analyze algorithms that employ this paradigm.
• Explain the major algorithms for sorting. Provide analyses of these algorithms.
• Explain the major graph algorithms and their analyses.
• Discuss parallel computer architecture and parallel algorithm design strategies.
• Prepare and make professional presentations.

Prerequisites

• CSC335