CSC 454/654: Algorithm Analysis and Design

Spring 2022

Department of Computer Science
UNC Greensboro
Class Meetings: Tues/Thurs 11:00-12:15, Petty 219

Instructor

Special Note for Spring 2022

This is an in-person class, and certain policies and protections must be followed to protect everyone during the ongoing COVID-19 pandemic. For more information on UNCG and class policies, please see the class syllabus.

Overview

This class is all about the study of algorithms, covering how to model real-world problems with precise mathematical models, how to apply different algorithmic problem solving techniques, how to analyze efficiency and reason about correctness of algorithms, and how to communicate clearly about algorithms. Student work will include theoretical analysis and proofs, on-paper design, and programming solutions. Expected background includes a solid mathematical background in discrete mathematics and proof-writing (CSC 250 and CSC 350) and knowledge of data structures (CSC 330). While you aren't expected to be an expert, you should have working knowledge of asymptotic notation, recurrence relations, hash tables, tree structures, graphs, and basic graph algorithms such as search and path-finding algorithms.

By the end of this class, students will have studied and worked with design techniques including divide-and-conquer, dynamic programming, greedy algorithms, and randomized algorithms. Students will have seen a variety of powerful graph-based modeling and optimization techniques, including shortest path and max-flow algorithms. The final few weeks of the class will focus on fundamental barriers to efficient algorithmic solutions, including the study of NP-completeness and heuristic/approximation algorithms (both for solutions and to understand limitations).