20433 Data Structures 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 (or Mathematics for Students of Social Sciences), Differential and Integral Calculus I 4

Recommended: Introduction to Statistics and Probability for Science Students (or Introduction to Statistics for Students of Social Sciences I or Probability for Computer Science Students) 5

The course is based on a translation of the first 18 chapters of Introduction to Algorithms, by T.H. Cormen, C.E. Leiserson, and R.L. Rivest (MIT Press, 1990).

The course deals with two closely related topics: algorithms and data structures.

Topics: Mathematical foundations asymptotic notation, recurrences; Sorts Heapsort, Quicksort, sorting in linear time; Elementary data structures; Hash tables; Binary search trees; AVL trees, Greedy algorithms.


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 (20433) soon after taking the introductory course.

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

4or Calculus for Students of Economics and Management (10142) for students taking the program in Economics and Computer Science Systems and Applications.

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