CSCD 320 — ALGORITHMS
Learning Objectives & Matches
Understand the mathematical definition of the five asymptotic notations: Θ, O, o, Ω, and ω.
Address the relationships of quantities, magnitudes, and forms through the use of numbers and symbols.
Analyze the asymptotic performance of algorithms.
Perform computations and apply methods of numerical analysis to data.
Monitor program performance to ensure efficient and problem-free operations.
Develop or implement data analysis algorithms.
Analyze, interpret, or disseminate system performance data.
Recommend and implement performance improvements.
Visit beta testing sites to evaluate software performance.
Examine theories, such as those of probability and inference, to discover mathematical bases for new or improved methods of obtaining and evaluating numerical data.
Analyze system performance or operational requirements.
Develop Web site performance metrics.
Investigate or resolve operational problems, such as material use variances or bottlenecks.
Write rigorous correctness proofs for algorithms.
Check preliminary and final proofs for errors and make necessary corrections.
Route proofs with marked corrections to authors, editors, typists, or typesetters for correction or reprinting.
Read copy or proof to detect and correct errors in spelling, punctuation, and syntax.
Read corrected copies or proofs to ensure that all corrections have been made.
Check source data to verify completeness and accuracy.
Build models for algorithm or control feature verification testing.
Verify the accuracy and validity of data entered in databases, correcting any errors.
Design and verify cryptographic protocols to protect private information.
Verify stability, interoperability, portability, security, or scalability of system architecture.
Check figures, postings, and documents for correct entry, mathematical accuracy, and proper codes.
Understand and use balanced search trees, including red-black tree and B-tree.
Develop techniques for measuring and identifying trees.
Improve search-related activities through ongoing analysis, experimentation, or optimization tests, using A/B or multivariate methods.
Trim, top, and reshape trees to achieve attractive shapes or to remove low-hanging branches.
Select trees to be cut down, assessing factors such as site, terrain, and weather conditions before beginning work.
Inspect trees to determine if they have diseases or pest problems.
Appraise trees for certain characteristics, such as twist, rot, and heavy limb growth, and gauge amount and direction of lean, to determine how to control the direction of a tree's fall with the least damage.
Collect and store patterns and lumber.
Control the direction of a tree's fall by scoring cutting lines with axes, sawing undercuts along scored lines with chainsaws, knocking slabs from cuts with single-bit axes, and driving wedges.
Record data about individual trees or load volumes into tally books or hand-held collection terminals.
Select lumber to be used for patterns.
Understand and use the heap data structure and its applications in sorting and priority queue.
Compile, sort, and verify the accuracy of data before it is entered.
Sort, assemble, and proof completed work.
Sort or classify information according to guidelines, such as content, purpose, user criteria, or chronological, alphabetical, or numerical order.
Sort books, publications, and other items according to established procedure and return them to shelves, files, or other designated storage areas.
Compile, copy, sort, and file records of office activities, business transactions, and other activities.
Design database applications, such as interfaces, data transfer mechanisms, global temporary tables, data partitions, and function-based indexes to enable efficient access of the generic database structure.
Recommend and implement performance improvements.
Prepare and structure data warehouses for storing data.
Electronically sort and compile text and numerical data, retrieving, updating, and merging documents as required.
Monitor program performance to ensure efficient and problem-free operations.
O*NET-aligned topic inventory
55 tags extracted from this course-term's Canvas content, organized by O*NET 30.2 dimension. Depth reflects what students do with each topic over the term: mastered, practiced, introduced.
Every HW spec instructs 'Submission must be computer typeset in the PDF format' and explicitly encourages LaTeX, and a sample_latex.zip starter file is posted under lecture material; HWs feature math-heavy proofs, recurrences, and asymptotic arguments students typeset.
files/homeworks/hw1.pdf;files/homeworks/hw2.pdf;files/homeworks/hw3.pdf;files/lecture material/sample_latex.zip
Programming assignments 1-4 require all source code to be written in Java per the spec ('All source code must be written in Java and commented reasonably well'); students implement order-statistic selection, external top-k, matrix-chain DP, and DAG topological sort in Java.
files/homeworks/prog1.pdf;files/homeworks/prog2.pdf;files/homeworks/prog3.pdf;files/homeworks/prog4.pdf
HW1-HW7 are math-dominated: students compute Theta/O/o/Omega bounds, solve recurrences via recursion-tree, induction, and the Master Theorem, and prove correctness of algorithms; the textbook chapters assigned are 2.1, 2.2, 3.1, 4.1, 4.3, 4.4, 4.5, 4.6, 13.1.
files/homeworks/hw1.pdf;files/homeworks/hw2.pdf;files/homeworks/hw3.pdf;pages/cscd320-course-schedule.html
Schedule explicitly assigns BST review as self-study ('PDF1-PDF5, video1-video5; take your own time to study/watch them ... Without knowing BST well, you won't be able to follow RBT'); students must independently bridge the prerequisite.
pages/cscd320-course-schedule.html
In-person lectures (with Zoom-live fallback) are the primary content delivery; instructor announces 'Take every homework as an opportunity to train yourself' and expects engagement, plus weekly Q&A and exam review sessions.
pages/cscd320-algorithms.html;pages/cscd320-course-schedule.html
prog2 'Finding the Richest People' requires students to design an external-memory top-k algorithm under a memory cap (10,000 items) — a multi-constraint problem requiring decomposition; prog3/prog4 require dynamic programming and graph algorithm composition.
files/homeworks/prog2.pdf;files/homeworks/prog3.pdf;files/homeworks/prog4.pdf
HWs ask open-ended algorithm-design questions ('design an algorithm with running time O(n log n)' style) and require students to choose appropriate strategy (D&C, DP, greedy) and justify correctness on three exams.
files/homeworks/hw2.pdf;files/homeworks/hw3.pdf;assignments/7131445-Exam 1.json
Students choose among algorithm-design strategies (D&C vs. DP vs. greedy vs. backtracking) and must justify why a chosen approach achieves the asked-for asymptotic bound on HWs and exams.
files/homeworks/hw2.pdf;files/homeworks/hw5.pdf;files/homeworks/hw6.pdf
Instructor explicitly directs students to learn via worked examples first ('use the insert sort as a simple example algorithm to define time cost') and then generalize; multiple lectures are scaffolded as intuition-then-formalism.
pages/cscd320-course-schedule.html
Students analyze running-time and space requirements of algorithms (insertion sort, merge sort, quicksort variants, RBT operations, BFS/DFS, Prim/Kruskal, Dijkstra/Bellman-Ford) — i.e., quantify operational characteristics of algorithmic systems.
files/lecture material/slides_asymp_1.pdf;files/lecture material/slides_asymp_2.pdf;files/homeworks/hw1.pdf
Four programming assignments require students to write working Java implementations of nontrivial algorithms (randomized order statistic via D&C, external top-k for memory-bounded data, matrix-chain DP, DFS-based topological sort).
files/homeworks/prog1.pdf;files/homeworks/prog2.pdf;files/homeworks/prog3.pdf;files/homeworks/prog4.pdf
Course follows CLRS: weekly readings span Ch.1, Ch.2.1-2.3, Ch.3.1, Ch.4.1, 4.3-4.6, Ch.13.1 across the term; students must internalize formal definitions and proofs to do HW.
pages/cscd320-course-schedule.html
Students decompose problems into algorithmic subroutines and reason about how subsystem time costs (recurrence relations) yield total system cost — e.g., Master Theorem application across 3 recurrence-solving lectures.
files/lecture material/slides_recurrence_1.pdf;files/lecture material/slides_recurrence_2.pdf;files/lecture material/slides_recurrence_3.pdf
Eleven graded deliverables (7 HWs + 4 progs) plus 3 exams across an 11-week quarter with hard deadlines ('The deadline is sharp. Late submissions will NOT be accepted'); students manage overlapping spec-and-implementation work.
assignments.json;files/homeworks/prog1.pdf
Programming assignments require Java implementations to produce correct output; students debug recursive partition, DP table-fill, and DFS-stack issues across prog1-prog4.
files/homeworks/prog1.pdf;files/homeworks/prog3.pdf;files/homeworks/prog4.pdf
HWs require typeset, structured written solutions with mathematical justification and English-language explanation; instructions mandate 'computer typeset in the PDF format' for submission.
files/homeworks/hw1.pdf;files/homeworks/hw2.pdf
Course substantively transmits asymptotic analysis (Theta/O/Omega/o/omega), recurrence relations and the Master Theorem, inductive proofs, and amortized analysis across 8+ lecture sessions and 7 HWs.
files/lecture material/slides_asymp_1.pdf;files/lecture material/slides_asymp_2.pdf;files/lecture material/slides_recurrence_1.pdf;files/lecture material/slides_recurrence_2.pdf;files/lecture material/slides_recurrence_3.pdf;files/homeworks/hw1.pdf;files/homeworks/hw3.pdf
Course is built around classical algorithms and data structures (heaps, BSTs, RBTs, B-trees, graphs); Java programming environment is the deliverable substrate. Following CLRS textbook.
files/lecture material/slides_intro.pdf;files/syllabus_320.pdf
Programming assignments require designing and implementing engineered solutions for stated specifications: external-memory top-k retrieval (prog2), DP-based optimization (prog3), graph-algorithm engineering (prog4).
files/homeworks/prog2.pdf;files/homeworks/prog3.pdf;files/homeworks/prog4.pdf
Written HW solutions and exam answers must communicate algorithmic ideas precisely in English (proofs, problem-statement reformulations, design rationale).
files/homeworks/hw1.pdf;files/homeworks/hw2.pdf
Lectures and HWs require deriving consequences from formal definitions of asymptotic notation, loop invariants, and tree-property invariants (RBT Lemma 13.1 has its own slide-resident proof students reproduce).
files/lecture material/slides_red_black_trees_1.pdf;files/lecture material/slides_red_black_trees_2.pdf;files/homeworks/hw3.pdf
Course is centrally about ordering information correctly: insertion sort, merge sort, randomized partitioning, heap-order, BST/RBT in-order traversal, topological sort of a DAG (prog4).
files/lecture material/slides_insertion_sort.pdf;files/lecture material/slides_heap_1.pdf;files/homeworks/prog4.pdf
Students prove asymptotic bounds, solve recurrences via the Master Theorem and induction, and prove correctness of algorithms (e.g. RBT invariant preservation, MST cut-property arguments) across HW1, HW3, HW5, HW6.
files/homeworks/hw1.pdf;files/homeworks/hw3.pdf;files/homeworks/hw5.pdf;files/homeworks/hw6.pdf
Students reclassify problems by algorithmic strategy (when D&C vs DP vs greedy applies) and recognize that the same operation (e.g., 'find min') has different costs across heap, BST, and unsorted-array representations.
files/lecture material/slides_dynamic_prog_1.pdf;files/lecture material/slides_greedy_1.pdf
Open-ended algorithm-design HW problems ask for an O(n log n) solution to a stated problem — students must generate multiple candidate approaches before selecting one.
files/homeworks/hw2.pdf;files/homeworks/hw5.pdf
Students perform pattern-recognition over recurrence unrolling (recursive-tree method) and structural induction over tree heights (RBT, B-tree depth) to derive bounds.
files/lecture material/slides_recurrence_1.pdf;files/lecture material/slides_recurrence_2.pdf
Three in-person exams test recall of definitions (asymptotic notation, RBT properties, MST cut/cycle properties, DP recurrences, Master-Theorem cases).
assignments/7131445-Exam 1.json;assignments/7191781-exam2.json;assignments/7232068-exam3.json;pages/cscd320-algorithms.html
HWs include hand-computation of recurrence solutions and asymptotic comparisons (e.g., 'Solve T(n) = 8T(n/2) + Theta(n^2) using the Master Theorem'); exams test arithmetic on running-time bounds.
files/homeworks/hw3.pdf
prog2 ('Finding the Richest People') is an external-memory adaptation challenge — students design their own approach under a non-textbook memory constraint rather than transcribing CLRS pseudocode.
files/homeworks/prog2.pdf
Students must recognize when a candidate algorithm is wrong (off-by-one in partition, missing case in RBT delete fixup, infeasible memory in prog2's IRS top-10000) and identify which constraint is violated.
files/homeworks/prog2.pdf;files/lecture material/slides_red_black_trees_3.pdf
Long-duration exams (3 closed-form exams, 100 pts each) and multi-page HWs require sustained focus on multi-step proofs and code where one missed boundary case fails the whole answer.
assignments/7131445-Exam 1.json;assignments/7191781-exam2.json;assignments/7232068-exam3.json
Students draw and reason over tree and graph diagrams: BST/RBT rotations, B-tree splits, recursion trees, BFS/DFS traversals, MST construction; the slide deck is dominated by diagrammatic content.
files/lecture material/slides_binary_tree_1.pdf;files/lecture material/slides_red_black_trees_1.pdf;files/lecture material/slides_b_tree_1.pdf;files/lecture material/slides_graph_bfs.pdf;files/lecture material/slides_graph_dfs.pdf
Course follows CLRS chapters; students must read formal definitions and theorems then apply them on HWs (e.g., reading 4.5-4.6 to apply the Master Theorem on hw3).
pages/cscd320-course-schedule.html;files/homeworks/hw3.pdf
HWs are PDF-typeset written deliverables in which students must explain algorithm design and prove correctness in English plus mathematical notation.
files/homeworks/hw1.pdf;files/homeworks/hw2.pdf;files/homeworks/hw5.pdf
Asymptotic analysis IS the act of estimating the quantifiable characteristic (running time, space) of an algorithm; this is the central work product of HW1 through HW7.
files/homeworks/hw1.pdf;files/homeworks/hw2.pdf;files/homeworks/hw3.pdf;files/lecture material/slides_asymp_1.pdf
Students analyze the running time of algorithms by computing recurrences, applying the Master Theorem, and comparing growth rates — i.e., quantitative analysis of algorithm behavior on input.
files/homeworks/hw1.pdf;files/homeworks/hw3.pdf;files/lecture material/slides_recurrence_3.pdf
Schedule encourages student questions and lists Discord and instructor/TA office hours as recurring channels; students also collaborate verbally per HW rule 1 ('Verbal discussions with classmates are encouraged').
pages/cscd320-algorithms.html;files/homeworks/hw1.pdf
Programming assignments require Java source files with author headers and 'reasonably well' commented code (per prog1-prog4 spec rule 4 and 5); HWs themselves are documentation of solution reasoning.
files/homeworks/prog1.pdf;files/homeworks/prog2.pdf
prog3 (matrix-chain DP) and prog4 (DAG topological sort) require students to specify class structure, input format, and method contracts in a Java program before implementation; specs name FastMatrixMulti and TopoSort classes.
files/homeworks/prog3.pdf;files/homeworks/prog4.pdf
Students verify their algorithms meet specified asymptotic bounds and produce required output formats; on exams, they evaluate whether a proposed algorithm satisfies a claimed running time.
files/homeworks/hw5.pdf;files/homeworks/hw6.pdf
Schedule lists weekly CLRS chapter readings; BST review week explicitly assigns 5 PDFs and 5 videos as prerequisite reading/watching.
pages/cscd320-course-schedule.html
Backtracking, BFS/DFS, and topological sort lectures train students to recognize state-space objects (nodes/edges/visited/colors) and the actions (relax, enqueue, recurse) at each step.
files/lecture material/slides_graph_dfs.pdf;files/lecture material/slides_backtracking.pdf;files/lecture material/slides_graph_bfs.pdf
Students choose an algorithm-design strategy per HW problem and justify the choice in writing; programming assignments require resolving design trade-offs (e.g., heap vs sort for prog2 top-k).
files/homeworks/hw5.pdf;files/homeworks/prog2.pdf
Students balance overlapping HW and prog deadlines (prog1 due same week as hw2; prog3 same week as hw6) across an 11-week quarter with sharp non-late-accepted deadlines.
assignments.json
Students implement information-processing algorithms: sorting, selection, top-k retrieval over large datasets, matrix-chain optimization, and graph traversals on adjacency-list inputs.
files/homeworks/prog1.pdf;files/homeworks/prog2.pdf;files/homeworks/prog3.pdf;files/homeworks/prog4.pdf
Several HW problems require designing a new algorithm to meet an asymptotic bound rather than reproducing a textbook one; prog2 demands an external-memory adaptation.
files/homeworks/hw2.pdf;files/homeworks/prog2.pdf
Course is built atop CSCD 300 (BST, basic DS); week-of-1/28 schedule explicitly directs review and application of prior knowledge before moving to RBT.
pages/cscd320-course-schedule.html
All four programming assignments are Java implementations submitted to Canvas; students compile, run, and validate output of their algorithm code.
files/homeworks/prog1.pdf;files/homeworks/prog2.pdf;files/homeworks/prog3.pdf;files/homeworks/prog4.pdf
The course's central deliverable is algorithm development: students design algorithms with target asymptotic bounds across HWs and implement nontrivial algorithms (D&C order-statistic, external top-k, DP matrix-chain, DFS topological sort) across progs.
files/homeworks/prog1.pdf;files/homeworks/prog2.pdf;files/homeworks/prog3.pdf;files/homeworks/prog4.pdf;files/homeworks/hw5.pdf
prog2's IRS top-k under memory cap is exactly an operational data-analysis problem: students must analyze input characteristics (size, file layout) and design an algorithm whose memory profile is feasible.
files/homeworks/prog2.pdf
Students validate program output and reason about its empirical running time against the asymptotic bound derived in the analysis section of each prog assignment.
files/homeworks/prog2.pdf;files/homeworks/prog3.pdf
Four Java programming assignments require students to write functioning code submitted to Canvas; rules 4-5 of each prog spec require named author and reasonable commenting.
files/homeworks/prog1.pdf;files/homeworks/prog2.pdf;files/homeworks/prog3.pdf;files/homeworks/prog4.pdf
Students analyze problem inputs and select an algorithmic strategy (D&C, DP, greedy, backtracking) and data structure (heap, RBT, B-tree, adjacency list) that fit the constraints.
files/homeworks/hw5.pdf;files/homeworks/hw6.pdf
prog2 implements top-k retrieval over a tax-payer income file (data retrieval under memory constraint); prog3 implements matrix-chain DP optimization; prog4 implements topological sort of a DAG — all in Java per spec.
files/homeworks/prog2.pdf;files/homeworks/prog3.pdf;files/homeworks/prog4.pdf
Programming assignments include implicit performance tuning: prog2 must handle a memory-bound dataset, requiring algorithmic choices that improve over a naive sort-everything approach.
files/homeworks/prog2.pdf