CMSC351

Introduction §

The CMSC351 course provides a brief introduction to algorithms. Here, we learn how to design algorithms, measure algorithms, and many of the common algorithms to problems we may face in the real world.

We discuss analysis of algorithms using Big-O Notation and Recurrence Relations (see Analysis of Algorithms). Then, we discuss a variety of algorithms and problems we can solve.

First, we propose some interesting problems and ways we can solve them.

• Coin Change
• Maximum Contiguous Sum

Then, we discuss some common algorithms in the field of Computer Science.

• Sorting Algorithms: Sorting Algorithms
• Binary Search: Binary Search
• Integer Multiplication: Karatsuba’s Algorithm
• Graph Algorithms
  • Graph Traversal
  • Dijkstra’s Algorithm
  • Floyd’s Algorithm
  • Minimal Spanning Trees
• Huffman Encodings: Huffman Algorithm
• Minimax Algorithm: Minimax Algorithm

Finally, we conclude with a discussion of $P$, $NP$, as well as the classic $P=NP$ question in Decision Problems, P vs. NP.