Assignment Chef icon Assignment Chef
All English tutorials

Programming lesson

Mastering Python Lists, Shifts, and Vector Class: A Data Structures Tutorial (NYU CS-UY 1134 Spring 2024 HW1)

Learn how to draw memory images for Python lists, implement an efficient shift function, and build a custom Vector class with operator overloading. This tutorial breaks down key concepts from NYU's CS-UY 1134 Spring 2024 Homework #1 using clear examples and timely analogies.

NYU CS-UY 1134 homework 1 Python list memory image shift function Python Vector class Python operator overloading Python Python __getitem__ Python __add__ dot product Python data structures tutorial Python list mutation list rotation algorithm Python O(N) shift Python negative indexing CS-UY 1134 spring 2024 Python homework help

Understanding Python Lists and Memory Images

When you write code like lst1 = [1, 2, 3], Python creates a list object in memory. References matter: lst2 = [lst1 for i in range(3)] creates a list of three references to the same lst1 object. So lst2[0][0] = 10 modifies the shared list, and print(lst2) outputs [[10, 2, 3], [10, 2, 3], [10, 2, 3]]. This is a classic pitfall—similar to how sharing mutable objects in AI model state can cause unexpected side effects.

Drawing the Memory Image

To visualize: lst1 points to a list [1, 2, 3]. lst2 is a list of three slots, each pointing to the same list as lst1. After assignment, the first element of that list becomes 10. All three references see the change.

Efficient Shift Function

Write a function shift(lst, k) that rotates a list left by k positions. The challenge: do it in O(N) time and O(1) extra space. A common approach is to reverse sublists. For example, shift([1,2,3,4,5], 2) yields [3,4,5,1,2]. This is like rotating a playlist on Spotify—efficiently reordering without copying the whole list.

Implementation Steps

  1. Reverse the entire list.
  2. Reverse the first N-k elements.
  3. Reverse the last k elements.

Check edge cases: k may be larger than N; use k %= N. Also handle empty lists.

Building a Vector Class with Operator Overloading

Implement a Vector class that supports indexing (positive and negative), addition, negation, scalar multiplication (both sides), and dot product. Use __getitem__, __setitem__, __add__, __neg__, __mul__, and __rmul__.

Constructor and Indexing

Initialize from an integer (size) or a list. For negative indices, convert to positive: if index < 0: index += len(self.data). This is similar to how TikTok's video queue handles wrap-around indexing.

Operator Overloading Examples

  • Addition: v1 + v2 returns a new Vector with element-wise sum. Raise exception if lengths differ.
  • Negation: -v2 returns a Vector with negated elements.
  • Scalar Multiplication: 3 * v2 and v2 * 3 both multiply each element. Use __rmul__ for left multiplication.
  • Dot Product: v1 * v2 returns scalar sum of products. This is key in machine learning for similarity computations.

Testing Your Implementation

v1 = Vector(5)
v1[1] = 10
v1[-1] = 10
print(v1)  # [0, 10, 0, 0, 10]
v2 = Vector([2, 4, 6, 8, 10])
print(v2)  # [2, 4, 6, 8, 10]
u1 = v1 + v2
print(u1)  # [2, 14, 6, 8, 20]
u2 = -v2
print(u2)  # [-2, -4, -6, -8, -10]
u3 = 3 * v2
print(u3)  # [6, 12, 18, 24, 30]
u4 = v2 * 3
print(u4)  # [6, 12, 18, 24, 30]
u5 = v1 * v2
print(u5)  # 140

Common Mistakes and Tips

  • Mutable default arguments: avoid def __init__(self, data=[]); use None and assign inside.
  • Negative index conversion: always compute index % len(self.data) for safety.
  • Dot product: ensure lengths match; use zip for clarity.

This homework builds foundational skills for data structures like stacks, queues, and graphs. Master these patterns—they appear in coding interviews and real-world apps like recommendation systems (dot products) and playlist shuffling (shift).