Week #02
	Pedro Ribeiro - DCC/FCUP

Main learning outcomes for this class

1. Big O Notation:
   • I understand the basic meaning of Big O Notation
   • I know how to estimate the complexity of simple programs and how to use it to estimate if my program will not obtain time limit exceeded when submitted
2. Fundamental Data Structures:
   • I know the concept of stacks, queues and deques and how to use them on my programming language
   • I know the concept of sets (set and multiset) and how to use them on my programming language
   • I know the concept of maps/dictionaries (map and multimap) and how to use them on my programming language
   • I know the concept of priority queues (priority_queue) and how to use them on my programming language
   • I understand the concept of ordered data structures and how to traverse them using iterators
   • I know that there are non ordered data structures for the fundamental data structures (ex: unordered_set and unordered_map)
3. Fast I/O:
   • I understand that some problems might require a lot of input and/or output and therefore need efficient I/O primitives
   • I know how to perform fast IO on my preferred language

Study Material

• Big O Notation
  • How fast is fast? Order of magnitude analysis [Bruce Merry] (brief introduction to big-oh notation)
  • Big O notation [Wikipedia]
  • Slides from my Design and Analysis of Algorithms class [Pedro Ribeiro, in portuguese 🇵🇹] (video lectures) [similar slides in english 🇬🇧, for my Algorithms class]
  • Doing the math with big o: cheat sheet [Pedro Ribeiro]
  • Chapter 2 of Competitive Programmer's Handbook book
• Programming Language References
  • C++ Reference: cppreference.com | cplusplus.com | devdocs.io
  • Java Reference: Oracle - Java 19 API
• Fundamental Data Structures:
  • cppreference containers library
  • The C++ Standard Template Library (STL) [GeeksforGeeks] (includes examples in C++ for all data structures discussed in this class)
  • Java Collection Tutorial (version 2) [GeeksforGeeks] (includes examples in Java for all data structures discussed in this class)
  • Sections 2.1 and 2.2 of the Competitive Programming book
  • Chapter 4 of Competitive Programmer's Handbook book
• Fast I/O:
  • Fast Reading and Printing for C, C++ and Java [Pedro Ribeiro, in Portuguese 🇵🇹]
    (note: FastScanner and FastPrint are available at Mooshak, no need to include their code)
  • Fast Input & Output for C++ and Java [USACO]
  • Fast I/O for Competitive Programming in Python [GeeksforGeeks]

I want my memes!

Pedro Ribeiro - DCC/FCUP | Last update: