Practice Problems

Theory without practice is incomplete. This article provides interactive problems covering logic, sets, combinatorics, and graphs — test your understanding with quizzes, code challenges, and worked examples.

Section 1: Logic

Quiz — Truth Tables

■ Викторина — 3 вопросов

Q1.What is the truth value of (T → F) ∧ (F → T)?

Q2.Which logical connective has this truth table: TT→T, TF→T, FT→F, FF→T?

Q3.De Morgan's Law: ¬(p ∧ q) is equivalent to...

0/3 отвечено

Practice — Boolean Simplification

Simplify the following boolean expression using logical equivalences:

\lnot(\lnot p \lor q) \lor (p \land q)

Section 2: Sets and Counting

Quiz — Set Operations

■ Викторина — 3 вопросов

Q1.If A = {1,2,3,4} and B = {3,4,5,6}, what is |A ∪ B|?

Q2.How many subsets does a set with 5 elements have?

Q3.C(10, 3) = ?

0/3 отвечено

Code Challenge — Powerset Generator

Write a function that generates the powerset (set of all subsets) of a given set.

▶ Песочницаpython

Редактируемо — измените код выше для экспериментов

Section 3: Combinatorics

The Birthday Problem

What's the probability that in a room of $n$ people, at least two share a birthday?

P(\text{at least one match}) = 1 - \frac{365!}{365^n \cdot (365-n)!}

▶ Песочницаpython

Редактируемо — измените код выше для экспериментов

Section 4: Graphs

Quiz — Graph Properties

■ Викторина — 3 вопросов

Q1.A tree with 10 vertices has how many edges?

Q2.What is the maximum number of edges in a simple undirected graph with 6 vertices?

Q3.Which traversal uses a queue?

0/3 отвечено

Code Challenge — Shortest Path

Implement Dijkstra's algorithm for finding the shortest path in a weighted graph.

▶ Песочницаpython

import heapq

def dijkstra(graph: dict, start: str) -> dict:
  """Find shortest distances from start to all vertices.

graph: dict mapping vertex to list of (neighbor, weight) tuples
  Returns: dict mapping vertex to shortest_distance
  """
  distances = {v: float('inf') for v in graph}
  distances[start] = 0
  pq = [(0, start)]  # (distance, vertex)

while pq:
      dist, u = heapq.heappop(pq)
      if dist > distances[u]:
          continue

for neighbor, weight in graph[u]:
          new_dist = dist + weight
          if new_dist < distances[neighbor]:
              distances[neighbor] = new_dist
              heapq.heappush(pq, (new_dist, neighbor))

return distances

# Example graph
graph = {
  'A': [('B', 4), ('C', 2)],
  'B': [('A', 4), ('C', 1), ('D', 5)],
  'C': [('A', 2), ('B', 1), ('D', 8), ('E', 10)],
  'D': [('B', 5), ('C', 8), ('E', 2)],
  'E': [('C', 10), ('D', 2)],
}

distances = dijkstra(graph, 'A')
print("Shortest distances from A:")
for vertex, dist in sorted(distances.items()):
  print(f"  A -> {vertex}: {dist}")

Редактируемо — измените код выше для экспериментов

Summary

Key takeaways from this practice session:

Logic: Master De Morgan's laws and truth tables — they're the basis of all conditional reasoning
Counting: The multiplication principle, permutations, and combinations appear in algorithm analysis constantly
Graphs: Know both BFS and DFS, understand adjacency representations, and practice shortest-path algorithms
Practice > Theory: The only way to get better is to solve more problems