COMPUTER SCIENCE

Course Credits: 3 Units

Prerequisites: CMSC 123

CMSC 142: Design and Analysis of Algorithms

Course Description

The module introduces formal techniques to support the design and analysis of algorithms, focusing on both the underlying mathematical theory and practical considerations of efficiency. The aim of this module is to learn how to develop efficient algorithms for simple computational tasks and reasoning about the correctness of them. Through the complexity measures, different range of behaviors of algorithms and the notion of tractable and intractable problems will be understood.

Course Learning Outcomes

After completion of the course, the student should be able to:

  1. Learn good principles of algorithm design.
  2. Learn how to analyze algorithm and estimate their worst-case and average-case behavior (in easy cases)
  3. Become familiar with fundamental data structures and with the way these data structures can best be implemented become accustomed to the description of algorithms in both functional and procedural styles.
  4. Learn how to apply theoretical knowledge in practice.
  5. Synthesize an efficient algorithm in common engineering design situations.
Course Outline

UNIT 1. Introduction to Algorithms

  1. The role of algorithms in computing
  2. Defining algorithms
  3. Algorithms as a Technology
  4. Design and Analysis of Algorithms
  5. Growth of functions (asymptotic notation, standard notation, and common functions)

UNIT 2. Sorting and Searching

  1. Bogosort
  2. Stoogesort
  3. Insertion sort
  4. Selection sort
  5. Bubble sort
  6. Shell sort
  7. Merge sort
  8. Heapsort
  9. Asymptotic Analysis of Sorting Algorithms
  10. Running Time and Memory
  11. Sequential Search
  12. Binary Search
  13. Hashing

UNIT 3. Divide and Conquer Algorithms

  1. Divide and Conquer Algorithms (ex. Counting inversions, finding the median)
  2. Recurrence relations

UNIT 4. Dynamic Programming

  1. Elements of Dynamic Programming
  2. Knapsack Algorithms
  3. Longest Common Subsequence
  4. Longest Increasing Subsequence
  5. Minimum Edit Distance

UNIT 5. Greedy Algorithms

  1. Introduction to Greedy Algorithms
  2. Activity Selection
  3. Fractional Knapsack
  4. Set Cover
  5. While Loop
  6. Huffman Encoding

UNIT 6. Graphs

  1. Introduction to Graphs
  2. Graph Representations
  3. Breadth fast search and depth first search algorithms

UNIT 7. Minimum Spanning Tree

  1. Prim’s Algorithm
  2. Kruskal’s Algorithm

UNIT 8. Single source shortest path algorithms

  1. Single-source path in DAGs
  2. Dijkstra's algorithm
  3. Bellman-Ford Algorithm

UNIT 9. All-Pairs Shortest Paths

  1. Floyd-Warshall algorithm
  2. Johnson's Algorithm

UNIT 10. Maximum Flow

  1. Flow Networks
  2. Ford-Fulkerson Method
  3. Maximum bipartite matching

UNIT 11. NP-Completeness

  1. Polynomial Time
  2. Polynomial Time Verification
  3. NP-Completeness and Readability

UNIT 12. Approximation problems

  1. The vertex-cover problem
  2. The traveling salesman problem
  3. Set-Covering Problem
  4. Randomization and linear programming
  5. The subset-sum problem