This syllabus is subject to change based on specific class needs, especially the schedule. Significant deviations will be discussed in class. Individual exceptions to the policies and schedule are granted only in cases of true emergency. Please make arrangements with me if an emergency arises.
Data structures continues the study of abstraction and programming through a focused study of data structures, algorithms, and abstract data types. The primary focus of this course is the design and development of algorithms and programs using data abstraction and information hiding via abstract data types ADTs. Data abstraction is absolutely fundamental to good programming practice and the management of large scale problems and data sets. This course is designed to round out a student’s understanding of basic computer science concepts while strengthening the program design and development skills through continued use of an object-oriented design methodology.
It is imperative that programmers and program designers be able to determine which of the many solutions available is the best for their specific task. Throughout the course, students will focus on to making solid quantitative and qualitative judgments about program efficiency and overall program design choices. Gone are the days when “it works” is a good enough assessment for the quality of a program.
Students will explore the ideas and concepts brought up in class and homework assignments during the weekly lab session. In addition to hands on exercises, lab sessions will be used to explore current, relevant research in computer science.
The course textbook will be:
Other sources will be posted on this webpage as needed.
The course aims to cover most of chapters 1-8 and parts of chapters 9-12. Other elements may be covered as time allows. The topics include, but are not limited to:
| - Review of Python fundamentals | - Object-Oriented Design Basics and Patterns |
| - Experimental and Asymptotic Algorithm Analysis | - Recursion |
| - Arrays and Sequence Data Types | - Stacks, Queues, Deques, and Priority Queues |
| - Abstract Data Types | - Linked Data Structures |
| - Binary Search Trees and Tree Traversal Algorithms | - Maps and Dictionaries |
| - Sorting, Searching, and Selection Algorithms | - Graph Algorithms (as time allows) |
This course uses Python 3 and repl.it, an online IDE service. Students will receive, complete, and submit assignments all via the website. Students can also complete assignments on their local machines or on the departmental server, but all assignment submissions must be done through repl.it unless otherwise specified.
The weekly workload for this course will vary by student and by week but should be about 14 hours per week on average. The following table provides a rough estimate of the distribution of time over different course components for a 16 week semester, as well as detailing the type, amount, and relative value of all assignments.
| Category | Amount | Final Grade Weight | Total Time | Time/Week (Hours) |
|---|---|---|---|---|
| Lectures | 41 | 10% (Participation) | - | 2.25 |
| Labs | 8–13 | 15% | - | 2.75 |
| Homework | 8–10 | 15% | 48 | 3 |
| Exam Study | - | - | 16 | 1 |
| Exams | 5–7 | 30% | - | - |
| Projects | 2 | 30% | 48 | 3 |
| Reading+Unstructured Study | - | - | 2 | |
| 14 |
Homework assignments will always either precede a lab to prepare for it or follow a lab to complete it. Each exam will focus primarily, but not necessarily exclusively, on the material covered since the previous exam.
Lab and homework assignments are graded on a simple 3 point scale, marked with (in decreasing order) a check-plus, check, or check minus. Your final grade for these two assignment categories is then based on the respective averages.
Your participation grade is based on a variety of activities. During class I will often make use of the Socrative app, so you’ll need to install this on your phones. Participating in Socrative questions and with in-class group activities is required for a decent participation grade; an A includes asking questions either in class or in office hours.
Your final grade is based on a weighted average of particular assignment categories. You can estimate your current grade based on your scores and these weights. You may always visit the instructor outside of class to discuss your current standing. Assignments and final grades use a standard grading scale shown below and will not be curved except in rare cases when deemed necessary by the instructor.
This courses uses a standard grading scale. Assignments and final grades will not be curved except in rare cases when its deemed necessary by the instructor. Percentage grades translate to letter grades as follows:
| Score | Grade |
|---|---|
| 94–100 | A |
| 90–93 | A- |
| 88–89 | B+ |
| 82–87 | B |
| 80–81 | B- |
| 78–79 | C+ |
| 72–77 | C |
| 70–71 | C- |
| 68–69 | D+ |
| 62–67 | D |
| 60–61 | D- |
| 0–59 | F |
You are always welcome to challenge a grade that you feel is unfair or calculated incorrectly. Mistakes made in your favor will never be corrected to lower your grade. Mistakes made not in your favor will be corrected. Basically, after the initial grading your score can only go up as the result of a challenge*.
You are always welcome to challenge a grade that you feel is unfair or calculated incorrectly. Mistakes made in your favor will never be corrected to lower your grade. Mistakes made not in your favor will be corrected. Basically, after the initial grading your score can only go up as the result of a challenge.
Late assignments: You have each been allotted a total of 5 late days. You may apply these to any homework or programming assignment (NOT exams, labs, or reading assignments) you see fit and turn in your solutions with no penalty. Each late days gives you exactly 24 extra hours from the original due date and time. However, you may use at most 2 late days on any individual assignment. The whole point here is to give you some flexibility that allows for things like illnesses, long trips, and the like. I am unlikely to grant further extensions. You must notify me if you will use late days, and how many, BEFORE the assignment is due. Late assignments (beyond any applied late days) will be subject to a grade reduction at my discretion. While you should expect a reasonable penalty for late work, know that I will NEVER give you a 0 for late work as long as it is turned in before the final exam.
Academic dishonesty: Monmouth College’s official policy on academic dishonesty can be found here. You are responsible for reading and complying with that policy.
In this course, any violation of the academic honesty policy will have varying consequences depending on the severity of the infraction as judged by the instructor. Minimally, a violation will result in an “F” or 0 points on the assignment in question. Additionally, the student’s course grade may be lowered by one letter grade. In severe cases, the student will be assigned a course grade of “F” and dismissed from the class. All cases of academic dishonesty must be reported to the Associate Dean who may decide to recommend further action to the Admissions and Academic Status Committee, including suspension or dismissal. It is assumed that students will educate themselves regarding what is considered to be academic dishonesty, so excuses or claims of ignorance will not mitigate the consequences of any violations
Collaboration: We encourage you to make use of the resources available to you – it is fine to seek help from a friend, tutor, instructor, internet, etc. However, copying of answers and any act worth of the label “cheating” is never permissible! In addition to listing your sources and collaborators, you should be producing your own writeup in your own words. By “your own words,” we mean you should be producing the text yourself, without some external aid. Verbatim copying of text is specifically disallowed, but so is taking a source and rearranging some phrases and changing some variable names to create a derivative version! Such behavior is definitely NOT “using your own words.” It does not matter if you helped contribute to this source text with others, since then you are still not the sole author of the text. The point of collaborating on an assignment is not to produce a jointly authored set of solutions, since that violates the course policies. Instead, it is to help you solve the problems, which sometimes involve a bit of creativity. After you have jointly come up with the ideas you need to solve the problems, though, you should part ways with your group and sit down to do the writing by yourself. I also advise against sharing the writeup you submit with others, since if someone else uses your text as a source for their own solution (with or without your permission), you will also be implicated in the violation of the academic integrity policy. In any case, if two nearly identical solutions are received, we have no way of tell which is the original, and the policy is to not award credit for either submission.
Electronic devices: Do not use your phone or other devices in class except where necessary. Any computer or tablet usage should be related to the course. If a device is not being used for Zoom or Socrative it should be put away and turned on silent. Other usage is rude and distracting to others.
General expectations: In short, I expect you to be respectful of others and take responsibility for your own learning. You are here to learn, so work hard and be professional.
Just attending class is not sufficient to truly learn the material. Read the text, use the resources available at Monmouth College, and go beyond the material.
If you miss class, you are responsible for everything covered on that day. College is, in some sense, your job. Take pride in creating quality work. Staple your assignments, label problems, and present your answers neatly and orderly.
Your job is to convince me that you have learned the material – show your work! Even if you do not know a particular answer, guide me through your thought process.
The following tentative calendar should give you a feel for how work is distributed throughout the semester. Assignments and events are listed in the week they are due or when they occur. This calendar is subject to change based on the circumstances of the course.
Note: All readings should be done before the class period in which they are listed below.
| Date | Topic | Assignment and Readings |
|---|---|---|
| Mon 01/09 (Week 1) | Logistics, Overview | |
| Wed 01/11 | Python Review | 1.1-1.5 |
| Wed 01/11 (lab) | Lab/Hwk 1: Python Basics with Turtle | |
| Fri 01/13 | Testing | |
| Mon 01/16 (Week 2) | Advanced Python | 1.6-1.11 |
| Wed 01/18 | Classes | 2.1-2.3 |
| Wed 01/18 (lab) | Lab/Hwk 2: Vector class | |
| Fri 01/20 | Inheritance | 2.4 |
| Mon 01/23 (Week 3) | Containment vs. Extension; Misc. OOP | 2.5-2.6 |
| Wed 01/25 | Performance Analysis | 3.1-3.2 |
| Wed 01/25 (lab) | Lab 3: Counting Primitives with Prefix Sums | |
| Fri 01/27 | Review | |
| Mon 01/30 (Week 4) | Exam 1 (Ch. 1-2) | |
| Wed 02/01 | Exam 1 Solutions, Big-O | 3.3 |
| Wed 02/01 (lab) | Homework 3: Big-O Exercises | |
| Fri 02/03 | Analysis Exercises | 3.4 |
| Mon 02/06 (Week 5) | Array-Based Sequences | 5.1-5.3.1 |
| Wed 02/08 | Dynamic Array Analysis | 5.3-5.4 |
| Wed 02/08 (lab) | Lab/Hwk 4: Dynamic Arrays | |
| Fri 02/10 | Exam 2 (Ch. 3) | |
| Mon 02/13 (Week 6) | Stacks | 6.1 |
| Wed 02/15 | Queues | 6.2 |
| Wed 02/15 (lab) | (Project 1) | |
| Fri 02/17 | Deques | 6.3 |
| Mon 02/20 (Week 7) | Recursive Functions | 4.1,4.4 |
| Wed 02/22 | More Recursion | |
| Wed 02/22 (lab) | (Project 1 Open Lab) | |
| Fri 02/24 | Analyzing Recursive Functions | 4.2 |
| Mon 02/27 (Week 8) | Project 1 Questions | |
| Wed 03/01 | Binary Search | |
| Wed 03/01 (lab) | (Project 1 Open Lab) | |
| (Fri 03/03) | (Exam day for 1st half-semester courses) | |
| (Mon 03/06 – Fri 03/10) | (Spring Break) | |
| Mon 03/13 (Week 9) | Binary Search Analysis; Recursion Run Amok | 4.3 |
| Wed 03/15 | Exam 3 Review | 12.1, 5.5 |
| Wed 03/15 (lab) | Lab/Hwk 5: Recursion Practice | |
| Fri 03/17 | Exam 3 (Mostly Ch. 4, some 5,6) | |
| Mon 03/20 (Week 10) | Selection Sort | 12.1, 5.5 |
| Wed 03/22 | Insertion Sort, Homework Review | |
| Wed 03/22 (lab) | Lab/Hwk 6: Sorting | |
| Fri 03/24 | Mergesort | 12.2 |
| Mon 03/27 (Week 11) | Quicksort | 12.3 |
| Wed 03/29 | Singly-Linked lists | 7 |
| Wed 03/29 (lab) | Lab/Hwk 7: Linked Lists | |
| Fri 03/31 | Doubly-Linked Lists | 7.2-7.3 |
| Mon 04/03 (Week 12) | Linked List Review/Exercises | |
| Wed 04/05 | Exam Review | |
| Wed 04/05 (lab) | During lab time: Exam 4 (Ch. 12,7) | |
| (Fri 04/07) | (Easter Break) | |
| (Mon 04/10) (Week 13) | (Easter Break) | |
| Wed 04/12 | Binary Trees | 8.1-8.2 |
| Wed 04/12 (lab) | Lab/Hwk 08: Trees | |
| Fri 04/14 | Binary Tree Implementation | 8.3 |
| Mon 04/17 (Week 14) | Properties of Binary Trees | |
| Wed 04/19 | Tree Traversals | 8.4 |
| Wed 04/19 (lab) | (Project 2 Start) | |
| Fri 04/21 | Non-recursive traversals, Priority Queues | 9.1-9.2 |
| Mon 04/24 (Week 15) | Heaps | 9.3-9.4 |
| Wed 04/26 | Array-Based Heaps, Intro to Maps | 10.1 |
| Wed 04/26 (lab) | (Project 2) | |
| Fri 04/28 | Using Maps, Hash Functions | 10.2-10.3 |
| Mon 05/01 (Week 16) | Hash Collisions, Binary Search Trees | 11.1 |
| Wed 05/03 | Self-Balancing Search Trees | 11.2-11.3 |
| Wed 05/03 (lab) | During lab time: Final Exam Review | Project 2 Due |
| Fri 05/05, 8:00 AM | Exam 5 (Final) |
Mental Health and Counseling Services: Monmouth College provides cost-free, professional mental health counseling to support you and to help you manage challenges that may impact your personal and academic success. The Counseling Center is located in the uppler level of Poling Hall (rooms 204 and 216), and the hours are Monday–Friday, 8:30 AM to 5:00 PM. For an appointment call 309-457-2115, email counselingservices@monmouthcollege.edu, cbeadles@monmouthcollege.edu, or tcaudill@monmouthcollege.edu, or request an appointment directly by going to titanium.monmouthcollege.edu and clicking on “request an appointment.”
The Academic Support and Accessibility Services Office offers FREE resources to assist Monmouth College students with their academic success. Programs include supplemental instruction for difficult classes, drop-in and appointment tutoring, and individual academic coaching. The office is here to help students excel academically, since everyone can work toward better grades, practice stronger study skills, and mange their time better. Please email academicsupport@monmouthcollege.edu for assistance.
Accessibility Services: If you have a disability and/or medical/mental health condition, or had academic accommodations in high school or another college, you may be eligible for academic accommodations at Monmouth College under the Americans with Disabilities Act (ADA). Monmouth College is committed to equal educational access. To discuss any of the services offered, please call or meet with Jennifer Sanberg, Associate Director of Academic Success and Accessibility Services. The ASAS office on the first floor of the Hewes Library, opposite Einstein Bros. Bagels. The office can be reached at 309-457-2257 or via email at academicsupport@monmouthcollege.edu.
The The Office of Student Equity Inclusion & Community can be found on the first floor of the Champion Miller Center for Student Equity Inclusion & Community. The office provides support to meet the needs of underrepresented students and international students. Services include: personal and academic advising, help with transition to Monmouth College, information on scholarships, internships, and employment opportunities with the help of other campus offices, and intercultural programming. Office Phone Number: 309-457-3612. Email: champion@monmouthcollege.edu
This course covers a variety of knowledge areas as categorized by the ACM/IEEE-CS Task Force on Computing Curricula. Note that not all of these areas are introduced in this course; some are touched upon previously and others will be developed further in later courses. At the end of the course, students should achieve the following learning outcomes with the specific level of mastery:
| Knowledge Unit | Learning Outcome with Level of Mastery |
|---|---|
| Basic Analysis | - In the context of specific algorithms, identify the characteristics of data and/or other conditions or assumptions that lead to different behaviors. [Familiarity] |
| - Explain what is meant by “best”, “average”, and “worst” case behavior of an algorithm. [Familiarity] | |
| - In the context of specific algorithms, identify the characteristics of data and/or other conditions or assumptions that lead to different behaviors. | |
| - Perform empirical studies to validate hypotheses about runtime stemming from mathematical analysis. Run algorithms on various input sizes and compare performance. [Assessment] | |
| - Determine informally the time and space complexity of simple algorithms. [Usage] | |
| - Understand the formal definition of big O. [Familiarity] | |
| - List and contrast standard complexity classes. [Familiarity] | |
| - Give examples that illustrate time-space trade-offs of algorithms. [Familiarity] | |
| - Use big O notation formally to give asymptotic upper bounds on time and space complexity of algorithms. [Usage] | |
| Algorithmic Strategies | - Have facility mapping pseudocode to implementation, implementing examples of algorithmic strategies from scratch, and applying them to specific problems. [Familiarity] |
| - Use a divide-and-conquer algorithm to solve an appropriate problem. [Usage] | |
| Fundamental Data Structures and Algorithms | - Implement simple search algorithms and explain the differences in their time complexities. [Usage, Assessment] |
| - Discuss factors other than computational efficiency that influence the choice of algorithms, such as programming time, maintainability, and the use of application-specific patterns in the input data. [Familiarity] | |
| - Be able to implement common quadratic and $O(n \log n)$ sorting algorithms. [Usage] | |
| - Demonstrate the ability to evaluate algorithms, to select from a range of possible options, to provide justification for that selection, and to implement the algorithm in a particular context. [Usage, Assessment] | |
| Fundamentals | - Explain the concept of modeling and the use of abstraction that allows the use of a machine to solve a problem. [Familiarity] |
| Basics of Counting | - Perform computations involving modular arithmetic. [Usage] |
| Processing | - Analyze simple problem statements to identify relevant information and select appropriate processing to solve the problem. [Assessment] |
| - Identify the issues impacting correctness and efficiency of a computation [Familiarity] | |
| Defensive Programming | - Demonstrate the identification and graceful handling of error conditions. [Usage] |
| Graphs and Trees | - Demonstrate different traversal methods for trees [and graphs], including pre, post, and in-order traversal of trees. [Usage] |
| - Model a variety of real-world problems in computer science using appropriate forms of [graphs and] trees, such as representing … a hierarchical file system. [Usage] | |
| Data Modeling | - Describe the main concepts of the OO model such as object identity, type constructors, encapsulation, inheritance, polymorphism, and versioning. [Familiarity] |
| Object-Oriented Programming | - Compare and contrast the procedural and object-oriented approach. Understand both as defining a matrix of operations and variants. [Assessment] |
| - Use subclassing to design simple class hierarchies that allow code to be reused for distinct subclasses. [Usage] | |
| Algorithms and Design | - Determine whether a recursive or iterative solution is most appropriate for a problem. [Assessment] |
| - Implement a divide-and-conquer algorithm for solving a problem. [Usage] | |
| - Apply the technique of decomposition to break a problem into smaller pieces. [Usage] | |
| - Implement a coherent abstract data type, with loose coupling between components and behavior. [Usage] | |
| - Discuss the importance of algorithms in the problem-solving process. [Familiarity] | |
| - Discuss how a problem may be solved by multiple algorithms, each with different properties. [Familiarity] | |
| - Implement, test, and debug simple recursive functions. [Usage] | |
| Fundamental Programming Concepts | - Analyze and explain the behavior of simple problems involving the fundamental programming constructs. [Assessment] |
| - Identify the base case and the general case of a recursively-defined problem. [Assessment] | |
| Fundamental Data Structures | - Discuss the appropriate use of built-in data structures. [Familiarity] |
| - Describe common applications for each data structure in the topic list. [Familiarity] | |
| - Write programs that use each of the following data structures: arrays, strings, linked lists, stacks, queues, sets, and maps. [Usage] | |
| - Compare alternative implementations of data structures with respect to performance. [Assessment] | |
| - Choose the appropriate data structures for modeling a given problem. [Assessment] | |
| Development Methods | - Trace the execution of a variety of code segments and write summaries of their computations. [Assessment] |
| - Apply a variety of strategies to the testing and debugging of simple programs. [Usage] | |
| - Construct and debug programs using the standard libraries available with the chosen programming language. [Usage] | |
| - Apply consistent documentation and program style standards that contribute to the readability and maintainability of software. | |
| Software Construction | - Construct models of the design of a simple software system that are appropriate for the paradigm used to design it. [Usage] |
| Professional Communication | - Evaluate written technical documentation to detect problems of various kinds. [Assessment] |