Fall 2017 — CRN 82739 — MWF 2:30-3:20 in WLH 320
| Instructor: | Chris Wyatt |
| Office: 439 Whittemore Hall | |
| Phone: 231-6658 | |
| Email: clwyatt@vt.edu | |
| Office Hours: Tues 10-11, Thurs 2-4. Other times by appointment. | |
| Class Links: | Canvas, where communication about grading occurs, assignments are collected, grades are posted, and warmups taken. |
| Piazza, where online communication occurs, ask a question! | |
| Software Engineering Lab (SWEL) | |
| The autograder, where you can check your code prior to submission. |
This course is the second in the software sequence for the CPE degree and a technical elective for the EE degree. The main goals of the course are to introduce you to the selection, implementation, and use of common data structures and algorithms. A secondary goal of the course is to improve your overall programming skills, particularly in software design and testing.
Specifically, having successfully completed this course, you should be able to:
design algorithms for solving problems that use data structures such as arrays, linked lists, stacks, queues, graphs, and trees, and algorithms such as those that are used for list manipulation, graph manipulation (e.g., depth-first search), sorting, searching, and tree traversals
implement algorithms in C++ using good programming style.
The course revolves around the concept of abstract data types (ADTs) and their implementation in C++ using data structures, and algorithms. Analysis of algorithms is used to characterize algorithms by the resources required to execute them.
This is the schedule for the semester, updated continually. It is important that you keep up with readings and assignments. The acronym CH in the Notes column refers to the Carrano and Henry text, 6th edition. The 5th and 7th editions are sufficiently close that they can be used as well.
| Meeting | Topic | Notes |
|---|---|---|
| 1 (Mo 8/28) | Course Introduction |
Reading: CH 1.1-1.4 P0 Released |
| 2 (We 8/30) | ADT Bag | Reading: CH 1.5 , Appendix A and B |
| 3 (Fr 9/1) | Class Design and Testing | Reading: CH pp. 31-37 |
| 4 (We 9/6) | Basic Polymorphism | Reading: CH pp. 37-46 |
| 5 (Fr 9/8) | Recursion Part I | Reading: CH pp. 48-66 |
| 6 (Mo 9/11) | Recursion Part II | Reading: CH pp. 67-87 |
| 7 (We 9/13) | Array-Based Implementations |
Reading: CH pp. 95-111 P1 Released |
| 8 (Fr 9/15) | Memory Management | Reading: CH pp. 117-132 |
| 9 (Mo 9/18) | Link-Based Implementations | Reading: CH pp. 133-148 |
| 10 (We 9/20) | Link-Based Performance | Reading: CH pp. 150-154 |
| 11 (Fri 9/22) | Applications of Recursion I | Reading: CH pp. 159-171 |
| 12 (Mo 9/25) | Applications of Recursion II | Reading: CH pp. 172-186 |
| 13 (We 9/27) | Stack ADT | Reading: CH Chapter 6 |
| 14 (Fri 9/29) | Stack Implementations |
Reading: CH chapter 7 P2 Released |
| 15 (Mo 10/2) | Exceptions and Alternatives | Reading: CH pp. 227-239 |
| 16 (We 10/4) | List ADT | Reading: CH chapter 8 |
| 17 (Fr 10/6) | List: Array Implementations | Reading: CH pp. 265-271 |
| 18 (Mo 10/9) | List: Linked-List Implementations | Reading: CH pp. 272-286 |
| 19 (We 10/11) | Analysis of Algorithms |
Reading: CH pp. 289-295, Appendix E (6th Edition) CH pp. 308-316,, Appendix E (7th Edition) |
| 20 (Mo 10/16) | O-Notation |
Reading: CH pp. 294-301 P3 Released |
| 21 (We 10/18) | Basic sorting algorithms | Reading: CH pp. 305-327 |
| 22 (Fr 10/20) | MIDTERM | |
| 23 (Mo 10/23) | Inheritance | Reading: CH pp. 333-346 |
| 24 (We 10/25) | Sorted List ADT | Reading: CH pp. 347-351 |
| 25 (Fr 10/27) | Sorted Linked-Lists | Reading: CH pp. 352-357 |
| 26 (Mo 10/30) | Queue ADT | Reading: CH pp. 373-378 and Chapter 14 |
| 27 (We 11/1) | Priority Queue ADT |
Reading: CH pp. 379-388 P4 Released |
| 28 (Fr 11/3) | Deque Implementations | Reading: (none) |
| 29 (Mo 11/6) | Operator Overloading | Reading: CH pp. 415-421 |
| 30 (We 11/8) | General and Binary Trees | Reading: CH pp. 425-441 |
| 31 (Fr 11/10) | Binary Search Tree ADT | Reading: CH pp. 442-449 |
| 32 (Mo 11/13) | Array-Based Trees and Heaps | Reading: CH pp. 455-458, chapter 17 |
| 33 (We 11/15) | Link-Based Binary Trees | Reading: CH pp. 459-482 |
| 34 (Fr 11/17) | Dictionary ADT | Reading: CH pp. 525-543 |
| 35 (Mo 11/27) | Balancing Trees: Treaps |
Reading: Wikipedia entry on Treaps P5 Released |
| 36 (We 11/29) | Hash Tables | Reading: CH pp. 544-563 |
| 37 (Fr 12/1) | Balancing Trees: Red-Black Trees | Reading: CH pp. 567- 591 and pp. 592-598 |
| 38 (Mo 12/4) | Graphs | Reading: CH pp. 603-614 |
| 39 (We 12/6) | Graph Traversals and Algorithms | Reading: CH pp. 614-630 |
| 40 (Fr 12/8) | STL Containers and Algorithms | Reading: CH pp. 671-684 |
| 41 (Mo 12/11) | Review | |
| 42 (We 12/13) | Review |
ECE 1574 Object-Oriented Engineering Problem Solving With C++. You are expected to be competent in the basics of programming in C++.
The following is strongly recommended, but not required: Carrano and Henry, Data Abstraction and Problem Solving with C++: Walls and Mirrors, 6th ed. (previous editions can be used with some caveats) , Addison-Wesley (ISBN 9780132923729).
Additional References:
Additional Resources
A modern C++ compiler with sufficient C++11 support is required (see below). Only ANSI/ISO C++ will be accepted, no compiler extensions or libraries may be used, unless otherwise directed. We will use the open source CMake application for managing the build process (www.cmake.org).
Recommended Compilers:
Development Environments
For development you can use your favorite editor and a command console to invoke the compiler toolchain (this is generally how I will demonstrate things in class), or you can use any integrated development environment (IDE) supported by CMake, including Visual Studio on Windows and XCode on the Mac. There are several other options including Visual Studio Code, QT Creator, and CLion. Use whatever works best for you but note the auto-grader is the final arbiter of working code.
Further information about the software development environment for this course, including installation instructions, is here.
The grades will be computed as follows:
| Warmups: | 5% (Extra Credit) |
| Exercises: | 10% |
| Projects: | 60% |
| Midterm: | 10% |
| Final: | 20% |
Most assignments will require programming in C++. All problem sets must be turned in by the time/date indicated on the assignment. No late work will be accepted, with the following exception: for projects (only) you get 5 free late days (24 hour periods including weekends) during the semester to accommodate emergencies. If you want to use one or more of these just turn it in via Canvas as normal after the due date. Once your late days are used up no more late work will be accepted without an official accomodation from the Dean of Students.
Assignments include completion of weekly warm-up questions prior to class. The purpose of these assignments is to make the most efficient use of class time. Your responses to the warm-ups indicate to me what potion of the material is already clear to you and what aspects need further development before we meet. Your participation in the warm-up exercises is important to the course. Warm-ups are graded based on a reasonable attempt at the answer and contribute 5 % of extra credit toward your grade. While your responses may be used in class to demonstrate correct reasoning and not-so-correct reasoning, no identifying information is used (I rely on a nickname of your choosing instead).
If you feel that an error has been made in grading any homework or examination, you must present a written appeal to the instructor (email is ok) within one week after the assignment or exam is returned to you. Verbal appeals are not considered prior to this step. Your appeal should be specific and factual.
The Undergraduate Honor Code pledge that each member of the university community agrees to abide by states:
“As a Hokie, I will conduct myself with honor and integrity at all times. I will not lie, cheat, or steal, nor will I accept the actions of those who do.”
Students enrolled in this course are responsible for abiding by the Honor Code. A student who has doubts about how the Honor Code applies to any assignment is responsible for obtaining specific guidance from the course instructor before submitting the assignment for evaluation. Ignorance of the rules does not exclude any member of the University community from the requirements and expectations of the Honor Code. For additional information about the Honor Code, please visit: www.honorsystem.vt.edu.
Adherence to Virginia Tech's honor code is expected in all phases of this course. All graded work, other than the in-class exercises, is expected to be the original work of the individual student. In working on the assignments, discussion and cooperative learning is encouraged. However, solutions are to be the work of the individual student. In all assignments you may discuss general concepts, such as algorithms, language syntax, Internet resources, or class and text topics, with others. However, copying of specific assignment program-code in the current or from previous semesters is an honor code violation. Any violations of the honor code will automatically be forwarded to the Office of the Honor System with the recommendation of an F* sanction as your final grade in the course. I do use a code comparison system.
Course Website: Students are expected to access class resources via the course website and through Canvas. This is the primary way assignments, examples, notes, and other information will be distributed. You should check the sites daily for updates or configure notifications appropriately.
Class Attendance and Classroom Conduct: Students are expected to attend class and contribute to the discussion. Distractions (e. g. arriving to class late or leaving early) are disrespectful to the entire class and will not be tolerated.
Email Communication: If you want to send email the instructor use clwyatt@vt.edu and use your VT email account as the sender to ensure it does not get filtered.
University Closings: In case of inclement weather you may call 231-6668 to find out if any University closings are scheduled. If the University is closed during the regular course hours any assignment due on that day will be due the next class meeting (including assignments turned in online).
Reasonable accommodations are available for students who have documentation of a disability from a qualified professional. Students should work through Services for Students with Disabilities (SSD) in Lavery Hall. Any student with accommodations through the SSD Office should contact me during the first two weeks of the semester.
If participation in some part of this class conflicts with your observation of specific religious holidays during the semester, please contact me during the first two weeks of class to make alternative arrangements.
If you miss class due to illness, especially in the case of an exam or some deadline, see a professional in Schiffert Health Center. If deemed appropriate, documentation of your illness will be sent to the Dean's Office for distribution to me. If you experience a personal or family emergency that necessitates missing class, contact the Dean of Students at 231-3787 or see them in 152 Henderson Hall.