Syllabus
Course Description
This course extends the work of CS 065. This object of the course is to understand data abstraction in computer science and to learn how to implement user-defined data types in an object-oriented language. Sorting, searching and tree traversal algorithms are used and analyzed. Preparation for further study in computer science. Prereq.: CS 065 or equivalent.
Learning Objectives
- given a description of an algorithm using common abstract data types and data structures, implement it in a high-level programming language (e.g., Python)
- write programs that use common abstract data types to solve a given problem
- implement custom abstract data type operations using appropriate data structures
- discuss factors that influence the selection of algorithms and data structures
- analyze the computational complexity of simple algorithms, including those for searching and sorting collections of data
Examples of common abstract data types include ordered and unordered collections, stacks, queues, priority queues, sets, maps, and graphs. Examples of common data structures include arrays, linked lists, trees, hash tables, and heaps.
Textbook
We will be using a free, open-source textbook: Problem Solving with Algorithms and Data Structures using Python by Brad Miller and David Ranum.
You can access it here: https://runestone.academy/ns/books/published/pythonds/index.html
This textbook will frequently be linked to from the class notes and course Content page, often abbreviated as pythonds. Other references will be provided as needed.
Course Topics
The programming language we will use is Python 3. Here is a more detailed list of the course topics with corresponding textbook sections in roughly the order we will go through them
- Review of basic Python and built-in collection types (1.7-1.12)
- Introduction to the requests module and Web APIs
- Introduction to writing Dash applications
- Introduction to Abstract Data Types (1.5, 4.20, 4.22, 6.5.3)
- Stack, Queue, and Deque Abstract Data Types (4.3-4.18)
- Introduction to Algorithm Analysis (3.1-3.9)
- Review of Python classes (1.13, 2.1, 2.2)
- Linear data structures: Linked Lists and Arrays (3.6, 4.19-4.23)
- Comparing alternative implementations of ADTs using linear data structures (4.5, 4.12, 4.17, 4.21, 4.23)
- Sequential and Binary Search (6.1-6.4)
- Hash Table data structure for sets and maps (6.5)
- Recursion (5.1-5.11)
- Comparing sorting algorithms (6.6 - 6.12)
- Search Tree data structure for sets and maps (7.1-7.5, 7.11-1.17)
- Heaps and Priority Queues (7.8-7.10) - covered as time allows
- Graph Abstract Data Type (8.1-8.20) - covered as time allows
Activities / Grading
Your grade in this course is determined by:
| Programming Assignments | 60% |
| Exams | 30% |
| Final Project | 10% |
The grading scale for the course is as follows.
| A | 93–100% | C+ | 77–80% |
| A- | 90–93% | C | 73–77% |
| B+ | 87–90% | C- | 70–73% |
| B | 83–87% | D | 60–70% |
| B- | 80–83% | F | 0–60% |
Programming Assignments
Programming assignments will be given regularly - once or twice per week. Some will be small (4 points) and some will be large (8 points). In some cases, they will be extensions of in-class exercises that are turned in for credit.
All code is to be submitted using the codePost tool. See the Resources page for more info. We’ll walk through using codePost before you submit your first assignment. Some assignments will include automated testing of your code, so you will need to follow instructions to make sure that your code works with the automated testing code.
You can find the due dates on the Assignments page and the Content page - both of which will be updated throughout the semester.
Assignment Grading
Each assignment will be with either 4 or 8 points depending on the amount of work involved, but they will both be graded based on the same basic rubric:
- 100%: submission is complete and correct, addressing all requirements given in the assignment document
- 75%: significant progress towards a solution to the assignment problem(s) has been made; though it may not be entirely complete or correct
- 50%: an attempt at the assigned problem(s) has been made that demonstrates serious effort was made in trying to understand the material and/or apply concepts in question
- 25%: the submission contains evidence of completion of work related to the assignment (such as solutions to in-class, non-graded exercises leading up to the assignment)
Assignment collaboration policy
Assignment work my be done in collaboration with other students in class. However, you may not copy others’ code - collaborating means that you are actively engaged in the entire problem-solving process, not merely being assisted by another student who has already solved it. Each student is expected write up and submit all of their code individually, and include the names of any collaborators in the comments of your code.
In order to avoid the attempt to copy, you may not look at code that another student has completed but you have not, including students from previous semesters of the course.
Exams
Content delivery (lectures, course notes, and readings) will be accompanied by exams over that content. There will be three exams which will be completed using the Test tool on the course Blackboard page. All exams are to be completed individually - you may not collaborate with anyone. The tentative plan is for the exams to be done asynchronously - meaning you will take them on your own and submit through Blackboard, and you will typically be allows to use the book, notes, and certain other outside resources. You will be given a day or two to complete each exam, and they will be tentatively due on the following dates:
- Exam 1: Friday, February 24th (Week 5)
- Exam 2: Friday, April 7th (Week 11)
- Exam 3: Wednesday, May 10th (Week 16 - Finals week)
The instructor reserves the right to adjust the exam schedule, switch to an in-class/synchronous exam, and/or adjust the resources that may be used when completing exams.
Course Project
You will complete a team project (2-3 students per team) in which you explore data structures beyond the scope of what is covered in the rest of the class. More information on the specific requirements will be made available later, but it will include an initial project proposal as well as a presentation over the project at the end.
Course Policies
Attendance and Class Delivery Mode
This class will be delivered in person, and your attendance is extremely important for your learning. You are expected to attend unless you have a good reason.
I will attempt to record audio and screen capture of most class periods and post them to the Blackboard Panopto tool. These are provided as a courtesy for your reference, but they will not be a substitute for the in-class experience (you’ll miss things written on the board, activities done in groups, etc.)
If the university or instructor determines it is necessary to switch to an online-only delivery mode, either temporarily (e.g., due to illness of the instructor) or permanently (e.g., a prolonged COVID outbreak on campus), arrangements will be communicated via an announcement on the Blackboard page and/or email.
What to do if you need to work remotely
If you need to miss an in-person class because of illness or other reasons, you are expected to use the resources on the course website and Blackboard to stay caught up. Use the class slides, videos, and textbook; and continue working through in-class exercises, assignments, exams, etc.
If, for some good reason, you require a prolonged absence, please communicate with the instructor to make arrangements.
Using ChatGPT and other AI-Based Tools
You are tentatively permitted to use ChatGPT and other AI-Based Tools to assist with your learning, including in the development of code you submit for assignments and in solutions to exam questions, under the following conditions:
- You must not present AI-generated work as if it were your own
- You must fill out and submit the AI Assisted Learning Reflection before the assignment’s due date. To do this, make a copy of the Google Document, fill it out as instructed, download it as a PDF document, and then submit the PDF document to the AI Assisted Learning Reflection submission form on the course Blackboard page.
Failure to abide by this policy will be considered an academic integrity violation and penalized as described below.
The instructor reserves the right to change this policy for any given assignment or exam, and this will be communicated when the assignment/exam is assigned.
Deadlines
Extensions to due dates need to be requested and approved before the item is due, so make sure to communicate with the instructor about exceptional circumstances that may require special accommodations.
Accommodations for Students with Disabilities
I will be happy to discuss any academic accommodations needed for students with disabilities. However, any student seeking accommodation must coordinate them with the Access and Success office before the accommodations are needed. No retroactive accommodations will be made.
Academic Integrity
Drake University has high standards for academic integrity, and you are expected to read the Academic Dishonesty Policy from the College of Arts and Sciences.
Below is a particularly relevant excerpt from the statement:
Academic dishonesty is an all encompassing term involving any activity that seeks to gain credit for work one has not done or to deliberately damage or destroy the work of others. Academic dishonesty includes, but is not limited to, plagiarism, cheating, fabrication, and knowingly helping another to commit an act of academic dishonesty.
Below are some examples of how Drake’s policy applies to this course:
- You may discuss concepts described in the readings or during class with anyone.
- You may collaborate with other students in the class on assignments as described in the Assignment Collaboration Policy given above
- Students are encouraged to seek out resources for help in understanding concepts when completing coursework. However, there is a big difference between seeking outside resources for help in understanding (which is good!) and searching for solutions (which is bad). Looking for solutions to an assignment defeats the purpose of the assignment and is not acceptable even if you write up the solution independently.
- All the work you submit must be entirely your own or you must specifically acknowledge and attribute any contribution or assistance from others or any other source that you used The suggested acknowledgment format is: “[Source X] helped me to do [thing Y] by [explaining Z].”
- If you use an AI tool to help you with an assignment, you must cite it and submit the AI Assisted Learning Reflection as described above.
- You are responsible for safeguarding your work from being copied by others.
The bottom line: Be completely transparent about your use of sources and other people. Even if you did something you weren’t supposed to, I might not give full credit, but it will not be considered an academic integrity issue.
Getting Help
Instructor
Feel free to reach out to me at any time. The quickest way to get a hold of me is to message me on Microsoft Teams.
My office hours are M 1:00-3:00PM, Th 9:30AM-12:30PM in Collier-Scripps 327.
Use the Calendly link to schedule an appointment. Preference will be given to students who sign up ahead of time, but you are also encouraged to drop in during scheduled office hours without an appointment.
NOTE: If you cannot make any of the times listed, feel free to message me on Microsoft Teams or send me an email to make other arrangements.
Tutoring
We may have some tutors available who can assist with this class. For more information, see the Tutoring page.
Academic Success Resources
Check out the Academic Success website. It includes a page for Skills for Success with excellent tips for management classwork. You may also find the following resources useful: