Difference between revisions of "CS 1332"

From Georgia Tech Student Wiki
m (1morebyte moved page CS 1332 - Data Structures and Algorithms to CS 1332 over redirect: Rename)
m (add resource)
 
(17 intermediate revisions by 6 users not shown)
Line 1: Line 1:
−
{{DISPLAYTITLE:CS 1332 - Data Structures and Algorithms for Applications}}
 +
{{DISPLAYTITLE:CS 1332 - Data Structures and Algorithms}}
  +
[[Category:Courses|^CS^CS]]
−
==Overview==
  
−
CS 1332 is a 3 credit hour core CS class with no lab and an optional recitation. It is taken by all CS majors, as well as a few other majors.
  
   
  +
'''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]].
⚫
====Topic List====
  
−
CS 1332 covers commonly used data structures and relevant algorithms, and uses the Java language for implementation.
  
   
  +
== 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.
  +
{{Collapsed|
  ⚫
==Topics List==
  +
|
  +
The topics covered in the course are as follows:
 
#Arrays
  
#Arrays
  +
#Lists
−
#ArrayLists and LinkedLists
  
  +
##ArrayLists
  +
##LinkedLists (Singly, Doubly, Circular)
 
#Stacks and Queues
  
#Stacks and Queues
  +
##Array-Backed Implementations
  +
##Node-Backed Implementations
  +
##Deques (Double-Ended Queues)
 
#Binary Search Trees
  
#Binary Search Trees
  +
##Tree Terminology
  +
##Tree Traversal (In-Order, Post-Order, Pre-Order, Level-Order)
  +
##Binary Search Trees
 
#Heaps
  
#Heaps
  +
##MaxHeaps
⚫
#Self-Balancing Binary Trees (AVLs and 2-4 Trees)
  
  +
##MinHeaps
  ⚫
#Self-Balancing Trees
  +
##AVLs
  +
##2-4 Trees
 
#HashMaps
  
#HashMaps
  +
##Probing
  +
##Chaining
  +
##Double Hashing
 
#Sorting Algorithms
  
#Sorting Algorithms
  +
##Bubble Sort
  +
##Insertion Sort
  +
##Selection Sort
  +
##Cocktail-Shaker Sort
  +
##Merge Sort
  +
##Quick Sort
  +
##Radix Sort
 
#Pattern Matching Algorithms
  
#Pattern Matching Algorithms
  +
##Brute Force
  +
##Boyer-Moore and Last Occurrence Table
  +
##Knuth-Morris Pratt and Failure Tables
  +
##Rabin-Karp
 
#Graphs and Graph Algorithms
  
#Graphs and Graph Algorithms
  +
##Graph Terminology
  +
##Breadth-First/Depth-First Search
  +
##MSTs and MST Algorithms (Prim's and Kruskal's)
  +
##Shortest Path Algorithm (Djikstra's)
 
#A selection of more advanced algorithms and data structures (varies by semester)
  
#A selection of more advanced algorithms and data structures (varies by semester)
  +
}}
   
  +
== Prerequisite Knowledge ==
−
====How it fits in the Curriculum====
  
−
CS 1332 is the third introductory CS class (after CS 1301 and 1331) and continues to use the Java language that was first introduced in CS 1331. It is required for ALL threads, and is one of the more important class for prerequisites, as a large majority of Intelligence thread classes require it as a prereq. Data Structures knowledge is also generally helpful for all CS classes after this one.
  
   
−
==Current Registration Info==
 +
=== 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.
−
CS 1332 is NOT a [[linked course]]. However, there is a second, optional, but highly recommended component of the class: [[Recitation]]. Recitation sections are under CS 1332R.
 
   
  +
=== Algorithms ===
⚫
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.).
  
  +
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==
−
=== [https://oscar.gatech.edu/bprod/bwckctlg.p_disp_course_detail?cat_term_in=202108&subj_code_in=CS&crse_numb_in=1332 Prerequisites] ===
  
  +
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.
⚫
The sole prerequisite is a C or higher in CS 1331.
  
  ⚫
==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.).
−
=== Majors That Require This Class ===
  
   
  +
'''Key Registration Footnote:'''
−
* Computational Media
  
−
* Computer Engineering
  
−
* Computer Science
  
   
  ⚫
Computer Engineering students must wait 2 weeks before being given access to register for this course (unlike CS, CM students, who can register immediately).
⚫
=== Other Registration Info ===
  
  ⚫
*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.
⚫
* Computer Engineering students must wait 2 weeks before being given access to register for this course (unlike CS, CM students, who can register immediately).
  
  ⚫
==Resources==
⚫
** This is still shorter than the wait period for other majors, which is roughly 4 weeks.
  
−  
⚫
== Resources ==
  
 
Dr. HB's Summer 2020 syllabus is linked [https://ctl.gatech.edu/sites/default/files/images/hudachek-buswell_cs1332_syllabus.pdf here]. Note that the class now uses Java 11 instead of Java 8.
  
Dr. HB's Summer 2020 syllabus is linked [https://ctl.gatech.edu/sites/default/files/images/hudachek-buswell_cs1332_syllabus.pdf here]. Note that the class now uses Java 11 instead of Java 8.
   
  +
There's a [https://www.edx.org/professional-certificate/gtx-data-structures-and-algorithms free self-paced online version of the course] available on edX. The videos are very well-produced.
−
{{DEFAULTSORT:CS_1332_-_Data_Structures_and_Algorithms_for_Applications}}
  
  +
  +
==== Fall 2020 ====
  +
Due to the pandemic, recitations were [https://www.youtube.com/playlist?list=PLhg2ByK-Jd0l7iMtgw7KSnuy-EyBrRe6B livestreamed].
  +
  +
====Spring 2021====
  +
The advanced topics in Spring 2021 included:
  +
*SkipLists
  +
*QuickSelect
  +
*An introduction to Dynamic Programming

Latest revision as of 19:59, 30 May 2022


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[edit | edit source]

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[edit | edit source]

Programming[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

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[edit | edit source]

Due to the pandemic, recitations were livestreamed.

Spring 2021[edit | edit source]

The advanced topics in Spring 2021 included:

  • SkipLists
  • QuickSelect
  • An introduction to Dynamic Programming
Retrieved from "https://gt-student-wiki.org/mediawiki/index.php?title=CS_1332&oldid=1898"