▲
CSCI 2270-100: Data Structures
Logistics
- Instructor: Ashutosh Trivedi (ashutosh \dot trivedi \at colorado \dot edu)
- Teaching Assistants (Recitations) :
- Bhimani, Prashil Vipul (prashil \dot bhimani \at colorado \dot edu)
- Lee, Yu-Ju (yuju \dot lee \at colorado \dot edu)
- Gayam, Prathyusha (prathyusha \dot gayam \at colorado \dot edu)
- Chatterjee, Avimita (amivita \dot chatterjee \at colorado \dot edu)
- Course description :
- Lectures 3 times a week (MWF)
- Weekly 75-minute recitation sections with course TAs
- Problem sets assigned weekly, due the following week
- Online lecture quizzes at the end of every week
- Two midterm exams
- One final project
- This will be a challenging course, please plan accordingly
- Pre-requisites:
- CSCI 1300 or CSCI 1310 or CSCI 1320 or ECEN 1030 or ECEN 1310 and APPM 1345 or APPM 1350 or MATH 1300 or MATH 1310 (all minimum grade C-).
- Class Meeting Times: Monday-Wednesday-Friday (10:00am—11:50am)
- Office hours:
- Ashutosh Trivedi (Monday 12:30pm—2:00pm and Friday 12:30am—1:30pm).
- TAs (TBA).
- Venue :
- Class meeting location: VAC 1B20
- Office Hour location: ECCE 1B11
Relevant Textbooks
- Course materials, such as lecture notes, assignments, and quizzes will be made available in electronic form on the Moodle site for the course. Your identikey is needed for signing in.
- The textbook for this course is an ebook (Hoenigman, R. 2015. Visualizing Data Structures. Lulu Press.), which will be distributed on the course Moodle site.
Course Outcomes
In this course, students will:- Document code including precondition/postcondition contracts for functions and invariants for classes.
- Create and recognize appropriate test data for simple problems, including testing boundary conditions and creating/running test cases.
- Design and test new classes using the principle of information hiding for the following data structures: array-based collections (including dynamic arrays), list-based collections (singly-linked lists, doubly-linked lists, circular-linked lists), stacks, queues, binary search trees, hash tables, graphs, and at least one balanced search tree.
- Identify features and applications of common data structures, including records/structs, lists, stacks, queues, trees, graphs, and maps.
- Implement algorithms for standard operations on common data structures and discuss the complexity of the operations.
- Comment on the features of different traversal methods for trees and graphs, including pre-, post-, and in-order traversal of trees.
- Describe the implementation of hash tables, including algorithms for collision avoidance and resolution.
- Describe the principles of recursion and iteration, and implement recursive and iterative solutions for a problem.
- Formulate and implement solutions to problems using fundamental graph algorithms, including depth-first and breadth-first search and a shortest-path algorithm.
- Explain the features of at least one tree balancing algorithm and how tree balancing affects the efficiency of various binary search tree operations.
- Correctly use and manipulate pointer variables to change variables and build dynamic data structures.
- Explain the differences between dynamic and static data structure implementations, and justify the use of static and dynamic implementations in different applications.
- Practice explaining design choices and algorithm features in small-group settings.
Grading
|
Tentative Course Calendar
# | Date | Description | Chapter |
1 | Week 1 — January 14 | Introduction to CSCI 2270 — Data Structures | N/A |
2 | Week 1 — January 16 | C++ Review, Arrays, Structs, File I/O | VDS Chapter 1 and C++ |
3 | Week 1 — January 18 | C++ Review, Arrays, Structs, File I/O | VDS Chapter 1 and C++ |
— | Week 2 — January 21 | No Class — Martin Luther King Jr. Day 2019. | |
4 | Week 2 — January 23 | Algorithms and pseudocode, Pointers, Dynamic memory | VDS Chapters 2 and 3 |
5 | Week 2 — January 25 | Algorithms and pseudocode, Pointers, Dynamic memory | VDS Chapters 2 and 3 |
6 | Week 3 — January 28 | C++ Classes and Objects introduction, Linked Lists | VDS Chapter 5 |
7 | Week 3 — January 30 | C++ Classes and Objects introduction, Linked Lists | VDS Chapter 5 |
8 | Week 3 — February 1 | C++ Classes and Objects introduction, Linked Lists | VDS Chapter 5 |
9 | Week 4 — February 4 | Stacks and Queues | VDS Chapters 6 and 7 |
10 | Week 4 — February 6 | Stacks and Queues | VDS Chapters 6 and 7 |
11 | Week 4 — February 8 | Stacks and Queues | VDS Chapters 6 and 7 |
12 | Week 5 — February 11 | Trees, Binary Trees | VDS Chapter 8 |
13 | Week 5 — February 13 | Trees, Binary Trees | VDS Chapter 8 |
14 | Week 5 — February 15 | Trees, Binary Trees | VDS Chapter 8 |
15 | Week 6 — February 18 | Binary Search Trees and Revision | Chapter 9 and Revision |
16 | Week 6 — February 20 | Binary Search Trees and Revision | Chapter 9 and Revision |
17 | Week 6 — February 22 | Midterm 1 Exam. | |
18 | Week 7 — February 25 | Tree Traversal Algorithms and Tree Balancing | Chapter 10 and 11 |
19 | Week 7 — February 27 | Tree Traversal Algorithms and Tree Balancing | Chapter 10 and 11 |
20 | Week 7 — March 1 | Tree Traversal Algorithms and Tree Balancing | Chapter 10 and 11 |
21 | Week 8 — March 4 | Hash Tables | Chapter 13 |
22 | Week 8 — March 6 | Hash Tables | Chapter 13 |
23 | Week 8 — March 8 | Hash Tables | Chapter 13 |
24 | Week 9 — March 11 | Heaps | |
25 | Week 9 — March 13 | Heaps | |
26 | Week 9 — March 15 | Heaps | |
27 | Week 10 — March 18 | Graphs, breadth-first search, depth-first search | Chapter 12 |
28 | Week 10 — March 20 | Graphs, breadth-first search, depth-first search | Chapter 12 |
29 | Week 10 — March 22 | Graphs, breadth-first search, depth-first search | Chapter 12 |
30 | Week 11 — March 25-31 | No Class — Spring Break | |
31 | Week 12 — April 1 | Graphs, Adjacency Matrix, Adjacency List | |
32 | Week 12 — April 3 | Graphs, Adjacency Matrix, Adjacency List | |
33 | Week 12 — April 5 | Graphs, Adjacency Matrix, Adjacency List | |
34 | Week 13 — April 8 | Revision | |
35 | Week 13 — April 10 | Revision | |
36 | Week 13 — April 12 | Midterm 2 Exam. | |
37 | Week 14 — April 15 | Project Discussion and Special topics | |
38 | Week 14 — April 17 | Special topics | |
39 | Week 14 — April 19 | Special topics | |
40 | Week 15 — April 22 | Special topics | |
41 | Week 15 — April 24 | Special topics | |
42 | Week 15 — April 26 | Special topics | |
43 | Week 16 — April 29 | Special topics | |
44 | Week 16 — May 1 | Special topics | |
45 | Week 16 — May 3 | Special topics |
Notes
- Accommodation Statement. If you qualify for accommodations because of a disability, please submit to me a letter from Disability Services in a timely manner (for exam accommodations provide your letter at least one week prior to the exam) so that your needs can be addressed. Disability Services determines accommodations based on documented disabilities. Contact Disability Services at 303-492-8671 or by e-mail at dsinfo [AT] colorado.edu. If you have a temporary medical condition or injury, see Temporary Injuries under Quick Links at the Disability Services website and discuss your needs with me.
- Religious Observances. Campus policy regarding religious observances requires that faculty make every effort to deal reasonably and fairly with all students who, because of religious obligations, have conflicts with scheduled exams, assignments or required attendance. In this class, you should notify your instructor of any conflict at least two weeks in advance. See full details here .
-
Classroom Behavior.
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, color, culture, religion, creed, politics, veteran's status, sexual
orientation, gender, gender identity and gender expression, age, disability, 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. For more information, see the
policies
on
classroom behavior and
the
student code.
It is my expectation that each of you will be respectful to your fellow
classmates and instructors at all times.
In order to create a professional atmosphere within the classroom,
you are expected to:
- Arrive to class on time.
- Turn off your cell phone (talk and text).
- Bring your laptop to class—if you have one— to participate in classroom activities. Please restrict laptop use to these activities only, no email, Facebook, Youtube, etc.
- Put away newspapers and magazines.
- Refrain from having disruptive conversations during class.
- Remain for the whole class; if you must leave early, do so without disrupting others.
- Display professional courtesy and respect in all interactions related to
this class
Compliance with these expectations will assist all of us in creating a
learning community and a high
quality educational experience.
Though many of the above stated policies address academic climate within the
classroom, these policies
should also be upheld outside of the classroom. As a member of the CU
community you are expected to
consistently demonstrate integrity and honor through your everyday
actions. Faculty, TAs, and staff
members are very willing to assist with your academic and personal
needs. However, multiple
professional obligations make it necessary for us to schedule our
availability. Suggestions specific to
interactions with faculty and staff include:
- Respect posted office hours. Plan your weekly schedule to align with scheduled office hours.
- Avoid disrupting ongoing meetings within faculty and staff offices. Please wait until the meeting concludes before seeking assistance. Respect faculty and staff policies regarding use of email and note that staff and faculty are not expected to respond to email outside of business hours. Send email messages to faculty and staff using a professional format. Tips for a professional email include:
- Always fill in the subject line with a topic that indicates the reason for your email to your reader.
- Respectfully address the individual to whom you are sending the email (e.g., Dear Professor Smith).
- Avoid email or text message abbreviations.
- Be brief and polite.
- Add a signature block with appropriate contact information.
- Reply to email messages with the previously sent message. This will allow your reader to quickly recall the questions and previous conversation.
- Discrimination and Harassment. The University of Colorado Boulder (CU Boulder) is committed to maintaining a positive learning, working, and living environment. CU Boulder will not tolerate acts of sexual misconduct, discrimination, harassment or related retaliation against or by any employee or student. CU's Sexual Misconduct Policy prohibits sexual assault, sexual exploitation, sexual harassment, intimate partner abuse (dating or domestic violence), stalking or related retaliation. CU Boulder's Discrimination and Harassment Policy prohibits discrimination, harassment or related retaliation based on race, color, national origin, sex, pregnancy, age, disability, creed, religion, sexual orientation, gender identity, gender expression, veteran status, political affiliation or political philosophy. Individuals who believe they have been subject to misconduct under either policy should contact the Office of Institutional Equity and Compliance (OIEC) at 303-492-2127. Information about the OIEC, the above referenced policies, and the campus resources available to assist individuals regarding sexual misconduct, discrimination, harassment or related retaliation can be found at the OIEC website.
- Submitting Work Late. Late work is not accepted in CSCI 2270. In the event of a documented personal, family, or medical emergency, consult your TA about receiving a penalty free extension. If you know you will be missing a weekly recitation, go to a recitation with the same TA being held at a different time. Recitation assignments are due by the end of recitation. Your lowest recitation grade will be dropped.
- Attendance. Attendance at all class meetings and recitations is required. You are responsible for knowing the material presented during class and recitation, even if you were not in attendance when the material was presented.
- Honor Code. All students enrolled in a University of Colorado Boulder course are responsible for knowing and adhering to the academic integrity policy of the institution. Violations of the policy may include: plagiarism, cheating, fabrication, lying, bribery, threat, unauthorized access, clicker fraud, resubmission, and aiding academic dishonesty. All incidents of academic misconduct will be reported to the Honor Code Council (honor@colorado.edu; 303-735-2273). Students who are found responsible for violating the academic integrity policy will be subject to nonacademic sanctions from the Honor Code Council as well as academic sanctions from the faculty member. Additional information regarding the academic integrity policy can be found at honorcode.colorado.edu.
- Collaboration Policy.
The Computer Science Department at the University of Colorado at Boulder
encourages collaboration among students. Students are most successful when
they are working with other students to understand new concepts. The
ultimate goal is that you fully understand the code you develop and be able
to collaborate with others in a mutually beneficial way.
To support students in collaboration, the Department has created a
Collaboration Policy that makes explicit when their collaborative behavior
is within the bounds of collaboration and when it is actually
academic dishonesty, and therefore a violation of the University of Colorado
at Boulder's Honor Code.
Unless otherwise specified, you may make reasonable use of outside resources
(the Internet, other books, people), but then you must give credit by citing
your sources in the comments inside your code.
Reasonable use of outside resources does NOT include downloading complete,
or almost complete, solutions to an assignment, or acquiring a complete, or
almost complete, solution from any source,
whether you cite the source of the solution or not. This is considered
plagiarism and violates the University's Honor Code policy.
Examples of citing sources include:
- // Modified version from https://github.com/Phhere/MOSS-PHP
- // Adapted from Program #7.2 in book "Accelerated C++" by B. Stroustrup
- // Worked with Joe Smith from class to come up with algorithm for sorting
- // Received suggestions from StackExchange website (see http://...)
Examples of violating the Collaboration Policy- Sharing a file with someone else.
- Submitting a file that someone else shared with you.
- Stealing a copy of someone else's work and submitting as your own (even with modification).
- Copying or using outside resources to solve a component of a larger problem and not citing your sources.
- Copying or using an entire solution that you did not generate, regardless of whether you cited your sources.
- Downloading a solution from the Internet and modifying it to make it look like your own work.
Examples of collaborating correctly:- Asking another student for a helpful suggestion.
- Reviewing another student's code for issues/bugs/errors.
- Working together on the whiteboard (or paper) to figure out how to approach and solve the problem. In this case you must include that person's name in your collaboration list at the top of your submission.
Other information on the Honor Code can be found at www.colorado.edu/policies/honor.html and www.colorado.edu/academics/honorcode. Collaboration boundaries are hard to define crisply and may differ from class to class. If you are in any doubt about where they lie for a particular course, it is your responsibility to ask the course instructor.