15-112 Agenda 11-June

• Nice work on the midterm :)
• Upcoming homework + all homeworks are in as placeholders
• String slicing
  • range(start,end,step)
    • step defaults to 1
    • start defaults to 0
    • end defaults to len(s)
  • Convert negative indexes to their positive equivs. Don’t covert step.
  • Constraints:
    • i >= 0
    • if pos: i < stop
    • if neg: i > stop
  • range is automatically empty if start does not meet constraint.

s = "abc"
print(s[-1:0:1])
print(s[-1:0:-1])
print(s[-1:])
print(s[-1:1])

• Cool Coding Thing of the Day:
  • Unix –> Linux + Mac
  • Getting Linux
  • Why use it and who uses it?
    • Specialized distributions
      • https://en.wikipedia.org/wiki/Damn_Small_Linux
      • https://www.kali.org/
      • https://www.scientificlinux.org/
    • Good security
    • Light and fast
    • Free
• Learning today:
  • Two new ways to store data
    • Sets: fast, unique elements, unordered
    • Dictionaries: key -> value
• 3 Types of Problems
  • Line by line analysis of the runtime of code
  • Use sets + dictionaries
  • Do some problem solving to make something efficient (maybe use sets in dictionaries, maybe just be clever)
• Content
  • Sets
    • What is a set?
    • Example + Syntax
      • Making a set
      • .add(), in , .remove(), len(s)
      • looping through a set
      • intersection, update, etc: learn on your own if needed
      • Can’t index (see below)
    • Properties:
      • Unordered
      • Elements unique
      • Elements must be immutable
    • Very effecient
  • Dictionaries
    • What is a dictionary?
    • Example + Syntax
      • Making a dictionary: dict(), {'a':'b', 'b':'c'}
      • Key vs Value
      • in, d[key], d[key] = ...
      • len(d), .get(key, default), del
      • Looping through dictionaries
    • Properties:
      • Keys are just like sets
      • Values are unrestricted
    • Very efficient
  • getCounts(L)
  • hasRepeats(L)
  • BigOH
    • What is it?
      • Function from input size to number of steps
    • Some examples
      • O(n): findMax
      • O(1): getFirstElem
      • O(n^2): getHighestCount
      • O(nlog(n)) digitCount
    • Figuring out what your input size is:
      • Strings
      • Lists
      • Numbers
        • Why is the length of a number log(n)?
    • We don’t care about constants
    • bigOHFamilies
    • bigOH of Everything we’ve used so far (see table in notes)
      • Operations on Numbers: Free
      • Operations on strings
      • Operations on Lists
      • Builtins: Some of these are a lie
    • Loops and Calls: Sequencing vs Nesting vs Composition
    • What we care about
      • Don’t care about space or number of seconds, just number of steps
      • Care about long term behavior
      • Care about worst case
      • It’s the code, not the problem, later courses you’ll look at problem bounds
      • Length of the code means nothing
    • Linear Search
    • Binary Search
    • bubbleSort
    • selectionSort
    • mergeSort
    • Need to sort? Use builtins
  • Hashtables (why sets + dictionaries are efficient) (This may move to Tuesday)
• Attendance Check: https://tinyurl.com/summer112att12