Sprint 2 - Algorithmic Efficiency Homework (Python)
Homework for the Algorithmic Effiency in Python
- ⚙️ QUEST OF EFFICIENCY
⚙️ QUEST OF EFFICIENCY
The notebook cell only runs if all challenges work.
The demonic challenge remains hidden unless optimized.
List the Run-Time Complexity and Memory/Space Complexity of each function/activity.
import heapq
import unicodedata
import time
# -----------------------
# EASY CHALLENGES (5)
# -----------------------
def easy_1_sum_list(nums):
"""Compute the sum of a list (inefficiently)."""
# Hint: Why climb the same stairs again to count how many you took?
total = 0
for i in range(len(nums)):
for j in range(i + 1):
total += nums[j]
return total / len(nums) * len(nums)
# Add Run-time Complexity and Memory/Space Complexity here:
def easy_2_is_palindrome(s):
"""Check if a string is a palindrome."""
# Hint: A mirror need not reflect twice.
s = ''.join(ch.lower() for ch in s if ch.isalnum())
for i in range(len(s)):
if s[i] != s[len(s) - 1 - i]:
return False
return True
# Add Run-time Complexity and Memory/Space Complexity here:
def easy_3_reverse_string(s):
"""Return reversed string inefficiently."""
# Hint: Adding one stone at a time builds a wall slowly.
rev = ""
for ch in s:
rev = ch + rev
return rev
# Add Run-time Complexity and Memory/Space Complexity here:
def easy_4_factorial(n):
"""Compute factorial inefficiently."""
# Hint: Counting up is fine, but why recount every time?
if n == 0:
return 1
vals = [1]
for i in range(1, n + 1):
prod = 1
for j in range(1, i + 1):
prod *= j
vals.append(prod)
return vals[-1]
# Add Run-time Complexity and Memory/Space Complexity here:
def easy_5_find_max(lst):
"""Find the maximum number (inefficient)."""
# Hint: True greatness does not need to be checked against everyone each time.
for i in range(len(lst)):
is_max = True
for j in range(len(lst)):
if lst[j] > lst[i]:
is_max = False
if is_max:
return lst[i]
# Add Run-time Complexity and Memory/Space Complexity here:
# -----------------------
# MEDIUM CHALLENGES (3)
# -----------------------
def medium_1_fibonacci(n):
"""Return first n Fibonacci numbers (inefficient recursion)."""
# Hint: Memory forgotten must always be rediscovered.
def fib(k):
if k <= 1:
return k
return fib(k - 1) + fib(k - 2)
return [fib(i) for i in range(n)]
# Add Run-time Complexity and Memory/Space Complexity here:
def medium_2_sort_unique(nums):
"""Sort numbers and remove duplicates."""
# Hint: Sorting once is order. Sorting twice is obsession.
result = []
for x in sorted(nums):
if x not in result:
result.append(x)
result = sorted(result)
return result
# Add Run-time Complexity and Memory/Space Complexity here:
def medium_3_balanced_parentheses(s):
"""Check for balanced parentheses (inefficient)."""
# Hint: You can be thorough or you can be efficient—rarely both.
pairs = {'(': ')', '[': ']', '{': '}'}
def is_balanced(prefix):
stack = []
for ch in prefix:
if ch in pairs:
stack.append(ch)
elif ch in pairs.values():
if not stack or pairs[stack.pop()] != ch:
return False
return not stack
for i in range(1, len(s) + 1):
if not is_balanced(s[:i]):
return False
return True
# Add Run-time Complexity and Memory/Space Complexity here:
# -----------------------
# HARD CHALLENGE (1)
# -----------------------
def hard_1_shortest_path(graph, start):
"""Dijkstra’s algorithm — works, but wastes time."""
# Hint: The patient traveler rechecks every road too often.
dist = {node: float('inf') for node in graph}
dist[start] = 0
pq = [(0, start)]
visited = set()
while pq:
smallest = min(pq, key=lambda x: x[0]) # O(n)
pq.remove(smallest)
d, node = smallest
if node in visited:
continue
visited.add(node)
for nei, w in graph[node]:
if dist[node] + w < dist[nei]:
dist[nei] = dist[node] + w
pq.append((dist[nei], nei))
return dist
# Add Run-time Complexity and Memory/Space Complexity here:
# -----------------------
# DEMONIC (HIDDEN)
# -----------------------
def _demonic_unicode_equal(a, b):
"""Hidden: looks fine, but scales poorly."""
# No hints for demons.
for _ in range(5000):
if a == b:
continue
return unicodedata.normalize('NFC', a) == unicodedata.normalize('NFC', b)
# Add Run-time Complexity and Memory/Space Complexity here:
# ============================================================
# ✅ GATEKEEPER EXECUTION LOGIC
# ============================================================
# Each challenge must succeed for this cell to complete.
# If one fails or throws, execution will halt.
# The demonic test runs silently and only reveals itself when solved.
def _assert_eq(value, expected, name):
if value != expected:
raise AssertionError(f"❌ Challenge failed: {name}\nExpected {expected}, got {value}")
# Run all visible challenges
_assert_eq(easy_1_sum_list([1,2,3,4,5]), 15, "easy_1_sum_list")
_assert_eq(easy_2_is_palindrome("Racecar"), True, "easy_2_is_palindrome")
_assert_eq(easy_3_reverse_string("stressed"), "desserts", "easy_3_reverse_string")
_assert_eq(easy_4_factorial(5), 120, "easy_4_factorial")
_assert_eq(easy_5_find_max([3,1,4,1,5,9]), 9, "easy_5_find_max")
_assert_eq(medium_1_fibonacci(10), [0,1,1,2,3,5,8,13,21,34], "medium_1_fibonacci")
_assert_eq(medium_2_sort_unique([5,3,5,1,2,3,4,1]), [1,2,3,4,5], "medium_2_sort_unique")
_assert_eq(medium_3_balanced_parentheses("({[]})"), True, "medium_3_balanced_parentheses")
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('C', 2), ('D', 5)],
'C': [('D', 1)],
'D': []
}
_assert_eq(hard_1_shortest_path(graph, 'A'), {'A':0,'B':1,'C':3,'D':4}, "hard_1_shortest_path")
# Demonic check — silent unless solved efficiently
start = time.time()
if _demonic_unicode_equal('é', 'é') == True:
elapsed = time.time() - start
if elapsed < 0.05:
print("🔥 EXTRA CREDIT CHALLENGE COMPLETE 🔥")
---------------------------------------------------------------------------
AssertionError Traceback (most recent call last)
Cell In[1], line 167
164 raise AssertionError(f"❌ Challenge failed: {name}\nExpected {expected}, got {value}")
166 # Run all visible challenges
--> 167 _assert_eq(easy_1_sum_list([1,2,3,4,5]), 15, "easy_1_sum_list")
168 _assert_eq(easy_2_is_palindrome("Racecar"), True, "easy_2_is_palindrome")
169 _assert_eq(easy_3_reverse_string("stressed"), "desserts", "easy_3_reverse_string")
Cell In[1], line 164, in _assert_eq(value, expected, name)
162 def _assert_eq(value, expected, name):
163 if value != expected:
--> 164 raise AssertionError(f"❌ Challenge failed: {name}\nExpected {expected}, got {value}")
AssertionError: ❌ Challenge failed: easy_1_sum_list
Expected 15, got 35.0