## CSCE350: Data Structures and Algorithms

### Section 004

1. Syllabus
2. Submit homework
3. Make appointment
4. Dropbox
For submitting projects and tracking grades.
5. Blackboard
For viewing recordings of the in-person class sessions.
6. Teaching assistant office hours
For asking questions during Dr. Olsen's office hours, Monday and Wednesday, 11:30-1:00.
7. Tutoring details
Tutoring for this class is available both in person and remotely.

### Part 0: Orientation

1. [2020-08-20] Class 0
Welcome. Discussion of class format and procedures. (video)
2. Welcome
Watch this video (1:27).
3. Review of course format
Review the syllabus.
Complete the First Day Survey.
Watch this video (28:12) reviewing the format and expectations for the class.
[optional] Peruse Homework 0.
[optional] Watch this video (50:16) response to the first day survey results.
4. [2020-08-28] Complete the Startup Quiz.

### Part 1: Introduction

1. [2020-08-27] Class 01
Discussion of HW1–HW3. (video)
2. What is an algorithm?
Watch this video (12:47) about the definition of algorithm.
Watch this video (12:39) about an example algorithm (Euclid's).
Watch this video (24:20) about how to describe algorithms.
Review these notes.
3. [2020-08-28] Complete Homework 1. (solutions)
4. The algorithm design process
Watch this video (13:37) about the algorithm design process.
Review these notes.
5. [2020-08-28] Complete Homework 2. (solutions)
6. Important problem types
Read Section 1.3. This section is a preview of later parts of the course. No video nor homework for this section.
7. Basic data structures
Watch this video (14:51) review of basic data structures.
Watch this video (26:30) about data structures for representing graphs.
Review these notes.
8. [2020-08-28] Complete Homework 3. (solutions)

### Part 2: Analyzing Algorithms

1. [2020-09-03] Class 2
Review of HW1, HW2, HW3 solutions. Questions and discussion about HW4 and HW5. Preview of HW6. (video)
2. What is algorithm analysis?
Watch this video (43:10) for an overview of the process of analyzing algorithms.
Review these notes.
3. [2020-09-04] Complete Homework 4. (solutions)
4. Asymptotic notations: Big-$\Theta$ and friends
Watch this video (27:29) which defines Big-$\Theta$ notation.
Watch this video (9:43) example of using this definition.
Watch this video (9:46) which defines Big-$O$ and Big-$\Omega$ notation.
Watch this video (21:09) which shows some asymptotic notation shortcuts.
Watch this video (6:05) about common efficiency classes.
Review these notes.
5. [2020-09-04] Complete Homework 5. (solutions)
6. [2020-09-10] Class 3
Introduction of Project Format Quiz and Project 1. Review of HW4 and HW5 solutions. Questions and discussion about HW6 and HW7. (video)
7. Analysis of non-recursive algorithms
Watch this video (14:32) about using summations to analyze non-recursive algorithms.
Watch this video (17:20) for another example of analysis using summations.
Review these notes.
8. [2020-09-11] Complete Homework 6 (solutions).
9. Analysis of recursive algorithms
Watch this video (16:24) about writing recurrences to analyze recursive algorithms.
Watch this video (14:59) about solving recurrences using backward substitution.
Watch this video (10:55) introduction to the Tower of Hanoi.
Watch this video (21:33) analysis of the Tower of Hanoi algorithm.
Review these notes.
10. [2020-09-11] Complete Homework 7 (solutions).

### Project Format Quiz

1. Review the imaginary assignment Project 0.
2. [2020-09-14] Complete the project format quiz.

### Project 1: The Tower of Huger

1. [2020-09-21] Project Description
2. Sample Inputs
project1-1.in
project1-2.in
project1-3.in
3. Sample Outputs
project1-1.out
project1-2.out
project1-3.out

### Part 3: Brute Force

1. [2020-09-17] Class 4
Review of HW6 and HW7 solutions. Discussion of HW8. Discussion of Exam Dry Run and Test A, including Review Sheet for Test A. (video)
2. Selection sort
Watch this video (9:28) introduction to brute force.
Watch this video (25:18) about selection sort.
Review these notes and these notes.
3. [2020-09-18] Complete Homework 8. (solutions)
4. String matching
Watch this video (22:04) about string matching using brute force.
Review these notes.
5. [2020-09-18] Complete Homework 9. (solutions)
6. Exhaustive search
Watch this video (31:06) about using exhaustive search for the traveling salesman and knapsack problems.
Review these notes.
7. [2020-09-18] Complete Homework 10. (solutions)

### Test A

1. [2020-09-24] Class 5
Discussion of Test A and its dry run. Review of HW08, HW09, and HW10 solutions. (video)
2. [2020-10-01] Class 6
No class on 10/01.
3. Test Dry Run
The required dry run, worth 10 points, was active 2020-09-22 until 2020-09-24. Details about Test Dry Run (solutions)
4. Test A
The first test, worth 100 points, will be conducted in a take-home format, between September 29 and October 1. Review sheet for Test A
5. Results
The average score was 79.84. Solutions are here.

### Project 2: Balanced Teams

1. [2020-10-19] Project Description
2. Sample Inputs
project2-1.in
project2-2.in
project2-3.in
project2-4.in
3. Sample Outputs
project2-1.out
project2-2.out
project2-3.out
project2-4.out

### Part 4: Decrease and Conquer

1. Insertion sort
Watch this video (18:47) introduction to decrease and conquer.
Watch this video (22:14) about insertion sort.
Review these notes and these notes.
2. [2020-10-02] Complete Homework 11. (solutions)
3. Binary Search
Watch this video (13:42) about binary search.
Review these notes.
4. [2020-10-02] Complete Homework 12.
5. Partitioning and selection
Watch this video (27:17) about array partitioning.
Watch this video (18:30) about quickselect.
Review these notes.
6. [2020-10-02] Complete Homework 13. (solutions)

### Part 5: Divide and Conquer

1. [2020-10-08] Class 7
Introduction of Project 2. Discussion of techniques for testing Project 2. Review of Project 1 solution. (video)
2. Mergesort
Read from the beginning of Chapter 5 through the start of Section 5.1.
Watch this video (5:55) introduction to divide and conquer.
Watch this video (17:32) about the Master theorem.
Watch this video (16:35) about Mergesort.
Review these notes and these notes.
3. [2020-10-09] Complete Homework 14. (solutions)
4. Quicksort
Consider re-watching this video (27:17) about array partitioning.
Watch this video (18:05) about quicksort.
Review these notes.
5. [2020-10-09] Complete Homework 15. (solutions)
6. Multiplication of Large Integers
Watch this video (16:48) about representing very large numbers using arrays.
Watch this video (29:52) about the Karatsuba multiplication algorithm.
Review these notes.
7. [2020-10-16] Complete Homework 16.

### Part 6: Transform and Conquer

1. [2020-10-15] Class 8
Test 1 solutions. Discussion of Project 2. Review of homework solutions. (video)
2. Presorting
Read the beginning of Chapter 6 and Section 6.1.
Watch this video (10:32) introduction to decrease and conquer, including the presorting technique.
Review these notes.
3. [2020-10-16] Complete Homework 17. (solutions)
4. AVL Trees
Read the first part of Section 6.3.
Watch this video (13:33) review of binary search trees.
Watch this video (24:55) about AVL trees.
Watch this video (18:37) for some examples of AVL tree rebalancing.
Review these notes.
5. [2020-10-16] Complete Homework 18. (solutions)
6. [2020-10-22] Class 9
Questions about Project 2. Review of HW18 solutions. Early preview of Test B. (video)
7. 2-3 Trees
Read the second part of Section 6.3.
Watch this video (20:19) about 2-3 trees.
Watch this video (10:36) for an example of 2-3 tree construction.
Review these notes.
8. [2020-10-23] Complete Homework 19.
9. Heaps
Watch this video (42:45) about heaps.
Review these notes.
10. [2020-10-23] Complete Homework 20.

### Test B

1. [2020-11-05] Class 11
No class on 11/05.
2. Test B
The second test, worth 100 points, will be conducted in a take-home format, between November 3 and November 5. A review sheet will be posted by October 27.

1. Hash tables
Read the introductory portion of Chapter 7.