Spring 2021

Data Structures

Lectures: 2:00-3:30 Monday/Wednesday Online

Labratory: Tuesday 3:00 - 4:50 Online

This is a 4 credit hour course.

First class: Wednesday, January 20 First lab: Tuesday January 19

Labratory: Tuesday 3:00 - 4:50 Online

This is a 4 credit hour course.

First class: Wednesday, January 20 First lab: Tuesday January 19

Last day to drop:
Monday February 1.

OUTLINE
Week:

1-2 Review of fundamentals of Java and its data structures. Discussion of programming style, problem solving methodology, and the top-down approach. The use of drivers. Introduction to data abstraction. Discussion of the Intcoll class and its use in the positive(P), negative(N), last(L) application. Three versions of this class are built - two using integer arrays and one using boolean arrays. Another application of the Intcoll class to a puzzle is discussed.

3-4 Introduction to linked lists. A simple linked list version and a generic LinkedList class version of Intcoll. Stacks and queues and the application of stacks to valid strings of parentheses.

5-6 Introduction to binary trees and binary search trees. A binary search tree version of Intcoll. Recursion. Binary tree traversals and searching, inserting and deleting algorithms for binary search trees.

7 Sorting - insertionsort, mergesort, quicksort.

8-9 Hash Tables. The MultiIntcoll class and comparison of different versions of it. The Stringcoll class and the MultiStringcoll class. Inheritance and the derived version of the Stringcoll class from the MultiStringcoll class.

10-11 Min and max heaps and their application to sorting (heapsort).

12 Trees and graphs and mazes.

13-14 Comparison of different versions of MultiStringcoll. Application of binary trees and heaps to Huffman coding. Review.

Last day to withdraw:
Monday April 26.

Tuesday February 23 and Wednesday March 24 are Wellness Days(no Class or Lab)
Last Class Lecture: Monday, April 26. Last Lab Tuesday April 20

__Instructor:__ Dr. James F. Korsh

Office: SERC 322 Phone: 204-8199 Email: korsh@temple.edu

__Office Hours__: To be decided at the start of classes.

Prerequisite: At least a C- in CIS 1068 and in CIS 1166.

__Text (optional) and References:__

Objects, Abstraction, Data Structures and Design Using Java -
Wiley, Koffman and Wolfgang

JAVA An Introduction to Problem Solving & Programming - 5^{th}
Edition Pearson/Prentice Hall, Savitch and Carrano

Java: How to Program - Prentice Hall, Deitel and Deitel

Data Structures and Abstractions with Java - Pearson/Prentice
Hall, Carrano and Savitch

Date Structures and Algorithms in JAVA, 4th ed. - Wiley, Goodrich
and Tamassia

__Assignments:__ There will be a series of programming
assignments
(5-7). Each will normally build upon previous assignments. You must
write
each program yourself but are encouraged to obtain help - from
fellow
students, the laboratory instructor or the instructor - to get to the
point
that you can do so. The assignments are to be handed in on time or
credit may be lost. You may develop the programs on any system but the
program
must end up on our system so it can be accessed, edited, and run in the
laboratory.

__Laboratory:__ You are expected to attend and use the laboratory
equipment to access, edit, and run programs and to know how to use the
programming environment it provides. A significant part of your grade
will
be based on your performance in the laboratory which includes your assignment grades.
The laboratory provides
for your interaction with other students as well as the Lab instructor.

__Grades:__ Determined by a combination of performance in the
Laboratory, on quizes, on the Mid Term and on the Final Examination. You
should expect a short quiz each week. To
obtain a passing grade a student MUST submit satisfactory assignments and get credit for each one.
This means that first, the assignments must be turned in, be properly documented and execute correctly. Secondly, and most important, it is the
responsibility of the student to arrange to meet with the lab instructor (in lab or during office hours or at a
specially determined time) to run their program,
explain it, and answer any questions about it. How well you do this determines
your Laboratory grade for the assignment. NO CREDIT is given for an assignment
unless this second requirement is carried out.

__Late-to-class or missed class:__ It is the student’s
responsibility
to find out what material or announcements were missed. After reviewing
this material,, if more help is needed, then the student can see the
instructor
or lab instructor.

__Notes:__

1. Since this is a lower division course, it is subject to midsemester
evaluation.

2. You will be enrolled in this course on Canvas where much of the material
and other information needed for this course is located. Canvas can be accessed
through the TUPortal

3. Access to the Temple Technology USAGE policy can be obtained through
http://policies.temple.edu/list_docs.asp#T.

4. Any student who has a need for accommodation based on the impact
of a disability should contact me privately to discuss the specific
situation
as soon as possible. Contact Disability Resources and Serrvices at
215-204-1280.

5. Freedom to teach and to learn are inseparable facets of academic freedom.
The University hasd a policy on Student and Faculty and Academic Rights and
Responsibilities which can be accessed through
http://policies.temple.edu/getdoc.asp?policy_no=03.70.02.

__Description:__ The purpose of this course is to stress three
main
themes

- Basic Internal Data Structures and their impact on programs.

- The use of Data Abstractions and the implementation of Data
Abstractions
in Java using classes.

- Problem Solving Methodology and Algorithms and and their impact on programs.

This course covers basic data structures, important algorithms for carrying out needed
operations on them, and illustrates the positive effect a proper choice of data structure
can have on an application. The data structures will include arrays, linked lists, stacks
and queues, binary trees, binary search trees, hash tables, min and max heaps, trees and
graphs. The worst cast execution time of algorithm involving these data structures will
be emphasized.
The course will illustrate the use of recursion, a special case of top-down problem
solving, in developing algorithms.
Sorting will be covered including insertionsort, mergesort, heapsort and quicksort.
The application of binary trees and heaps to sorting will used to develop heapsort and also
for Huffman coding. Stacks will be used to determine valid parenthes strings. Graphs will
be used in solving mazes.
The Intcoll class will be introduced as a vehicle to demonstrate the use and implementaion
of classes and numerous versions of it will be built. Each version uses either integer
arrays, boolean arrays, a simple linked lists, generic linked lists, binary search trees,
or hash tables. The Intcoll class will be generalized to a MultiIntcoll class and will be
used as the starting point for developing a Stringcoll class and a MultiStringcoll class.
The MultiIntcoll class will be used to demonstrate the significant impact of data structure
choice on program execution time. The MultiStringcoll class will be used to count the
number of occurrences of words in text and to again illustrate again the significant impact
of data structure choice on program execution time.
Inheritance will be applied to derive another version of the Stringcoll class from the
Multistringcoll class.

The outline below should give some idea of what we will do and when we will do it, however, do not expect it to necessarily be rigidly followed. Be sure to talk with me about this at the start of classes if any significant deviation will present a problem to you.

1-2 Review of fundamentals of Java and its data structures. Discussion of programming style, problem solving methodology, and the top-down approach. The use of drivers. Introduction to data abstraction. Discussion of the Intcoll class and its use in the positive(P), negative(N), last(L) application. Three versions of this class are built - two using integer arrays and one using boolean arrays. Another application of the Intcoll class to a puzzle is discussed.

3-4 Introduction to linked lists. A simple linked list version and a generic LinkedList class version of Intcoll. Stacks and queues and the application of stacks to valid strings of parentheses.

5-6 Introduction to binary trees and binary search trees. A binary search tree version of Intcoll. Recursion. Binary tree traversals and searching, inserting and deleting algorithms for binary search trees.

7 Sorting - insertionsort, mergesort, quicksort.

8-9 Hash Tables. The MultiIntcoll class and comparison of different versions of it. The Stringcoll class and the MultiStringcoll class. Inheritance and the derived version of the Stringcoll class from the MultiStringcoll class.

10-11 Min and max heaps and their application to sorting (heapsort).

12 Trees and graphs and mazes.

13-14 Comparison of different versions of MultiStringcoll. Application of binary trees and heaps to Huffman coding. Review.