This describes Data Structures & Algorithms, sometimes known as CSCI 2270, at the University of Colorado, Boulder. The course home page is actually a GitHub repository located here:
https://github.com/johnsogg/cs2270
(See below for office hours info)
(See the email_policy.md file for info on emailing the instructor
or the TAs before you send mail.)
Instructor: Gabe Johnson - gabe.johnson@gmail.com
TAs:
- Yogesh Virkar - Yogesh.Virkar@colorado.edu
- Xin Pan - xin.pan@colorado.edu
- Shang Ma - Shang.Ma@colorado.edu
LAs:
- Nathaniel Pohl - nathaniel.pohl@colorado.edu
All office hours are held in ECCS 128, also known as the CSEL. This room requires a keycard for entry, but you can get one by following the instructions at http://csel.cs.colorado.edu/.
The schedule will begin Jan 28. (Gabe is doing office hours already.) You might find people in the lab to help, so be bold and give it a shot.
For specific office hours please see the Google Calendar for CSCI 2270 Office Hours
We will be using table tags to identify who is there providing help.
Where: Ramaley C250 When: M-W-F 11:00--11:50am
Final Exam: May 8, 1:30--4:00pm Ramaley C250 (same as classroom)
The purpose of this class is to introduce you to some of the fundamental tools in computer science: data structures and the algorithms that operate on them. This will be a tricky course, but it is not by any means meant to be a "weed out" class. If you are having trouble, please come see me before it is too late and we can work something out.
Computer programming, and the more general idea of computational thinking, is rapidly becoming a basic literacy skill. By the end of this course you should be prepared to tackle many advanced CS and programming challenges.
There are two components to your final grade: Homeworks and tests. Each component is worth 1/2 of your grade. Homeworks are due on Fridays. Test dates and homework due dates are given on the calendar.
There are eleven homework assignments. Each is worth 15 points, for a total of 165 points. Homeworks are due at 6pm. After they are late, you may only receive a maximum of 5 points. You may use RetroGrade to turn in your assignment as often as you like. Keep in mind that if you turn it in after it is due, it will cap your score at 5/15.
Many assignments can be completed in more than one language, though you are only required to complete it in C++. Happily, you can turn in assignments in the other available langauges and earn up to 15 extra credit points.
At the end of the semester, provided you received at least 5 points on all homework assignments, extra credit will be aded to your total homework grade, but extra credit is weighted at 50%. So for example, suppose your homework score is 150, you qualify for extra credit, and you have 40 points of extra credit. Your final homework score would then be:
final_hw_score = hw_score + (0.5 * extra_credit)
==
final_hw_score = 150 + (0.5 * 40) = 170
So in this example you got 103% on the homework component. Congrats.
Collaboration on homework assignments is strongly encouraged. If you work together or find a web site with code that you learn from, you must indicate the relevant people and web sites in the source code you submit. Further, if you do work with other people, or find code on other web sites, you must type all the code yourself. Obviously we can't police copy/paste, so please realize this is for your own good. You won't learn anything with Control-V.
Homework assignment descriptions and file downloads will appear in the course GitHub repository over time. I will try to make them available far in advance so you can work ahead if you like.
There are three tests. Two will happen during normal lecture periods, and the final is held whenever the university scheduled it. (I'll find out when this is.) The first two tests will cover material covered just before it; the final will be comprehensive.
Tests are not collaborative. The Eye of Sauron will be watching. So will I. Do not cheat.
Tests have the following point values:
- Test 1: 40 points
- Test 2: 50 points
- Final: 75 points
Specific information about tests will appear in the course GitHub repository about a week before they happen.
There is no required book for this course. There are a number of high-quality introductory texts available online. Learning to program is best done by writing lots and lots of code, and the fundamental ideas in computer science are well-documented far and wide. If one source is confusing to you, try a different one. But above all, write code. Sometimes, a description of some concept is confusing until you try implementing it in code.
We will primarily use the C++ version of book linked below by Clifford A. Shaffer. There are two versions of this book that differ only slightly---one is for C++, the other for Java. You are required to turn in assignments in C++, but extra credit may be earned by submitting in Java or Python.
The books below are freely available on the web, but in some cases you can give the author money if you want a nicer version.
Data Structures and Algorithm Analysis by Clifford A. Shaffer
:: http://people.cs.vt.edu/~shaffer/Book/
C++ Language Tutorial
:: http://www.cplusplus.com/doc/tutorial/
Learn C The Hard Way
:: http://c.learncodethehardway.org/
Learn Python the Hard Way
:: http://learnpythonthehardway.org/
Here are the general topics we will cover in CS 2270:
-
Course overview
-
Desired outcomes:
- Write standard datastructs/algos (DS&A)
- Understand when DS&A are appropriate
- Recognize/create test data for well known DS&A
-
Document code:
- pre/post conditions
- function contracts
- class invariants
-
Foundational concepts:
- pointers
- recursion
- linked lists
- binary search (trees)
-
Sorting algorithms:
- Mergesort
- Quicksort
- Heapsort
-
Algorithm efficiency:
- log, linear, quadratic
- identify algorithm big-O
-
Classes (design/write/test)
- List-based collections
- Stacks
- Queues (priority and otherwise)
- Binary Search Trees
- Balanced Search Trees
-
The Art of Defensive Programming
- Two programming activities: debugging, or bugging
- Top-down design
- Programming with pencils
- Collaboration
- Find and fix bugs
- Good programming style
- Testing strategies (unit tests, interactive tests)
-
Optional Advanced Topics:
- Inheritance
- Graphs
- Finite State Machines
If you qualify for accommodations because of a disability, please submit to me a letter from Disability Services in a timely manner so that your needs may be addressed. Disability Services determines accommodations based on documented disabilities. Contact: 303-492-8671, Willard 322, and http://www.Colorado.EDU/disabilityservices.
Disability Services' letters for students with disabilities indicate legally mandated reasonable accommodations. The syllabus statements and answers to Frequently Asked Questions can be found at http://www.colorado.edu/disabilityservices.
Campus policy regarding religious observances requires that faculty make every effort to reasonably and fairly deal with all students who, because of religious obligations, have conflicts with scheduled exams, assignments or required attendance. In this class, {{insert your procedures here}} See full details at http://www.colorado.edu/policies/fac_relig.html
Students and faculty each have responsibility for maintaining an appropriate learning environment. Those who fail to adhere to such behavioral standards may be subject to discipline. Professional courtesy and sensitivity are especially important with respect to individuals and topics dealing with differences of race, culture, religion, politics, sexual orientation, gender variance, and nationalities. Class rosters are provided to the instructor with the student's legal name. I will gladly honor your request to address you by an alternate name or gender pronoun. Please advise me of this preference early in the semester so that I may make appropriate changes to my records. See polices at http://www.colorado.edu/policies/classbehavior.html and at http://www.colorado.edu/studentaffairs/judicialaffairs/code.html#student_code.
All students of the University of Colorado at Boulder are responsible for knowing and adhering to the academic integrity policy of this institution. Violations of this policy may include: cheating, plagiarism, aid of academic dishonesty, fabrication, lying, bribery, and threatening behavior. All incidents of academic misconduct shall be reported to the Honor Code Council (honor@colorado.edu; 303-725-2273). Students who are found to be in violation of the academic integrity policy will be subject to both academic sanctions from the faculty member and non-academic sanctions (including but not limited to university probation, suspension, or expulsion). Other information on the Honor Code can be found at http://www.colorado.edu/policies/honor.html and at http://www.colorado.edu/academics/honorcode/.
The University of Colorado at Boulder policy on Discrimination and Harassment http://www.colorado.edu/policies/discrimination.html, the University of Colorado policy on Sexual Harassment and the University of Colorado policy on Amorous Relationships applies to all students, staff and faculty. Any student, staff or faculty member who believes s/he has been the subject of discrimination or harassment based upon race, color, national origin, sex, age, disability, religion, sexual orientation, or veteran status should contact the Office of Discrimination and Harassment (ODH) at 303-492-2127 or the Office of Judicial Affairs at 303-492-5550. Information about the ODH and the campus resources available to assist individuals regarding discrimination or harassment can be obtained at http://www.colorado.edu/odh
Test