CompSciWeek4

Reading Assignment

• Algorithms, Chapter 2-3

Class 1: Formal Proofs

• Complexity Notation
• Rules - state assumptions, use logical operations on assumptions
• Modus Ponens - (a, a =>b) => b
• Modus Tollens - (a => b, ~b) => ~a
• Disjunctive Syllogism - ((a v b), ~a) => b
• Contradiction - (a, ~a) => Yikes!

  ex. from 1+1 = 1, prove that I am the Pope.
  A: The Pope and I make 2, but 1+1 = 1, so I and the Pope are
     one and the same.

• • Anything that proves a false statement is false.
  • If a then False => ~a
• Induction

Class 2: Using HPC Resources

• accessing binaries and libraries, using modules
• using scratch space
• submitting a job script
• managing queued jobs
• advanced scripting tips and tricks

Homework 3 - due Monday, Sept. 22

• Coding Problems
  • Write a code to build a graph representation of what's inside the /usr/share/X11 directory on circe. Use (os.walk and/or os.listdir, os.path.join).
    1. How many directories are there total?
    2. What is the maximum depth, counting files and dirs so the depth of a dir with no files/subdirs = 0, and with any files/subdirs = 1?
    3. How many references are there to each directory -- node in-degree? (ignore symlinks)
    4. What is the maximum number of references from a directory (i.e. maximum out-

degree)?

• Problems from Algorithms in Python:
  • 2-4
  • 2-7 (write and turn in a test code for each case mentioned)
  • 2-10
  • 2-12