Generated on Tue Oct 25 10:19:18 2022

CS 372: Data Structures and Algorithms (JSON)

Catalog description: Introduction to efficient data structure and algorithm design. Order notation and asymptotic run-time of algorithms. Recurrence relations and solutions. Abstract data type dynamic set and data structures based on trees. Classic algorithm design paradigms: divide-and-conquer, dynamic programming, greedy algorithms.

Prerequisites: At least a C- in CS 272 and C S 278.    (Catalog Link)

Credits: 4 (3+2P)

Coordinator: Inna Pivkina

Textbook: Algorithms, Dasgupta, Papadimitriou, Vazirani. First Edition. McGraw Hill, ISBN 0073523402; and Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein. Third edition. The MIT Press. ISBN 9780262033848
    (also: online reading)

BS degree role: required

Course Learning Objectives

  1. Analyze the growth of functions via asymptotic notation
  2. Evaluate the asymptotic running time of a given algorithm
  3. Solve recurrence relations of the kinds encountered in algorithm analysis
  4. Design algorithms using the divide-and-conquer technique
  5. Design algorithms using the greedy technique
  6. Design algorithms using the dynamic-programming technique
  7. Use and analyze data structures based on trees
  8. Analyze the design, correctness, and time complexity of basic graph algorithms

Course Practicum Requirements

  1. Be able to implement algorithms in a programming language of choice
  2. Be able to compare empirical runtime differences on large input between efficient and inefficient algorithms

Course Topics

  1. Running time calculations
  2. Asymptotic notation
  3. Sorting algorithms
  4. Solving recurrences
  5. Divide-and-conquer algorithms
  6. Graph algorithms
  7. Data structures based on trees
  8. Greedy algorithms
  9. Dynamic programming

Course Improvement Decisions

(Course improvement decisions or recommendations from past assessments)

  1. FA19: broaden LO of binary search trees to other trees; improve practice on graph algorithms
  2. FA15: more examples of dynamic programming and divide and conquer
  3. FA13: improve presentation of divide and conquer

ABET Outcome Coverage

(Provide Mapping to ABET Student Outcomes)

  1. TBD

Other Notes

(Any important notes or issues to consider)

  1. none