CSC 454/654: Algorithm Analysis and Design

Spring 2021

Department of Computer Science
UNC Greensboro
Class Meetings: Tues/Thurs 9:30-10:45, Online (Zoom link in Canvas)

Instructor

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).

Spring 2021 Note

For the safety of everyone, this class will be offered as a remote/online class in Spring 2021 due to the ongoing COVID pandemic. All class and individual meetings will use Zoom for videoconferencing – links and more information are available in Canvas. Classes are at the scheduled time, and students are expected to attend at that time. There will be real-time group exercises, using Zoom breakout rooms, that students are required to participate in. To take this class, you must have a computer that is capable of running Zoom and online collaboration apps (like Google Jamboard), and you must have and use camera/audio capabilities for collaboration during class.