CT Week 7: Dictionaries

1. The Concept: Key-Value Pairs

Up to this point, we have used Lists to store collections of data. Lists are indexed by integers (0, 1, 2…). Dictionaries allow us to index data using any valid key (usually strings or numbers).

Think of a Dictionary like a real-world dictionary:

• Key: The word you look up.
• Value: The definition you find.

Syntax

• Empty Dictionary: D = {}
• Initialization: Scores = {"Alice": 90, "Bob": 85}
• Access: x = Scores["Alice"] (x becomes 90)
• Update/Insert: Scores["Charlie"] = 95 (Adds new key “Charlie” with value 95)

IMPORTANT

• Keys must be UNIQUE. You cannot have two “Alice” keys.
• Keys are usually Strings or Numbers.
• Values can be ANYTHING (Integers, Strings, Lists, even other Dictionaries).

---

2. Basic Operations

2.1 Accessing and Updating

D = {}
D["ID_1"] = 100    # Insert
val = D["ID_1"]    # Access (val is 100)
D["ID_1"] = 200    # Update (Overwrites 100 with 200)

2.2 Checking Existence (Membership)

Before accessing a key, it’s often safe to check if it exists to avoid errors.

if(key in D){ ... }  # Pythonic
# OR in Pseudocode often:
if(isKey(key, D)) { ... }

In IITM CT Pseudocode, we often just access it or check if(key in D).

2.3 Iterating

You can iterate through keys.

foreach key in keys(D){
    val = D[key]
    # Process key and val
}

---

3. Pattern Bank: Common Dictionary Algorithms

Pattern 1: Frequency Count (The “Histogram” Pattern)

Goal: Count how many times each item appears in a list. Example: Count occurrences of words in a dataset.

Algorithm:

1. Initialize empty dict CountDict = {}.
2. Loop through items.
3. If item is already in dict, increment count.
4. If item is NOT in dict, initialize count to 1.

Pseudocode:

Words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
Freq = {}
 
foreach w in Words{
    if(w in Freq){
        Freq[w] = Freq[w] + 1  # Increment
    }
    else{
        Freq[w] = 1            # Initialize
    }
}
# Result: {"apple": 3, "banana": 2, "cherry": 1}

Pattern 2: Grouping / Bucketing

Goal: Group items based on a property (e.g., group students by “City”). Structure: Key = City, Value = List of Students.

Algorithm:

1. Initialize CityGroups = {}.
2. Loop through students.
3. Get city = Student.City.
4. If city in CityGroups, append student to list: CityGroups[city] = CityGroups[city] ++ [Student.Name].
5. Else, create new list: CityGroups[city] = [Student.Name].

Pseudocode:

foreach X in Table1{
    city = X.City
    name = X.Name
    
    if(city in CityGroups){
        CityGroups[city] = CityGroups[city] ++ [name]
    }
    else{
        CityGroups[city] = [name]
    }
}

Pattern 3: The “Seen” Tracker (Boolean Map)

Goal: Keep track of whether we have seen an item before, or if it satisfies a condition. Example: medalDict from PYQ. Map SeqNo to True if they won all medals.

medalDict = {}
# Logic to populate
if(condition_met){
    medalDict[SeqNo] = True
}
else{
    medalDict[SeqNo] = False
}

---

4. Trace Table: Dictionary Updates

Code:

L = ["A", "B", "A", "C"]
D = {}
foreach x in L{
    if(x in D){
        D[x] = D[x] + 1
    }
    else{
        D[x] = 0  # Note the trap: initialized to 0 here for some reason?
                  # Usually should be 1. Let's trace exactly what's written.
        D[x] = D[x] + 1
    }
}

Trace:

Iteration	x	x in D?	Action	D State (After)
Start	-	-	Init	{}
1	”A”	False	Else: D["A"]=0, then D["A"]=1	{"A": 1}
2	”B”	False	Else: D["B"]=0, then D["B"]=1	{"A": 1, "B": 1}
3	”A”	True	If: D["A"] = 1 + 1	{"A": 2, "B": 1}
4	”C”	False	Else: D["C"]=0, then D["C"]=1	{"A": 2, "B": 1, "C": 1}

---

5. Nested Dictionaries

Values can be dictionaries too! StudentGrades = { "Alice": {"Math": 90, "Physics": 85}, "Bob": {"Math": 70, "Physics": 80} }

Access: StudentGrades["Alice"]["Math"] returns 90.

Pattern: Updating a nested value often requires checking the outer key first.

if("Alice" in StudentGrades){
    StudentGrades["Alice"]["Math"] = 95
}

6. Summary Checklist

• Initialization: D = {}.
• Keys: Unique, usually strings/ints.
• Values: Anything.
• Membership: if(key in D).
• Frequency Pattern: The most common use case. Initialize to 1 if new, increment if exists.
• Grouping Pattern: Value is a List. Initialize to [item] if new, append ++ [item] if exists.

---

🧠 Level Up: Advanced Practice

Question 1: Frequency Count Pattern

Problem: Count occurrences of words in a list L. Logic:

D = {}
For word in L:
    If (isKey(D, word)):
        D[word] = D[word] + 1
    Else:
        D[word] = 1

Result: Dictionary D with word counts.

Question 2: Key Error Trap

Problem: Accessing D["Unknown"] without checking. Result: Error. Fix: Always use isKey(D, k) before accessing, or use a get(k, default) function if available.

Question 3: Inverting a Dictionary

Problem: D = {A: 1, B: 2, C: 1}. Invert to {1: [A, C], 2: [B]}. Logic:

NewD = {}
For key in keys(D):
    val = D[key]
    If (isKey(NewD, val)):
        NewD[val] = NewD[val] ++ [key]
    Else:
        NewD[val] = [key]