CSE 214 Data Structures
Spring 2022
Final Exam
ExamFinal.java
Course Description (Syllabus)
An extension of programming methodology to data storage and manipulation on complex data sets.
Topics include: programming and applications of data structures; stacks, queues, lists, binary trees, heaps,
priority queues, balanced trees and graphs.
Recursive programming is heavily utilized.
Fundamental sorting and searching algorithms are examined along with informal efficiency comparisons.
Instructor
YoungMin Kwon (youngmin.kwon at sunykorea dot ac dot kr)
Office: B420
Office hours: TuTh 3:30pm ~ 4:30pm
TA
Shubhangi Garnaik (email: shubhangisaile.garnaik at stonybrook dot edu, zoom) Tu:700pm-10:00pm, F:7:00pm-10:00pm
Hyo Jong Chung (email: hyojong.chung at stonybrook dot edu, zoom) M:6:00ppm-10:00pm, F:6:00pm-10:00pm
Class hours: Lecture: TuTh 10:30am ~ 11:50am, Recitation: W 2:00pm ~ 2:55pm
Class room: Online (Zoom)
Text books and References
- "Data Structures and Algorithms in Java," by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser, 6th Edition,
Wiley, 2014, ISBN-10:1-11-877133-8.
Useful links
Grading
- Midterm exam 1: 20%
- Midterm exam 2: 20%
- Final exam: 25%
- Programming assignments: 30%
- Recitation exercises: 5%
- Attendance: missing more than 20% of the class will fail the course
Major Topics Covered in the Course
- Software Design: Specifications; memory and execution time efficiency; introduction to Big Oh notation;
abstract data types and examples; review of object-oriented techniques
- Linked Lists: Singly-linked lists; implementation; inserting and removing data; variations: doubly-linked lists,
circularly-linked lists; comparison of arrays and linked lists to store general lists
- Stacks and Queues: Basic operations of a stack; implementation using an array and a linked list;
various stack applications (evaluating postfix, conversion of infix to postfix, etc.). Basic operations of a queue;
implementation using an array and a linked list; queue applications (Josephus problem, simulations, Jai Alai)
- Recursion: Recursion and activation records, backtracking, introduction to dynamic programming, tail recursion
- Binary Trees: Terminology; implementation of trees using nodes; Binary search trees: insertion and removal of data;
Tree traversals. Heaps; implementation using arrays; use of a heap as a priority queue
- Balanced Trees: B-trees; 2-3-trees; 2-3-4-trees; red-black trees; AVL trees; splay trees; examples
- Searching: Sequential and binary search algorithms; hashing and hash tables; time analysis
- Sorting: Quadratic sorting algorithms; divide and conquer sorts (quick sort and merge sort); heap sort, time analysis
- Introduction to Graphs: Terminology; implementations using arrays and linked nodes; graph traversals
Course Learning Outcomes
- An ability to program using sophisticated features of object oriented programming.
- An ability to define and use data types, and use data structures.
- An understanding of the importance of time and memory efficiency in algorithm design.
Lecture Slides
- Lecture01: Objects and Classes,
programming assignment 1: hw1.zip
- Lecture02: Object-Oriented Design,
programming assignment 2: hw2.zip
- Lecture03: Order of Complexity
- Lecture04: Arrays and Singly Linked Lists
- Lecture05: Circularly Linked Lists and Doubly Linked Lists,
exercise: LinkedList.java
- Lecture06: List Abstractions,
programming assignment 3: hw3.zip
- Lecture07: Stacks,
programming assignment 4: hw4.zip
- Lecture08: Queues,
programming assignment 5: hw5.zip
- Lecture09: Recursion,
programming assignment 6: hw6.zip
- Lecture10: Trees,
programming assignment 7: hw7.zip
- Lecture11: Heaps,
programming assignment 8: hw8.zip
- Lecture12: Balanced Trees,
programming assignment 9: hw9.zip
- Lecture13: Maps,
- Lecture14: Sorting
programming assignment 10: RadixSort.java
- Lecture15: Graphs
Recitation
- Recitation01: Java programming, download: Euclidean.java
- Recitation02: Java programming 2, download: Polynomial.java
- Recitation03: Generics, download: Generic.java
- Recitation04: Linked lists, download: LinkedList.java
- Recitation05: Iterator, download: IterableSinglyLinkedList.java
- Recitation07: Queues, download: PathByQueue.zip
- Recitation08: Lambda, download: LambdaExercise.java
- Recitation09: Binary search tree, download: BinarySearchTree.java
- Recitation10: Heap sort, download: HeapSort.java
- Recitation11: Balanced tree, download: BSTRestructure.java
- Recitation12: Map, download: WordCounter.java
Academic Integrity
Students should pursue their academic goals in an honest way that does not put you at
an unfair advantage over other students.
You are responsible for all work you submitted and representing other's work as yours is always wrong.
Faculty is required to report any suspected instance of academic dishonesty to the school.
Regarding your homework, you are encouraged to discuss it with others, but you should write
your own code.
For more information please refer to
Academic integrity
Students with Disabilities
If you have a physical, psychological, medical or learning disability that may impact
your course work, please let the instructor know.
Reasonable accommodation will be provided if necessary and appropriate.
All information and documentation are confidential.
Critical Incident Management
The University expects students to respect the rights, privileges, and property of other people.
Faculty are required to report to the Office of Judicial Affairs any disruptive behavior that
interrupts their ability to teach, compromises the safety of the learning environment,
or inhibits students' ability to learn.
Covid-19: Classroom Mask Policy
Everyone participating in this class during in-person sessions must wear a mask or face covering
at all times or have the appropriate documentation for medical exemption.
Any student not in compliance with this policy will be asked to leave the classroom.
If students need to drink or eat, they should step out of the classroom to do so.