Hi There!

I'm Dan Schlegel, an Assistant Professor in the Computer Science Department at SUNY Oswego

CSC241 – Fall 2017

Abstract Data Types and Programming Methodologies

Lecturer:

Prof. Daniel R. Schlegel, 395 Shineman Center, daniel.schlegel@oswego.edu
Office/Lab hours: Monday 4pm-5pm; Tuesday 4pm-5pm; Friday 10am-11am
Section 810: MWF 3:00-3:55pm, Shineman 174

Course Description:

A developing computer scientist must understand and explain how their proposed data structure 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 a large-scale software system 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 object-oriented 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
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 (I don’t recommend this). If use of any electronics becomes districting 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 or Eclipse. I will use GNU Emacs much of the time, but you are free to use Vim or a less fully-features editor (but don’t expect me to know how to use it :)).

Grading:

Assignments will be evaluated in one of two ways, depending on the assignment:

Submitted via Blackboard and graded according to the grading criteria.
Satisfactorily demoed in person (i.e., everything works, good practices were used, and you can explain it), then submitted on Blackboard. In this case, partial solutions will not receive any credit.

You will be able to resubmit a single assignment to be re-graded, provided it is submitted before the next assignment is due, and that you submitted compiling code by the original deadline. Submit it again on Blackboard and send me an email to let me know you have done so and I will regrade it.

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.

Assignments50%
Exam 115%
Exam 215%
Final Exam20%

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: 93-100C+: 77-79
A-: 90-92C: 73-76
B+: 87-89C-: 70-72
B: 83-86D+: 67-69
B-: 80-82D: 60-66
 E: 0-59

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
Problem-solving 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.

WeekDayDate 
1Monday8/28First day of class
Syllabus and Project Overview
Remember to answer the office hours survey!
Assignment 1 Due 9/7 9/8, 11:59pm on Blackboard
Wednesday8/30Object orientation in Java intro/review
Friday9/1No Class
2Monday9/4Labor Day - No Class
Wednesday9/6Quick Emacs / console demo
Object orientation in Java intro/review (continued)
Class Code
Thursday9/7Add deadline
Friday9/8Value vs. Reference
Class Code
Assignment 2 Due 9/24, 11:59pm on Blackboard
3Monday9/11Class design
Readings: Review class inheritance on your own; Try these exercises
Wednesday9/13Interfaces & Abstract Classes
Class Code
Friday9/15Abstract Classes & Polymorphism
Class Code
4Monday9/18Drop deadline
Event-driven Programming; XML Parsing (SAX)
Wednesday9/20SAX Parsing; JavaFX / FXML
FXML Tutorial
Class Code
Readings: FXML Tutorials
Friday9/22Rosh Hashanah - No Class
5Monday9/25Quick HashMap Introduction;
Drawing with JavaFX
JavaFX Scene Graph
Class Code
Assignment 3 due 10/8, 11:59pm
Wednesday9/27Review for Exam 1
Friday9/29Exam 1
6Monday10/2Intro to Data Structures
Intro to Asymptotic Analysis
Expandable Array (see Java's ArrayList)
Class Code
Readings: Asymptotic notation @ Khan Academy
Wednesday10/4Asymptotic Analysis
Friday10/6ExpandArray concluded
Linked Lists
Class Code
7Monday10/9Linked Lists
Assignment 4 Due 10/22, 11:59PM on Blackboard
Class Code
Readings: Java Generics Tutorial
Wednesday10/11Java Generics
Class Code
Friday10/13Iterator and Iterable
Linked List Variations: Circular, Doubly Linked
Class Code
8Monday10/16Stacks and Queues
Class Code
Wednesday10/18Trees
Breadth-first Search
Friday10/20Depth-first Search
Recursion
Class Code
9Monday10/23Recursion, cont'd
Binary Search
Assignment 5 Due 11/5 11/9, 11:59PM on Blackboard
Wednesday10/25Binary Search Trees
Class Code
Friday10/27Binary Search Trees, cont'd
Class Code
Withdraw deadline
10Monday10/30Class Cancelled - Dan Sick
Wednesday11/1Lambda Expressions
Functional Interfaces and java.util.function
Method References
Class Code
Friday11/3Streams
Stream API
Readings: Streams Tutorial
11Monday11/6Exam 2
Wednesday11/8No Class - Dan at AMIA
Friday11/10
12Monday11/13Streams, concluded (map)
Sorting Intro
Assignment 6 Due 11/26 11/28 11/30 12/5, 11:59PM on Blackboard
Wednesday11/15Selection sort, concluded
Insertion sort
Class Code
Friday11/17Insertion sort, concluded
Comparing quadratic sorting methods
Sorting algorithms, visualized
Class Code
13Monday11/20Divide and conquer algorithms
Merge sort
Wednesday11/22No Class - Thanksgiving Recess
Friday11/24No Class - Thanksgiving Recess
14Monday11/27No Class - Dan Sick
Wednesday11/29Merge sort, concluded
Quick sort
Class Code
Friday12/1Quick sort, concluded
Just for fun: Advent of Code
Assignment 7 due 12/15/17, 11:59PM on Blackboard
15Monday12/4Binary Heaps
Class Code
Wednesday12/6In-class Game Demos!
Friday12/8Last day of class
Final Exam Study Guide
In-class Game Demos!
Finals WeekWednesday12/13Final Exam, 2-4pm, 174 Shineman

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.