Modern computers, from handheld devices to super computers with thousands of cores, rely on efficient algorithms for solving all types of computing problems. There are many algorithms to choose from, and not all are the right one for the job. After this course, you will be able to:
- recognize the best tool to use for your specific computing problem,
- design new algorithms based on the techniques in this course,
- show that your algorithms run correctly, and
- prove bounds on the amount of time and space your algorithms need.
Covered topics include divide and conquer, dynamic programming, greedy algorithms, amortized analysis, graph algorithms, randomized algorithms, NP-completeness, approximation algorithms, and undecidability.
Why I Teach This Course
This is one of my favorite courses, even as a student, and here is why:
- It challenges you to think critically and creatively to solve problems.
- The same basic algorithm can be applied to many different domains if you choose to look at them with an open mind. Who knew that the same graph algorithm could be used to plan the motion of robots and model protein folding at the molecular level? Or that an algorithm called “the pebble game” can analyze bridge/truss integrity and bond flexibility in a molecular structure?
- It teaches you to be aware of how implementation choices can dramatically impact algorithm performance and make informed decisions. Arrays vs. linked lists can be pivotal.
Course Information
The course syllabus is posted on Howdy.
Course Description:
Study of computer algorithms for numeric and non-numeric problems; design paradigms; analysis of time and space requirements of algorithms; correctness of algorithms; NP-completeness and undecidability of problems.
Credits: 3 (3 Lecture Hours)
Prerequisites: Grade of C or better in CSCE 221 and CSCE 222/ECEN 222; junior or senior classification or approval of instructor.
Learning Outcomes:
This course will teach you how to:
- explain fundamental algorithms and illustrate algorithmic techniques,
- prove the correctness, running time, and space complexity of a given algorithm,
- judge which algorithmic technique is best for a given situation,
- adapt existing algorithms to new situations and build solutions from algorithmic techniques learned,
- prove a problem is NP-complete, explain the implications, and build approximate solutions, and
- identify if a problem is undecidable and explain the implications.
We will cover many topics including:
- Divide and conquer
- Dynamic programming
- Amortized analysis
- Greedy algorithms
- Graph algorithms
- Randomized algorithms
- Complexity theory, approximation algorithms, and undecidability
Required Textbook:
Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, THIRD EDITION, MIT Press, 2009. You cannot use earlier editions.