CS1010X Review 06 and Tutorial 03 (Repeat) on 21 Feb 2026 (Sat) [Transcript]
Summary:
The meeting covered programming concepts including data abstraction, list operations, parameter passing methods in Python, and time/space complexity analysis for various algorithms, with focus on recursive functions, Fibonacci sequences, and taxi fare calculations.
From 00:00: Data Abstraction: Tuples vs Lists
Tan conducted a review session on data abstraction, focusing on similarities and differences between tuples and lists. Key points included the immutability of tuples versus the mutability of lists, and how this affects their usage in programming. Tan emphasized choosing the appropriate data structure for specific tasks, covered their use in recursion, and demonstrated methods like count and index on tuples.
From 13:12: Python List Operations
Tan and Chen discussed Python list operations, focusing on how different methods modify lists and return values. They explored append, remove, pop, insert, and reverse operations. Chen clarified that append and remove don't return values, while pop does, and insert adds an element at a specified position while shifting other elements.
From 24:58: Parameter Passing Methods
Tan explained the differences between passing parameters by value, by reference, and by object reference in Python, using examples with tuples, strings, and lists. He demonstrated how these passing methods affect variables inside and outside functions, particularly highlighting the behavior of mutable objects like lists, and walked through a recursive multiplication example.
From 39:06: Recursive Function Complexity Analysis
Tan led a discussion on recursive functions and their time and space complexity, explaining four versions of a solution and highlighting trade-offs between time complexity, space complexity, and side effects. Tan announced he would post the code examples for reference and encouraged further exploration. The session concluded with Tan handing over to Junjie for the next tutorial.
From 54:05: Recursion and Counting Change
Chan led a tutorial on recursion, iteration, and orders of growth, focusing on the counting change problem. They discussed drawing a tree representing counting change for 11 cents with five denominations (1, 5, 10, 25, and 50 cents), explained base cases and recursive calls, and walked through valid and invalid counting paths before addressing time and space complexity.
From 01:11:14: Exponential Recursive Function Complexity
Zhuo and Chan discussed time and space complexity of an exponential recursive function in the counting change problem. Chan explained that time complexity is O(2^n) because recursive calls double with each increment, while space complexity is O(n) as the maximum call stack size is proportional to input size. They also touched on writing a recursive function for a piecewise mathematical function F(n).
From 01:23:20: Fibonacci Algorithm Complexity
Yanqin explained that a recursive Fibonacci function has O(3^n) time complexity due to three recursive calls, and O(n) space complexity. Yutao described an iterative solution with O(n) time and O(1) space complexity. Chan provided additional insights into iterative solutions using dynamic programming, emphasizing the growth of the results tuple over iterations.
From 01:34:38: Time and Space Complexity Discussion
Chan led a discussion on time and space complexity through code examples. The group analyzed several functions, with Chan clarifying that space complexity for one function was O(N) as the results tuple scales linearly, while time complexity for another involved both N and M, making it O(max(N,M)). The session concluded with an exercise on checking if a number is a Fibonacci number.
From 01:49:56: Algorithm Complexity and Taxi Fare
The meeting focused on Fibonacci number checking and taxi fare calculation. Chan explained O(log N) time complexity for a Fibonacci function through a visual demonstration of exponential growth, and clarified that different logarithmic bases are equivalent in big O notation. Siyuan correctly converted a global variable approach into a higher-order function returning a nested function. For a tuple concatenation problem, the team determined O(N² + NM + M²) time complexity, with Yanqin and Siyuan explaining why tuple concatenation takes O(N) time.
Next Steps:
1. Tan: Post the code examples from the review session next to the review materials so students can download and try it out themselves
2. Students: Review the webpage on pass by value, pass by reference, and pass by object reference to understand the differences among the three methods
3. Students: Check the Python complexity page listed in the forum to understand time complexity of list and dictionary methods
4. Students: Draw out the counting change tree for practice to better understand how the function works
5. Students: Try other examples beyond what was covered in the review session for additional practice