knoxelhub
Explore the published course outline by module or academic week.
Lectures 1-3 (3 contact hours): iterative integer multiplication, iterative code analysis, and asymptotic analysis. CLO mappings are provisional and apply to instructional topics. The eight-week plan covers 24 lectures of one hour each.
Grade-school multiplication, input-size identification, digit operations, and operation counting. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO2. Book references: AI1: Sections 1.2, 1.6; CLRS: Section 2.2.
Analysis of sequential, nested, dependent-bound, and logarithmic loops using operation counts and summations. Duration: 1 contact hour. Provisional CLO mapping: CLO1. Book references: CLRS: Section 2.2, Appendix A.1.
Big O, Big Omega, Big Theta, growth-rate comparisons, and best-, average-, and worst-case analysis. Duration: 1 contact hour. Provisional CLO mapping: CLO1. Book references: CLRS: Sections 3.1-3.3; AI1: Chapter 2.
Usage of algorithms and data structures in real life
Lectures 4-6 (3 contact hours): Insertion sort and loop invariants; Selection sort and bubble sort; Merge sort. Provisional CLO mappings apply to instructional topics.
Insertion-sort procedure and correctness using initialization, maintenance, and termination of a loop invariant. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO2. Book references: CLRS: Sections 2.1-2.2.
Sorting procedures, comparison and swap counts, stability, and running-time analysis. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO2. Book references: CLRS: Exercise 2.2-2; Chapter 2 problem on bubble-sort correctness.
Divide-and-conquer sorting, merging, recurrence formulation, correctness, and auxiliary-space requirements. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO2. Book references: CLRS: Section 2.3; AI1: Sections 1.4-1.5.
Lectures 7-9 (3 contact hours): Recursive integer multiplication and Karatsuba; Recurrence solving through substitution and recursion trees; Master theorem. Provisional CLO mappings apply to instructional topics.
Conventional recursive multiplication, Karatsuba's reduction in recursive products, and recurrence formulation. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO2. Book references: AI1: Sections 1.3, 4.1.
Inductive verification of bounds and calculation of work across recursion-tree levels. Duration: 1 contact hour. Provisional CLO mapping: CLO1. Book references: CLRS: Sections 4.3-4.4; AI1: Section 1.5.
Identification of recurrence parameters, application of theorem cases, and applicability conditions. Duration: 1 contact hour. Provisional CLO mapping: CLO1. Book references: CLRS: Section 4.5; AI1: Sections 4.1-4.3.
Lectures 10-12 (3 contact hours): Iterative and recursive matrix multiplication; Strassen's matrix multiplication; Hybrid sorting; Quiz 1. Provisional CLO mappings apply to instructional topics.
Conventional matrix multiplication, block decomposition, recursive computation, and complexity analysis. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO2. Book references: CLRS: Section 4.1.
Seven-product recursive multiplication, block reconstruction, recurrence analysis, and computational tradeoffs. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO2. Book references: CLRS: Section 4.2; AI1: Section 3.3.
Combination of merge sort and insertion sort using a cutoff for small subarrays; Quiz 1. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO3. Book references: CLRS: Sections 2.1, 2.3; Chapter 2 problem on insertion sort within merge sort. The CLO mapping applies to the instructional topic. Quiz assessment mapping requires the corresponding question paper.
Lectures 13-15 (3 contact hours): Quicksort; Randomized quicksort; K-select through Quickselect; Quiz 2. Provisional CLO mappings apply to instructional topics.
Partitioning, partition correctness, recursive sorting, and balanced versus unbalanced partitions. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO2. Book references: CLRS: Sections 7.1-7.2; AI1: Sections 5.1-5.3.
Random pivot selection, expected running time, worst-case behavior, and the effect of pivot choice. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO2. Book references: CLRS: Sections 7.3-7.4; AI1: Sections 5.4-5.5.
Partition-based selection of the kth smallest element, rank adjustment, and selective recursion; Quiz 2. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO2. Book references: CLRS: Section 9.2; AI1: Section 6.1. The CLO mapping applies to the instructional topic. Quiz assessment mapping requires the corresponding question paper.
Lectures 16-18 (3 contact hours): Quickselect analysis and counting sort; Radix sort; Bucket sort; assignment idea discussion and selection. Provisional CLO mappings apply to instructional topics. Assignment discussions cover idea selection and scope clarification only.
Selection complexity; frequency counting, cumulative counts, stable placement, and key-range requirements in counting sort. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO2. Book references: CLRS: Sections 9.2, 8.2; AI1: Section 6.2.
Digit-wise sorting, stable intermediate passes, and complexity in terms of digit count and radix. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO2. Book references: CLRS: Section 8.3.
Bucket distribution, sorting within buckets, and distribution assumptions; discussion and selection of assignment ideas. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO3. Book references: CLRS: Section 8.4. Assignment-related discussions were limited to idea selection and clarification of the proposed assignment scope. The CLO mapping applies to the instructional topic; assignment discussion is recorded as a class activity.
Lectures 19-21 (3 contact hours): Linked lists; Stacks; Queues; assignment idea discussion and selection. Provisional CLO mappings apply to instructional topics. Assignment discussions cover idea selection and scope clarification only.
Singly and doubly linked lists, traversal, insertion, deletion, pointer updates, and operation costs. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO2. Book references: CLRS: Section 10.2.
LIFO behavior, stack operations, array and linked implementations, and boundary conditions. Duration: 1 contact hour. Provisional CLO mapping: CLO2. Book references: CLRS: Section 10.1.
FIFO operations, circular-array and linked implementations, and boundary conditions; clarification of assignment ideas and scope. Duration: 1 contact hour. Provisional CLO mapping: CLO2, CLO3. Book references: CLRS: Section 10.1. Assignment-related discussions were limited to idea selection and clarification of the proposed assignment scope. The CLO mapping applies to the instructional topic; assignment discussion is recorded as a class activity.
Lectures 22-24 (3 contact hours): Real-world applications of stacks and queues; Hash tables and separate chaining; Open addressing; assignment idea discussion and selection. Provisional CLO mappings apply to instructional topics. Assignment discussions cover idea selection and scope clarification only.
Applications in expression processing, undo operations, buffering, and service scheduling. Duration: 1 contact hour. Provisional CLO mapping: CLO3, CLO4. Book references: CLRS: Section 10.1 for underlying structures; class notes for applications.
Dictionary operations, hash functions, collisions, chaining, load factor, and lookup complexity. Duration: 1 contact hour. Provisional CLO mapping: CLO1, CLO2. Book references: CLRS: Sections 11.1-11.3; AI2: Sections 12.1-12.3.
Collision resolution through probing, deletion handling, and resizing; discussion and selection of assignment ideas. Duration: 1 contact hour. Provisional CLO mapping: CLO2, CLO3. Book references: CLRS: Sections 11.4-11.5; AI2: Sections 12.3-12.4. Assignment-related discussions were limited to idea selection and clarification of the proposed assignment scope. The CLO mapping applies to the instructional topic; assignment discussion is recorded as a class activity.
Files, textbooks, presentations, and external links.