COURSE DESCRIPTION

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.

COURSE TOPICS

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

PREREQUISITES

You must have taken CSE 114 and received a grade of "C" or better in order to take this course.

COURSE OUTCOMES

At the end of the course you should have the following knowledge and skills:

• An ability to program using sophisticated features of object oriented programming.
• An ability to define and use data types, and use algorithmic design.
• An understanding of the importance of time and memory efficiency in algorithm design.

LECTURE

01 Tuesdays & Thursdays 9:00am-10:20am A704

RECITATION

R01 Wednesdays 2:00pm-2:53pm A704

INSTRUCTOR

Richard McKenna richard@cs.stonybrook.edu B424 Office Hours: --Tuesdays 10:30am - 12:30pm --Thursdays 10:30am - 12:30pm

TEACHING ASSISTANTS (Office Hours in CS Commons)

OFFICE HOURS GRID

Start Time	End Time	MONDAY	TUESDAY	WEDNESDAY	THURSDAY	FRIDAY

PLATFORMS

This course will use the Java programming language, version 8. The programming environment for this semester will be the NetBeans IDE. The current version is 8.2. This IDE has a syntax-directed editor, run-time environment, debugger, unit tester, and additional software development tools. Note that the following references will be helpful to students while completing the Java programming assignments:

• Java 8 API - this reference provides a summary of all the Standard Edition classes, many of which we'll make use of.
  
  
• The Java Tutorial - walks one through programming in Java, including the new features of Java 8.
  
  

TEXTBOOK (online version available via link below)

Algorithms and Data Structures in Java
by Michael Goodrich, Roberto Tamassia, Goldwasser
Published by Wiley, 2014

COURSE COMPONENTS

• Recitations - Students will attend weekly recitations that will introduce use of essential development tools and will require completion of an exercise for submission.
  
  
• Homework Assignments - The assignments will develop a students ability to design and implement solutions requiring the use of various abstract and custom data structures. Grading will be based on functionality. Submitted code that does not compile will receive no credit. Late submissions will NOT be accepted. Programming assignments will be handed in electronically, instructions for which will be provided early in the semester.
  
  
• Exams - Exams will cover all lecture, recitation, and homework materials covered during the semester.
  
  

GRADING BREAKDOWN

Recitation Exercises	5%
7 Homework Assignments	35 %	(5 % each)
3 Exams	60 %	(20 % each)
	100 %

Note CEAS Policy: The Pass/No Credit (P/NC) option is not available for this course.

ACADEMIC DISHONESTY

You may discuss the homework in this course with anyone you like, however each student's submission, including written material and coding, must be his or her own work, and only his or her own work. Any evidence that written homework submissions or source code have been copied, shared, or transmitted in any way between students (this includes using source code downloaded from the Internet or written by others in previous semesters!) will be regarded as evidence of academic dishonesty. Additionally, any evidence of sharing of information or using unauthorized information during an examination will also be regarded as evidence of academic dishonesty.

The College of Engineering and Applied Sciences regards academic dishonesty as a very serious matter, and provides for substantial penalties in such cases, such as receiving an `F' grade, or expulsion from the University. For more information, obtain a copy of the CEAS guidelines on academic dishonesty from the CEAS office.

Be advised that any evidence of academic dishonesty will be treated with utmost seriousness. If you have a situation that may tempt you into doing something academically dishonest, resist the urge and speak with your instructor during office hours for help.

SUNY Korea Attendance Policy

Per the SUNY Korea Academic Bulletin:

1. All students of SUNY Korea are required to attend every class.
2. Unexcused absences will seriously affect the student’s final grade in the course.
3. If a student has over 20% unexcused absences in a course, the student’s final grade in the said course will be an ‘F’. For Example:
   1. If the class is a 150 minute class, and is held once a week, the 4th unexcused absence will lead to an F grade in the course.
   2. If the class is a 75 minute class, and is held twice a week, the 7th unexcused absence will lead to an F grade in the course.
   3. If the class is a 50 minute class, and is held three times a week, the 10th unexcused absence will lead to an F grade in the course.
   4. In the Intensive English Course (IEC), if a student misses more than 40 hours of the class in a semester, the student will receive an F grade in the course.
4. Students should report the reason for the absence to the instructor in advance, or immediately after the absence.
5. When a student gets an excused absence, the student must provide documentation for the said reason for the absence to the instructor.
6. The instructor of the course reserves the right to excuse absences.
7. The course instructor may excuse the absence if the submitted documentation fulfills the conditions below:
   1. Extreme emergencies (e.g. death in the family)
   2. Severe medical reasons with doctor’s diagnosis (Not a slight illness)
   3. Very important events (e.g. national conference, official school event)
8. At the end of the semester, the course instructor should submit a copy of the attendance sheet to the Academic Affairs Office.

SUNY Korea Disability Support

If you have a physical, psychological, medical or learning disability that may impact your course work, please contact One-Stop Service Center, Academic Building A201, (82) 32-626-1117. They will determine with you what accommodations, if any, are necessary and appropriate. All information and documentation is confidential.

In addition, this statement on emergency evacuation is often included, but not required: Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and One-Stop Service Center.

---