Welcome!
Welcome to comp15!
The goal of this course is to build on your experience in comp11 and help you develop your skills as a programmer and computer scientist.
Class Information
General
|
Staff
|
||||||||||||||||||||
News and Important Dates
Assignment 1: Supermarket Simulator -- three parts, full system due Feb 23, 2012.
Assignment 2: Surrealist Turing Test -- due March 14, 2012.
Assignment 3: If I Ran the Zoo -- due April 17, 2012
Assignment 3: Song Search -- due May 6, 2012
Schedule
Week 1 (Jan 23): Introduction
Overview of the course; Separation of interface from implementation; review of core comp11 topics: structs and classes, pointers, dynamic memory allocation.
No lab
Week 2 (Jan 30): Sequences
Sequence and queue abstract datatypes (interfaces and their behavior). Two implementations: dynamic array and linked list.
Lab 1: Get In Line! Building a queue of strings
Week 3 (Feb 6): Building software
Translation of C++ source code into a program; development cycle: edit->compile->link->run; header vs cpp files; object files; layout of memory at runtime.
Examples: Structuring the code for the Car/Engine example.
Lab 2: Get Back in Line! More practice with linked data structures.
Assignment 1 out: Supermarket Simulator
Week 4 (Feb 13): Stacks, more on ADTs
Makefiles and compile scripts; Abstract datatype vs interface vs implementation; Stack abstract datatype; Using stacks to manage goals and subgoals.
Lab 3: Stacks. Using a stack to evaluate arithmetic expressions.
Week 5 (Feb 20): Recursion
Structural and generative recursion; base cases and recursive cases
Examples: Notes on recursion.
No lab
Week 6 (Feb 27): Trees
Tree structure; tree terminology; traversals: preorder, postorder, inorder, level-order (breadth-first); recursive versus explicit stack/queue.
Lab 4: Sorting With Recursion
Week 7 (Mar 5): Cost
Cost functions; big-O notation; recurrence relations; cost of common linked list and dynamic array operations.
Lab 5: Working with trees
Week 8 (Mar 12): Midterm and Project Work
Week 9 (Mar 26): Sets and finite maps
Introduction to the set and finite map (aka dictionary or associate array) abstract data types; operations and algebraic laws ("contract").
Week 10 (Apr 2): Fast lookup
Data structures for fast lookup; move-to-front linked list; binary search tree; skip-list
Lab 7: Zoological Dictionary
Week 11 (April 9)
Self-balancing binary search trees: AVL tree, balance factor, tree rotations
Lab 8: Enhancing Your BST class
Week 12 (April 16)
Exploiting the structure of keys: tries, hash tables
Lab 9 (Last Lab!): A Better Way to Keep Track of Animals
Week 13 (April 23)
More on hashing: load factor, resizing, rehashing; sets with findmin: partially ordered trees, heaps; graphs and graph representations.
Lab: Discuss your design for song search with a TA.
Policies
Grading
Your grade in this course will be based on the programming assignments, the midterm, and the final. Labs are not graded, but attendance is required. Grades will be computed as follows:50% Assignments
20% Midterm
25% Final
5% Class participation, lab attendance
Late policy
Everyone runs into situations, both within and out of their control, when they need extra time to finish an assignment. I will be using the "late day token" system, which functions kind of like "sick days" in the real world. It gives you control over these situations and avoids the unpleasant conversations where you try to convince me you deserve more time. Here's how it works:
- Each of you gets three (3) late day tokens. Each token lets you turn in one assignment one day late.
- You can budget them in different ways: 3 assignments 1 day late, 1 assignment 3 days late, etc. -- but tokens must be used whole (they cannot be split into pieces).
- You don't need explain why you're using tokens. That's the beauty! However, you must tell me when you're using tokens. If you just turn assignments in late without telling me, I will apply a steep penalty.
- I'm not a real stickler for deadline times, so you don't need to waste a token if you turn in an assignment 15 minutes after the deadline. But if you're going to turn it in any time the next day you will need to use a token.
- Once you have used up your tokens, you must turn assignments in on time. The late penalty will be 50% for each day late (in other words, two days late and it is a zero).
- There are, of course, exceptions for exceptional circumstances. You know what I'm talking about -- death in the family, illness or injury requiring hospitalization, etc.
My advice: if you're having trouble get help early. We have a boatload of TAs who can help you with any topic or assignment. If you start early you'll be able to enlist their help before you get into trouble and need to burn up late day tokens.
Academic (mis)conduct
Students in this class are encouraged to discuss the programming assignments, but each student must produce his or her solutions completely independently. Specifically, you may verbally discuss problems, issues, and ideas, but you may not write anything down together. In addition, I ask that you document, in your code, anyone with whom you discussed the assignments.
Academic misconduct (also known as "cheating") is a very serious issue at Tufts. As a member of the University community, I am obligated to report any incidents. The consequences are painful for everyone involved. For more details, see the Tufts brochure on academic conduct: http://uss.tufts.edu/dosa/publications/documents/integrity.pdf
The most common reason for cheating is becoming overwhelmed by the work. Every one of us has been in this situation, and we're more than willing to help you if you feel like you're in trouble. Please, please come to us before you get into a situation where you're tempted to take someone elses solution.
Updated February 13, 2012