CSCE350: Data Structures and Algorithms

Fall 2020 - University of South Carolina - Jason O'Kane

Section 001

Documents and Links

  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. Welcome
    Watch this video (1:27).
  2. 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.
  3. [2020-08-28] Complete the Startup Quiz.

Part 1: Introduction

  1. [2020-08-25] Class 1
    Welcome. Discussion of class format and procedures. (video)
  2. What is an algorithm?
    Read Section 1.1.
    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
    Read Section 1.2.
    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
    Read Section 1.4.
    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-01] Class 2
    Review of HW1, HW2, HW3 solutions. Questions and discussion about HW4 and HW5. Preview of HW6. (video)
  2. What is algorithm analysis?
    Read Section 2.1.
    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
    Read Section 2.2.
    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-08] 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
    Read Section 2.3.
    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
    Read Section 2.4.
    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.
    Watch this video (14:06) about an additional trick for solving recurrences.
    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-15] Class 4
    Review of HW6 and HW7 solutions. Discussion of Exam Dry Run and Test A, including Review Sheet for Test A. (video)
  2. Selection sort
    Read Section 3.1.
    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
    Read Section 3.2.
    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
    Read Section 3.4.
    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-22] Class 5
    Discussion of Test A and its dry run. Review of HW08, HW09, and HW10 solutions. (video)
  2. [2020-09-29] Class 6
    No class on 9/29.
  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
    Read Section 4.1.
    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
    Read Section 4.4.
    Watch this video (13:42) about binary search.
    Review these notes.
  4. [2020-10-02] Complete Homework 12.
  5. Partitioning and selection
    Read Section 4.5.
    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-06] 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.
    Read Section 5.1.
    Watch this video (16:35) about Mergesort.
    Review these notes and these notes.
  3. [2020-10-09] Complete Homework 14. (solutions)
  4. Quicksort
    Read Section 5.2.
    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
    Read Section 5.4.
    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-13] Class 8
    Discussion of Project 2 solution strategies. Review of homework solutions. Test 1 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-20] 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
    Read Section 6.4.
    Watch this video (42:45) about heaps.
    Review these notes.
  10. [2020-10-23] Complete Homework 20.

Test B

  1. [2020-11-03] Election Day
    No class on 11/03.
  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.

Part 7: Space-Time Tradeoffs

  1. Hash tables
    Read the introductory portion of Chapter 7.
    Read Section 7.3.
    Watch this video (52:15) about hash tables.
    Review these notes.
  2. [2020-11-06] Complete Homework 21.

Distant Future

  1. Part 8: Dynamic Programming
  2. Part 9: Greedy Algorithms
  3. Part 10: Graph Algorithms
  4. [2020-12-11] Final Exam