CS1010X Review 06 and Tutorial 03 (First) on 20 Feb 2026 (Fri) [Transcript]
Summary:
The meeting covered Python data structures, time/space complexity, recursive functions, and dynamic programming. Topics ranged from tuples and lists to algorithm optimization and higher-order functions.
From 01:11: Python Data Structures Overview
Tan discussed data abstraction, focusing on tuples and lists, emphasizing their differences to make informed decisions about time and space complexity. Tuples are immutable while lists are mutable; Tan covered count() and index() methods, noting lists would appear on the upcoming midterm.
From 12:03: Python List Modifications Discussion
Tan and Chenyi explored how modifying list elements affects variables pointing to different parts of the list. Aasher joined to review list operations and the behavior of print vs. return statements in Python.
From 21:57: Python List Operations and Parameters
Tan explained remove, insert, and pop methods, highlighting complexity differences between pop(0) and pop(-1) — both O(n) in Python, though O(1) is theoretically achievable. Tan then introduced parameter passing, covering call by value and call by reference, noting Python only supports call by value.
From 30:21: Python Pass-by-Reference Concepts
Tan explained pass-by-value, pass-by-reference, and pass-by-object-reference. Numbers and strings use pass-by-value, while mutable objects like lists use pass-by-object-reference. Tan also covered Python's memory allocation and garbage collection behavior.
From 41:05: Recursive Function Implementation Analysis
Tan guided the group through four versions of a recursive function calculating a list's product. Versions 1 and 2 had O(N²) time and space complexity due to creating new structures. Version 3 improved time complexity to O(N) by modifying in place. Version 4 resolved a side effect by copying the list within the helper function, preserving the original.
From 53:57: Recursion and Time Complexity Tutorial
Tan explained why the first two examples have O(n²) complexity — recursion involves copying elements, resulting in n-1 total copies. Chan then led a tutorial on recursion and orders of growth, asking students to draw a tree illustrating the coin change process for 11 cents.
From 01:08:55: Dynamic Programming Coin Change Algorithm
Chan explained the dynamic programming approach to coin change. Bruce determined the time complexity to be O(2^n) due to exponential recursive calls, comparing it to Fibonacci. Chan stressed explaining reasoning alongside complexity answers on exams.
From 01:17:43: Recursive Function Complexity Analysis
Junhan explained that space complexity for an exponential function is O(N) since Python frees stack space after each call, with maximum stack depth of N. Chan clarified O notation already implies worst-case. The group then implemented a piecewise mathematical function recursively, with Chan guiding base case implementation.
From 01:25:10: Recursive Function Complexity Analysis
The group analyzed a recursive function F(n) calling itself three times per call, yielding O(3^n) time complexity. Space complexity was O(N) based on maximum call stack depth. Students were encouraged to submit iterative solutions for further discussion.
From 01:33:23: Time and Space Complexity Analysis
Chan and Kendrick confirmed recursive call stack space complexity approximates O(N). Julius presented a list-based solution with O(N) time and space. Chan reinforced the distinction between mutable lists and immutable tuples, inviting alternative approaches.
From 01:41:05: Time and Space Complexity Analysis
Julius and Chan explained that a tuple-based function has O(N²) time complexity due to concatenation, with O(N) space. Kai described a Fibonacci approach using three previous values — O(N) time and O(1) space. Chan then asked for solutions determining whether a number is Fibonacci.
From 01:48:05: Algorithm Complexity Analysis Tutorial
Junhan presented an O(n) time, O(1) space Fibonacci solution; Shinkai offered a formula-based O(1) solution. Chan noted O(n³) or worse is inadequate professionally. The group discussed logarithm base equivalence in Big O and higher-order functions, concluding with a taxi fare problem requiring a function that returns another function.
Next Steps:
1. Tan: Post the codes from the lecture tomorrow after completion
2. Students: Try out the examples shown in lecture themselves to practice working with tuples and lists
3. Students: Read the webpage about passing parameters (call by value, call by reference, call by object reference) on their own
4. Students: Review the reference slides for tuple and list methods when needed
5. Students: Check the forum discussion about whether 2 to the power of n and 3 to the power of n are equivalent time complexities