CSIS 310 Data Structures

---

Course Description

An introduction to the concepts of information organization and manipulation. The course covers basic sequential structures such as lists, 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

Brian R. Snider
Office hours: Wood-Mar 222 (see schedule)

Texts

required

• M.A. Weiss, Data Structures and Algorithm Analysis in Java, 3rd Ed. Pearson, 2011.
  ISBN: 978-0132576277
• 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

• CSIS 310 mailing list
• CSIS 310 on GitLab
• Oracle Java 14 API Reference
• Oracle Java SE 14 Development Kit (JDK)
• Apache Netbeans
• JetBrains IntelliJ IDEA
• JUnit 4
• Java coding style guidelines

---

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.

The course will include regular homework and/or programming assignments. Unless otherwise specified, assignments are due before the beginning of class on the due date. There will be no credit given for late assignments (without an excused absence)—turn in as much as you can.

Reading assignments should be completed before the lecture covering the material. Not all reading material will be covered in the lectures, but you will be responsible for the material on homework and exams. Quizzes over the assigned reading may be given at any time.

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, and you'll find that collaboration is a valuable skill in the working world. While some of you may be tempted to collaborate too much, others will collaborate too little. When appropriate, it's a good idea to make use of others—the purpose here is to learn. Be sure to make the most of this opportunity but do it earnestly and with integrity.

Engineering Your Soul

The mission and vision statement of the Computer Science & Information Systems (CSIS) program states that our students are distinctive by "bringing a Christ-centered worldview to our increasingly technological world."

As one step towards the fulfillment of this objective, each semester, the engineering faculty will collectively identify an influential Christian writing to be read and reflected upon by all engineering faculty and students throughout the term. As part of the College of Engineering, CSIS students participate in this effort, known as Engineering Your Soul (EYS). This exercise will be treated as an official component of every engineering course (including CSIS courses) and will be uniquely integrated and assessed at my discretion, typically as a component of the quiz grade.

Students should read the assigned reading each week. Regular meetings will be scheduled throughout the semester that can be attended for chapel elective credit. Students should attend these meetings prepared to discuss the assigned reading, or email a reflection on the assigned reading on or before each meeting date.

It is our hope that students will not view this as one more task to complete, but as a catalyst for continued discussion ultimately leading to a deeper experience of Jesus Christ.

Online Portfolio

All students in the College of Engineering are required to create and maintain an online portfolio on Portfolium to showcase their best work. Portfolium is a "cloud-based platform that empowers students with lifelong opportunities to capture, curate, and convert skills into job offers, while giving learning institutions and employers the tools they need to assess competencies and recruit talent."

Students will post portions of their coursework to Portfolium as directed by their instructor. For example, a portfolio entry might be PDF of poster or presentation content, screenshots or a video demonstration of a software or hardware project, or even an entire source code repository. In addition to required portfolio entries, students are encouraged to post selected work to their portfolios throughout the year.

Students will work with their faculty advisor to curate and refine their portfolios as they progress through the program. Students shall ensure that all portfolio entries are appropriate for public disclosure (i.e., they do not reveal key components of assignment solutions to current or future students).

University Resources

If you have specific physical, psychiatric, or learning disabilities and require accommodations, please contact the Disability & Accessibility Services as early as possible so that your learning needs can be appropriately met. For more information, go to georgefox.edu/das or contact das@georgefox.edu).

My desire as a professor is for this course to be welcoming to, accessible to, and usable by everyone, including students who are English-language learners, have a variety of learning styles, have disabilities, or are new to online learning systems. Be sure to let me know immediately if you encounter a required element or resource in the course that is not accessible to you. Also, let me know of changes I can make to the course so that it is more welcoming to, accessible to, or usable by students who take this course in the future.

The Academic Resource Center (ARC) on the Newberg campus provides all students with free writing consultation, academic coaching, and learning strategy review (e.g., techniques to improve reading, note-taking, study, time management). During the 2021 spring semester, the ARC is offering physically distanced, in-person appointments as well as virtual appointments over Zoom. The ARC, located on the first floor of the Murdock Library, is open from 1:00–8:00 p.m., Monday through Thursday, and 12:00–4:00 p.m. on Friday. To schedule an in-person or virtual appointment, go to the online schedule at arcschedule.georgefox.edu, call 503-554-2327, email the_arc@georgefox.edu, or stop by the ARC. Visit arc.georgefox.edu for information about ARC Consultants' areas of study, instructions for scheduling an appointment, learning tips, and a list of other tutoring options on campus.

Health and Safety Considerations

All members of our university community are committed to making health and safety top priorities as we return to campus in the midst of the current pandemic. As such, all employees and students are expected to take measures to keep our campus communities healthy and safe in this coming season. Please review the entirety of the university's official COVID-19 web page for the most up-to-date community guidance, including specific policies that all individuals are required to adhere to, as we attempt to return to face-to-face instruction on campus.

Please be aware of the following specific guidance for the instructional setting, subject to change at any time:

• Complete a daily self-screening through the CampusClear app before entering classrooms, buildings, or offices (read full policy).
• Face coverings must be properly worn at all times while indoors, and outdoors where physical distancing is not easily maintained (read full policy). See the Centers for Disease Control and Prevention (CDC) website for the most up-to-date guidance on face shields and masks with exhalation valves or vents, which are currently not recommended by the CDC as a substitute for a proper face mask that filters exhaled air. However, remain mindful of those with conditions or circumstances that make it not feasible to wear a mask and may have approved accommodations.
• Maintain six (6) feet of distance from others. All spaces on campus, including instructional spaces, have been assessed and modified to enable proper distancing to minimize viral spread. DO NOT move or rearrange furniture in any space. DO NOT remove, modify, or otherwise tamper with signage in the room or elsewhere on campus related to distancing or direction of traffic flow.
• Participate remotely as directed, just as you would in a face-to-face setting. Due to distancing requirements, some course sections are being taught in a "hybrid" format, with one cohort of the class physically in the classroom, and another joining virtually via video conference. You are expected to participate in every class session regardless of location or modality, and exhibit the same degree of professionalism online as you would in person.
• Consumption of food is prohibited in instructional spaces, including the CS labs, as it typically requires removal or adjustment of your mask. Beverages and other consumable products (fitness shakes, etc) are permitted if you use a container with a straw that allows you to consume the item by slipping the straw under your mask without removing it. However, we encourage you to plan your dietary and hydration needs accordingly to minimize the risk to others.
• Reset and sanitize your workspace before you leave the classroom. This includes disposing of garbage, pushing in your chair, etc. These common courtesies are more important than ever in our current environment. Cleaning supplies and hand sanitizer should be available for use in each room or building.
• Practice good hygiene including proper frequent handwashing as part of your daily routine. Use the provided hand sanitzer as you enter and exit buildings. Avoid touching your mask or face.
• Be mindful of others' time and space. Do not congregate in hallways, near entrances, etc before, during, or after class. Allow occupants from a preceding class to exit before entering. Respect the 6-foot distancing guideline to the extent possible if you need to leave the room (e.g., to use the restroom facilities) during class. Promptly exit the room at the end of class to give the next class sufficient time to enter and prepare, and wait until you are in the atrium/lobby/outdoors to attend to social matters such as making a phone call or waiting for friends.
• If you are sick or symptomatic, DO NOT come to class. Alternate, synchronous delivery methods will be provided for those who are unable to be physically present. Email me before class to inform me that you will not be physically present (as you would for any other absence), and participate remotely as you are able. Please familiarize yourself with the class attendance and absence policies. I will work with you as much as possible to give you every opportunity to succeed, but must adhere to established processes to do so; the key here will be staying in communication.
• If you are sick or believe you have been exposed to infection, notify the university immediately via the COVID-19 Concern and Reporting Form. Doing so will enable the university to better manage contact tracing and reporting efforts. Please also be aware of the isolation and quarantine policy.
• Refusal to follow the university's face covering and distancing policies will be interpreted as behavior that is unethical and in violation of the university's expectations, per the Standards of Conduct of the university. I have the right—and indeed the responsibility—to ask you to follow these policies in my courses, and will require you to leave class if you do not comply. Any individual who continues to exhibit conduct that is detrimental to the total welfare of the community shall be subject to disciplinary action that may warrant appropriate consequences, including suspension or dismissal from the university.

These are unprecedented times, which call for unprecedented measures. At George Fox University, the health and safety of our students, our employees and faculty, and any guest or visitor to our campus is paramount as we navigate the uncertainty of the pandemic. We want to do all we can to ensure a safe community; this will require your cooperation, patience, and respect.

I, as one of many whom your families have entrusted with your care, will err on the side of caution, and continue to follow the latest evidence-based, peer-reviewed science—even if it is inconvenient, requires me to put the needs of others before my own just as Christ did for us, or goes beyond what others on campus are doing—and urge you to do the same for the sake of those amongst us on campus or at home who are immunocompromised or otherwise considered at elevated risk. I believe this sentiment is evident throughout the Bruin Pledge, a solemn promise that all members of our community must aspire to remain true to in this uncertain and trying time. Furthermore, due to my training at a world-class healthcare institution as a research-oriented member of the medical profession, I am also bound by the Declaration of Geneva.

If you feel you are unable to comply with the community policies and guidelines for any reason, please contact Disability & Accessibility Services (or other student services, as appropriate) as early as possible so that your learning needs can be appropriately met. I as a faculty instructor am not authorized to approve any accommodations that minimize or eliminate the established guidelines set forth by the university, but fully support those who do receive official approval for accommodation.

---

Grading

Grading Scale

Current Grades

The final course grade will be based on:

• 55% Homework & programming assignments
• 45% Exams

---

Tentative Schedule

Week 1 · 8/24 Introduction

Week 1 · 8/26 Expectations Misc: Examples

Week 1 · 8/28 Abstraction & Encapsulation Bailey: Ch. 1

Week 2 · 8/31 Art of Programming FoCS: Ch. 1.1–1.3, 1.5

Week 2 · 9/2 Java Programming Bailey: Appx. B

Week 2 · 9/4 Java Review: Classes & Instances Bailey: Ch. 1

Week 3 · 9/7 Java Review: Inheritance; Generics Bailey: Ch. 4

Week 3 · 9/9 Java Review: Javadoc & Miscellany Misc: Javadoc

Week 3 · 9/11 Robust Programming: Assertions & Exceptions Bailey: Ch. 2 FoCS: Ch. 2 Misc: Exceptions

Week 4 · 9/14 Robust Programming: Unit Testing Misc: JUnit

Week 4 · 9/16 Arrays FoCS: Ch. 6.1–6.5

Week 4 · 9/18 ArrayList & Vector Weiss: Ch. 1.5–1.6 Bailey: Ch. 3.1–3.5

Week 5 · 9/21 Introduction to Algorithm Analysis Weiss: Ch. 1.1–1.3, 2.1–2.3 Bailey: Ch. 5.1–5.2

Week 5 · 9/23 Amortized Analysis Weiss: Ch. 2.4 FoCS: Ch. 3.1–3.3

Week 5 · 9/25 Complexity Categories & Big-Oh Notation Bailey: Ch. 5.3 FoCS: Ch. 3.4–3.6

Week 6 · 9/28–10/2 Midterm exam Weiss: Ch. 1–2 Bailey: Ch. 1–5 FoCS: Ch. 1–3 Misc: *

Week 7 · 10/5 Abstraction & Interfaces Bailey: Ch. 7 Misc: Collections

Week 7 · 10/7 Iteration Weiss: Ch. 3.1–3.3 Bailey: Ch. 8.1–8.2 FoCS: Ch. 2.2

Week 7 · 10/9 Mid-semester break — no class

Week 8 · 10/12 Abstract List Weiss: Ch. 3.1–3.2 Bailey: Ch. 9.1–9.3 FoCS: Ch. 6.1–6.3

Week 8 · 10/14 List: Implementations Weiss: Ch. 3.3–3.5 Bailey: Ch. 9.4–9.7 FoCS: Ch. 6.4

Week 8 · 10/16 List: Analysis Bailey: Ch. 9.8–9.9

Week 9 · 10/19 Searching Weiss: Ch. 2.4.4 Bailey: Ch. 11.1–11.2 FoCS: Ch. 6.5

Week 9 · 10/21 Sorting Weiss: Ch. 7.1–7.3, 7.6–7.7 Bailey: Ch. 6 FoCS: Ch. 2.8

Week 9 · 10/23 Stack Weiss: Ch. 3.6.1–3.6.2 Bailey: Ch. 10.1 FoCS: Ch. 6.6

Week 10 · 10/26 Stack: Applications Weiss: Ch. 3.6.3 FoCS: Ch. 6.7

Week 10 · 10/28 Queue Weiss: Ch. 3.7 Bailey: Ch. 10.2 FoCS: Ch. 6.8

Week 10 · 10/30 Deque Bailey: Ch. 10.4 FoCS: Ch. 6.11

Week 11 · 11/2–11/6 Midterm exam Weiss: Ch. 1–3, 7 Bailey: Ch. 1–10 FoCS: Ch. 1–3, 6 Misc: *

Week 12 · 11/9 Abstract Tree Weiss: Ch. 4.1 FoCS: Ch. 5.1–5.5, 9.6–9.7

Week 12 · 11/11 Binary Tree Weiss: Ch. 4.1.2 Bailey: Ch. 12.1, 12.4, 12.6–12.7 FoCS: Ch. 5.1–5.6

Week 12 · 11/13 Priority Queue; Heap Weiss: Ch. 6.1–6.4; 6.9 Bailey: Ch. 13.1–13.7 FoCS: Ch. 5.9–5.10

Week 13 · 11/16 Map & Optimal Search Weiss: Ch. 5.1–5.3 Bailey: Ch. 15.1–15.3 FoCS: Ch. 7.1–7.5

Week 13 · 11/18 Hashing Weiss: Ch. 5.4–5.6, 5.9 Bailey: Ch. 15.4–15.7 FoCS: Ch. 7.1–7.6

Week 13 · 11/20 Abstract Graph Bailey: Ch. 16.1 FoCS: Ch. 9.1–9.2

Week 14 · 11/23 Graph: Implementations Weiss: Ch. 9.1 Bailey: Ch. 16.2–16.4 FoCS: Ch. 9.3–9.4

Week 14 · 11/25 Graph: Algorithms Weiss: Ch. 9.5 Bailey: Ch. 16.5–16.6 FoCS: Ch. 9.5–9.9

Week 14 · 11/27 Thanksgiving holiday — no class

Week 15 · TBD Final exam Weiss: * Bailey: * FoCS: * Misc: *

Week	Date	Topic	Weiss	Bailey	FoCS	Misc
Week 1	8/24	Introduction	-	-	-	-
	8/26	Expectations	-	-	-	Examples
	8/28	Abstraction & Encapsulation	-	Ch. 1	-	-
Week 2	8/31	Art of Programming	-	-	Ch. 1.1–1.3, 1.5	-
	9/2	Java Programming	-	Appx. B	-	-
	9/4	Java Review: Classes & Instances	-	Ch. 1	-	-
Week 3	9/7	Java Review: Inheritance; Generics	-	Ch. 4	-	-
	9/9	Java Review: Javadoc & Miscellany	-	-	-	Javadoc
	9/11	Robust Programming: Assertions & Exceptions	-	Ch. 2	Ch. 2	Exceptions
Week 4	9/14	Robust Programming: Unit Testing	-	-	-	JUnit
	9/16	Arrays	-	-	Ch. 6.1–6.5	-
	9/18	ArrayList & Vector	Ch. 1.5–1.6	Ch. 3.1–3.5	-	-
Week 5	9/21	Introduction to Algorithm Analysis	Ch. 1.1–1.3, 2.1–2.3	Ch. 5.1–5.2	-	-
	9/23	Amortized Analysis	Ch. 2.4	-	Ch. 3.1–3.3	-
	9/25	Complexity Categories & Big-Oh Notation	-	Ch. 5.3	Ch. 3.4–3.6	-
Week 6	9/28–10/2	Midterm exam	Ch. 1–2	Ch. 1–5	Ch. 1–3	*
Week 7	10/5	Abstraction & Interfaces	-	Ch. 7	-	Collections
	10/7	Iteration	Ch. 3.1–3.3	Ch. 8.1–8.2	Ch. 2.2
	10/9	Mid-semester break — no class
Week 8	10/12	Abstract List	Ch. 3.1–3.2	Ch. 9.1–9.3	Ch. 6.1–6.3	-
	10/14	List: Implementations	Ch. 3.3–3.5	Ch. 9.4–9.7	Ch. 6.4	-
	10/16	List: Analysis	-	Ch. 9.8–9.9	-	-
Week 9	10/19	Searching	Ch. 2.4.4	Ch. 11.1–11.2	Ch. 6.5	-
	10/21	Sorting	Ch. 7.1–7.3, 7.6–7.7	Ch. 6	Ch. 2.8	-
	10/23	Stack	Ch. 3.6.1–3.6.2	Ch. 10.1	Ch. 6.6	-
Week 10	10/26	Stack: Applications	Ch. 3.6.3	-	Ch. 6.7	-
	10/28	Queue	Ch. 3.7	Ch. 10.2	Ch. 6.8	-
	10/30	Deque	-	Ch. 10.4	Ch. 6.11	-
Week 11	11/2–11/6	Midterm exam	Ch. 1–3, 7	Ch. 1–10	Ch. 1–3, 6	*
Week 12	11/9	Abstract Tree	Ch. 4.1	-	Ch. 5.1–5.5, 9.6–9.7	-
	11/11	Binary Tree	Ch. 4.1.2	Ch. 12.1, 12.4, 12.6–12.7	Ch. 5.1–5.6	-
	11/13	Priority Queue; Heap	Ch. 6.1–6.4; 6.9	Ch. 13.1–13.7	Ch. 5.9–5.10	-
Week 13	11/16	Map & Optimal Search	Ch. 5.1–5.3	Ch. 15.1–15.3	Ch. 7.1–7.5	-
	11/18	Hashing	Ch. 5.4–5.6, 5.9	Ch. 15.4–15.7	Ch. 7.1–7.6	-
	11/20	Abstract Graph	-	Ch. 16.1	Ch. 9.1–9.2	-
Week 14	11/23	Graph: Implementations	Ch. 9.1	Ch. 16.2–16.4	Ch. 9.3–9.4	-
	11/25	Graph: Algorithms	Ch. 9.5	Ch. 16.5–16.6	Ch. 9.5–9.9	-
	11/27	Thanksgiving holiday — no class
Week 15	TBD	Final exam	*	*	*	*

---

1. GFU
2. CSIS
3. Brian R. Snider
4. CSIS 310