CS 231: Syllabus

Title image Fall 2016

Syllabus for CS 231 Fall 2016

Topics and Reading Assignments

Course Description

The course focuses on the common structures used to store data and the standard algorithms for manipulating them. Standard data structures include lists, stacks, queues, trees, heaps, hash tables, and graphs. Standard algorithms include searching, sorting, and traversals. Along with implementation details, students will learn to analyze the time and space efficiency of algorithms and how to select appropriate data structures and algorithms for a specific application. In homework, labs, and programming projects, students will implement their own data structures and make use of existing libraries to solve a variety of computational problems.


Learning Goals

  1. Students understand the advantages and disadvantages of fundamental data structures and can implement them using object-oriented design principles.
  2. Students understand, can implement, and can calculate the time and space efficiency of classic search, sort, and traversal algorithms, including the use of big-Oh notation.
  3. Students understand the tradeoffs between different implementation of data structures and algorithms and can make appro- priate design decisions based on application data requirements.
  4. Students can use fundamental data structures and algorithms appropriately to solve a variety of computational problems.
  5. Students can communicate the result of their work and describe an algorithm.

Grading rubric and course goals.


Textbooks

You may choose from any number of Data Structures with Java textbooks that are available, however, we do not require any specific text. There are also lots of on-line resources available.

Links to free online data structures textbooks:

Grading

Weekly Projects 45%
Quizzes 25%
Homeworks 5%
Class Participation 5%
Final Exam 20%

Help and Discussion Outside of Lecture

Office Hours

Bruce and Stephanie will both be available to help outside of class time with questions about concepts or projects. Please do not hesitate to stop by our offices, or send us an email. We both enjoy talking about computer science and getting to know you.

Evening TA Help

In order to provide as much help as possible to you as you work on assignments in this course, the CS Dept has hired upper-level CS students to work as TAs in the Davis 102 lab in the evenings. You are strongly encouraged to take advantage of this resource. The TAs are getting paid to help you, so don't feel guilty about asking them for help. The evening TA hours are: Sunday 4-10pm, Monday 7-10pm, and Tuesday 4-6 & 7-10 pm.

Guidelines


Daily Topics and Readings

WeekTopicsReadings/Exams
1:
  • Python v. Java
  • Java syntax and semantics
  • Classes
2:
  • Constructors, polymorphism
  • Generics, arrays
  • Memory Model
Quiz
3:
  • ArrayLists and 2D arrays
  • Stacks: array-based
  • Abstract classes and Interfaces
Quiz
4:
  • Foreach loops, Iterable interface
  • Linked List, generic implementations
  • Node-based implementations of ADTs
Quiz
5:
  • Time complexity analysis
  • Doubly-linked lists
  • Sorting algorithms
Quiz
6:
  • Sorting
  • Searching
  • Relative time complexity
Quiz

October Break
7:
  • Recursion
  • Recursion v. iteration
  • Queues
No quiz
8:
  • Binary Search Trees
  • Tree insertion, deletion
  • Tree traversal
Quiz
9:
  • Balanced Trees
  • Heaps, Priority Queues
  • Heapsort
Quiz
10:
  • Array-based Heap implementation
  • Hash tables
  • Maps
Quiz
11:
  • Iterators and hash maps
  • Hash map implementations
  • Graphs
Quiz
12:
  • Graph representations
13:
  • Graph properties
  • Graph analysis
  • Shortest path algorithms
Quiz
14:
  • Intellectual Property
  • Copyright, Trademark
  • Patents
Quiz

Policies

Attendance and Participation

For this course to be truly successful, your presence and participation are important. Asking questions in class is an important part of learning. When you have a question, ask it. It is highly probable that many of your classmates have the same question. When you have an opportunity to share your opinion or your answer, please speak up. Your professor wants to hear what you have to say. And, of course, to participate in class you must attend class. If you must miss a class, you are responsible for making up the material covered in that lecture.

Deadlines

The short homework assignments must be turned in on time. No late short assignments will be accepted because we will refer to their solutions in class. Homework will be graded in a binary fashion: if you hand in a reasonable attempt, you get a 1, otherwise a 0.

All programming projects will be due at the end of the day on Monday (i.e. midnight). All programming projects must be submitted on time to be considered for full credit, except that every student is allowed one free 3-day extension to one project. Let both of us know when you are taking your extension. Programming projects submitted on time are graded on a 30 point scale. Late projects will be graded on a reduced scale. Projects for which you use your 3-day extension must be turned in by midnight on Friday for full credit.

Collaboration and Academic Honesty

Computer science, both academically and professionally, is a collaborative discipline. In any collaboration, however, all parties are expected to make their own contributions and to generously credit the contributions of others. In our class, therefore, collaboration on homework and programming assignments is encouraged, but you as an individual are responsible for understanding all the material in the assignment and doing your own work. Always strive to do your best, give generous credit to others, start early, and seek help early from both your professors and classmates.

The following rules are intended to help you get the most out of your education and to clarify the line between honest and dishonest work. We reserve the right to ask you to verbally explain the reasoning behind any answer or code that you turn in and to modify your project grade based on your answers. It is vitally important that you turn in work that is your own. We do use automated plagiarism detection software, so please be sure to abide by these, rather minimal, rules. Reports of academic dishonesty are handled by an academic review board and a finding of academic dishonesty may result in significant sanctions. For more details on Colby’s Academic Integrity policies and procedures, see www.colby.edu/academicintegrity/.

If you have had a substantive discussion of any homework or programming solution with a classmate, then be sure to cite them in your write-up. If you are unsure of what constitutes "substantive", then ask us or err on the side of caution. As one rule of thumb, if you see more than 10 lines of someone else's code, then you should cite them. You will not be penalized for working together. You must not copy answers or code from another student either by hand or electronically. Another way to think about it is that you should be talking English with one another, not Java.


The Colby Affirmation

Colby College is a community dedicated to learning and committed to the growth and well-being of all its members.

As a community devoted to intellectual growth, we value academic integrity. We agree to take ownership of our academic work, to submit only work that is our own, to fully acknowledge the research and ideas of others in our work, and to abide by the instructions and regulations governing academic work established by the faculty.

As a community built on respect for ourselves, each other, and our physical environment, we recognize the diversity of people who have gathered here and that genuine inclusivity requires active, honest, and compassionate engagement with one another. We agree to respect each other, to honor community expectations, and to comply with College policies.

As a member of this community, I pledge to hold myself and others accountable to these values.


Sexual Misconduct/Title IX Statement

Colby College prohibits and will not tolerate sexual misconduct or gender-based discrimination of any kind. Colby is legally obligated to investigate sexual misconduct (including, but not limited to sexual assault and sexual harassment).

If you wish to speak confidentially about an incident of sexual misconduct, please contact Colby Counseling Services (207-859-4490) or the Director of the Gender and Sexual Diversity Program, Emily Schusterbauer (207-859-4093).

Students should be aware that faculty members are considered responsible employees; as such, if you disclose an incident of sexual misconduct to a faculty member, they have an obligation to report it to Colby's Title IX Coordinator. "Disclosure" may include communication in-person, via email/phone/text, or through class assignments.

To learn more about sexual misconduct or report an incident, visit http://www.colby.edu/sexualviolence/.