CSCI 104 - Summer 2017 Data Structures and Object Oriented Design

Overview

The course covers the fundamentals of data structures and object-oriented programming. They are two sides of the same coin. As a programmer becomes more proficient, they realize that how well and efficiently a problem can be solved often depends on how the data are stored. Some of the ideas are quite sophisticated and clever, and we will explore a spectrum of them in this class, ranging from fairly basic to moderately advanced structures.

The other side is that once one realizes the importance of data structures, it is natural to think of programs not as sequences of instructions that pass around some data, but as data packets that come with the code needed to process them. This is at the heart of the object-oriented design paradigm, and often leads to more modular and extensible (and readable) programs. We will learn about the basics of object-oriented programming, along with many of the interesting things that can be naturally done within the paradigm.

The class will put significant emphasis on a theoretical understanding of data structures, their implementation, and the object-oriented viewpoint. Assignments will contain significant programming projects along with programming-free questions to explore how data structures work.

Learning Objectives

  1. Ability to choose appropriate and efficient data structures and algorithms to solve a problem.
  2. Ability to compare data structures and algorithms for efficiency using algorithm analysis and experiments.
  3. Ability to apply algorithm analysis and knowledge of discrete mathematics to evaluate algorithms and data structures.
  4. Ability to implement and use linear data structures, including stacks, queues, lists.
  5. Ability to implement and use search structures and algorithms including binary search, search trees, and hash tables.
  6. Ability to use and implement search data structures, including search trees and hash tables.
  7. Ability to use and implement priority queues.
  8. Knowledge of and ability to implement sorting algorithms and compare their performance analytically and empirically
  9. Understanding of graphs and their representations; ability to implement graph search using BFS, DFS, and Dijkstra's Algorithm.
  10. Ability to solve problems using pointers and dynamically managed memory.
  11. Ability to write recursive functions and understand when recursion is appropriate to a problem.
  12. Ability to design, document, and implement classes and object hierarchies.
  13. Ability to apply tools and techniques for program correctness, such as unit testing, use of a symbolic debugger, and assert statements.
  14. Ability to write readable and maintainable code.
  15. Ability to explain computational solutions in person and in writing.

Catalog Entry

Introduces the student to standard data structures (linear structures such as linked lists, (balanced) trees, priority queues, and hashtables), using the C++ programming language.

Prerequisites

Corequisites

Lecture / Labs

See Sections page.

Course Websites

Grading

See Assignments & Grading page.

Textbook

Data Abstraction & Problem Solving with C++, 6th Ed. Carrano & Henry, Pearson, 2013 (ISBN 978-0132923729)

The textbook is required. While the class will not always follow the order or presentation style of the textbook, the textbook is an excellent source for much of the material. Students can use older versions of the textbook if they so desire. In that case, it is the students' responsibility to ensure that they have access to all required material.

In addition to the textbook, you should download (and possibly print) the Lecture notes. These are based on teaching of CSCI 104 in past semesters, and cover the material quite accurately as presented in class. However, the lecture notes may be out of order as we have changed the schedule slightly. In addition, we will post Powerpoint slides the day before lecture. For Professor Redekopp's section, you are encouraged to print them and bring them to class with you. (Notice, however, that the lecture itself is intended as supplemental to the textbook, not a replacement.)

In addition to the textbook and lecture notes, we strongly recommend that each student have access to a quality book on the C++ programming language, such as the textbook used for CSCI 103.

Reading Assignments

Readings from the book, lecture notes and other sources form the base of your learning pyramid. These readings contain theoretical concepts, examples and usable code that will be very helpful for all the work in this course.

It is strongly recommended that students read the relevant chapters of the textbook before coming to class. Class will proceed at a brisk pace and often be more focused on providing extra intuition and discussions rather than rehashing the book content in great detail.

Statement on Academic Conduct and Support Systems

Academic Conduct

Below is USC's official language. For more detailed information, see also the Assignments & Grading page.

Plagiarism - passing off someone else's ideas as your own, either verbatim or recast in your own words - is a serious academic offense with serious consequences. Please familiarize yourself with the discussion of plagiarism in SCampus in Section 11, Behavior Violating University Standards https://scampus.usc.edu/1100-behavior-violating-university-standards-and-appropriate-sanctions/. Other forms of academic dishonesty are equally unacceptable. See additional information in SCampus and university policies on scientific misconduct, http://policy.usc.edu/scientific-misconduct/.

Discrimination, sexual assault, and harassment are not tolerated by the university. You are encouraged to report any incidents to the Office of Equity and Diversity http://equity.usc.edu/ or to the Department of Public Safety http://capsnet.usc.edu/department/department-public-safety/online-forms/contact-us. This is important for the safety of the whole USC community. Another member of the university community - such as a friend, classmate, advisor, or faculty member - can help initiate the report, or can initiate the report on behalf of another person. The Center for Women and Men http://www.usc.edu/student-affairs/cwm/ provides 24/7 confidential support, and the sexual assault resource center webpage sarc@usc.edu describes reporting options and other resources.

Support Systems

A number of USC's schools provide support for students who need help with scholarly writing. Check with your advisor or program staff to find out more. Students whose primary language is not English should check with the American Language Institute http://dornsife.usc.edu/ali, which sponsors courses and workshops specifically for international graduate students. The Office of Disability Services and Programs http://sait.usc.edu/academicsupport/centerprograms/dsp/home_index.html provides certification for students with disabilities and helps arrange the relevant accommodations. If an officially declared emergency makes travel to campus infeasible, USC Emergency Information http://emergency.usc.edu/ will provide safety and other updates, including ways in which instruction will be continued by means of blackboard, teleconferencing, and other technology.

Emergency Preparedness/Course Continuity in a Crisis

In case of a declared emergency if travel to campus is not feasible, USC executive leadership will announce an electronic way for instructors to teach students in their residence halls or homes using a combination of Blackboard, teleconferencing, and other technologies.