MC202 - Data Structures - 2s2018

• Teacher: Rafael CS Schouery
  • rafael@ic.unicamp.br
  • Room 74 - Institute of Computing
• Theoretical classes: Tuesdays at 21pm and Thursdays at 19pm on CB12
• Practical classes: Saturdays at 10 am, rooms 303 and 304 of IC3
• Monitoring: Wednesdays, Thursdays and Fridays, at 13 pm and 18 pm at SI04

Class Material

Unit 30 - Choosing an ED (29/11)

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

Unit 29 - B Trees (27/11)

• Slides
• Institutional
• 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 - Graphs (algorithms) (22/11)

• Slides
• Institutional
• 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 27 - Graphs (route) (13/11)

• Slides
• Institutional
• 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 26 - Graphs (representation) (08/11)

• Slides
• Institutional
• 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 25 - Exercises (06/11)

• Slides

Unit 24 - Hashing (01/11)

• Slides
• Institutional
• 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 - Mergesort and Quicksort (30/10)

• Slides
• Institutional
• 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]
• 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 22 - Ordination and Heapsort (23/10)

• Slides
• 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
• 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 21 - Priority and Heap Queues (16/10)

• Slides
• Institutional
• 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 20 - Exercises (11/10)

• Slides

Unit 19 - Red-Black Trees (09/10)

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

Unit 18 - Binary Search Trees (04/10)

• Slides
• Leaf It Up To Binary Trees
• Institutional
• 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 - Binary Trees (02/10 and 04/10)

• Slides
• 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 - Exercises (27/09)

• Slides

Unit 15 - Battery Applications (25/09)

• Slides
• Institutional
• 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 14 - Stack and Row (20/09)

• Slides
• Institutional
• 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 13 - Variations of Linked Lists (18/09)

• Slides
• Institutional
• 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 12 - Linked Lists (13/09)

• Slides
• Institutional
• 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 11 - Exercises (11/09)

• Slides

Unit 10 - Notions of Algorithm Efficiency (06/09)

• Slides
• Institutional
• 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 9 - Backtracking (04/09)

• Slides
• Institutional
• Related material:
  • Chapter 12 of “Algorithms in C language” - Paulo Feofiloff

Unit 8 - Recursion (28/08)

• Slides
• Institutional
• Related material:
  • Class Slides 27 e 28 MC102 (in C)
  • Recursion and recursive algorithms
  • Wikipedia - Recursion
  • Wikipedia - Recursion (computer science)

Unit 7 - C Course - Part 6 (23/08)

• Slides
• Institutional
• Related material:
  • Going from Python to C

Unit 6 - C Course - Part 5 (21/08)

• Slides
• Institutional
• Related material:
  • Going from Python to C

Laboratory 3 - Debugging (18/08)

• Slides
• Related material:
  • Valgrind Tutorial

Unit 5 - C Course - Part 4 (16/08)

• Slides
• Institutional
• Related material:
  • Going from Python to C
  • Chapter 4 of “Algorithms in C - Parts 1-4 - Third Edition” - R. Sedgewick
  • Wikipedia - Abstract DataType

Unit 4 - C Course - Part 3 (14/08)

• Slides
• Institutional
• Related material:
  • Going from Python to C

Laboratory 2 - Virtual Machine (11/08)

• Slides
• Linux Virtual Machine

Unit 3 - C Course - Part 2 (09/08)

• Slides
• Institutional
• Related material:
  • Going from Python to C

Unit 2 - C Course - Part 1 (07/08)

• Slides
• Institutional
• Related material:
  • Why Computers are Bad at Algebra
  • Methods of square root computing
  • Going from Python to C

Unit 1 - About the Discipline (02/08)

• Slides
• Institutional
• Related material:
  • Discipline Development Plan
  • Going from Python to C
  • Diagnostic Evaluation

Info

• Notes and Frequency Worksheet
• Course page on SuSy
• Discipline Development Plan
• Course discussion list (Apply as soon as possible)
• Send questions to the monitors only by email monitors-mc202@googlegroups.com
• Monitors
  • Leandro Augusto Fernandes de Magalhães (PAD - GH Classes)
  • Lucas Borges Rondon (PED - EF Classes)
  • Miguel Antonio Rodríguez Santander (PED - GH Classes)
  • Pedro Terra Delboni (PED - GH Classes)
  • Rafael Sartori Martins Dos Santos (PAD - EF Classes)
  • Welverton Rodrigues da Silva (PED - EF Classes)

Useful / Interesting Links

• Going from Python to C
  • Material developed by Prof. Lehilton thinking about MC202 students
• Diagnostic Evaluation
• Linux Virtual Machine
• Valgrind Tutorial
• Passing Susy's test on your computer
• visualgo - Animations of algorithms and data structures
• Course Algorithms KhanAcademy
• An ongoing series of nonverbal algorithm assembly instructions

Calendar

• Start: 02/08
• Exam: 11/12
• We will not have class on 30/08 (I will be at an event)
• We will not have class on 08/09 (holiday)
• We will not have class on 13/10 (holiday)
• We will not have class on 18/10 (Scientific Initiation Congress)
• We will not have class on 25/10 (I will be at an event) new
• We will not have class on 15/11 (holiday)
• We will not have class on 17/11 (holiday)
• We will not have class on 20/11 (holiday)

SECOMP participants will be paid absenteeism

• Provided they present proof

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.