CS 1332

Overview

CS 1332 is a 3 credit-hour CS class with 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.

Class Structure

Average estimated hours per week: 9 hrs (3 hrs/week of classes + 2 hrs/week recitation + 4 hrs/week HW & Studying)

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.

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.

Topic 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)

Majors

Majors that take CS 1332 are listed below:

• Computer Science
• Computer Engineering
• Computational Media

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.

Resources

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

Spring 2021

The advanced topics in Spring 2021 included:

• SkipLists
• QuickSelect
• An introduction to Dynamic Programming