Math 273: Introduction to Data Structures and Algorithms (27970)
Instructor: Regis Smith
Èmāiĺ: smithr ăŧ elac dőt edu
Office: G5-111W (323) 265-8887
Office Hours: Monday/Wednesday 12:30-1:35, Tuesday 4:10-6:00, Wednesday 4:25-6:00, and by appointment
Programming Site: Moodle Virtual Programming Lab
Textbook 1: Data Structures and Algorithm Analysis by Clifford A. Shaffer
Textbook 2: Open Data Structures by Pat Morin
Recommended: Introduction to Algorithms, by Cormen, Leiserson, Rivest, & Stein (great content, easy exercises)
Recommended: The C++ Programming Language, by Bjarne Stroustrup
Prerequisite: Math 173
This course is an introduction to data structures and algorithm analysis as well as a continuation of Math 173 (Object Oriented Programming). You should be familiar with object oriented programming in C++ (classes, basic inheritance, and polymorphism) as well as second semester calculus. We will use the SFML library for graphical programming. Topics: Review of classes, inheritance, and dynamic memory allocation in C++. Templates, containers, and generic programming in C++. Recursion, algorithm analysis including running times, efficiency, and big O notation. Standard data structures, including linked lists, stacks, queues, deques, trees, heaps, and treaps. Standard sorting and searching algorithms. Graphs, and more!
Assignments and Grading
You are required to complete six programming projects, including a final project which includes most concepts discussed in class. In addition, there are lab assignments and quizzes given every class meeting, written homework, two term exams, and a final exam. You must complete exams without the aid of a calculator or computer; however, accommodations will be made if you have a documented disability which prevents this (see below). Your final grade is a weighted average of the following.
- Programming Projects (30%)
- Lab Assignments, Homework, and Quizzes (15%)
- Two Term Exams (30%)
- Final Exam (25%)
Final averages are rounded to the nearest tenth of a percent and assigned letter grades in the standard way: 90.0%+ A, 80.0%–89.9% B, 70.0%–79.9% C, 60.0%–69.9% D, 0.0–59.9% F.
Students with Disabilities
Students with disabilities who need reasonable accommodation should provide verification of their disability to Disabled Student Program and Services (DSP&S), which is located in E1-106. Appointments can be made by calling (323) 265-8787. A letter from DSP&S outlining accommodations should be given to the instructor. If a student with a disability feels that accommodations offered are inappropriate or insufficient, (s)he should seek the assistance of the DSP&S Coordinator and/or the Vice President of Student Services.
- You may not use goto in any C++ program submitted for grading. If you use goto in a program, your grade on that program is 0. (However, using goto in pseudocode or algorithm specifications is OK.)
- You may never use (in C++ code) variable names which begin or end in an underscore.
- You may not use library functions (unmentioned in class) which greatly simplify your work. For example, if I ask you to implement a list, I hope you agree it would be silly to use C++’s std::list. In general, use only C++ commands and functions discussed in class.
- You may not cheat on any assignment or exam. Cheating includes copying code in whole or in part. If you cheat on an assignment, your grade is 0 and you may be suspended from class for two days.
You are required to attend all lectures and labs. Absences are excused only if documentation is provided and verified by the instructor. If you have an excused absence, it is your responsibility to arrange a time to make up missed work. Late work is never accepted without a legitimate excuse.
After completing this course you should be able to
- design and implement algorithms in pseudocode and/or C++,
- analyze the running time of algorithms and estimate their memory usage,
- design and implement standard data structures, including linked lists, stacks, queues, trees, and heaps,
- design, implement, and analyze running times of standard sorting algorithms, including quick sort, merge sort, and heap sort,
- use appropriate data structures and algorithms in designing and writing complex computer programs in C++.
The official CLOs for this course are
- Use the stack memory structure to write a program involving recursion.
- Design and create a program using indirect recursion to model a process with dependent rules.
- Apply the stack memory structure.