Lecture notes for Week 4: Pointers & Dynamic Allocation

1. Linked lists

2. Reference (pointer) implementations

3. Memory allocation and freeing

Textbook portions covered

Introduction to Algorithms (Cormen et al.)

Chapter 10 Sections 2 and 3

Engineering Algorithms...(Clowes “online book”)

Appendix B (Data Structures, Memory and Pointers)

Announcements

• Problem set available in course directory (ProbSet1-2003.pdf).

• firefox http://www.mozilla.org/products/firefox

• Reduced counselling next Tuesday (unavail 11:00-11:30)

• Lab 4 now available.

Solving Recurrences (continued)

Substitution method

Recurrence Tree method

Data Structures

Pointers

Announcements

Introduction to Algorithms (Cormen et al.)

• Exercise 10.3-1
• Exercise 10.3-3

Engineering Algorithms...(Clowes “online book”)

• B.2
• B.3
• B.4