## Math 273: Introduction to Data Structures and Algorithms (27970)

#### Syllabus

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.

#### Forbidden Things

- 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.

#### Makeup Work

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.

#### Learning Outcomes

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.