Corning Community College

Computer and Information Science

CSCS2320 Data Structures

Fall 2023

Syllabus / Course Home Page

Instructor:Matthew Haas (haas@corning-cc.edu)
Office:CHM123
Office Hours:TR 10:00a-10:50a, R 11:00a-12:50p
In-person meeting details:CHM123 W 02:30pm - 04:20pm
Class Desig:data
Class Chat:#data on discord
PublicDirectory:/var/public/fall2023/DATA
CRN:10048
'W' Drop Date:October 29, 2023

Discord: https://discord.gg/kPhh9r2MZ3
Projects: https://lab46.g7n.org/haas/fall2023/DATA/projects
SUNY CCC Syllabus Statements: https://docs.google.com/document/d/1JsIuYeV5c72l5qaQEFOoNhJDYeaCv60U-kCKMaKzhv4/

Course Description

Data and data structures, linear lists, strings, stacks, queues, linked lists, arrays, and orthogonal lists. Trees, multi-linked structure, table search, sorting techniques, storage allocation, and sequential and random file access.

(3 cr. hrs.) (Fall). Prerequisite: CSCS1320 C/C++ Programming.

Course Objectives

Upon successful, knowledgeable completion of this course, students will be able to:

  • Discuss the representation and use of primitive data types and built-in data structures
  • Describe how the data structures are allocated and used in memory
  • Describe common applications for each data structure described in class
  • Implement the user-defined data structures in a high-level language
  • Compare alternative implementations of data structures with respect to performance
  • Write programs that use the following data structures: linked lists, stacks, queues, binary trees, and hash tables
  • Compare and contrast the costs and benefits of dynamic and static data structure implementations
  • Choose the appropriate data structure for solving a given problem

Assumptions

There are many great opportunities for realization and insight ahead, but there are also many obstacles standing in the way of you staying on a path of success. I find that uncommunicated assumptions can play a role in hampering progress, so please ensure you are suitably read up and aware of my assumptions coming into the course, along with my assumptions of your assumptions, playing the role of a studious student seeking enlightenment.

Let's also make sure we are on the same playing field by establishing some definitions:

student: A student is primarily a person enrolled in a school or other educational institution and who is under learning with goals of acquiring knowledge, developing professions and achieving easy employment at a particular field. In the broader sense, a student is anyone who applies themselves to the intensive intellectual engagement with some matter necessary to master it as part of some practical affair in which such mastery is basic or decisive. (https://en.wikipedia.org/wiki/Student)

While a decent definition, I would argue that it falls short by not also indicating certain things that should be stated, so herein are some further assumptions:

  • a student, entering into the educational environment of a particular class or degree of study (especially at the undergraduate level where we reside), DOES NOT need to have any prior experience with the subject matter. That is: if you are taking a course on introductory programming in a certain language, the student is not expected to know how to program in that specific language (and depending on prerequisites to the course, may not even need to know anything about programming at the introductory level).
  • to learn something means you don't know it. Not knowing something, there's a state of not understanding, and not being aware of what a particular thing or concept is. A student taking a class to learn something necessarily needs to be in active pursuit of gaining an understanding, but is not expecting to come in knowing anything. Learning is often a mistake-ridden process of bumping around in progressively less conceptually dark spaces as patterns are sussed out and intuitive connections are established. We learn best from our mistakes, so a student that does not make mistakes, or that avoids opportunities to make mistakes, isn't being a good student.
  • learning is build upon an ever-growing foundation (your life experience and knowledge, some derivation of society's and civilization's collective body of experience and knowledge), and to be eligible to take a college class, yes, SOME prerequisite knowledge is assumed, namely:
    • you know how to and can/will read (input/consume)
    • you know how to and can/will write (output/create/produce)
    • you know how to and can/will do math/computations
    • you know how to and can/will think
    • you know how to and can/will ask questions
  • a student's (or learner's) absolute BEST tool is the question, specifically the regular asking of them. You NEED to be regularly engaging yourself and the class with questions, and responses to questions. No two people perceive something the same exact way. One explanation is not ideal for every individual. If an available explanation falls short with respect to being clarifying or promoting understanding, you should ask a question. If an available explanation is clarifying, but then upon further thought creates confusion or makes you wonder about other, potentially related things: YOU SHOULD ALSO ASK a question.

The benefit of authentic education is that it transitions one from a state of predominantly not knowing what they don't know, to a state where while they may know that they know more than they did before, also then cultivates an important perception of then KNOWING that they don't know even more things.

Education isn't about certainty or comfort in attaining a set of facts and calling it quits: It is about coming to terms with the endless uncertainty of possible things that can be pursued or known. We can never know everything, but we CAN know that we can never know everything. We instead strive for a functioning subset where we learn enough to give us a foundation in the present, and consistently keep learning (although hopefully less so exclusively in a classroom as time goes by, but instead by the individual having gained enough experience to become a self-learner) to keep up with the demands of tomorrow.

So, as a student learner embarking upon and taking this class, know that I don't assume you know anything about the course you are taking, and that you will be reading and thinking and doing and computing and asking questions regularly so that by the conclusion of the course, you will have some greater idea of the nature of what was encountered in the class.

If you don't want to ask questions, for whatever reason, nor want to bother with expanding your horizons, in learning new and different concepts and ways of doing things (ie you want to remain small and stagnant), then I would urge you to reconsider taking this course: it is NOT a daycare to keep your mind and hands pacified. It is an educational environment where you will be tasked to grow and improve.

Referenced Books

Cover of The C Programming Language

The C Programming Language, 2nd edition
By: Brian W. Kernighan and Dennis M. Ritchie
Publisher: Prentice Hall
ISBN: 0-13-110362-8
Book URL: http://cm.bell-labs.com/cm/cs/cbook/

Cover of C Pocket Reference

C Pocket Reference
By: Peter Prinz, Ulla Kirch-Prinz
Publisher: O'Reilly
ISBN: 0-596-00436-2
Book URL: http://oreilly.com/catalog/9780596004361

Cover of C++ Pocket Reference

C++ Pocket Reference
By: Kyle Loudon
Publisher: O'Reilly
ISBN: 0-596-00496-6
Book URL: http://oreilly.com/catalog/9780596004965

Cover of Algorithms in a Nutshell

Algorithms In A Nutshell
By: George T. Heineman, Gary Pollice, and Stanley Selkow
Publisher: O'Reilly
ISBN: 0-596-51624-X
Book URL: http://oreilly.com/catalog/9780596516246


Vilros Raspberry Pi 4 Complete Kit with Black Fan Cooled Case (4GB)
By: Raspberry Pi Foundation
Vendor: Vilros
Model: B07VD9P96R
Kit URL: https://www.amazon.com/Vilros-Raspberry-Complete-Black-Cooled/dp/B07VD9P96R

Grading Policy

The grading policy is broken down into 4 areas, totalling 104 points (which will account for 100% of the grade):

  • Journal/Writing (13pts)
  • Projects (52pts)
  • Participation (13pts)
  • EoCE (26pts).

Each area, as well as the overall grade, will be evaluated based on a sum of accumulated points on each projects out of a sum of total points on each project (as opposed to a sum of averages on each project). This totaling tends to favor those who consistently do work throughout the semester, and I want to reward that.

While the term 'percent' may be used, it is more appropriate to consider it a 'percent-oh-four', as the word 'percent' refers to PER each CENT (100). We are dealing not with 100s, but 104s.

Also: with the possible exception of the project component, any accumulated point excesses will be capped at the allocation per that grading unit.

Letter Grades

Letter grades are pegged to the following numeric values:

  • A (100.00+)
  • A- (94.00-99.99)
  • B+ (88.00-93.99)
  • B (82.00-87.99)
  • B- (76.00-81.99)
  • C+ (70.00-75.99)
  • C (64.00-69.99)
  • D (58.00-63.99)
  • F ( 0.00-57.99)

Any calculated values in excess of two decimal places that may impact the result is at the sole evaluatory discretion of the instructor (for example, getting a 93.997; if you've been a pleasant, decent human being, I may do you a favor. Just sayin'). Application of any 'rounding' or other result processing is also at the sole discretion of the instructor.

Bonus points, if given/available, are applied to a particular grade component (for example, a project bonus point will only pad the projects component of the grade), and then only up to a maximum of that grade component's total value (ie, one cannot use bonus points to exceed the 13 possible overall points on the journal, or participation, for example).

In addition, some further constraints pertaining to bonus point eligibility:

  • bonus projects that are due the same week as a for-credit project will only be considered if all the following are met:
    • the for-credit project was actually turned in
  • the for-credit project had a final evaluated result of >= 52%
  • bonus points from early submission of a for-credit project:
  • the for-credit project had a final evaluated result of >= 52%

NOTE: bonus projects or other items are not eligible for early submission bonuses.

Journal

Accomplishing the assigned tasks represents only part of the educational experience. A vital part of learning involve understanding and thinking. Writing is perhaps the best tool we have of capturing thought.

There are two main writing components you can undertake to gain credit for this component:

  • journal: a weekly, 256 word minimum entry detailing your experiences in the course (posted to the appropriate week entry on your allocated wiki-based journal), by the pertinent week deadline (typically by the end of the given week's Wednesday).
  • documentation: as appropriate, some projects as assigned will include class-collaborative documentation, where the aim will be to assemble a coherent, informative document providing insight into how one can undertake the project (background information, instructions).

Projects

Projects constitute the portion of your grade involving activities you perform in the name of experiencing and demonstrating knowledge in this class- the means by which I will be assessing your understanding of the material through directed explorations of various topics. Such projects may be comprehensive to one another.

In some cases, depending on the situations involved, a project may be conducive for group-based collaboration. This is not the default case, but is specified on a case-by-case basis. In such scenarios, all involved group members should be identified prior to starting on the project. Additionally, ALL group members in a collaborative situation must perform fairly equivalent work output into the completion of the project. Deficient members may experience reduced success.

In accordance with the late policy, projects past their deadline will see a late penalty of 33% levied per day. This is to mitigate procrastination and encourage better time management, and also to ensure progress continues- once we hit the third day, a past due project is no longer worth any credit, so it behooves everyone to stay on top of assigned work and to complete it by its respective deadline. To clarify, if a project is due by the end of Wednesday, it would be 33% late Thursday (1 day late), 66% late Friday (2 days late), 100% late once it becomes Saturday (3+ days late).

Participation

Maintaining an ever present effort in your journey with respect to being present for class gatherings and making such effort known is an important aspect to academic interactions.

For class (no matter the setting), you are to show your effort through demonstrating regular interactive activity on lab46 and related resources (discord). Emphasis will be on communications taking place with the entire class (the class discord chat).

Participating in class interactions is also of significant importance. Participation is like the “I care” component of your grade. If you care enough to learn and help enhance the experience, you will have no trouble here. If you are disruptive or are not putting forth effort, however, then it will be duly reflected.

Each week, you have the ability to earn participation credit by performing various activities (for some amount of points per week, likely reflective of week and progression of semester). The particular wcp# projects will detail the specific attributes and points available (and needed) for a particular week.

I would encourage you to vary your participation activities from week to week.

There will be some method of collecting this data from you each week, be it a specific weekly project with submit-time questionnaire or script you run that will allow you to itemize your participation contributions for the week; failure to perform sanctioned activities and submit your participation contributions (if applicable) will result in points not being earned (you have to be proactive about your participation). You should also maintain a log of your specific participation activities in case I wish to follow up on the specifics of a particular participation claim (if you cannot substantiate your participation, any claimed credit may be voided).

If you anticipate missing a class, please notify me in advance. While you may still lose applicable participation credit, the advance notice will be taken into positive consideration.

EoCE

As the semester starts wrapping up, the End of Course Experience (EoCE) will be released.

Intended as a sort of comprehensive project(s), its aim is to evaluate your knowledge gained from the class this semester. Unlike other classes which have a “Final Exam”, the EoCE is meant to be an EXPERIENCE, and as such celebrated across the land. If you're new to my classes, you'll see those with prior experience jump for joy at the thought of an EoCE (the twitching / convulsing is merely ecstatic joy that is difficult for the corporeal body to manifest).

Submission Guidelines

The following are some guidelines to keep in mind when preparing your work for submission. Not all may always be applicable, to each class, or even each submission.

Digital is best

Technology is a wonderful thing. It facilitates many of the tasks we'd otherwise have to do manually by hand.

The intent here is to make things easy on both you and me.

So use the technology, and don't just it for the sake of using it– use it to make the task at hand easier (ie use the technology available for the course).

With that said, some additional aspects to keep in mind:

  • e-mails were designed to be plain text; don't make them into web pages
  • e-mails should always have an informative subject line
  • if you've got non-text files to include in an e-mail, attach them to the message
  • if you've got many attachments, archive & compress them, and just attach the archive
  • I can not easily open Microsoft Works documents; don't give me any in that format
  • Plain text is preferable over any enriched text format (RTF, WORD, WordPerfect, etc.)

If appropriate, I also will accept submissions via singing telegram, airplane banner, crop circles, creative dance, three part rock aria, etc. so long that I get to witness such creativity, and receive something which lets me look back on it later (photos, video, transcription on paper, etc.). Chances are such unique submissions will gain you favorable considerations.

Identification

Where applicable, be sure to include the following information on any submission:

  • Name,
  • Course and Section,
  • Due Date,
  • Assignment # and description,
  • Short abstract describing the purpose of your program / assignment.

Presentation of this information in a clear and organized fashion will make your assignment all the easier to read. You may come up with your own format for the display of this information.

Any e-mail submissions should have an appropriate subject line. Please use subjects on all e-mails. This is also very important.

Leaving off the subject line is like sending a letter without putting a stamp on it– it causes someone extra work. And that someone would be me. So don't do it. Please please please use informative subject lines!

Paraphrasing

For any provided questions, keywords, etc.: identify each question or selection you are answering by listing or paraphrasing the original question.

Do not just give me an answer.

This is important. I mean it. You don't know how frustrating it is to get an assignment that just has the answers on it. It takes so much longer to grade.

I reserve the right to deduct points if you don't do this.

Organization

Keep your programs and assignments organized and easy to read.

Use a uniform writing style. Messy or unorganized submissions will have points deducted. Think to yourself: does it look good? Would I want to read this? Take pride in your work.

These assignments are not just for me to read and grade- you may wish to incorporate them into a portfolio for use in the future. Making an investment now could pay off later!

Timeliness

Turn in submissions on time.

Late submissions will be subject to an appropriate penalty. Circumstances vary, see the Late Policy for details.

In many cases, where possible, I do accept resubmissions.

Errors

If you encounter an error while performing some task (and the directions do not indicate you should be receiving an error), chances are you made a typo. Consult the class mailing list, class chat, ask someone, or contact me.

WARNING


Submissions containing answers based on user error will be considered incorrect.

Backups

Be sure to keep a backup copy of all assignments submitted in the event something is lost in transmission.

Important


It is your responsibility to be able to send another copy of your submission should the original be lost.

Common Sense

Use your own judgment. The world today is increasingly filled with rules and policies dictating what you can and cannot do. I am not about to go and list all the specifics and restrictions regarding assignment submission.

You are here to learn and to grow, and I want to allow you a certain amount of flexibility in that process. Spending all your time formatting an assignment to my specifications isn't my idea of learning. Incorporate these guidelines into your general style, if you miss the mark I'll let you know. But focus more on learning and understanding than worrying about dotting every 'i' or crossing every 't'. There's enough of that elsewhere in the world.

Late Policy

Sometimes, even though we try our hardest to get everything in on time, the spurious Murphy's Law will make an appearance. Your dog ate your network cable, a burst of cosmic rays damaged your RAM precisely where your work was located… the list goes on.

If something is not submitted by its respective due date, and no advance attempt has been made to communicate with me, the assignment will be invalidated of any value.

Bottom line.. if something is going to be late: let me know. It happens, just don't make a habit of it. Communication is key.

Unless otherwise specified, past due assignments will lose 25% credit per day, rendering them worthless credit-wise after 4 days.

Attendance

Attendance plays an important part in one's educational journey each semester. Missing class deprives you of essential knowledge and hinders understanding towards your eventual mastering of a topic.

Because we are all here to learn (and if learning isn't a priority, I highly suggest you think about making it such), and believe it or not- learning isn't just about one person, but the entire group. So it is important to be present in order to positively contribute to the learning experience.

I also reserve the right to drop students from the course due to excessive absences. On the same token, I reserve the right NOT to drop students from the course due to excessive absences.

Behaviour

Should your behaviour in the class be notably and consistently unruly, off-topic, or alarming, I have the ability to remove you from the class.

I will likely issue a warning, indicating a desire to have you cease the particular behaviour, but through continued transgressions, may actually elevate to forced removal from the class.

The priority is to the well-being of the class community. I cannot have individuals derailing that for their own personal gain or purposes.

Collaboration

Because this course is open resource (ie book, computer, note, etc.) I would like it generally to remain closed person and closed intelligence (the thinking done should be your own, not outsourcing it to some artificial entity). The reason for this is that the amount of resources available to you are vast, and the goal here is to discover and learn the material through individual initiative.

It IS possible to help others without giving away answers.

Respond to questions with a question, give pointers to where information might be located in legitimate sources, remind them of the usefulness of manuals, and the availability of search engines.

Individuals are allowed and expected, to assist others through the mailing list and class chat WITHOUT GIVING EXPLICIT ANSWERS, so long as it does not interfere with any other existing circumstance. If group work is required on anything, that attribute will be specifically stated.

Explicit copying on or of any class work is forbidden. If any evidence or suggestion of non-authentic work is discovered (and I can tell you some stories) in your particular direction, you risk both my wrath as well as the possibility of disciplinary action by the school. Academic dishonesty and plagiarism may be prosecuted under the purview as laid out in the school's Academic Honesty Policy, as listed under the Code of Student Conduct: Academic Honesty section in the CCC Course Catalog.

So just play it safe and make sure your work is your own, and borrowed information is appropriately cited or referenced.

Pet Peeves

Everyone has their buttons that can be pushed the wrong way. Here are a few of mine, that I would prefer not encountering:

  • the eager, often surface-only desire to destroy things (especially with no desire to understand the why behind it all)
  • the notion that 'old', 'unpopular', 'uncomfortable', or 'different', especially in terms of technology or experiences, is somehow bad (there are plenty of useful things to learn, for the patterns will often remanifest in future technologies down the road)
  • apologizing: “sorry I had to ask a question”, “sorry I misunderstood”, “sorry I failed to do that action”; I WANT people to ask questions. Questions are based on not fully understanding something. And if your actions come up short, apologies only serve to highlight the deficiency. The best solution: to fix it and not keep repeating the same mistake. There may be things worthy of apologizing for. For most incidents of apology I encounter related to classes, such is irrelevant. If you feel you are in the wrong for asking a question, you're doing this whole learning thing wrong.
  • overhelping “the weakest link”; a somewhat modern trend, where I see woefully unprepared/unready individuals overly assisted through the course (where the intent is to save them from failing). This is but a short-term perspective, contributing to their long-term failure.
  • opting out of things that seem overwhelming, yet somehow expecting things will get better as time goes on.
  • the desire to impress me– impressing comes by being impressive, not selling an act to me (in short, don't try to impress me, just do your best work)
  • avoiding the developing/strengthening your own memory and recall, and relying on others (including the instructor) to be your memory.
  • the obsession over and recitation of hardware specs– this has nothing to do with computing, yet many mistakenly believe it to be such (a small aspect of IT and an occasionally fun hobby? sure.)
  • the compensation for lack of knowledge by clinging tightly to (perceived) known knowledge– I expect everyone not to know things; knowing we don't know enables us to learn.
  • the avoiding of questions out of fear they may not be worthy of asking– how else can I know where you are if you don't ask?
  • the asking for the answer as if it were a question, to avoid thinking or doing the work yourself. Questions are the a result of your thinking, not “I don't know, so tell me?”, or the worst (literally): “What do I need to do in order to get an A/full credit?”
  • the absolute belief that if I say something then it is the truth (same for the inverse, converse, contrapositive, etc.)– being open-minded and questioning is one of the greatest abilities we can have. Society trains you to be compliant with external authority at the expense of your own; to be educated and intelligent, in part, means you have cultivated your own self-authority so you can make your own decisions.
  • the impression that if you say something frequently or confidently enough, then it must be true, and that you are an expert that should be believed, followed, and unquestioned.
  • the tendency to brute force through something instead of trying to think or learn new approaches– memorizing and regurgitation will often not work out in your favour here (or greatly annoy me).
  • being tangibly obsessed with knowing your exact grade, while being uninformed about the process of calculating it yourself from available information.
  • trying to add me to your “LinkedIn” network; I delete these e-mails without even reading them (nothing personal, I just do not use LinkedIn).
  • complaining upstream about me/my class without actually bringing issues to me first to address.

Rules for Success

For maximum success in the class, please adhere to the following rules:

  • start on activities early
  • observe/study, read/intuit, and comprehend the subject matter
  • play/tinker/experiment with the subject matter (external to assigned projects)
  • ask well-informed and copious questions

Struggle and problems in the course almost immediately arise when one fails to follow one or more of these guidelines.

Documentation

The following criteria should be kept in mind when contributing content to collaborative documentation, the wiki, your journal, and any pertinent class-related communications:

  • Never use a form of a word in its own definition
  • Use external hyperlinks only as citations
  • Content first, then formatting
  • There is only one empire- ours
  • Contribute only original content
    • paraphrase and cite existing information
    • do NOT blatantly copy existing information
  • A healthy wiki is an active wiki
  • Do not focus on just your contributions
  • Mistakes are opportunities for future contributions

Topics

The following is a list of the major topics being covered in this course:

  • Pointers (address of, assignment, dereferencing)
    • arrays, pointer arithmetic
    • pointers to pointers
    • null pointers
    • void pointers
    • function pointers
  • Static allocation vs. Dynamic allocation
    • Memory allocation (malloc(), new)
    • Memory De-allocation (free(), delete)
  • structures
    • structure pointer
  • Singly Linked Lists
    • creating
  • inserting
  • appending
  • obtaining
  • copying
  • deleting
  • Doubly Linked Lists
  • Stacks (array-based, linked-list based)
    • Pushing
    • Popping
    • Top
    • Overflow condition (where applicable?)
    • Underflow condition
    • LIFO or FIFO?
  • Queues (array-based, linked-list based)
    • Enqueuing
    • Dequeuing
    • Overrun and Underrun conditions
    • LIFO or FIFO?
  • Computational Complexity
    • Big-O, Theta, bounds
  • Sorting Algorithms
    • Selection sort algorithm
    • Bubble sort algorithm
    • Insert sort algorithm
    • Quick sort algorithm
    • Merge sort algorithm
  • Binary Search algorithm
  • Trees, Binary Trees (nodes, parents, children)
    • insertion
    • removal
    • searching
    • traversal (pre-order, post-order, in-order)
  • Graphs
  • Hash Tables (keys, collisions)

Student Understanding and Agreement of Syllabus Terms

By reading through this document, participating in the class chat, utilizing class resources, and performing the various class activities and projects, you consent and agree to the following:

  • You understand and consent to the rules and policies governing your status as a student at SUNY Corning Community College.
  • You understand and consent to the structure, policies, and nature of the course as laid out in this syllabus.
  • You understand and consent to having an adequate understanding of stated and assumed course prerequisite knowledge, or are willing to take on the personal challenge of getting yourself up to par with prerequisite knowledge, to succeed in the class.
  • You understand and consent to maintain a respectful, inquisitive, well-behaved, and learning-oriented focus as you participate and go through the course.
  • You understand and consent to practice (and further cultivate, as needed) the fundamental aspects of a student taking this course, which includes:
    • able and willing to read, comprehend and work with the material and information inherent to the course.
    • able and to write and express your thoughts in coherent, descriptive sentences.
    • able and willing to analyze, problem solve, debug, troubleshoot, ideate, creatively, and logically/rationally think.
    • able and willing to compute and transact in number concepts (literal, symbolic or abstract) and any related units in their various processes.
    • upon facing uncertainty, confusion, or lack of understanding, will ask copious, well-informed, and well-intending questions to clarify your state of understanding.
    • if cause for issue rises, you will bring it to my attention so that it may be best addressed as locally and pertinently as possible to the course and its educational environment.
    • participate in the course with a focus on curiosity, discovering, exploring, learning, and understanding.
    • starting early on deliverables so that ample time is available for discovering, exploring, learning, and asking any questions as needed.
  • You acknowledge that, as a student, a genuine learning experience necessarily involves some level of unfamiliarity, which may invoke discomfort.
  • You understand that your learning and the nature of the course is an inherently asynchronous thing. It is your responsibility to manage your time, so that you can have adequate time to ask questions and accomplish your own tasks.