20407 Data Structures and Introduction to Algorithms 1

Credits: 6 intermediate credits in Computer Science

Prerequisites: none

Required: Introduction to Computer Science Using Java 2 (or Fundamentals of Programming with Java), Discrete Mathematics: Set Theory, Combinatorics and Graph Theory 3

Recommended: Infinitesimal Calculus I, Linear Algebra I, Probability for Computer Science Students (or Introduction to Statistics and Probability for Science Students) 4

The course is based on a translation of the first 14 chapters of Introduction to Algorithms (2nd ed.), by T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein (MIT Press, 2001).

The course acquaints students with basic concepts and methods related to algorithms and data structures development. Formal criteria for analyzing an algorithmic solution to a given problem are defined.

Topics: Growth of functions; Recurrences; Correctness of algorithms; Sorting; Medians and order statistics; The heap and its uses; Elementary data structures; Hash tables; Binary search trees; Red-black trees; Augmenting data structures.

---

1There is some overlap in the content of this and other courses. For details, see Overlapping Courses.

2or both Introduction to Computer Science Using Java I (20453) and Introduction to Computer Science Using Java II (20454). Students are advised to take Data Structures and Introduction to Algorithms (20407) soon after taking the introductory course.

3or Discrete Mathematics: Set Theory, Combinatorics and Logic (20283), which is no longer offered.

4This requires some mathematical sophistication, acquired by taking other courses in Mathematics.