Abstract Data Types and Programming Methodologies
Lecturer:
Prof. Daniel R. Schlegel, 395 Shineman Center, daniel.schlegel@oswego.edu
Office/Lab hours: M 45pm; W 78am; Th 11:3012:30; or by appointment
Section 810: MWF 3:003:55pm, Shineman 444
Course Description:
A developing computer scientist must understand and explain how their proposed data structures and algorithmic solutions compare to other solutions in terms of complexity, run time, and resource requirements. This course introduces students to traditional techniques used to describe such solutions. In addition, we will look at classic data structures and their applications in order to expand the depth and breadth of a student’s knowledge.
This course is intended to challenge the student to design and implement software based on specifications prepared by the instructor. Throughout the semester, each student will need to identify appropriate design elements and justify their selections.
Course Objectives:
To employ objectoriented design techniques to model problems and solutions.
To employ decomposition techniques to break a program into smaller pieces
To analyze algorithmic solutions using asymptotic notation
To demonstrate effective use of abstract data types (ADTs), e.g., stacks, queues, lists, hash tables, trees, etc., in their designs
To demonstrate correct use of recursive algorithms and data structures
To articulate the advantages and disadvantages of competing algorithmic solutions
Textbooks:
Recommended: Koffman, E.B. and Wolfgang, P.A.T., Data Structures: Abstraction and Design Using Java, 3e. Wiley, 2015.
Useful Resources:
Introduction to Computer Science Using Java
Data Structures @ Wikibooks
Data Structure Visualizations
Java Tutorials @ Oracle
Java 8 Standard Libraries @ Oracle
JavaFX API
Java on Lynda.com
GNU Emacs Reference Card
Compiling on the Command Line Workshop Activity (by Oswego CSA)
Attendance Policy and Classroom Etiquette:
As per college policy, attendance in all sessions is obligatory. If you cannot attend a class meeting due to religious, athletic, health related circumstance, or circumstance of particular hardship, please notify me in advance via email. Please be ready to present proof, if necessary. Cell phones and headphones should not be out or used during lecture, and laptops should only be used for taking notes. If use of any electronics becomes distracting to other students I reserve the right to discontinue the allowance of their use.
Assignments:
All assignments will be completed alone, but working together without writing or sharing code to come up with general solutions is encouraged. The assignments are difficult, and I recommend starting work on them early, avoiding any tendency toward procrastination. You should plan on spending at least 10 hours per week on course work outside of class.
You will complete all assignments using a text editor, NOT an IDE like Netbeans, Eclipse, or Visual Studio. I will use GNU Emacs much of the time, but you are free to use Vim or a less fullyfeatured editor like nano or Notepad++ (but don’t expect me to know how to use it :)).
Grading:
Assignments will be submitted via Blackboard and graded according to the grading criteria. Code which does not compile or immediately crashes will receive no credit. There may be inclass presentations of your work.
You will have 7 days to use throughout the semester to submit late work. A maximum of 3 days may be used on any one assignment. We will say that a span of days where the university is closed will count only as one day. Therefore if an assignment is due on a Friday, it may be submitted Saturday or Sunday using only one late day. A submission on Monday will use two, and so on. Outside of this late policy, no late assignments will be accepted.
It is expected that each person participate during each class. As discussed above, attendance is required.
Each exam question will be assigned a point value (generally some multiple of 3 depending on difficulty), where the following scheme will be used in grading it:
0 – Did not attempt / No serious attempt
1 – Mostly incorrect solution
2 – Somewhat incorrect solution
3 – Perfect solution
If the problem is a multiple of 3, then intermediate scores will be given as appropriate. The total points received on all questions will then be summed and divided by the points possible and scaled as appropriate according to the percentages given below.
Assignments  50% 
Exam 1  15% 
Exam 2  15% 
Final Exam  20% 
You may not receive a grade more than one letter grade above min(exams, assignments). That is, if your exam average is D, the best grade you can achieve in the course is a C. Likewise if you receive an E average on your assignments, the highest grade you can expect is a D.
The default grading for the course will be along the university’s standard grading curve:
A: 93100  C+: 7779 
A: 9092  C: 7376 
B+: 8789  C: 7072 
B: 8386  D+: 6769 
B: 8082  D: 6066 
E: 059 
A more generous curve may be used, but should not be expected.
Schedule/Outline:
During the semester we aim to cover the following topics:
Object Orientation
Problemsolving Techniques
Recursion
Sorting Algorithms
Basic Search Algorithms
Lambdas and Streams in Java
Asymptotic Analysis
Data Structures
This syllabus and the course schedule are subject to change by the instructor. All changes and related justifications will be announced in class, and updates will be reflected in this web version.
Lecture slides will be maintained on Blackboard, but many lectures will include use of the whiteboard which may not be reflected in notes elsewhere.
Week  Day  Date  

1  Monday  8/27  First day of class Syllabus, Overview Download and import the development environment VM! Readings: Review Introduction to Computer Science Using Java parts 16,89 Be sure to answer office hours survey! 
Wednesday  8/29  Development Environment On your own: Development Environment Configuration Reading: Read tutorials as necessary from the above configuration document (e.g., linux, emacs, ...) 

Friday  8/31  Java Review  Anatomy of a Program Readings: From this page, read Getting Started with Swing, and begin reading the first few sections in Using Swing Components 

2  Monday  9/3  No Class  Labor Day 
Wednesday  9/5  Introduction to Swing Class code: SwingHello Readings: Introduction to Computer Science Using Java  Chapter 50  Inheritance Continue reading Swing tutorials 

Thursday  9/6  Add Deadline  
Friday  9/7  Drawing with Swing Class Code: SwingPaintDemo Assignment 1 due on Blackboard 9/23, 11:59pm 

3  Monday  9/10  No Class  Rosh Hashanah 
Wednesday  9/12  Inner Classes, Anonymous Inner Classes, Lambdas Intro  
Friday  9/14  Lambdas  
4  Monday  9/17  Streams Class code: Person Reading: A Guide to Streams in Java 8; First 3 sections of SAX tutorial 
Wednesday  9/19  No Class  Yom Kippur  
Thursday  9/20  Drop Deadline  
Friday  9/21  Two final stream examples XML and XML Parsing using the SAX parser 

5  Monday  9/24  SAX Parsing, continued Class code: XML Parsing Assignment 2 due on Blackboard 10/9, 11:59pm 
Wednesday  9/26  Asymptotic Analysis Introduction 

Friday  9/28  Dynamic Arrays  
6  Monday  10/1  Dynamic Arrays, continued Class code: DynamicArray Java 8 ArrayList Source 
Wednesday  10/3  Exam 1  
Friday  10/5  Linked Lists Introduction  
7  Monday  10/8  Linked lists, continued Primitive and reference types review OO Concept review: Encapsulation 
Wednesday  10/10  Linked lists, continued  
Friday  10/12  No Class  Dan sick  
8  Monday  10/15  Linked lists, concluded Class Code: LinkedList Reading: Java Generics Tutorial Assignment 3 due on Blackboard 
Wednesday  10/17  Linked List Variations; Stacks 

Friday  10/19  No Class  Fall Break Mid Term Grades Posted 

9  Monday  10/22  Stacks and Queues Class Code: LinkedStack and LinkedQueue 
Wednesday  10/24  Polymorphism; Generics Polymorphism Example 

Friday  10/26  Iterator and Iterable Class Code: LinkedListIterable Withdraw Deadline 

10  Monday  10/29  O(n^2) Sorting Algorithms: Selection Sort Sorting Algorithm Visualizer 
Wednesday  10/31  The Comparable interface Abstract Classes Assignment 4 due on Blackboard 11/18, 11:59pm 

Friday  11/2  Exam 2  
11  Monday  11/5  Complete Day 1 of the Doubly Linked List Exercise Dan at AMIA Annual Symposium 
Wednesday  11/7  Complete Day 2 of the Doubly Linked List Exercise Dan at AMIA Annual Symposium 

Friday  11/9  Complete Day 3 of the Doubly Linked List Exercise Dan at AMIA Annual Symposium 

12  Monday  11/12  Insertion Sort n^2 Sorting Benchmarks 
Wednesday  11/14  Trees Binary Search Trees 

Friday  11/16  BST Search / Insert BST Visualization 

13  Monday  11/19  BST Insert (concluded), Traversal Class code: BST Assignment 5 due on Blackboard 12/9, 11:59pm 
Wednesday  11/21  No Class  Thanksgiving Break  
Friday  11/23  No Class  Thanksgiving Break  
14  Monday  11/26  BST Remove 
Wednesday  11/28  Divide and Conquer Principle Merge Sort 

Friday  11/30  Merge Sort, continued  
15  Monday  12/3  Asymptotic Analysis of Merge Sort Quick Sort Intro 
Wednesday  12/5  Quick Sort Final Exam Study Guide 

Friday  12/7  A few final topics... Class Code  O(nlogn) sorting algorithms and benchmarks Last Day of Class 

Finals Week  Wednesday  12/12  Final Exam 24PM 
Academic Integrity:
While it is acceptable to discuss general approaches with your fellow students, the work you turn in must be your own. You may not turn in code found on the internet. If you have any problems doing the assignments, consult the instructor. Please be sure to read the webpage, “Academic Integrity“, which spells out all the details of this, and related policies. See my page on plagiarism for an explanation of what I consider cheating.
Disability Statement:
If you have a disabling condition, which may interfere with your ability to successfully complete this course, please contact the Office of Disability Services at dss@oswego.edu and x3358.