CS 1332 - Data Structures and Algorithms

CS 1332, formally known as Data Structures and Algorithms, is a 3-credit Computer Science class taken as a core requirement for College of Computing and Computer Engineering majors. It provides a detailed overview of data structures and algorithms common in the field of software development and their implementation in the Java programming language. It is immediately preceded by CS 1331.

Workload

Like most 1000-level CS classes, CS 1332 primarily consists of homework assignments and a set of exams.

Homework assignments generally explore the implementation of a data structure or algorithm from scratch in the Java programming language. Aid is occasionally given through pseudo-code. Average homework length tends to be between 2 and 6 hours, depending on the difficulty.

Exams test knowledge of the theory of the data structure (efficiency, inner workings) as well as usage and implementation through multiple choice, fill-in-the-blank, and code writing questions.

Topics List

The topics covered in the course are as follows:

1. Arrays
2. Lists
   1. ArrayLists
   2. LinkedLists (Singly, Doubly, Circular)
3. Stacks and Queues
   1. Array-Backed Implementations
   2. Node-Backed Implementations
   3. Deques (Double-Ended Queues)
4. Binary Search Trees
   1. Tree Terminology
   2. Tree Traversal (In-Order, Post-Order, Pre-Order, Level-Order)
   3. Binary Search Trees
5. Heaps
   1. MaxHeaps
   2. MinHeaps
6. Self-Balancing Trees
   1. AVLs
   2. 2-4 Trees
7. HashMaps
   1. Probing
   2. Chaining
   3. Double Hashing
8. Sorting Algorithms
   1. Bubble Sort
   2. Insertion Sort
   3. Selection Sort
   4. Cocktail-Shaker Sort
   5. Merge Sort
   6. Quick Sort
   7. Radix Sort
9. Pattern Matching Algorithms
   1. Brute Force
   2. Boyer-Moore and Last Occurrence Table
   3. Knuth-Morris Pratt and Failure Tables
   4. Rabin-Karp
10. Graphs and Graph Algorithms
    1. Graph Terminology
    2. Breadth-First/Depth-First Search
    3. MSTs and MST Algorithms (Prim's and Kruskal's)
    4. Shortest Path Algorithm (Djikstra's)
11. A selection of more advanced algorithms and data structures (varies by semester)

Prerequisite Knowledge

Programming

As CS 1332's direct prerequisite is CS 1331, CS 1332 demands decent knowledge of the Java programming language. While CS 1332 does not expect you to remember minute details about the language (using the documentation during homework assignments is strongly encouraged), an understanding of programming concepts such as inheritance, polymorphism, generics, exceptions, and overriding is highly critical to success in the class.

Algorithms

As the class is called "Data Structures and Algorithms", one would assume some algorithms or algorithms analysis knowledge is needed, but no algorithms knowledge is needed other than the naive definition of big-O introduced in CS 1331.

Future Outlook

While the topics in CS 1332 are quite useful for technical interviews, many classes do not actually have CS 1332 as a direct prerequisite. The only key classes that use CS 1332 as a prerequisite are CS 3510 (Algorithm Design) and CS 3600 (Intro to AI). Overall, CS 1332 is quite important for the Theory and Intelligence threads, but is not an important prereq for classes in other threads.

Registration

CS 1332 has no lab or studio and an optional recitation. Recitation sections are under CS 1332R.

You must register for one of the lecture sections, marked by a single letter (A, B, C, etc.). If you do decide to register for recitation, you must register for a recitation section with the same leading letter (e.g. if you register for lecture section B, you must register for recitation section B01, B02, etc.).

Key Registration Footnote:

Computer Engineering students must wait 2 weeks before being given access to register for this course (unlike CS, CM students, who can register immediately).

• This is still shorter than the wait period for other majors, which is roughly 4 weeks.

Prerequisites

The sole prerequisite for CS 1332 is a C or higher in CS 1331.

Due to this prerequisite, CS 1332 expects all students to have a solid grasp of fundamental concepts in the Java programming language, including inheritance, polymorphism, and exception handling. However, at least when I took it in Fall 2018, you weren't allowed to use Java 8 features like lambdas, method references, and streams, so you probably don't need to be an expert at those.

Resources

Dr. HB's Summer 2020 syllabus is linked here. Note that the class now uses Java 11 instead of Java 8.

There's a free self-paced online version of the course available on edX. The videos are very well-produced.

Fall 2020

Due to the pandemic, recitations were livestreamed.

Spring 2021

The advanced topics in Spring 2021 included:

• SkipLists
• QuickSelect
• An introduction to Dynamic Programming