Data structures and algorithms I

COSC 202 - Spring 2024

Instructor

Scott Emrich
Office: 608 Min Kao Hall
Phone: (865) 974-3891; E-mail: semrich at utk.edu
Office hours: TBD; and by appointment

Overview

This course is part one of our two course sequence that focuses on fundamental data structures and associated algorithms. During the semester we will cover basic data structures with a focus on the Standard Template Library (vectors, deques, lists, sets, and maps), basic memory management, queues, stacks, hash tables, binary search trees, binary heaps, recursion, and introductions to both generics (templates) and algorithm analysis. For these topics students are expected to design and implement compilable code with the overall goal of becoming more self-sufficient (C++) programmers. All programming will take place in a Unix environment and will be reinforced by weekly assignments.

Text and syllabus

I have chosen to make the textbook optional given the large number of online (and FREE!) resources available to you, including my and Dr. Plank's historical notes.


That said, when I have previously taught this class students have found the text below an inexpensive but useful resource. Since we'll largely avoid newer C++ syntax (e.g., C++11) any version of this text will work the same as a resource. You should consider this text entirely supplementary, though.

C++ How to Program by Deitel and Deitel.

The syllabus can be found here

Schedule

Date Topic Homework Notes
1/23/2024 Brief C++ review [Lab 0],
due 1/26 6PM

[Lab 1],
due 1/31 8AM
[Notes]
[CS102/202 review]
1/25/2024 String and STL (review)   [Notes]
[Historical]
1/30/2024 Classes / OOP / Constructors [Lab 2],
due 2/7 8AM
[Notes]
[Historical]
2/01/2024 Code review / making a good interface (.h)   [Notes]
2/06/2024 The rule of three [Lab 3],
due 2/14 8AM
[Notes]
[Historical]
2/08/2024 Polymorphism and exceptions   [Notes]
[Historical]
2/13/2024 Lists, Deques, Iterators [Lab 4],
due 2/21 8AM
[Notes]
[Historical]
2/15/2024 Linked data structures: Stacks, Queues and Doubly linked lists, sorting (STL)   [Notes]
2/20/2024 Intro to Hashing [Lab 5],
due 3/8 3pm
[Historical]
2/22/2024 Collaborative midterm review; resolving collisions w/ separate chaining   [Notes]
2/27/2024 Hash functions: good, bad and in-between   [Challenge]
2/29/2024 Midterm    
3/05/2024 Sets and maps [Lab 6],
due 3/20 8AM
[Notes]
[Historical]
3/07/2024 Big-O   [Historical]
3/19/2024 Recursion [Lab 7],
due 3/27 8AM
[Historical]
3/21/2024 A recursive Sudoku solver   [Historical]
3/26/2024 The basics of trees and binary search trees [Lab 8],
due 4/3 8AM
[Historical]
3/28/2024 Spring recess (no class)    
4/02/2024 AVL trees (1) [Lab 9],
due 4/17 8AM
[Historical]
4/04/2024 AVL trees (2)   [Historical]
4/09/2024 Trees + recursion   (see notes
for Lab 9)
4/11/2024 TBD (Class choice)    
4/16/2024 Priority queues and binary heaps [Lab 10],
due 4/24 8AM
[Historical]
4/18/2024 Binary heaps (cont)   [Historical]
4/23/2024 TBD (Class choice)    
4/25/2024 Case study: circular linked list API   [Exercise]
4/30/2024 Case study: searching approaches for a sequence container    
5/02/2024 TBD    
5/07/2024 Final wrap up/review    

Academic dishonesty

All are required to abide by the EECS and University honor code. Discussions are encouraged, but all answers/programs must be written/developed individually unless explicitly told otherwise (e.g., final lab projects based on student feedback)