Intermediate building blocks for solving problems using computers. Topics include data structures, object-oriented design and development, algorithms for manipulating these data structures and their runtime analyses. Data structures introduced include stacks, queues, lists, trees, and sets. 4 units.
Computer Science 16 (CMPSC 16) or Engineering 3 (ENGR 3); Matematics 3B (MATH 3B). Course counts as legal repeat of Computer Science 12 (CMPSC 12). Not open for credit to students who have completed Computer Science 12 (CMPSC 12) or Computer Science 20 (CMPSC 20).
In this course, you will:
By the end of this course, you will have:
- Learn how to design and implement programs using object-based programming techniques, particularly techniques for data abstraction and encapsulation
- Specify, implement, and apply basic data structures, such as lists, stacks, and queues
- Understand the concepts of runtime and complexity analysis and correctly analyze the runtime complexity of code samples
- Learn to distinguish algorithms and data structures based on efficiency
In terms of your learning, this course will
- Understood how to apply the new programming concepts learned in class to design efficient code that solves or suits particular problems. This skill will be assessed through the class project.
- Enable you to become a better programmer, where programming is a tool at your disposal.
Lara Deek: TR 1-2PM HFH 2152A
David Adams: T 12:30-2:00PM, W 9:30-11:00am CSIL
A Practical Introduction to Data Structures and Algorithms (C++ Version)
Class attendance in Lectures and Discussions is mandatory: you are responsible for everything that goes on in class. Prepare in advance for class by reading and studying the assigned text, and by making sure you understand the previous lecture.
Weekly lab sessions, led by the TA, will focus on solving and submitting the Lab Assignments. It is required that students attend these labs; you are responsible for the material presented in these labs. In the case where a student is unable to attend, contact the instructor beforehand and prepare to complete the assignment prior to the beginning of the lab. We ask of absent students to do so to be able to address their questions remotely.
Grades will be based on Lab Assignments, Homeworks, Midterm Exam, Project, and the Final Exam.
- Lab assignments: 12.5%
- Project: 35%
- Homeworks: 12.5%
- Midterm: 15%
- Final: 25%
- In-class pop quizzes: 5%-10% (extra credit)
Unless otherwise instructed, homeworks must be submitted by 11:59pm on the due date, and lab assignments by the end of the lab session. Late assignments will loose 10% of credit for every hour they are late.
For your class project, you will work with a partner (more details in the first lecture). Collaboration, code sharing with people other than your partner is not allowed.
There will be NO makeup exam.
Please read this section carefully. The university, the department, and this instructor all take the issue of academic integrity very seriously. A university requires an atmosphere of mutual trust and respect. While collaboration is an integral part of many scholarly activities, it is not always appropriate in a course, and it is never appropriate unless due credit is given to all participants in the collaboration. This goes for both ideas and programming or other work.
For some views on academic integrity at UCSB see:
Summary: Academic integrity is absolutely required - dishonesty (cheating, plagiarism, etc.) benefits no one and hurts everyone. If you are not sure whether or not something is appropriate, please ask the instructor or TA.
If you are a student with a disability and would like to discuss special academic accommodations, please contact the instructor. In addition, students with temporary or permanent disabilities are referred to the Disabled Students Program (DSP) at UCSB. DSP will arrange for special services when appropriate (e.g., facilitation of access, note takers, readers, sign language interpreters). Please note that it is the student's responsibility to communicate his or her special needs to the instructor, along with a letter of verification from DSP.
Lecture slides will be linked after the lecture.
Date Topic Related Reading T: 6/26/2012 Software Development Process R: 6/28/2012 C to C++: Programming Language Transition; Abstract Data Types and Classes T: 7/3/2012 Inheritance R: 7/5/2012 Pointer Review and ADT List Chapter 3 T: 7/10/2012 Linked Lists Chapter 4.1 R: 7/12/2012 Exceptions and Linked Lists Chapter 3 T: 7/17/2012 Sorted Linked Lists Chapter 4 R: 7/19/2012 Sorting Algorithms Chapter 7 T: 7/24/2012 Algorithm Running Time Analysis: Complexity Chapter 3 R: 7/26/2012 MIDTERM EXAMINATION T: 7/31/2012 Midterm Answers R: 8/2/2012 Stacks and Queues Chapter 4.3, 4.4 T: 8/7/2012 Stacks and Queues Chapter 4.3, 4.4 R: 8/9/2012 Stack and Queue Algorithm Chapter 4.3, 4.4 T: 8/14/2012 Recursion Chapter 2.4 R: 8/16/2012 Binary Search Tree Chapter 5.4 T: 8/21/2012 Binary Search Tree, Templates, and STL Chapter 5.4 R: 8/23/2012 Advanced Data Structures: Sets and Graphs Chapter 11 T: 8/28/2012 Advanced Data Structures: Heaps Chapter 5.5 R: 8/30/2012 FINAL EXAMINATION