Introduction to the Design and Analysis of Algorithms

Course
Course Catalog URL: 
http://catalog.iastate.edu/azcourses/com_s/
Identifier: 
COM S 3110
Professor(s): 
Dr. Prabhu,
Dr. Muhr

Last Updated: Fall 2024

Offered during Fall and Spring Semesters each year.

  1. Credits and contact hours: 3 credits
  2. Instructor’s or course coordinator’s name: Gurpur Prabhu and Trent Muhr
  3. Text book, title, author, and year: Introduction to Algorithms, Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein, 2022.
  4. Other supplemental materials: None

Specific course information

  1. Brief description of the content of the course: Basic techniques for design and analysis of algorithms. Sorting, searching, graph algorithms, string matching, and NP-completeness. Design techniques include dynamic programming, divide and conquer, greedy methods, and approximation. Asymptotic, worst-case, average-case, and amortized analyses. Topics from advanced data structures such as balanced trees and hashing. Programming projects.
  2. Prerequisites or co-requisites: COM S 2300 or CPR E 3100; COM S 2280, MATH 1660, and ENGL 1500 with C- or better
  3. Required, elective, or selected elective? Required

Specific goals for the course

  1. Specific outcomes of instruction:
    • Ability to understand problem statements based on mathematical/logical specifications
    • Ability to design solutions using standard algorithmic strategies (such as graph modeling, divide and conquer, and dynamic programming)
    • Ability to develop a correct and efficient implementation of algorithms from their description.
    • Knowledge of computational intractability.

Brief list of topics to be covered

  • Running time Analysis and Asympotitic Notation
  • Review of Data Structures: Heaps and Hasing
  • Graphs and Graph Exploration
  • Algorithm Design Strategies
    • Greedy Algorithms
    • Divide and Conquer
    • Dynamic Programming
  • NP and Computational Intractability
  • Introduction to Public-Key Cryptography