CSCI 3230 – Data Structures

COURSE INFORMATION
Instructor: Dr. Y. Daniel Liang
Office: Science Center 272 Armstrong Campus
Office Phone: (912) 344 - 3264
email: [email protected]
Office Hours: Click https://yongdanielliang.github.io/spring2018/Officehours.htm
Text: Introduction to Java Programming and Data Structures. ISBN-13: 978-
0134167008
This is an online interactive text. You can purchase the access online or buy an
access card from the school bookstore or Amazon. The access code is good for
one year. You can sign up for multiple courses using the same access code
during this one-year period. The instructor will give you a URL for signing up
for the course.
Course URL: https://yongdanielliang.github.io/

PREREQUISITES
A minimum grade of C in CSCI 1302, MATH 2130.

CATALOG DESCRIPTION
New 3230 description: Introduction to abstract data types such as lists, stacks, queues, and trees, and algorithm
analysis. Prerequisite(s): A minimum grade of "C" in CSCI 1302, MATH 2130.

COURSE OBJECTIVES
As part of this course, students
 will learn the concepts and techniques for recursion.
 will learn how to parameterize data types using generics.
 will learn how to measure the algorithm complexity using the Big O, Ω, and Θ notation.
 will learn how to use classic data structures: array lists, linked lists, stacks, queues, priority queues, sets, maps,
binary trees, and hashing.
 will learn how to implement data structures.
 will learn graph algorithms and use them to solve practical problems.

COURSE OUTCOMES
Upon successful completion of this course, students will be able to
 Understand O, Ω, and Θ and time/space complexity.
 Ability to understand the concepts of lists, stacks, and queues, and to implement them using arrays/linked
structures.
 Ability to understand, and to implement linear and binary searches
 Ability to understand, program, and apply O(N^2), O(N*LN(N)) and possible other sorts of lists.
 Understand the concept of divide and conquer wrt algorithms.
 Understand the concept of a hash function and its application in search.
 Understand concepts in graphs: directed/ undirected/ oriented, graphs and chains/ paths/ cycles.
 Understand the concepts of weakly and strongly connected graphs.
 Understand the concept of a tree, a forest, a singly rooted tree, and a binary tree
 Understand the concept of ancestral relationships in trees
 Understand the concept of a binary search tree, and modify a binary tree to a binary search tree
 Ability to program preorder, inorder, and postorder binary tree traversals
 Understand Dijkstra’s shortest path algorithm
 Ability to understand the concept of a minimal spanning tree and to find a minimal spanning trees for a graph
CLASS
Class time will be used for short lectures, design examples, in class exercises, and quizzes and exams. Class
attendance is mandatory and students are responsible for all material covered in class. Missed work, quizzes, or
exams will receive a grade of zero. Class disruption (cell phones, sleeping, talking, etc.) during class will not be
tolerated. A warning will be given on the first instance and you will be asked to leave the class on any subsequent
instances.

GRADING
Grades will be determined from: attendance (5% Attendance will be checked regularly, but not for every class),
REVEL exercises (20%), LiveLab programming projects (20%), two exams (15% each), and final exam (25%).
Evaluation scheme is subject to change with a prior notice. Dates for exams will be announced in the class.

Attendance will be checked regularly. Missing classes frequently will be automatically dropped out of class.

Final grades will be based on the following scale: A (90 - 100), B (80 - 89), C (70 – 79), D (60 – 69), and F (< 60).
The instructor reserves the right to adjust the grading percentages and scale if necessary.

Extenuating circumstances that prevent timely submittal of work must be discussed with the instructor at least 24
hours in advance or cleared through the Office of the Dean of Students (including a death in the family, serious
injury, or illness). Students must supply appropriate documentation verifying the extenuating circumstances that
prevented a timely submittal of the assignment.

TENTATIVE WEEKLY PLAN

Week 1 Ch18: Recursion

Week 2 Ch19: Generics and Ch20: Collections
Week 3 Ch21: Sets and Maps
Week 4 Exam 1 and Ch22 Big-O and algorithm design
Week 4 Ch22
Week 5 String matching
Ch23 Implementation of ArrayLists and LinkedLists
Week 6 Ch23 Stacks, Queues, and Priority Queues
Week 7 Ch24 Sorting
Week 8 Ch24 Sorting and Ch25 BST
Week 9 Ch25 BST, Hoffman Encoding
Week 10 Ch26 AVL Trees
Week 11 Ch27 Hashing
Week 12 Exam 2
Week 13 Ch28 Unweighted Graphs
Week 14 Ch29 Weighted Graphs
Week 15 Thanksgiving
Week 16 Review

ASSIGNMENTS
Due dates for programming assignments will be announced in the class. Missed quizzes and late or missed
assignments will receive a grade of zero. Programming assignments must be done individually. Source file
printout must be submitted in the class on the due day regardless its status (complete or incomplete). In addition to
submitting a hard copy, students must also submit the programs to LiveLab. Your grades will be recorded on
LiveLab.

Students are expected to perform their work individually unless otherwise specified by the instructor. Plagiarism will
be checked by LiveLab. Students may discuss assignments in general terms with other students and may receive
assistance from the instructor or classmates. Assistance does not mean obtaining working designs or solutions and
modifying them; this is considered copying.

Submission to LiveLab with the intention to deceive LiveLab is considered as cheating.

All instances of academic misconduct will receive a zero for the assignment and be reported to the Dean of Students.
A second instance of academic misconduct will result in an automatic F in the course and possible disciplinary
action.

ABSENCES
Class attendance is mandatory. Students who miss class due to illness will be counted as attending on LiveLab if
proper documents are given. Students registering after the semester begins are responsible for all missed
assignments and cannot expect that due dates will be altered.

EMAIL POLICY
For a prompt response, put CSCI 2410 in the subject of the email.

HELP
Before you ask for help on programs, explain to yourself what the program is doing step-by-step. When you visit me
during office hours, make sure you have already submitted your program on LiveLab and bring a printed copy of the
program. You can resubmit the program on LiveLab before it is due.

COMPUTER LABS
The following labs have the software necessary for this course: SC 129, SC 2016

Academic Integrity Policy:

Violations of the University Academic Integrity Policy (including cheating and plagiarism) are taken very seriously.
Any violation of this policy will become part of the student’s permanent educational record. More information on
the Academic Integrity policy and procedure can be found at https://students.georgiasouthern.edu/conduct/.

Title IX Clause:
The university is dedicated to providing a safe and equitable learning environment for all students. Discrimination,
sexual assault, and harassment are not tolerated by the university. You are encouraged to report any incidents to the
Title IX Office in Victor Hall Room 245. This is important for the safety of the whole university community.
Another member of the university community – such as a friend, classmate, advisor, or faculty member – can help
initiate the report, or can initiate the report on behalf of another person. The University Counseling Center provides
24/7 confidential support, and the https://students.georgiasouthern.edu/counseling/ describes reporting options and
other resources.

Disability Related Accommodations

The university is committed to providing reasonable accommodations to students with documented

disabilities, as required under federal law. Disabilities may include learning disabilities, ADD,
psychological disorders, brain injury, Autism Spectrum Disorders, serious chronic medical illnesses,
mobility impairment, communication disorders, vision or hearing loss or temporary injuries. The purpose
of disability accommodation is to provide equal access to the academic material and equal access to
demonstrate mastery of the material. Students with disabilities must meet all the academic requirements
and standards of the class, including the attendance policy. If you have a disability and need
accommodations, please contact the Office of Disability Services, located on the second floor of Memorial
College Center, room 208. You will need to meet with Disability Services Staff, who can help you gather
documentation of your disability or refer you to an appropriate resource for assessment. Once
documentation of the disability is gathered and approved, Disability Staff will provide you with an
Accommodation Letter, detailing the appropriate, approved accommodations, which you should present to
me so we can discuss and implement your accommodations. Disability accommodations work best
starting at the beginning of the semester, but can be approved and started at any point in the semester.
Accommodations start at the time the Accommodation Letter is presented to faculty, within reasonable
timelines. Accommodations are not given retroactively. Accommodations are not part of your academic
transcript.

Campus Carry Law

For Campus Carry law, please see http://www.usg.edu/hb280.