CSIS 310 Data Structures

---

Course Description

An introduction to the concepts of information organization and manipulation. The course covers basic sequential structures such as array-backed lists, singly- and doubly-linked lists, stacks, and queues, and moves on to more complex data structures such as trees, graphs, priority queues, and dictionaries. Programming projects are completed in one or more high-level languages.

Instructor

J. Walker Orr, Ph.D.
Office hours: WMR 216 (see schedule)

Texts

required

• D.A. Bailey, Java Structures, √7 Edition, 2007.
  (full text online)

recommended

• A.V. Aho and J.D. Ullman, Foundations of Computer Science, C Edition. W.H. Freeman and Company, 1994.
  ISBN: 978-0716782841 (full text online)

Resources

• Oracle Java API Reference
• Oracle Java Development Kit (JDK)
• JUnit
• In-class activities - section A
• In-class activities - section B

---

Objectives

Students will:

• Understand how to build and use basic data structures, including lists, stacks, queues, trees, graphs, priority queues, and maps
• Be introduced to basic computational complexity and algorithm analysis as applied to data structures
• Be able to choose, implement, and use data structures appropriate to a given problem
• Be capable of using these basic data structures to build more complex data structures and complete programs to solve specific problems

---

Course Organization

This course will be programming intensive. Though many data structures are now provided by libraries or programming languages themselves, we will implement many of these structures in this course to gain programming experience and an understanding of basic programming principles. The data structures studied here form the fundamental building blocks used in developing complex programs.

I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships.

Programming assignments will be carried out in a prescribed high-level language. Instruction in the use of this language will be provided, but the focus of this course will not be on a particular programming language, but on language-independent data structures. You are assumed to have previous experience with one or more high-level languages and will be expected to independently acquire the language skills necessary for this course with a minimum level of instruction.

Collaboration

See the GFU CS/IS/Cyber policies for collaboration and discussion of collaboration and academic integrity. Most students would be surprised at how easy it is to detect collaboration in programming—please do not test us! Remember: you always have willing and legal collaborators in the faculty.

Almost all of life is filled with collaboration (i.e., people working together). Yet in our academic system, we artificially limit collaboration. These limits are designed to force you to learn fundamental principles and build specific skills. It is very artificial but intensional for your own benefit. The only way for you to learn is by doing the work.

To be clear, do not:

• Copy other students work
• Copy code from an online sources such as Stack Overflow
• Generate code with "AI" tools such as ChatGPT or GitHub Copilot

Oral Defense Policy

I may require an oral defense for any assignment at my discretion. This is a brief meeting where you explain and defend your submitted work. This process mirrors the business world, where professionals routinely present and defend their analyses to supervisors and clients, and ensures your work represents authentic learning. If required, you must schedule and complete your defense within 72 hours of notification to receive a non-failing grade; without the defense, you will receive a zero on the assignment. If the work product is a group submission, all team members must be present at the meeting. Routine scheduling conflicts (work, other classes, social commitments) do not qualify for extensions. Be prepared to summarize your arguments, explain your methodology, defend your conclusions with evidence, and answer questions about your work and your problem solving process. You should be ready to articulate and defend the rationale behind your work.

Spiritual Formation

Besides EYS, I am always available to discuss the Christian faith if you have any questions or doubts. Send me an email, come by my office hours, or talk to my after class, Christ is the reason I am at GFU, I always have time to talk about faith.

---

Grading

The final course grade will be based on:

Grading Scale

• 40% Homework & programming assignments
• 60% Exams

---

Tentative Schedule

Week 1 · Mon Introduction

Week 1 · Wed Expectations Misc: Examples

Week 1 · Fri Abstraction & Encapsulation Reading: Ch. 1

Week 2 · Mon Art of Programming

Week 2 · Wed Java Programming Reading: Appx. B

Week 2 · Fri Java Review: Classes & Instances Reading: Ch. 1

Week 3 · Mon Java Review: Inheritance; Generics; Javadoc Reading: Ch. 4 Misc: Javadoc

Week 3 · Wed Serve Day—no classes

Week 3 · Fri Robust Programming: Assertions & Exceptions Reading: Ch. 2 Misc: Exceptions

Week 4 · Mon Robust Programming: Unit Testing Misc: JUnit

Week 4 · Wed Arrays

Week 4 · Fri ArrayList & Vector Reading: Ch. 3.1–3.5

Week 5 · Mon Introduction to Algorithm Analysis Reading: Ch. 5.1–5.2

Week 5 · Wed Complexity Categories & Big-Oh Notation Reading: Ch. 5.3

Week 5 · Fri Amortized Analysis

Week 6 · Mon Midterm exam review

Week 6 · Wed Midterm exam Reading: Ch. 1–5

Week 6 · Fri Midterm exam post mortem

Week 7 · Mon Abstraction & Interfaces Reading: Ch. 7 Misc: Collections

Week 7 · Wed Iteration Reading: Ch. 8.1–8.2

Week 7 · Fri Mid-semester break—no classes

Week 8 · Mon Abstract List Reading: Ch. 9.1–9.3

Week 8 · Wed List: Implementations Reading: Ch. 9.4–9.7

Week 8 · Fri List: Analysis Reading: Ch. 9.8–9.9

Week 9 · Mon Searching Reading: Ch. 11.1–11.2

Week 9 · Wed Sorting: Insertion, Selection, Merge Sort Reading: Ch. 6.1–6.4

Week 9 · Fri Sorting: Quick Sort Reading: Ch. 6.5, 6.7

Week 10 · Mon Stack Reading: Ch. 10.1

Week 10 · Wed Queue Reading: Ch. 10.2

Week 10 · Fri Deque Reading: Ch. 10.4

Week 11 · Mon Midterm exam review

Week 11 · Wed Midterm exam Reading: Ch. 6–11

Week 11 · Fri Midterm exam post mortem

Week 12 · Mon Abstract Tree Reading: Ch. 12.1

Week 12 · Wed Binary Tree Reading: Ch. 12.4, 12.7

Week 12 · Fri Binary Tree: Traversals Reading: Ch. 12.6

Week 13 · Mon Priority Queue; Heap Reading: Ch. 13.1, 13.3

Week 13 · Wed Binary Min-Heap Reading: Ch. 13.4

Week 13 · Fri Thanksgiving break—no classes

Week 14 · Mon Heap: Analysis Reading: Ch. 13.4

Week 14 · Wed Abstract Graph Reading: Ch. 16.1

Week 14 · Fri Directed Graph: Implementations Reading: Ch. 16.2–16.3

Week 15 · Mon Maps & Hashing Reading: Ch. 15.1–15.4

Week 15 · Wed Directed Graph: Analysis Reading: Ch. 16.4–16.5

Week 15 · Fri Final exam review

Week 16 · TBD Final exam Reading: Ch. 12–16

Week	Day	Topic	Reading	Misc
Week 1	Mon	Introduction	-	-
	Wed	Expectations	-	Examples
	Fri	Abstraction & Encapsulation	Ch. 1	-
Week 2	Mon	Art of Programming	-	-
	Wed	Java Programming	Appx. B	-
	Fri	Java Review: Classes & Instances	Ch. 1	-
Week 3	Mon	Java Review: Inheritance; Generics; Javadoc	Ch. 4	Javadoc
	Wed	Serve Day—no classes	-	-
	Fri	Robust Programming: Assertions & Exceptions	Ch. 2	Exceptions
Week 4	Mon	Robust Programming: Unit Testing	-	JUnit
	Wed	Arrays	-	-
	Fri	ArrayList & Vector	Ch. 3.1–3.5	-
Week 5	Mon	Introduction to Algorithm Analysis	Ch. 5.1–5.2	-
	Wed	Complexity Categories & Big-Oh Notation	Ch. 5.3	-
	Fri	Amortized Analysis	-	-
Week 6	Mon	Midterm exam review	-	-
	Wed	Midterm exam	Ch. 1–5	-
	Fri	Midterm exam post mortem	-	-
Week 7	Mon	Abstraction & Interfaces	Ch. 7	Collections
	Wed	Iteration	Ch. 8.1–8.2	-
	Fri	Mid-semester break—no classes	-	-
Week 8	Mon	Abstract List	Ch. 9.1–9.3	-
	Wed	List: Implementations	Ch. 9.4–9.7	-
	Fri	List: Analysis	Ch. 9.8–9.9	-
Week 9	Mon	Searching	Ch. 11.1–11.2	-
	Wed	Sorting: Insertion, Selection, Merge Sort	Ch. 6.1–6.4	-
	Fri	Sorting: Quick Sort	Ch. 6.5, 6.7	-
Week 10	Mon	Stack	Ch. 10.1	-
	Wed	Queue	Ch. 10.2	-
	Fri	Deque	Ch. 10.4	-
Week 11	Mon	Midterm exam review	-	-
	Wed	Midterm exam	Ch. 6–11	-
	Fri	Midterm exam post mortem	-	-
Week 12	Mon	Abstract Tree	Ch. 12.1	-
	Wed	Binary Tree	Ch. 12.4, 12.7	-
	Fri	Binary Tree: Traversals	Ch. 12.6	-
Week 13	Mon	Priority Queue; Heap	Ch. 13.1, 13.3	-
	Wed	Binary Min-Heap	Ch. 13.4	-
	Fri	Thanksgiving break—no classes	-	-
Week 14	Mon	Heap: Analysis	Ch. 13.4	-
	Wed	Abstract Graph	Ch. 16.1	-
	Fri	Directed Graph: Implementations	Ch. 16.2–16.3	-
Week 15	Mon	Maps & Hashing	Ch. 15.1–15.4	-
	Wed	Directed Graph: Analysis	Ch. 16.4–16.5	-
	Fri	Final exam review	-	-
Week 16	TBD	Final exam	Ch. 12–16	-

---

1. GFU
2. CSIS
3. J. Walker Orr
4. CSIS 310