Weekly Schedule

ICS-46: Data Structure Implementation and Analysis

For an alternative presentation of the listing of course materials, see the Lectures/Lab Schedule page.

Week 0

9/26: Lab
- Download and Install Cygwin, Clang C++, and CLion.
- Start Program #0: CLion/Clang C++, Course/GoogleTest Libraries, and Checkmate

9/27: Lecture
- Course Overview
- Notes
- (Abstract) Data Types and Data Structures
- Time/Space Performance
- CLion Demo

Week 1

Monday (9/30): Lecture
- The ICS-46 Template Library: Stack, Queue, Priority Queue, Set, and Map Notes
- Interesting Graphs
- Pass out Academic Integrity Contract
  (discuss on Wednesday; turn in signed copy on Friday)
Tuesday (10/1): Lab
- Work on Program #0: CLion/C++, Course/GoogleTest Libraries, and Checkmate
Wednesday (10/2): Lecture
- Discuss Academic Integrity Contract
  (turn in a signed copy on Friday, not today)
- The ICS-46 Template Library: Stack, Queue, Priority Queue, Set, and Map (continued) Notes
- test_itl project folder
  (for performing simple experiments with the ITL)
- cross_reference project folder
  (a comprehensive example of using the ITL in a real program)
Thursday (10/3): Lab
- Start Program #1: Using the ICS-46 Template Library
Friday (10/4): Lecture
- Return signed Academic Integrity Contract
- Array Implementations of ICS-46 Template Library Classes Notes
- Iterator Worksheet
- Quiz #1: Handed out online only ( CLion Helper project for Quiz)
  (due: Checkmate submission on Thursday 10/10, at 11:30 pm)

Week 2

Monday (10/7): Lecture
- Linked Lists and Linked List Processing Notes
  Pictures
  Driver
  Practice Sheet
Tuesday (10/8): Lab
- Work on Program #1: Using the ICS-46 Template Library
Wednesday (10/9): Lecture
- Special Linked Lists: Circular, Header, Trailer, Doubly-linked Notes
  Pictures
Thursday (10/10): Lab
- Work on Program #1: Using the ICS-46 Template Library
- Quiz #1: Checkmate submission due at 11:30 pm
Friday (10/11): Lecture
- Recursion: General, Strings, Linked Lists Notes
  Pictures
  Recursion (implemented by the Cat in the Hat) Elephants
- Quiz #2: Handed out online only ( CLion Helper project for Quiz)
  (due: Checkmate submission on Thursday 10/17, at 11:30 pm;
  paper submission on Friday 10/18, at the start of Lecture)

Week 3

Monday (10/14): Lecture
- Analysis of Algorithms I: Complexity Classes and big-O Notation Notes
Tuesday (10/15): Lab
- Start Program #2: Implementing Queue/Priority Queue/Set with Linked Lists
Wednesday (10/16): Lecture
- Analysis of Algorithms II: Composing Complexity Classes: examples; Ω (big-Omega) and Θ (big-Theta) Notations Notes
Thursday (10/17): Lab
- Work on Program #2: Implementing Queue/Priority Queue/Set with Linked Lists
- Quiz #2: Checkmate submission due at 11:30 pm
Friday (10/18): Lecture
- Quiz #2: Paper submission due at the Start of Lecture
- Introducing Binary Trees Notes
  Pictures
- Trees as Seen by Computer Scientists
- Quiz #3: Handed out in class
  (There is No CLion Helper project for this Quiz)
  (due: paper submission on Friday 10/25, at the start of Lecture)

Week 4

Monday (10/21): Lecture
- Binary Search Tree Processing and Traversals Notes
  Pictures
  Driver
  Empirical Program Empirical Text
Tuesday (10/22): Lab
- Work on Program #2: Implementing Queue/Priority Queue/Set with Linked Lists
Wednesday (10/23): Lecture
- Heap Trees and Special Trees Notes
  Pictures
Thursday (10/24): Lab
- Work on Program #2: Implementing Queue/Priority Queue/Set with Linked Lists
Friday (10/25): Lecture
- Quiz #3: Paper submission due at the Start of Lecture
- AVL (and other self-balancing search trees) Notes
- Quiz #4: Handed out online only ( CLion Helper project for Quiz)
  (due: Checkmate submission on Thursday 10/31, at 11:30 pm;
  paper submission on Friday 11/1, at the start of Lecture)

Week 5

Monday (10/28): Lecture
- General Trees (set, etc. children), Binary embedding, Quad trees, Digital Trees, Structure Trees Notes
  Pictures
Tuesday (10/29): Lab
- Start Program #3: Implementing Priority Queues and Maps with Binary Trees
Wednesday (10/30): Lecture
- Hash Tables: Hashing, Chaining, Probing, Iterators Notes
  Empirical Program Empirical Text
Thursday (10/31): Lab
- Work on Program #3: Implementing Priority Queues and Maps with Binary Trees
- Quiz #4 Checkmate submission due at 11:30 pm
Friday (11/1): Lecture
- Quiz #4: Paper submission due at the Start of Lecture
- Problem Solving and Search Trees: Backtracking Notes
- Backtracking Program
- Graph for 3-Coloring
- Quiz #5: Handed out in class ( CLion Helper project for Quiz)
  (due: Checkmate submission on Thursday 11/7, at 11:30 pm;
  paper submission on Friday, 11/8 at the start of Lecture)

Week 6

Monday (11/4): Lecture
- Problem Solving and Search Trees: State-Space Searching Notes
- State-Space Program
Tuesday (11/5): Lab
- Work on Program #3: Implementing Priority Queues and Maps with Binary Trees
Wednesday (11/6): Lecture
- Midterm Exam: please arrive promptly for maximum time
  Topics: ICS-46 Template Library and Iterators; Linked Lists (iterative and recursive); Analysis of Algorithms; Trees: Binary/BST/Heap/.../Heap Trees and Special Trees
Thursday (11/7): Lab
- Work on Program #3: Implementing Priority Queues and Maps with Binary Trees
- Quiz #5: Checkmate submission due at 11:30 pm
Friday (11/8): Lecture
- Quiz #5: Paper submission due at the start of class
- Sorting 1: Time/Space/Stability, O(N^2) Sorts Notes
- Empirical Sorting Tool
- No quiz this week.

Week 7

Monday (11/11): Lecture
- Holiday (No Class): Veteran's Day
Tuesday (11/12): Lab
- Start Program #4: Implementing Maps and Sets via Hash Tables
Wednesday (11/13): Lecture
- Sorting 2: O(N Log N) Sorts, lower bounds Notes
Thursday (11/14): Lab
- Work on Program #4: Implementing Maps and Sets via Hash Tables
Friday (11/15): Lecture
- Sorting 3: Sorting without Comparisons: Bucket and Radix Sort Notes
- Quiz #6: Handed out online only ( CLion Helper project for Quiz)
  (due: Checkmate submission on Thursday 11/21, at 11:30 pm)

Week 8

Monday (11/18): Lecture
- Equivalences Notes
Tuesday (11/19): Lab
- Work on Program #4: Implementing Maps and Sets via Hash Tables
Wednesday (11/20): Lecture
- Graphs: Terminology and Representations Notes
  Pictures
Thursday (11/21): Lab
- Work on Program #4: Implementing Maps and Sets via Hash Tables
- Quiz #6: Checkmate submission due at 11:30 pm
Friday (11/22): Lecture
- Graph Algorithms I: Topological Sorting, Connected Components, and Spanning Trees Notes
- Graph For Minimum Spanning Tree
- Quiz #7: Handed out online only ( CLion Helper project for Quiz)
  (due: Checkmate submission on Thursday 11/28, at 11:30 pm)

Week 9

Monday (11/25): Lecture
- Graph Algorithms II: Extended Dijkstra's Algorithm (Shortest Paths) Dijkstra's Notes
- Illustrated Example of Dijkstra (from notes)
- Dijkstra Graph (from Goodrich & Tamassia)
Tuesday (11/26): Lab
- Start Program #5: Implementing Graphs and Dijkstra's Algorithm
Wednesday (11/27): Lecture
- Speeding-up code without changing its algorithm/complexity class Notes
- Quiz #8: Handed out in class ( CLion Helper project for Quiz)
  (due: Checkmate submission on Thursday 12/5, at 11:30 pm;
  paper submission on Friday, 12/6 at the start of Lecture) )
Thursday (11/28): Lab
- Holiday (No Class): Thanksgiving
Friday (11/29): Lecture
- Holiday (No Class): Thanskgiving

Week 10

Monday (12/2): Lecture
- Computer Memory: Introduction Notes
Tuesday (12/3): Lab
- Work on Program #5: Implementing Graphs and Dijkstra's Algorithm
Wednesday (12/4): Lecture
- Computer Memory: Data Structures and Algorithms for Searching Notes
- Example
Thursday (12/5): Lab
- Work on Program #5: Implementing Graphs and Dijkstra's Algorithm
- Quiz #8: Checkmate submission due at 11:30 pm
Friday (12/6): Lecture
- Quiz #8: Paper submission due at the Start of Lecture
- Computer Memory: Algorithms for Sorting Notes

Final Exams Week

Monday (12/9): Final Exam
- 4:00pm - 6:00pm
- In ELH 100
- Instructions and seating assignments will be emailed before the exam
- Bring a photo ID with a legible name and picture (UCI, drivers license, passport, etc.)