| Lesson | Topics | Assignment Due |
Meeting 1 Sat, Jan 13
|
- Syllabus Overview
- Course Introduction
- Canvas tour
- How to be successful in this course
- Using the ARC computing environment
|
Exercises are due by midnight on
the date due unless it is stated
otherwise. Activities must be submitted during lab period. All reading assignments must be
completed prior to the indicated class meeting.
- Verification of Prerequisites
- Log on to the class website
- Establish your ARC gmail account
- Writing the Mandelbrot classes
- Read Chapter 1
- Introduction to Software Design
-
Activity 1
- 3 x 5 card about yourself
|
Meeting 2 Sat, Jan 20
|
- Software development
- Writing detailed specifications
- Interpreting specifications
- Modularity
- Language basics
- Memory management
- Static vs. dynamic
- Pointers
- Pass-by-value vs. pass-by-reference
- Parameter passing: formal vs. actual
|
- Read Chapters 2.1-2
- Program Correctness and Efficiency
-
Activity 2
- Related Content
|
Meeting 3 Sat, Jan 27
|
- Data protection
- Data abstraction
- Abstract data type (ADT)
- Set of operations and set of values
- Information hiding
- User interface
- Least privilege
- Basic ADTs
- ADT array
- ADT record
- Implementation details
|
- Read Chapter 3
- Inheritance and Class Hierarchies
-
Exercise 1
- Mandelbrot using ComplexNumber and PPMFile classes
-
Activity 3
- Related Content
|
Meeting 4 Sat, Feb 3
|
- ADT list
- ADT list Operations
- ADT list Implementation: array, array of pointers, and linked structures
- ADT list Using lists to solve problems
|
- Read Chapter 4
- Sequential Containers
-
Quiz 1
- Related Material
|
Meeting 5 Sat, Feb 10
|
- ADT stack
- ADT stack Operations
- ADT stack Implementation: array, array of pointers, and linked structures
- ADT stack Implementation using ADT list
- ADT stack Using stacks to solve problems
|
- Read Chapter 5
- Stacks
-
Exercise 2
- Related content
-
Activity 4
- Related Content
|
Meeting 6 Sat, Feb 17
|
- ADT queue
- ADT queue Operations
- ADT queue Implementation: array, array of pointers, and linked structures
- ADT queue Implementation using ADT list
- ADT queue Using queues to solve problems
|
- Read Chapter 6
- Queues and Deques
-
Activity 5
- Related Content
|
Meeting 7 Sat, Feb 24
|
- File processing
- File processing: Reading and writing
- File processing: Text and non-text files
- File records: fixed size vs. variable size
|
-
Exercise 3
- Related Content
-
Activity 6
- Related Content
|
Meeting 8 Sat, Mar 3
|
- Introduction to recursion
- Recursion: Basic algorithms
- Recursion: Efficiency vs. iteration
- Advanced recursion
- Backtracking
- Defining languages
- The base case
- Recursion and proof by induction
|
- Read Chapter 7
- Recursion
-
Quiz 2
- Related Material
|
Meeting 9 Sat, Mar 10
|
Midterm: This comprehensive lab practical involves content presented up to Recursion.
|
|
Meeting 10 Sat, Mar 17
|
- Sorting, searching
- Sequential search
- Binary search
- Bubble, selection, and insertion sort
- Merge and quick sort
- Radix sort
- Big-O
- Big-O Worse case estimation
- Big-O Data set size
- Big-O Conceptual categories
- Big-O Definition and proof
- Big-O analysis of searching and sorting
|
- Read Chapter 10.1-4,10.7,10.9
- Sorting
- Read Chapter 2.6
- Efficiency of Algorithms
-
Exercise 4
- Related content
-
Activity 7
- Related Content
|
Meeting 11 Sat, Mar 24
|
- Trees: Introduction
- Trees: General tree terminology
- Trees: ADT binary tree
- Trees: ADT binary search tree
|
- Read Chapter 8
- Trees
-
Quiz 3
- Related Material
|
Sat, Mar 31
|
- Spring Break(no class this Saturday)
| |
Meeting 12 Sat, Apr 7
|
- Binary trees
- Binary trees: Implementation as: array of data, array of pointers, linked nodes
- Binary trees Tree traversal: in-order, pre-order, post-order
- Binary trees Full and complete trees
- Binary trees Adelson-Velskii and Landis (AVL) trees
|
-
Exercise 5
- Related content
-
Activity 8
- Related Content
|
Meeting 13 Sat, Apr 14
|
- ADT heap
- ADT heap using Binary tree
- ADT heap Complete tree
- ADT heap Parent/child relation
- ADT heap Re-heapify upward
- ADT heap Re-heapify downward
- ADT heap Heap sort
- ADT heap Implementation
|
- Read Chapter 10.8
- Heapsort
-
Quiz 4
- Related Material
|
Meeting 14 Sat, Apr 21
|
- ADT hash table
- ADT hash table Non-linear structure
- ADT hash table Unique keys
- ADT hash table Hash function types
- ADT hash table Perfect hash functions
- ADT hash table Collisions
- ADT hash table Collisions resolution
- ADT hash table Hash buckets
- ADT hash table External chaining
|
- Read Chapter 9.3
- Hash Tables
-
Exercise 6
- Related content
-
Activity 9
- Related Content
|
Meeting 15 Sat, Apr 28
|
- ADT graph
- ADT graph Edges and vertices
- ADT graph Path
- ADT graph Cycle
- ADT graph Degree of a vertex
- ADT graph Directed and undirected edges
|
- Read Chapter 12
- Graphs
-
Quiz 5
- Related Material
|
Meeting 16 Sat, May 5
|
- Sub-graph
- Connectivity
- Graph traversal: breadth-first, depth-first
- Final review and in-class activity
|
-
Exercise 7
- Related content
-
Activity 10
- Related Content
|
Final Exam Sat, May 12
|
| |
