MCS 360 Introduction to Data Structures

Course Description

Pointers and dynamic memory allocation in C/C++, recursion, stacks, queues, heaps, binary and multiway trees, graphs, hash tables. Sorting and searching algorithms.

Course Prerequisites

Grade of C or better in MCS 260 and Grade of C or better in MCS 275.

Class Schedule Information

To be properly registered, students must enroll in one Discussion/Recitation and one Lecture.

Course Content

Week 1:
C++ Primer; Primitive Data Types, Operators, Control Statements, and Functions in C++; Arrays, Objects, Pointers, and References;

Week 2:
Martin Luther King Jr. Day (Monday). No classes. Working with Variable Addresses and Pointer Variables; Strings, Iterators, and Vectors;

Week 3:
File Input and Output in C++; Abstract Data Type (ADT) with struct and class; Object-Oriented Programming, Classes and Operator Overloading;

Week 4:
Object-Oriented Programming, Class Inheritance, and Polymorphisms; C++ Templates; Non-Recursive Sorting Algorithms;

Week 5:
Algorithm Analysis and Code Efficiency; Exam 1 review; Exam 1

Week 6:
Singly connected linked list, Part 1; Singly connected linked list, Part 2; Doubly linked list;

Week 7:
The stack data structure; Applications of the stack data structure; The queue data structure;

Week 8:
The deque data structure; Recursion; Working with recursion: recursive merge sort;

Week 9:
Working with recursion: recursive quick sort; Working with recursion: binary search; Binary trees and operations on binary trees;

Week 10:
Binary search tree: recursive construction and traversal; Exam 2 review; Exam 2;

Week 11:
Spring vacation. No classes.

Week 12:
Binary search tree: additional operations, functions and their recursive implementations; The heap data structure; The heapsort;

Week 13:
Huffman tree and Huffman code; The associative containers set and map; Hash tables;

Week 14:
Self-balancing search trees;

Week 15:
Graphs;

Week 16:
Advanced C++ topics; Semester review;