# 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.