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.