MC202E - Data Structures

This page contains links to slides and videos from MC202 - Data Structures.

Slides change over time and the link is always to the latest version. Therefore, the slides shown in the videos may not match the actual slides. Also, depending on the semester, the order of some classes may change in relation to the order of videos on YouTube. The site will be maintained in the order that the classes will be taught in the respective semester.

Corrections on links and suggestions for other content are more than welcome!

Index

1. classrooms
   1. Unit 1 - About the Discipline
   2. Unit 2 - C Course - Part 1
   3. Unit 3 - C Course - Part 2
   4. Unit 4 - C Course - Part 3
   5. Unit 5 - C Course - Part 4
   6. Unit 6 - C Course - Part 5
   7. Unit 7 - C Course - Part 6
   8. Unit 8 - Recursion
   9. Unit 9 - Notions of Algorithm Efficiency
   10. Unit 10 - Vectors
   11. Unit 11 - Linked Lists
   12. Unit 12 - Linked List Variations
   13. Unit 13 - Stack and Queue
   14. Unit 14 - Stack Applications
   15. Unit 15 - Binary Trees
   16. Unit 16 - Binary Search Trees
   17. Unit 17 - Red-Black Trees
   18. Unit 18 - Priority and Heap Queues
   19. Unit 19 - Sorting and Heapsort
   20. Unit 20 - Mergesort and Quicksort
   21. Unit 21 - Sorting in Linear Time
   22. Unit 22 - Hashing
   23. Unit 23 - Graphs (representation)
   24. Unit 24 - Graphs (course)
   25. Unit 25 - Graphs (algorithms)
   26. Unit 26 - Backtracking
   27. Unit 27 - B Trees
   28. Unit 28 - Choosing an ED
2. tutorials
3. Interesting Links
4. REFERENCES

classrooms

Unit 1 - About the Discipline

• Slides (handouts)

Unit 2 - C Course - Part 1

• Slides (handouts)
• ADIEX

Unit 3 - C Course - Part 2

• Slides (handouts)
• ADIEX
• Related material:
  • Why Computers are Bad at Algebra
  • Methods of square root computing

Unit 4 - C Course - Part 3

• Slides (handouts)
• ADIEX

Unit 5 - C Course - Part 4

• Slides (handouts)
• ADIEX
• Related material:
  • Wikipedia - Abstract DataType
  • Chapter 4 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick

Unit 6 - C Course - Part 5

• Slides (handouts)
• ADIEX

Unit 7 - C Course - Part 6

• Slides (handouts)
• ADIEX

Unit 8 - Recursion

• Slides (handouts)
• ADIEX
• Related material:
  • Visual: Recursion
  • Recursion Slides in MC102
  • Recursion and recursive algorithms
  • Wikipedia - Recursion
  • Wikipedia - Recursion (computer science)

Unit 9 - Notions of Algorithm Efficiency

• Slides (handouts)
• ADIEX
• Related material
  • Chapter 2 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Chapters 1 and 2 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein
  • Advanced: Chapter 3 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein

Unit 10 - Vectors

• Slides (handouts)
• ADIEX

Unit 11 - Linked Lists

• Slides (handouts)
• ADIEX
• Visualgo - Linked List
• Related material
  • Section 3.3 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Section 10.2 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein

Unit 12 - Linked List Variations

• Slides (handouts)
• ADIEX
• Visualgo - Linked List
• What's a Linked List, Anyway? [Part 1]
• What's a Linked List, Anyway? [Part 2]
• Related material
  • Section 3.4 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick

Unit 13 - Stack and Queue

• Slides (handouts)
• ADIEX
• Stacks and Overflows
• To Queue Or Not To Queue
• Related material
  • Sections 4.1 to 4.6 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Section 10.1 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein

Unit 14 - Stack Applications

• Slides (handouts)
• ADIEX
• Related material
  • Sections 4.1 to 4.4 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Section 10.1 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein

Unit 15 - Binary Trees

• Slides (handouts)
• Video - Part 1
• Video - Part 2
• How Not To Be Stumped By Trees
• Related material
  • Chapter 12 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Chapter 12 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein

Unit 16 - Binary Search Trees

• Slides (handouts)
• ADIEX
• Leaf It Up To Binary Trees
• Related material
  • Chapter 12 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Chapter 12 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein

Unit 17 - Red-Black Trees

• Slides (handouts)
• ADIEX
• Painting Nodes Black With Red-Black Trees
• Related material
  • Chapter 3 of “Algorithms - Fourth Edition” - R. Sedgewick

Unit 18 - Priority and Heap Queues

• Slides (handouts)
• ADIEX
• Visualgo - Binary Heap
• Learning to Love Heaps
• Related material
  • Chapter 9 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Chapter 6 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein

Unit 19 - Sorting and Heapsort

• Slides (handouts)
• Visualgo - Ordering
• Visualgo - Binary Heap
• Learning to Love Heaps
• Sorting Out The Basics Behind Sorting Algorithms
• Exponentially Easy Selection Sort
• Bubbling Up With Bubble Sorts
• Inching Towards Insertion Sort
• Heapify All The Things With Heap Sort
• Ordering and Dance Algorithms:
  • Select-sort with Gypsy folk dance
  • Bubble-sort with Hungarian (“Csángó”) folk dance
  • Insert-sort with Romanian folk dance
  • HEAP-sort with Hungarian (MEZŐSÉGI) folk dance
• Related material
  • Chapter 6 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Chapter 9 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Chapter 2 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein
  • Chapter 6 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein

Unit 20 - Mergesort and Quicksort

• Slides (handouts)
• ADIEX
• Visualgo - Ordering
• Making Sense of Merge Sort [Part 1]
• Making Sense of Merge Sort [Part 2]
• Pivoting To Understand Quicksort [Part 1]
• Pivoting To Understand Quicksort [Part 2]
• Ordering and Dance Algorithms:
  • Quick-sort with Hungarian (Küküllőmenti legényes) folk dance
  • Merge-sort with Transylvanian-Saxon (German) folk dance
• Related material
  • Chapter 7 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Chapter 7 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein
  • Chapter 8 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Section 2.3 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein

Unit 21 - Sorting in Linear Time

• Slides (handouts)
• ADIEX
• Counting Linearly With Counting Sort
• Getting To The Root Of Sorting With Radix Sort

Unit 22 - Hashing

• Slides (handouts)
• ADIEX
• Taking Hash Tables Off The Shelf
• Hashing Out Hash Functions
• Related material
  • Chapter 14 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Chapter 11 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein

Unit 23 - Graphs (representation)

• Slides (handouts)
• ADIEX
• From Theory To Practice: Representing Graphs
• Related material
  • Chapter 17 of “Algorithms in C - Part 5 - Third Edition” - R. Sedgewick
  • Section 3.7 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Section 22.1 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein

Unit 24 - Graphs (course)

• Slides (handouts)
• ADIEX
• Deep Dive Through A Graph: DFS Traversal
• Going Broad In A Graph: BFS Traversal
• Related material
  • Chapter 18 of “Algorithms in C - Part 5 - Third Edition” - R. Sedgewick
  • Section 5.8 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Sections 22.2 and 22.3 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein

Unit 25 - Graphs (algorithms)

• Slides (handouts)
• ADIEX
• Spinning Around In Cycles With Directed Acyclic Graphs
• Finding The Shortest Path, With A Little Help From Dijkstra
• Related material:
  • Sections 19.1 to 19.6, 21.1 and 21.2 of “Algorithms in C - Part 5 - Third Edition” - R. Sedgewick
  • Chapter 14 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Sections 22.4 and 24.3 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein

Unit 26 - Backtracking

• Slides (handouts)
• ADIEX
• Related material:
  • Chapter 12 of “Algorithms in C language” - Paulo Feofiloff

Unit 27 - B Trees

• Slides (handouts)
• ADIEX
• Busying Oneself With B-Trees
• Related material:
  • Chapter 18 of “Introduction to Algorithms - Second Edition” - T. Cormen, C. Leiserson, R. Rivest and C. Stein

Unit 28 - Choosing an ED

• Slides (handouts)
• Video (from 2s2017)
• Choosing an ED in C ++

tutorials

• Valgrind Tutorial
• GDB Tutorial
• git tutorial

Interesting Links

• visualgo - Animations of algorithms and data structures
• Course Algorithms KhanAcademy
• An ongoing series of nonverbal algorithm assembly instructions

REFERENCES

The main bibliography for the course is the book “Algorithms in C - Third Edition” by R. Sedgewick. Another interesting book is “Introduction to Algorithms - Third Edition” by Cormen, Leiserson, Rivest and Stein. Other books can be found in the Discipline Development Plan.