CSC 330: Advanced Data Structures

This course will delve into an array of advanced topics crucial for mastering data manipulation and algorithmic problem-solving. Topics include static and dynamic arrays, linked lists, hash tables, binary trees, heaps, graphs, and various sorting algorithms. Through comprehensive study and practical implementation, you will gain a deep understanding of these data structures and their associated algorithms, enabling you to analyze their efficiency and apply them effectively to real-world scenarios.

Instructor and Course Details

Amitabha Dey, a_dey@uncg.edu

Emailing Ettiquete: Email is the best way to reach me. Communication via any other medium is discouraged.

For the fastest response, include #COURSE_NUMBER #SECTION_NUMBER followed by a word or two describing what your email is regarding in the subject title.

Some examples: CSC330 Section 1 – Struggling with homework 2, CSC330 Section 2 – Absence due to sickness, CSC330 Section 1 - Questions regarding running times of programs.

Note: Sending email to your professor or teaching assistants should be treated as professional communication. Emails should have an appropriate greeting and ending; students should refrain from using any kind of “shortcuts”, abbreviations, acronyms, slang, etc. in the email text.

Office Location: Petty Science Building 005 [directions]

Drop-In Office hours: By appointment, in-person or virtual. Email to schedule or to check availability.

Course Modality: This course is structured as an entirely in-person experience and is not intended for asynchronous participation. If attending lectures in person is not feasible for you, it is advisable to reconsider enrolling in this class.

Course Objectives

• Understand the principles and applications of static arrays, including concatenation, building arrays from permutations, and solving problems like counting good pairs and the two-sum problem.
• Explore the manipulation and utilization of 2D arrays in various scenarios, such as determining the wealth of the richest customer and finding words containing specific characters.
• Master the implementation and optimization of hashmap tables, solving tasks like identifying non-repeating characters, merging sorted arrays, and counting distinct absolute values.
• Gain proficiency in working with linked-lists, including singly and doubly linked lists, and performing operations such as conversion to integers, reversal, and removal of elements.
• Learn about dynamic arrays, circular buffers, and sparse arrays, along with amortized analysis techniques for analyzing their performance.
• Delve into the world of binary trees, including self-balancing trees like AVL and Red-Black trees, and learn operations such as insertion, deletion, and traversal.
• Explore the concept of heaps, including max and min heaps, building heaps from unordered arrays, and performing heap sort and priority queue operations.
• Understand the functionality and implementation of stacks, including push, pop, top, and isEmpty operations, and grasp their role in undo-redo functionalities.
• Study time complexity analysis and function calls to assess the efficiency and performance of algorithms and data structures.
• Gain insights into syntax parsing techniques, such as checking for balanced parentheses and converting decimal numbers to binary representations.
• Explore graph theory concepts, including terminologies, traversal algorithms like Dijkstra’s and Bellman-Ford, minimum spanning tree algorithms like Kruskal’s and Prim’s, and graph coloring problems.

Textbook and Readings

There is no required textbook for the course. The textbooks listed below can be used for supplemental reading.

• Advanced Data Structures Theory and Applications, Suman Saha and Shailendra Shukla

Evaluation and Grading

For practice and to demonstrate abilities, students will be given 4 assignments and 1 group project over the semester which will account for 50% of the overall grade. They are all going to be take-home assignments and should be treated like quizzes. All submissions must be typed and in PDF format. Handwritten submissions will not be accepted. You must complete all the assignments to the best of your ability by the deadline to do well in this course. Besides assignments, there will be one mid-term exam and one final exam. Each student’s work product will be graded, and the student’s final grade will be determined by assigning each category of work a weighted score according to the following distribution.

Mark Allocation and Letter Grade Assignment

Syllabus

Course Modification Disclaimer

This syllabus is intended to give the student guidance on what may be covered during the semester and will be followed as closely as possible. However, as the instructor, I reserve the right to modify, supplement, and make changes as course needs arise. I will communicate such changes in advance through in-class announcements and in writing via this website.

Late Policy and Makeup Exams

[Borrowed from Dr. Stephen R. Tate]

Assignments are due at 11:59 PM on the due date and may be turned in up to 7 calendar days late with a 25% late penalty. Students with planned absences, whether for university events, religious observance, or other reasons, are expected to make arrangements with the instructor to turn in assignments or take exams before the scheduled date of the assignment or test. No assignment will be accepted more than 7 calendar days after the original due date.

Exam/test dates will be announced at least two weeks in advance and may be made up only if it was missed due to an extreme emergency and arrangements are made before the exam date. Exams may not be taken early or late due to personal travel plans.

Note: Canvas submission will automatically get locked past the deadline. Late submission must be made via email with a proper Subject Title and valid explanation. All submissions made past 11:59 PM of the due date will be regarded as late submissions. To avoid any technical difficulty, you must try to submit the assignment a couple of hours in advance at the very least. To be fair to the rest of the students, no excuses will be accepted.

Generative AI

[Borrowed from Dr. Chris Kanich]

You will almost certainly be using GenAI (ChatGPT, GitHub Copilot, Grammarly, etc) in some way for the rest of your career. You are encouraged to use whatever GenAI tools you would like to complete the assignments and final project in this class.

While these tools are amazing, please do not use their existence as an excuse to procrastinate on getting started with your assignments. They are good, but they aren’t that good. While you can use GenAI on your homework, using autocomplete and copy-paste until the tests pass is not acceptable. You must understand any code that you use. We reserve the right to review your submitted code with you, and if you cannot explain the code you submitted, it will be considered a violation of the academic integrity code equivalent to plagiarism (see below).

Please remember that in-class assessments (quizzes and exams) are a comparatively large portion of your grade, and you cannot use GenAI on them. This policy is subject to change as we all learn more about how GenAI works and doesn’t work as part of learning college-level course content.

Academic Integrity Policy

Assignments are clearly labeled as collaborative or solo, which indicates whether you can discuss the assignment with other students or not. In collaborative assignments, you may discuss the problem and solutions with other students and can help classmates debug their code. However, no code may be copied from either another student or from a website — all code submitted must have been written by you. If you do work with other students on collaborative assignments, you must put their names in a comment at the top of the file that you collaborated on. Solo assignments are just that – solo – and you may not discuss the assignment with anyone other than the instructor. If you need help during a solo assignment you can (and should!) contact the instructor for help, but cannot talk with another student or post something online seeking help. Sharing your own work is a serious violation of academic integrity, and if homework is copied then both the person who actually did the work and the person who copied it will be punished. Note that I use a plagiarism detection tool on submissions, and if your solution is too close to that of another student or of an online resource, you will be required to explain your solution and how you arrived at it.

Any incidents of academic dishonesty will be handled strictly, resulting in either a zero on the assignment or an F in the class, depending on the severity of the incident. Any cheating in an online exam, no matter how minor, will result in an automatic F in the class. Significant incidents will be reported to the UNCG Office of Student Rights and Responsibilities. Note that the Department of Computer Science maintains records of all academic integrity incidents, and multiple violations, even in different classes or semesters, will always result in reporting to the university and serious penalties.

Students are expected to be familiar with and abide by the UNCG Academic Integrity Policy, which is online at https://academicintegrity.uncg.edu/. Academic Honor Policy will be strictly enforced. By submitting an assignment, each student is acknowledging their understanding and commitment to the Academic Integrity Policy on all major work for the course. Any infraction(s) will result in failure of the entire course and a reduced grade up to an F. Any incidents of academic dishonesty will be handled strictly, resulting in either a zero on the assignment or an F in the class, depending on the severity of the incident. Significant incidents will be reported to the UNCG Office of Student Rights and Responsibilities. Note that the Department of Computer Science maintains records of all academic integrity incidents, and multiple violations, even in different classes or semesters, will always result in reporting to the university and serious penalties.

Attendance Policy

Attendance will not be taken in class, and is voluntary; however, all students are responsible for everything done or said in class (this can include changes in assignments, due dates, etc.). It is highly unlikely that a student who regularly misses classes will be successful in the course. If you are going to miss a lecture, you need to notify the instructor prior by sending an email following the format mentioned above. I am obligated to inform the department if a student is missing classes frequently. If you find yourself repeatedly unable to attend lectures for health reasons, you may want to apply for accommodations.

Please see UNCG Attendance Policy for more information.

Canvas Announcements

Communication includes Announcements in Canvas, and individual emails. You should be ready to RECEIVE the following types of messages. You will receive regular communication via the Announcements on the course Canvas site that is intended for all students regardless of your group. Check these each time you access the course in Canvas to be sure you are up to date with the latest information (these are time-stamped so if you know when you logged in last, you can determine if anything is new).

Accommodations/ADA Statement

UNCG seeks to comply fully with the Americans with Disabilities Act (ADA). Students requesting accommodations based on a disability must connect with the Office of Accessibility Resources and Services (OARS) at 215 Elliott University Center, (336) 334-5440, oars.uncg.edu.

The University of North Carolina at Greensboro respects and welcomes students of all backgrounds and abilities. If you encounter any barriers to full participation in this course due to the impact of a disability/condition impacting a major life activity, please contact the Office of Accessibility Resources and Services (OARS). OARS will engage students in an interactive process to determine the need for any reasonable accommodations.

Connect quickly via a brief Welcome Form. Upon receipt, OARS will contact you to schedule a convenient, virtual consultation. You may also request a consultation by calling (336) 334-5440, emailing oars@uncg.edu, or walking into the OARS suite at 215, EUC. Additional OARS info may be found at oars.uncg.edu.

Technical Support

Students with technical issues with the course and email should contact 6-TECH for support either by email, phone or chat ( 6TECH Help). Please also make your instructor aware of the issue and if there will be any delays in resolving the issue.

COVID-19 Policy

Students who are ill, quarantined, or isolated should not attend in-person class meetings but should instead contact their instructor(s) so alternative arrangements for learning and the submission of assignments can be made where possible. We should actively engage in behaviors that limit the spread of COVID-19. These actions include, but are not limited to:

Following face-covering guidelines https://veoci.com/v/p/132667/workflow/fs2x25pzqnd5 Engaging in proper hand washing hygiene Self-monitoring for symptoms of COVID-19 https://www.cdc.gov/coronavirus/2019-ncov/symptoms-testing/symptoms.html Staying home when ill Complying with directions from health care providers or public health officials to quarantine or isolate if ill or exposed to someone who is ill Completing a self-report when experiencing COVID-19 symptoms, testing positive for COVID-19, or being identified as a close contact of someone who has tested positive Staying informed about the University’s policies and announcements via the COVID-19 website https://covid.uncg.edu/

Inclusive Community

UNCG values diversity and inclusion. Regardless of age, disability, ethnicity, race, gender, gender identity, sexual orientation, socioeconomic status, geographic background, religion, political ideology, language, or culture, we expect all members of this class to contribute to a respectful, welcoming, and inclusive environment for every other member of our class. If aspects of this course result in barriers to your inclusion, engagement, accurate assessment, or achievement, please notify me as soon as possible.

Religious Obligation Statement

It is expected that instructors will make reasonable accommodations for students who have conflicts due to religious obligations. Please make arrangements with the instructor in advance of any conflict. For more information on UNCG’s Religious Obligations policy, visit: UNCG’s Religious Obligations Policy.

Mental and Physical Health

Health and well-being impact learning, access, and academic success. Throughout your time at the university, you may experience a range of concerns that can cause barriers to your academic success. These might include illnesses, strained relationships, anxiety, high levels of stress, alcohol or drug dependency, crime victimization, feeling down, loss of motivation, or death of a loved one. Student Health Services, the Counseling Center, the Campus Violence Response Center, and the Spartan Recovery Program are here to help.

Anna M. Gove Student Health Center: 107 Gray Drive; (336) 334-5340 Counseling and Psychological Services: 107 Gray Drive; (336) 334-5874 (24/7); https://shs.uncg.edu/cc Campus Violence Response Center: 107 Gray Drive; (336) 334-9839; https://cvrc.uncg.edu/ Spartan Recovery Program (support service for students in recovery from alcohol and other drug addiction): 107 Gray Drive; (336) 209-9388; srpepic@uncg.edu https://shs.uncg.edu/srp

Title IX

UNCG is committed to fostering a safe, productive, learning environment. Title IX and our school’s policy prohibit discrimination on the basis of sex. Sexual harassment, which includes gender-based harassment, domestic and dating violence, sexual assault, and stalking, is prohibited. We encourage anyone who has experienced sexual harassment to speak with someone and get the support and resources they need. I, because of my role with the University, am not required to share information with the University’s Title IX Coordinator. Please be aware that if you share a situation related to interpersonal violence with an Official with Authority, they are required to share that information with the University’s Title IX Coordinator.

UNCG has confidential staff members trained to support students in navigating campus life, understanding reporting options, accessing health and counseling services, and more. Confidential support services include: Campus Violence Response Center (CVRC) located on the ground floor of Gove Student Health Center or UNCG’s Medical Clinic, Wellness Center, and Counseling Center located in the Gove Student Health Center.

If you wish to report sexual harassment or have questions about school policies and procedures regarding sexual harassment, please contact our school’s Title IX Coordinator, Murphie Chappell at (336) 256-0362 or mechappe@uncg.edu. For more information, see this page: https://titleix.uncg.edu/

Name and Pronoun Use

If your name does not match the name on my class roster, please let me know as soon as possible. My pronouns are [she/her; he/him; they/them]. I welcome your pronouns if you would like to share them with me. For more information about pronouns, see this page: https://pronouns.org/what-and-why

Elasticity Statement

The instructor intends that this syllabus and course calendar will be followed as outlined, however, as the need arises there may be adjustments to the syllabus and calendar. In such cases, the instructor will notify the students in class and via e-mail with an updated syllabus and calendar within a reasonable timeframe to allow students to adjust as needed.

Adverse Weather

In cases of inclement weather that impacts this course and course schedule, details can be found:

In your University email: UNCG sends out Adverse Weather updates. In the UNCG Mobile App: You can set it to provide you alerts. Via television announcements: UNCG makes weather announcements available on five local stations (WFMY-2, WGHPV, WXII-TV, WXLV-TV, and Spectrum News). Visit Spartanalert.uncg.edu or the UNCG homepage: UNCG posts up-to-date information on the main University website (uncg.edu) and on the main Spartan Alert page ( spartanalert.uncg.edu).