Weekly Schedule
ICS46: Data Structure Implementation and Analysis
For an alternative presentation of the listing of course materials, see the
Lectures/Lab Schedule page.
Week 0
 9/28: Lab
 Download and Install Cygwin, Clang C++, and CLion.
 Start
Program #0: CLion/Clang C++, Course/GoogleTest Libraries, and Checkmate
Week 1
 Monday (10/2): Lecture
 The ICS46 Template Library:
Stack, Queue, Priority Queue, Set, and Map
Notes

Pass out Academic Integrity Contract
(discuss on Wednesday; turn in signed copy on Friday)
 Tuesday (10/3): Lab
 Work on
Program #0: CLion/C++, Course/GoogleTest Libraries, and Checkmate
 Wednesday (10/4): Lecture

Discuss Academic Integrity Contract
(turn in a signed copy on Friday, not today)
 The ICS46 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/5): Lab
 Friday (10/6): Lecture
Week 2
 Monday (10/9): Lecture
 Tuesday (10/10): Lab
 Wednesday (10/11): Lecture
 Special Linked Lists: Circular, Header, Trailer, Doublylinked
Notes
Pictures
 Thursday (10/12): Lab
 Work on
Program #1: Using the ICS46 Template Library
 Quiz #1: Checkmate submission due at 11:30 pm
 Friday (10/13): Lecture
Week 3
 Monday (10/16): Lecture
 Analysis of Algorithms I: Complexity Classes and bigO Notation
Notes
 Tuesday (10/17): Lab
 Start
Program #2: Implementing Queue/Priority Queue/Set with Linked Lists
 Wednesday (10/18): Lecture
 Analysis of Algorithms II: Composing Complexity Classes: examples;
Ω (bigOmega) and Θ (bigTheta) Notations
Notes
 Thursday (10/19): Lab
 Work on
Program #2: Implementing Queue/Priority Queue/Set with Linked Lists
 Quiz #2: Checkmate submission due at 11:30 pm
 Friday (10/20): Lecture
Week 4
 Monday (10/23): Lecture
 Tuesday (10/24): Lab
 Work on
Program #2: Implementing Queue/Priority Queue/Set with Linked Lists
 Wednesday (10/25): Lecture
 Thursday (10/26): Lab
 Work on
Program #2: Implementing Queue/Priority Queue/Set with Linked Lists
 Friday (10/27): Lecture
 Quiz #3: Paper submission due at the Start of Lecture
 AVL (and other selfbalancing search trees)
Notes
 Quiz #4:
Handed out online only
(
CLion Helper project for Quiz)
(due: Checkmate submission on Thursday 11/2, at 11:30 pm;
paper submission on Friday 11/3, at the start of Lecture)
Week 5
 Monday (10/30): Lecture
 General Trees (set, etc. children), Binary embedding,
Quad trees, Digital Trees, Structure Trees
Notes
Pictures
 Tuesday (10/31): Lab
 Start
Program #3: Implementing Priority Queues and Maps with Binary Trees
 Wednesday (11/1): Lecture
 Thursday (11/2): Lab
 Work on
Program #3: Implementing Priority Queues and Maps with Binary Trees
 Quiz #4 Checkmate submission due at 11:30 pm
 Friday (11/3): Lecture
Week 6
 Monday (11/6): Lecture
 Quiz #5: Paper submission due at the start of class
 Problem Solving and Search Trees: StateSpace Searching
Notes
 StateSpace Program
 Tuesday (11/7): Lab
 Work on
Program #3: Implementing Priority Queues and Maps with Binary Trees
 Wednesday (11/8): Lecture

Midterm Exam: please arrive promptly for maximum time
Topics:
ICS46 Template Library and Iterators;
Linked Lists (iterative and recursive);
Analysis of Algorithms;
Trees: Binary/BST/Heap/..., Hash Table concepts
 Thursday (11/9): Lab
 Work on
Program #3: Implementing Priority Queues and Maps with Binary Trees
 Quiz #5: Checkmate submission due at 11:30 pm
 Friday (11/10): Lecture
 Holiday (No Class): Veterans Day
 No quiz this week.
Week 7
 Monday (11/13): Lecture
 Sorting 1: Time/Space/Stability, O(N^2) Sorts
Notes
 Tuesday (11/14): Lab
 Start
Program #4: Implementing Maps and Sets via Hash Tables
 Wednesday (11/15): Lecture
 Sorting 2: O(N Log N) Sorts, lower bounds
Notes
 Thursday (11/16): Lab
 Work on
Program #4: Implementing Maps and Sets via Hash Tables
 Friday (11/17): Lecture
Week 8
 Monday (11/20): Lecture
 Tuesday (11/21): Lab
 Work on
Program #4: Implementing Maps and Sets via Hash Tables
 Wednesday (11/22): Lecture
 Thursday (11/23): Lab
 Holiday (No Class): Thanksgiving
 Quiz #6: Checkmate submission due at 11:30 pm
 Friday (11/24): Lecture
Week 9
 Monday (11/27): Lecture
 Tuesday (11/28): Lab
 Start
Program #5: Implementing Graphs and Dijkstra's Algorithm
 Wednesday (11/29): Lecture
 Thursday (11/30): Lab
 Work on
Program #5: Implementing Graphs and Dijkstra's Algorithm
 Quiz #7: Checkmate submission due at 11:30 pm
 Friday (12/1): Lecture
 Speedingup 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/7, at 11:30 pm;
paper submission on Friday, 12/8 at the start of Lecture)
)
Week 10
 Monday (12/4): Lecture
 Computer Memory: Introduction
Notes
 Tuesday (12/5): Lab
 Work on
Program #5: Implementing Graphs and Dijkstra's Algorithm
 Wednesday (12/6): Lecture
 Computer Memory: Data Structures and Algorithms for Searching
Notes
 Example
 Thursday (12/7): Lab
 Work on
Program #5: Implementing Graphs and Dijkstra's Algorithm
 Quiz #8: Checkmate submission due at 11:30 pm
 Friday (12/8): Lecture
 Quiz #8: Paper submission due at the Start of Lecture
 Computer Memory: Algorithms for Sorting
Notes
Final Exams Week
 Friday (12/15): Final Exam
 8:00am  10:00am
 In EH 1200
 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.)